是否可以为此语法编写递归下降解析器？

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

1. 该语法是否有"LL"分类(例如LL(k),LL(*))？
2. 是否可以为此语法编写递归下降解析器？怎么办？(需要回溯吗？)
3. 是否可以简化此语法以简化递归下降方法？

Answer 1

语法不是具有有限前瞻的LL,但语言是LL(1),因为LL(1)语法存在.实际上,即使不修改语法,递归下降解析器也很容易编写.

1. 该语法是否有"LL"分类(例如LL(k),LL(*))？

如果α是一个衍生expression的β term和γ factor,那么top_level可以得出这两个句子(α )+β和句子(α )*γ(但不能推导出一句(α )).但是,(α )是两者的可能推导expression和term,所以它是top_level在)遇到符号之后,无法决定使用哪种产品.由于α可以是任意长度的,不存在ķ对于其先行ķ足以区分两个制作.有些人可能称之为LL(∞),但这对我来说似乎不是一个非常有用的语法范畴.(LL(*)是afaik,由Terence Parr发明的解析策略的名称,而不是一类语法的公认名称.)我只想说语法不是任何k的 LL(k).

2. 是否可以为此语法编写递归下降解析器？怎么办？(需要回溯吗？)

当然.这甚至都不困难.

第一个符号必须是a NUMBER或a (.如果是a NUMBER,我们预测(通话)expression.如果是(,我们消耗它,调用expression,消耗以下)(或声明错误,如果下一个符号不是一个紧密的括号),然后调用expression1或term1然后expression1,取决于下一个符号是什么.再次,如果下一个符号不匹配第一组的任一expression1或者term1,我们声明了一个语法错误.请注意,上述策略根本不需要top_level*制作.

由于这显然可以在没有回溯的情况下工作,因此它可以作为如何编写LL(1)语法的基础.

3. 是否可以简化此语法以简化递归下降方法？

我不确定以下语法是否更简单,但它确实对应于上面描述的递归下降解析器.

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.但毫无疑问,你有理由.(当然,你可以很容易地通过更换禁止冗余双括号expression与top_level第二生产factor.

其次,在我看来,在第三部分中涉及LL(1)语法的箍跳是另一个理由,为什么有任何理由使用LL语法.LR(1)语法更容易阅读,它与语言的句法结构的对应关系更加清晰.生成的递归下降解析器的逻辑可能更容易理解,但对我来说似乎是次要的.