parsing - 移位/减少具有 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为：

替代文字 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上面语法中的规则，会自动生成以下内容并显示在屏幕底部：

替代文字 http://img340.imageshack.us/img340/6793/53395907.png

当然，这条规则一点也不复杂，但是当你开始使用更复杂的规则时，很容易像这样可视化它们。

HTH。