提问人：Amol Borkar 提问时间：6/18/2023 更新时间：6/18/2023 访问量：120
如何检查语法是否为 LL（1） 且不模棱两可
How to check if a grammar is LL(1) and not ambigious
问：
这是我第一次尝试为一种新的（类似 python）语言编写语法，我试图使用递归下降解析器进行解析。我没有 EBNF、上下文无关语法和解析方面的背景，我发现很难清楚地定义我想要什么。
例如，以可能导致 .但是，如果表达式的输出被分配给标识符，该怎么办？为了适应这一点，我添加了规则，但我认为一旦我实现我的解析器，这将导致无限递归。ExpressionAssignment<Identifier> '=' Expression
我基本上是在寻找关于如何定义尽可能简洁的语法以及如何确保我的语法明确无误的指针。任何提示/资源都非常感谢。
陈述
Statement ::=
| 'if' Condition ':' Statement
| 'if' Condition ':' Statement 'else:' Statement
| Expression
| Function
表达
Expression ::= Assignment
| MathExpression
| Condition
分配
Assignment ::= <Identifier> '=' Term
| <Identifier> '=' Expression
| <Identifier> '=' Function
数学表达式
MathExpression ::= Term ( '+' | '-' ) Expression
| Term ( '*' | '/' ) Expression
| Term
条件
Condition ::= Term ( '<' | '>' | '<=' | '>=' } MathExpression
| Term ( '<' | '>' | '<=' | '>=' } Term
术语
Term ::= <Identifier>
| <Literal>
答：
0赞
Michael Dyck
6/18/2023
#1
检查语法是否为 LL（1） 的简单方法是尝试为其生成 LL（1） 解析表。如果成功，则语法为 LL（1）（因此是明确的）。
但是，您说要使用递归下降解析器，而不是 LL（1） 解析器，因此可能没有必要确保语法是 LL（1）（甚至明确）。如果你手写解析器，你基本上可以做任何你想做的事，只要它能工作。另一方面，如果你打算使用解析器生成器生成它，那么你的语法将需要符合它的约束，这可能与 LL（1） 不同。
无论如何，你的语法是模棱两可的（因此不是LL（1））。例如，这部作品具有经典的“悬而未决”的模棱两可。另一方面，推导意味着有两种推导方式和两种推导方式（例如）StatementExpression -> MathExpression -> TermAssignment<Identifier> '=' TermConditionTerm '<' Term
您可以通过消除一些生产来解决后一个问题：
Assignment ::= <Identifier> '=' TermCondition ::= Term ( '<' | '>' | '<=' | '>=' } Term你应该说服自己，这不会改变语法生成的语言。
对于悬而未决的 else 问题，这取决于。如果您手动编写递归下降解析器，那么一种可能性是在语法中将其保留为模棱两可，但在下一个符号为 时在解析器中执行特定操作。如果你使用的是解析器生成器，它的文档很有可能会告诉你是否/如何使用它来解决歧义。'else'
即使处理歧义，此语法也可能不能很好地用作 RD 分析器的基础，因为替代项不容易区分。例如，在函数的开头，如果下一个符号是 ，则可能是 或 a 或 a 的开头，那么您调用哪些函数呢？（LL（1） 解析器生成器会抱怨替代方案没有不相交的 FIRST 集。另一方面，我认为您可以通过查看 后面的符号来解决问题（即，您至少需要 2 个符号的展望）。Expression<Identifier>AssignmentMathExpressionCondition<Identifier>
你担心推导会导致无限递归：它肯定会导致递归，但不会导致无限递归。表达式解析函数的每次递归调用都会消耗 an 和 ，而程序将只有有限数量的这些函数，因此递归最终必须“触底反弹”。Expression -> Assignment -> <Identifier> '=' Expression<Identifier>'='
评论