时间戳

首页 > 解决方案 > 如何简化递归下降解析器？

parsing - 如何简化递归下降解析器？

问题描述

我有以下简单的 LL(1) 语法，它描述了一种只有三个有效句子的语言""："x y"和"z x y"：

S -> A x y | ε .
A -> z | ε .

我已经构建了以下解析表，并从中构建了一个“天真的”递归下降解析器：

  | x          | y | z          | $
S | S -> A x y |   | S -> A x y | S -> ε
A | A -> ε     |   | A -> z     |

func S():
    if next() in ['x', 'z']:
        A()
        expect('x')
        expect('y')
        expect('$')
    elif next() == '$':
        pass
    else:
        error()

func A():
    if next() == 'x':
        pass
    elif next() == 'z':
        expect('z')
    else:
        error()

但是，该功能A似乎比必要的复杂。如果简化为，我的所有测试仍然通过：

func A():
    if next() == 'z':
        expect('z')

这是有效的简化A吗？如果是这样，是否有任何关于何时进行这样的简化有效的一般规则？

标签： parsingcompiler-constructioncontext-free-grammarbnfrecursive-descent

解决方案

这种简化当然是有效的（而且很常见）。

主要区别在于没有与产生式 A→ε 相关的代码。如果要实现一些语义，则需要测试条件。如果你只需要忽略可以为空的产生式，你当然可以直接返回。

合并错误和 epsilon 产生式还有另一个区别：错误（例如，在 input 中y）在A()返回后稍后检测到。有时这使得产生好的错误消息变得更加困难（有时它不会）。

推荐阅读