移位/减少 n 元和/积算术表达式语法中的冲突

Question

解析二进制和/乘积很容易，但我在定义解析

a + b * c + d + e

为

sum(a, prod(b, c), d, e)

我最初（天真的）尝试生成 61 移位/减少冲突的语法时遇到了麻烦。

我正在使用 java cup（但我想任何其他解析器生成器的解决方案都可以很容易地翻译）。

Answer 1

以下 ANTLR 语法：

parse
  :  exp EOF
  ;

exp
  :  add_exp
  ;

add_exp
  :  mul_exp ('+' mul_exp)* 
  ;

mul_exp
  :  atom ('*' atom)* 
  ;

atom
  :  Number
  |  '(' exp ')'
  ;

Number
  :  'a'..'z'
  ;

将输入 a + b * c + d + e 解析为：

alt text http://img266.imageshack.us/img266/7099/17212574.png

如您所见，mul_exp 是树中距离最远的并且（使用适当的“步行”穿过你的树）将首先被评估。

输入 a + b * (c + d) + e 被解析为：

替代文本 http://img688.imageshack.us/img688/2207/89332200.png

图像是使用 ANTLRWorks。

编辑：

像 ANTLRWorks 这样的工具使调试语法变得简单微风！例如，如果我点击上面语法中的 atom 规则，则会自动生成以下内容并显示在屏幕底部：

alt text http://img340.imageshack.us/img340/6793/53395907.png

当然，这个规则一点也不复杂，但是当您开始处理更复杂的规则时，将它们可视化是非常容易的。

HTH。