如何确定一个语法是LL(1)，LR(0)还是SLR(1)？

Question

如何确定一个语法是LL(1)，LR(0)还是SLR(1)？

parsinggrammarlr-grammarll-grammar

80

如何确定语法是LL(1)、LR(0)还是SLR(1)？

有谁能够使用这个示例或其他示例来解释一下吗？

X → Yz | a

Y → bZ | ε

Z → ε

- Prashant Bhardwaj

5个回答

18

如果你的语法没有FIRST/FIRST冲突和FIRST/FOLLOW冲突，那么它就是LL(1)文法。

一个FIRST/FIRST冲突的例子：

S -> Xb | Yc
X -> a 
Y -> a

仅凭第一个输入符号“a”，您无法确定是应用产生式S -> Xb还是S -> Yc，因为“a”都在X和Y的FIRST集中。

FIRST/FOLLOW冲突的一个例子：

S -> AB 
A -> fe | ε 
B -> fg

仅凭第一个输入符号“ f”，您无法确定是应用产生式A -> fe还是A -> ε ，因为“ f”既在A的FIRST集合中又在A的FOLLOW集合中（A可以被解析为空，B为f）。

请注意，如果没有ε-产生式，则不可能存在FIRST/FOLLOW冲突。

- Kent Munthe Caspersen

你所说的"f"（或"a"）是指句子开头还是句子中的任何位置？ - Mehdi Charife

如果你的语法中存在任何FIRST/FIRST或FIRST/FOLLOW冲突，那么它就不是LL(1)。在冲突变得相关之前，你能够在给定字符串中进展多远并不重要。如果你的语法中有任何规则，在这些规则中，使用的产生式不能立即通过1个向前看符号确定，那么你的语法就不是LL(1)。@MehdiCharife - Kent Munthe Caspersen

我们能否说，仅凭看到符号“f”，我们无法知道自己是否处于A的开头或结尾？ - Mehdi Charife

6

简单回答：如果关联的LL(1)分析表中每个表项最多只有一个产生式，则语法被称为LL(1)。

Take the simple grammar A -->Aa|b.[A is non-terminal & a,b are terminals]
   then find the First and follow sets A.
    First{A}={b}.
    Follow{A}={$,a}.

    Parsing table for Our grammar.Terminals as columns and Nonterminal S as a row element.

        a            b                   $
    --------------------------------------------
 S  |               A-->a                      |
    |               A-->Aa.                    |
    --------------------------------------------

由于[S，b]包含两个Production，因此存在哪个规则应选择的混淆。因此，它不是LL（1）。

一些简单的检查方法可用于检查语法是否为LL（1）。检查1：语法不应为左递归。示例：E --> E + T.不是LL（1），因为它是左递归的。检查2：文法应为左公因式。左公因式在两个或多个文法规则选择共享相同的前缀字符串时是必需的。例如：S --> A + int | A。检查3：语法不应具有歧义。

These are some simple checks.

- Anil Kumar

1

你的回答可以通过包含一个应用此规则的示例和可能支持你的说法的来源来改进。 - ankh-morpork

2

感谢您的评论。我已经添加了一个示例和一些其他有用的信息。 - Anil Kumar

2

LL(1)文法是一种上下文无关且无歧义的语法，可以由LL(1)解析器进行解析。

在LL(1)中：

第一个L表示从左到右扫描输入。第二个L表示最左派生。1表示每次使用一个输入符号。

要检查文法是否为LL(1)，您可以绘制预测分析表。如果在表中找到多个条目，则可以说该文法不是LL(1)。

还有一种简便方法来检查文法是否为LL(1)。快捷技巧

- Badal

1

用这两个步骤，我们可以检查它是否为LL(1)。两者都必须满足。

1. 如果我们有产生式：A->a1|a2|a3|a4| ..... |an。那么，First(a(i))交 First(a(j)) 必须是空集 [a(i)-a下标i]。

2. 对于每个非终结符'A'，如果First(A)包含epsilon，则First(A)交 Follow(A)必须是空集。

- bit_radiation_96

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

检查语法是否为LL(1)的一个方法是构建LL(1)分析表并检查任何冲突。这些冲突可能会有：

FIRST/FIRST冲突，其中针对非终端/终端对需要预测两个不同的产生式。
FIRST/FOLLOW冲突，其中预测了两个不同的产生式，一个表示应该采取某些产生式并展开为非零数量的符号，而另一个表示应该使用某个产生式，指示某些非终端符最终会展开为空字符串。
FOLLOW/FOLLOW冲突，其中两个产生式指示某个非终端符最终展开为空字符串与彼此冲突。

我们可以通过为每个非终端构建FIRST和FOLLOW集合来尝试对您的语法进行操作。在这里，我们得到：

FIRST(X) = {a, b, z}
FIRST(Y) = {b, epsilon}
FIRST(Z) = {epsilon}

我们还有FOLLOW集合：

FOLLOW(X) = {$}
FOLLOW(Y) = {z}
FOLLOW(Z) = {z}

基于此，我们可以构建以下 LL(1) 分析表：

    a    b    z   $
X   a    Yz   Yz  
Y        bZ   eps
Z             eps

由于我们可以构建不带冲突的解析表，所以这个文法是LL(1)。

要检查一个文法是否是LR(0)或SLR(1)，我们首先需要为该文法构建所有LR(0)配置集。在此情况下，假设X是您的起始符号，我们得到以下结果：

(1)
X' -> .X
X -> .Yz
X -> .a
Y -> .
Y -> .bZ

(2)
X' -> X.

(3)
X -> Y.z

(4)
X -> Yz.

(5)
X -> a.

(6)
Y -> b.Z
Z -> .

(7)
Y -> bZ.

从这里我们可以看出，语法不是LR(0)，因为状态(1)存在移进/归约冲突。具体来说，由于我们有移进项目X → .a和Y → .，我们无法确定是将a移进还是规约为空字符串。更普遍地说，具有ε-productions的文法都不是LR(0)。

但是，这个文法可能是SLR(1)。为了看清楚这一点，我们用特定非终结符的展望集合扩充每个规约。这给出了SLR(1)配置集的集合：

(1)
X' -> .X
X -> .Yz [$]
X -> .a  [$]
Y -> .   [z]
Y -> .bZ [z]

(2)
X' -> X.

(3)
X -> Y.z [$]

(4)
X -> Yz. [$]

(5)
X -> a.  [$]

(6)
Y -> b.Z [z]
Z -> .   [z]

(7)
Y -> bZ. [z]

在状态(1)中的移位/规约冲突已被消除，因为我们仅在向前看符号为z时才进行规约，这不会与任何其他项发生冲突。