时间戳

首页 > 解决方案 > 递归下降解析语法

parsing - 递归下降解析语法

问题描述

有没有一种简单的方法来判断一个简单的语法是否适合递归下降？消除左递归和左分解语法是否足以实现这一目标？

标签： parsinggrammarcontext-free-grammar

解决方案

不必要。

要构建递归下降解析器（没有回溯），您需要消除或解决所有预测冲突。因此，一项确定性测试是查看语法是否为 LL(1)；根据定义，LL(1) 语法没有预测冲突。左分解和左递归消除对于此任务是必要的，但它们可能还不够，因为预测冲突可能隐藏在两个相互竞争的非终结符后面：

 list  ::= item list'
 list' ::= ε 
         | ';' item list'
 item  ::= expr1
         | expr2
 expr1 ::= ID '+' ID
 expr2 ::= ID '(' list ')

上述问题（或至少一个问题）是，当解析器期望 anitem并看到 anID时，它不知道要尝试哪个expr1and 。expr2（这是一个预测冲突：两个非终结符都可以预测。）在这种特殊情况下，很容易看出如何消除这种冲突，但它并不是真正的左分解，因为它从组合两个非终结符开始。（在完整的语法中，这可能是摘录自，组合两个非终结符可能要困难得多。）

在一般情况下，没有一种算法可以将任意文法转换为 LL(1) 文法，甚至无法判断该文法识别的语言是否也具有 LL(1) 文法。（但是，很容易判断语法本身是否为 LL(1)。）因此总会涉及到一些艺术和/或实验。

我认为值得补充的是，您实际上并不需要在实际递归下降解析器中消除左递归，因为您通常可以将其转换为 while 循环而不是递归。例如，撇开上述两种expr类型的问题不谈，带有重复运算符的扩展 BNF 中的原始语法可能类似于

list ::= item (';' item)*

这转化为类似的东西：

def parse_list():
    parse_item()
    while peek(';'):
        match(';')
        parse_item()

（省略了错误检查和 AST 构建。）

推荐阅读