如何识别语法是LL(1)，LR(0)还是SLR(1)? [英] How to identify whether a grammar is LL(1), LR(0) or SLR(1)?

问题描述

如何识别语法是LL(1)，LR(0)还是SLR(1)?

How do you identify whether a grammar is LL(1), LR(0), or SLR(1)?

任何人都可以使用此示例或任何其他示例进行解释吗?

Can anyone please explain it using this example, or any other example?

X→ Yz |一个

X → Yz | a

Y→ bZ | ε

Y → bZ | ε

Z→ ε

Z → ε

推荐答案

要检查语法是否为LL(1)，一种选择是构造LL(1)解析表并检查是否存在任何冲突.这些冲突可能是

To check if a grammar is LL(1), one option is to construct the LL(1) parsing table and check for any conflicts. These conflicts can be

• FIRST/FIRST冲突，对于非末端/末端对，必须预测两种不同的产生.
• FIRST/FOLLOW冲突，其中预测了两种不同的乘积，一种表示应该采用某种乘积，并扩展为非零符号数，一种表示应该使用一种乘积来指示最终应扩展一些非终端的符号移至空字符串.
• FOLLOW/FOLLOW冲突，其中两个表示非终结符最终应扩展为空字符串的结果彼此冲突.

让我们通过为每个非终结点构建FIRST和FOLLOW集来对语法进行尝试.在这里，我们得到了

Let's try this on your grammar by building the FIRST and FOLLOW sets for each of the nonterminals. Here, we get that

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

我们也有以下Follow集

We also have that the FOLLOW sets are

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

由此，我们可以构建以下LL(1)解析表:

From this, we can build the following LL(1) parsing table:

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

由于我们可以无冲突地构建此分析表，因此语法为LL(1).

Since we can build this parsing table with no conflicts, the grammar is LL(1).

要检查语法是LR(0)还是SLR(1)，我们首先为语法建立所有LR(0)配置集.在这种情况下，假设X是您的开始符号，我们得到以下信息:

To check if a grammar is LR(0) or SLR(1), we begin by building up all of the LR(0) configurating sets for the grammar. In this case, assuming that X is your start symbol, we get the following:

(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).

From this, we can see that the grammar is not LR(0) because there are shift/reduce conflicts in states (1) and (6). Specifically, because we have the reduce items Z → . and Y → ., we can't tell whether to reduce the empty string to these symbols or to shift some other symbol. More generally, no grammar with ε-productions is LR(0).

但是，此语法可能是SLR(1).为了看到这一点，我们使用针对特定非终结点的超前集来增加每个减少量.这将返回这组SLR(1)配置集:

However, this grammar might be SLR(1). To see this, we augment each reduction with the lookahead set for the particular nonterminals. This gives back this set of SLR(1) configurating sets:

(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时才减少，而z与其他任何项均不冲突.同样，由于相同的原因，(6)中的冲突也消失了.

Now, we don't have any more shift-reduce conflicts. The conflict in state (1) has been eliminated because we only reduce when the lookahead is z, which doesn't conflict with any of the other items. Similarly, the conflict in (6) is gone for the same reason.

希望这会有所帮助！

这篇关于如何识别语法是LL(1)，LR(0)还是SLR(1)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！