5

我正在尝试使用基于 PEG 的 Python 解析器生成器tatsu编写一个简单的 int 表达式解析器。这是我的代码：

import tatsu

grammar = r'''
    start = expression $ ;
    expression = add | sub | term ;
    add = expression '+' term ;
    sub = expression '-' term ;
    term = mul | div | number ;
    mul = term '*' number ;
    div = term '/' number ;
    number = [ '-' ] /\d+/ ;
'''
parser = tatsu.compile(grammar)
print(parser.parse('2-1'))

这个程序的输出['-', '1']不是预期的['2', '-', '1']。

如果我得到正确的输出：

  • 删除对一元减号的支持，即将最后一条规则更改为number = /\d+/ ;
  • 去掉term、mul和div规则，只支持加减法
  • 将第二条规则替换为expresssion = add | sub | mul | div | number ;

最后一个选项实际上可以在不遗漏任何功能的情况下工作，但我不明白它为什么会起作用。到底是怎么回事？

编辑：如果我只是翻转 add/sub/mul/div 规则以摆脱左递归，它也可以工作。但是随后评估表达式成为一个问题，因为解析树被翻转了。（3-2-1变成3-(2-1)）

4

1 回答 1

1

存在 TatSu 无法处理的左递归情况，并且正在修复当前处于搁置状态的问题。

您可以使用左/右连接/聚集运算符来控制非左递归语法中已解析表达式的关联性。

于 2018-11-17T08:16:39.967 回答