来自 this question ,一种涉及二元运算符 (+ - */) 的表达式的语法,它不允许外括号:
top_level : expression PLUS term
| expression MINUS term
| term TIMES factor
| term DIVIDE factor
| NUMBER
expression : expression PLUS term
| expression MINUS term
| term
term : term TIMES factor
| term DIVIDE factor
| factor
factor : NUMBER
| LPAREN expression RPAREN
这个语法是 LALR(1)。因此,我能够使用 PLY (yacc 的 Python 实现)为语法创建自下而上的解析器。
为了进行比较,我现在想尝试为同一语言构建一个自上而下的递归下降解析器。我已经转换了语法,删除了左递归并应用了左因式分解:
top_level : expression top_level1
| term top_level2
| NUMBER
top_level1 : PLUS term
| MINUS term
top_level2 : TIMES factor
| DIVIDE factor
expression : term expression1
expression1 : PLUS term expression1
| MINUS term expression1
| empty
term : factor term1
term1 : TIMES factor term1
| DIVIDE factor term1
| empty
factor : NUMBER
| LPAREN expression RPAREN
如果没有 top_level
规则,这个文法就是 LL(1),所以写一个递归下降解析器会相当简单。不幸的是,包括 top_level
,语法不是 LL(1)。
- 此语法是否有“LL”分类(例如 LL(k)、LL(*))?
- 是否可以为该文法编写一个递归下降解析器?那将如何完成? (是否需要回溯?)
- 是否可以简化此语法以简化递归下降方法?
最佳答案
文法不是有限前瞻的 LL,但语言是 LL(1),因为存在 LL(1) 文法。从实用的角度来说,即使不修改语法,递归下降解析器也很容易编写。
- Is there an "LL" classification for this grammar (e.g. LL(k), LL(*))?
如果 α 是 expression
的导数,term
的 β 和 factor
的 γ,则 top_level
可以导出句子 (α)+β 和句子 (α) *γ(但它无法导出句子(α)。)但是,(α) 是 expression
和 term
的可能推导,因此在符号出现之前无法决定使用 top_level
的哪个产生式遇到 ) 之后。由于 α 可以是任意长度,因此没有 k 的前瞻性 k 足以区分这两个产生式。有些人可能会称其为 LL(∞),但对我来说这似乎不是一个非常有用的语法类别。 (据我所知,LL(*) 是 Terence Parr 发明的解析策略的名称,而不是一类语法的公认名称。)我只想说语法不是 LL(k) 对于任何 k。
- Is it possible to write a recursive-descent parser for this grammar? How would that be done? (Is backtracking required?)
当然。甚至没有那么难。
第一个符号必须是 NUMBER
或 (。如果它是 NUMBER
,我们预测(调用) expression
。如果是(,我们消费它,调用expression
,消费后面的)(或者声明错误,如果下一个符号不是右括号),然后调用 expression1
或 term1
,然后调用 expression1
,具体取决于下一个符号是什么。同样,如果下一个符号与 expression1
或 term1
的第一组不匹配,我们将声明语法错误。请注意,上述策略不需要 top_level*
作品。
由于这显然不需要回溯就可以工作,因此它可以作为编写 LL(1) 语法的基础。
- Is it possible to simplify this grammar to ease the recursive-descent approach?
我不确定下面的语法是否更简单,但它确实对应于上面描述的递归下降解析器。
top_level : NUMBER optional_expression_or_term_1
| LPAREN expression RPAREN expression_or_term_1
optional_expression_or_term_1: empty
| expression_or_term_1
expression_or_term_1
: PLUS term expression1
| MINUS term expression1
| TIMES factor term1 expression1
| DIVIDE factor term1 expression1
expression : term expression1
expression1 : PLUS term expression1
| MINUS term expression1
| empty
term : factor term1
term1 : TIMES factor term1
| DIVIDE factor term1
| empty
factor : NUMBER
| LPAREN expression RPAREN
我留下了两个观察结果,您可以完全忽略这两个观察结果(特别是第二个是 100% 的意见)。
首先,我觉得禁止 (1+2)
但允许 (((1)))+2
或 ( (1+2))+3
。但毫无疑问,你有你的理由。 (当然,在 factor
的第二个产生式中,您可以通过将 expression
替换为 top_level
来轻松禁止多余的双括号。
其次,在我看来,第三部分中 LL(1) 文法中涉及的跳圈只是询问为什么有任何理由使用 LL 文法的又一个原因。 LR(1)文法更易读,与语言句法结构的对应更清晰。生成的递归下降解析器的逻辑可能更容易理解,但对我来说这似乎是次要的。
关于parsing - 是否可以为此语法编写递归下降解析器?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36099930/