是否有一种简单的方法可以在不进行复杂分析的情况下确定语法是LL(1), LR(0), SLR(1)呢？
例如：要确定BNF语法是否为LL(1)，您需要计算First和Follow集，这在某些情况下可能很耗时。
有人有什么快速的方法吗？ 任何帮助都将不胜感激！
7个回答
34
首先，稍微有些学究气的一点是，你无法通过检查语法来确定一个语言是否是LL(1)，你只能对语法本身作出陈述。完全有可能为某种存在LL(1)语法的语言编写非LL(1)语法。
既然解释清楚了这个问题：
既然解释清楚了这个问题：
您可以编写一个解析器用于语法分析，并让程序为您计算first和follow集等其他属性。毕竟，这是BNF语法的最大优势，它们是机器可理解的。
检查语法并查找各种语法类型约束条件的违规。例如：LL(1)允许右递归但不允许左递归，因此，包含左递归的语法不是LL(1)。(对于其他语法属性，您需要花费一些时间阅读定义，因为我现在就想不起来其他的了 :).
- zacherates
3
5关于语言和文法的区别，你提出了一个很好的观点。如果一个文法不是LL(1)，仍然有可能为该语言构造一个LL(1)文法。 - Bruce Alderman
11+1 知识上的严谨是非常关键的区别，而通常忽略这一点是理解的障碍。 - Jason Orendorff
@JasonOrendorff：同意。 - alecov
15
回答您的主要问题：对于非常简单的语法，可能可以在不构造FIRST和FOLLOW集的情况下确定它是否是LL（1），例如：
但当你变得更加复杂时，你需要做一些分析。
算术规则的语法规则很快变得非常复杂：
话虽如此，有一些明显的迹象表明该语法不是LL（1）——就像上面的A → A + A一样——如果您在语法中找到任何这些迹象，您将知道如果您正在编写递归下降解析器，则需要重写该语法。但是，没有捷径可以验证语法是否LL（1）。
是LL（1）。A → A + A | a
不是LL（1），而
A → a | b
但当你变得更加复杂时，你需要做一些分析。
这不是LL（1），但可能不是显而易见的。A → B | a
B → A + A
算术规则的语法规则很快变得非常复杂：
这个语法仅处理乘法和加法，已经不清楚这个语法是否是LL（1）。仍然可以通过查看语法来评估它，但随着语法的增长，这变得不太可行。如果我们为整个编程语言定义一个语法，几乎肯定需要进行一些复杂的分析。expr → term { '+' term }
term → factor { '*' factor }
factor → number | '(' expr ')'
话虽如此，有一些明显的迹象表明该语法不是LL（1）——就像上面的A → A + A一样——如果您在语法中找到任何这些迹象，您将知道如果您正在编写递归下降解析器，则需要重写该语法。但是，没有捷径可以验证语法是否LL（1）。
- aardvark
2
顺便提一下，对于LL（1）语法分析器，您不需要计算FOLLOW集，因为它仅基于FIRST集进行定义。 - jpalecek
4如果非终结符可为空，则LL(1)确实需要FOLLOW集合。这样，您可以“跳过”非终结符并查看要使用哪个产生式。 - templatetypedef
9
直接引用自Aho等人所著的《编译器：原理、技术与工具》一书。
第223页：
如果文法G满足以下条件，则G是LL（1）文法：
1.对于任何终结符“a”，既不能由alpha推导出以“a”开头的字符串，也不能由beta推导出以“a”开头的字符串。 2.alpha和beta中最多只有一个可以推导出空串。 3.如果beta可以通过零个或多个转换到达空转换，则alpha不会推导出以FOLLOW（A）中的任何终结符开头的字符串。同样，如果alpha可以通过零个或多个转换到达空转换，则beta不会推导出以FOLLOW（A）中的任何终结符开头的字符串。
本质上，这是验证文法是否通过了成对不相交性测试并且不涉及左递归的问题。更简洁地说，左递归或模棱两可的文法G不能是LL（1）文法。
第223页：
如果文法G满足以下条件，则G是LL（1）文法：
1.对于任何终结符“a”，既不能由alpha推导出以“a”开头的字符串，也不能由beta推导出以“a”开头的字符串。 2.alpha和beta中最多只有一个可以推导出空串。 3.如果beta可以通过零个或多个转换到达空转换，则alpha不会推导出以FOLLOW（A）中的任何终结符开头的字符串。同样，如果alpha可以通过零个或多个转换到达空转换，则beta不会推导出以FOLLOW（A）中的任何终结符开头的字符串。
本质上，这是验证文法是否通过了成对不相交性测试并且不涉及左递归的问题。更简洁地说，左递归或模棱两可的文法G不能是LL（1）文法。
- Matthew Erwin
2
检查语法是否存在歧义。如果有歧义，则该语法不是LL（1），因为没有歧义的语法是LL（1）。
- Ananya Sahu
0
嗨，这里有LL(1)语法的快捷方式：
1）如果A -> B1 | B2 | ....... | Bn，则first(B1)交集first(B2)交集......交集first(Bn)=空集，则它是LL(1)语法。
2）如果A -> B1 | epsilon，则B1交集follow(A)为空集。
3）如果G是任何文法，每个非终端符号只派生一个产生式，则该文法是LL(1)。
- srinath
-2
p0 S' → E
p1 E → id
p2 E → id ( E )
p3 E → E + id
- 构建LR（0）DFA，E的FOLLOW集和SLR动作/转移表。
- 这是一个LR（0）语法吗？请证明你的答案。
- 使用SLR表，展示LR解析器分析
id ( id + id )的步骤（移进、规约、接受）。
- dida
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接