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

Question

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

任何人都可以使用此示例或任何其他示例来解释它吗？

X→Yz | 一个

Y→bZ | ε

Z→ε

Answer 1

要检查语法是否为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)和(6)中存在移位/减少冲突.具体来说,因为我们有减少项目Z→.和Y→.,我们无法判断是将空字符串减少到这些符号还是移动其他符号.更一般地,没有具有ε产生的语法是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时减少,这与任何其他项目都不冲突.同样,(6)中的冲突也因同样的原因而消失.

希望这可以帮助!

Answer 2

如果您没有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的第一组和A的FOLLOW集中都是(A可以解析为epsilon和B为f).

请注意,如果您没有epsilon-productions,则不能发生FIRST/FOLLOW冲突.

Answer 3

简单回答：如果关联的 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.