75

您如何识别语法是 LL(1)、LR(0) 还是 SLR(1)？

任何人都可以使用这个例子或任何其他例子来解释它吗？

X → Yz | 一种

Y → bZ | ε

Z → ε

4

5 回答 5

121

要检查语法是否为 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 还是减少空字符串。更一般地说，没有具有 ε-产生式的文法是 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 时归约，这不会与任何其他项冲突。

希望这可以帮助！

于 2011-12-13T22:03:50.367 回答
16

如果您没有 FIRST/FIRST 冲突，也没有 FIRST/FOLLOW 冲突，则您的语法为 LL(1)。

FIRST/FIRST 冲突的示例： 

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

通过只看到第一个输入符号 a，您无法知道是应用产生式 S -> Xb 还是 S -> Yc，因为 a 在 X 和 Y 的第一个集合中。

FIRST/FOLLOW 冲突的示例：

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

通过只查看第一个输入符号 f，您无法决定是应用产生式 A -> fe 还是 A -> epsilon，因为 f 既在 A 的 FIRST 集合中，又在 A 的 FOLLOW 集合中（A 可以解析为 epsilon和 B 为 f)。

请注意，如果您没有 epsilon-productions，则不能有 FIRST/FOLLOW 冲突。

于 2013-06-11T15:01:30.297 回答
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] 包含两个产生式，因此对于选择哪个规则存在混淆。所以它不是 LL(1)。

一些简单的检查来查看语法是否为 LL(1)。 检查 1：语法不应该是递归的。示例：E --> E+T。不是 LL(1)，因为它是左递归的。 检查 2：语法应该是左因式。

当两个或多个语法规则选择共享一个公共前缀字符串时，需要左分解。示例：S--> A +int| 一个。

检查3：语法不应该是模棱两可的。

These are some simple checks.
于 2015-08-05T11:45:02.340 回答
1

LL(1) 语法是上下文无关的明确语法，可以被 LL(1) 解析器解析。

在 LL(1)

  • 第一个 L 代表从左到右扫描输入。第二个 L 代表最左推导。1 代表在每一步使用一个输入符号。

对于检查语法是 LL(1)，您可以绘制预测解析表。如果您在表中找到任何多个条目，那么您可以说语法不是 LL(1)。

它们也是检查语法是否为 LL(1) 的捷径。 捷径技术

于 2016-05-01T12:39:18.443 回答
0

通过这两个步骤，我们可以检查它是否为 LL(1)。两个人都得满足。

1.如果我们有产生式：A->a1|a2|a3|a4|.....|an。那么，First(a(i)) 交点 First(a(j)) 一定是 phi(empty set)[a(i)-a subscript i.]

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

于 2018-06-24T05:39:51.187 回答