如何识别语法是LL(1)、LR(0)还是SLR(1)？
如何识别语法是LL(1)、LR(0)还是SLR(1)？
有人能用这个例子或其他例子来解释它吗？
X→Yz _a Y bZ→ε Z→ε
回答 5
Stack Overflow用户
发布于 2011-12-13 22:03:50
要检查语法是否为LL(1)，一个选项是构造LL(1)解析表并检查是否存在冲突。这些冲突可能是
- 第一/第一冲突，其中必须为非终端/终端对预测两个不同的产品。
- 第一个/跟随冲突，其中两个不同的结果被预测，一个表示某些生产应该被取出来并扩展到一个非零个数的符号，另一个表示应该使用一个生产，指示一些非终端应该最终扩展到空字符串。
- 跟踪/跟踪冲突，其中两个结果指示一个非终端最终应该展开为空字符串冲突彼此。
让我们在语法上尝试这一点，为每个非终端构建第一个和后续的集合。给，我们明白了
FIRST(X) = {a, b, z}
FIRST(Y) = {b, epsilon}
FIRST(Z) = {epsilon} 我们还拥有以下集合
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)中存在移位/约简冲突。具体来说，因为我们有shift项X→→和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时才减少冲突，这与任何其他项都没有冲突。
希望这能有所帮助！
Stack Overflow用户
发布于 2013-06-11 15:01:30
如果你没有第一次/第一次冲突和第一次/跟随冲突，你的语法就是LL(1)。
第一次/第一次冲突的一个例子：
S -> Xb | Yc
X -> a
Y -> a 只看到第一个输入符号a，就无法知道是应用产品S -> Xb还是S -> Yc，因为a位于X和Y的第一个集合中。
第一次/跟随冲突的一个例子：
S -> AB
A -> fe | epsilon
B -> fg 只看到第一个输入符号f，您就无法决定是应用生产A -> fe还是A -> epsilon，因为f同时位于A的第一组和后面的A集中(A可以解析为epsilon，B可以解析为f)。
请注意，如果您没有epsilon-产品，您就不能有第一个/跟随冲突。
Stack Overflow用户
发布于 2015-08-05 11:45:02
简单的答案:语法被称为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包含两个Productions，所以对于choose.So的哪个规则不是LL(1)存在混淆。
一些简单的检查看看语法是否是LL(1)。检查1：语法不应该是递归的。示例:e-> E+T.不是LL(1)，因为它是递归的。检查2：语法应该是左因子。
当两个或多个语法规则选择共享一个公共前缀字符串时，就需要左因式分解。示例: S-->A+int|A.
检查3：语法不应模棱两可。
These are some simple checks.https://stackoverflow.com/questions/8496642
复制相似问题
腾讯云开发者
