问题标签 [ll]

我目前在空闲时间阅读《龙书》。该书指出，当且仅当对于任何产生式 A -> a|b，语法是 LL，以下两个条件适用。

1) FIRST(a) 和 FIRST(b) 是不相交的。这意味着它们不能都导出 EMPTY

2) 如果 'b' 可以导出 EMPTY，那么 'a' 不能导出任何以 FOLLOW(A) 开头的字符串

我知道 LL 解析器一般不能处理左递归，但是如果我做一个语法

S -> S(S) | 空的，

FIRST(S) = {'('} 和 FOLLOW(S) = {EOF}。这似乎与两条规则中的任何一条都不矛盾，我是否遗漏了什么？

提前谢谢你，迈克尔

我一直在 Wikipedia 中阅读这两个内容，并注意到尽管存在 LR(0) 解析器，但没有 LL(0) 解析器之类的东西。

从我读到的内容，我了解到 LL(k)/LR(k) 中的 k 表示解析器可以在当前正在处理的当前字符之外看到多少个字符。

所以我的问题是，为什么没有 LL(0) 解析器之类的东西，即使 LR(0) 存在？

这是 ll 命令的常规输出

我想问一下这个输出是不是这样的，

“c”是什么意思？

我有以下语法：

S → a S b S | b S a S | ε

由于我正在尝试为其编写一个小型编译器，因此我想将其设为 LL(1)。我看到这里似乎存在 FIRST/FOLLOW 冲突，我知道我必须使用替换来解决它，但我不完全确定如何去做。这是我提出的语法，但我不确定它是否正确：

S-> aSbT | ε

T->bFaF| ε

F-> ε

有人可以帮忙吗？

所以我有一个家庭作业，我花了 2 多个小时试图找出为什么这个语法不适用于 LL 解析器：

有人可以指出我正确的方向吗？我知道 LL 可能被绊倒的一种方式是，如果它陷入无限循环，我不相信它在这里会发生。

谢谢

我如何将 FIRST() 规则应用于生产，例如：

A -> AAb | 抗体 | s

其中 A 是非终结符，b,s 是终结符。

备选方案 1 和 2 的 FIRST(A) 将再次成为 A，但这会以 FIRST 的无限应用而告终，因为我需要一个终端来获取 FIRST 集？

龙书中，LL语法定义如下：

语法是 LL 当且仅当对于任何产生式A -> a|b，以下两个条件适用。

1. FIRST(a)并且FIRST(b)是不相交的。这意味着它们不能同时导出EMPTY

2. 如果b可以导出EMPTY，则a不能导出任何以 开头的字符串FOLLOW(A)，即FIRST(a)并且FOLLOW(A)必须是不相交的。

而且我知道LL语法不能递归，但是形式上的原因是什么？我猜左递归语法会与规则 2 相矛盾，对吧？例如，我写了以下语法：

因为FIRST(SA) = {a, empty}and FOLLOW(S) ={$, a}, then FIRST(SA)andFOLLOW(S)不是不相交的，所以这个文法不是 LL。但我不知道是左递归makeFIRST(SA)而FOLLOW(S)不是不相交，还是有其他原因？换句话说，是否每个左递归文法都会有一个违反 LL 文法条件 2 的产生式？

有人问我 LL(3) 是否是 LR(2) 的子集，反之亦然。

我成功地证明了 LL(3) 不是 LR(2) 的子集：

在 LL(3) 中，我们可以在读取开头的 3 个字符后识别规则。

在 LR(2) 中，我们可以在读取 2 个字符后识别规则。

因此，假设规则为空（upsilon），那么 LL(3) 会给我们比 LR(2) 更多的信息。因此，LL(3) 不包含在 LR(2) 中。

我如何证明另一种方式？

鉴于此语法：

S → S ₁ S ₂

S ₁ → a | ε

S ₂ → ab | ε

因此，我们有

FIRST(S ₁ ) = { a, ε }

跟随(S ₁ ) = { 一 }

这是否意味着在解析表中，我将在 S ₁的行和 1 的列中有多个定义a？

语法是这样的：

S -> e (epsilon)

S -> TS

T -> (S)

我认为它确实是 LL(1)，我的理由是，对于一个语法是 LL(1)，对于每个具有超过 1 个生产规则的非终结符，规则的指导符号集必须是不相交的，因此在这种情况下：

DS(S->e) =

首先(S->e) U 跟随(S->e) = { ) }

和，

DS(S->TS) = 第一(S->TS) = { ( }

由于{ ) }和{ ( }是不相交的，因此文法是 LL(1)。

我的理由正确吗？