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

发布于 2024-08-21 14:57:02 字数 227 浏览 8 评论 0原文

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

a + b * c + d + e

为

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

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

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

原文

Parsing binary sums / products are easy, but I'm having troubles defining a grammar that parses

a + b * c + d + e

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

My initial (naive) attempt generated 61 shift / reduce conflicts.

I'm using java cup (but I suppose a solution for any other parser generator would be easily translated).

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

GRAY°灰色天空 2024-08-28 14:57:02

以下 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。

The following ANTLR grammar:

parse
  :  exp EOF
  ;

exp
  :  add_exp
  ;

add_exp
  :  mul_exp ('+' mul_exp)* 
  ;

mul_exp
  :  atom ('*' atom)* 
  ;

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

Number
  :  'a'..'z'
  ;

parses the input a + b * c + d + e as:

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

As you can see, the mul_exp is the furthest away in the tree and (using an appropriate "walk" through your tree) will be evaluated first.

and the input a + b * (c + d) + e is parsed as:

alt text http://img688.imageshack.us/img688/2207/89332200.png

The images were generated with ANTLRWorks.

EDIT:

A tool like ANTLRWorks makes debugging a grammar a breeze! For example, if I click on the atom rule in the grammar above, the following is automatically generated and displayed at the bottom of the screen:

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

Of course, that rule isn't complex at all, but when you do get to work with more complex rules, it's pretty darn easy to visualize them like that.

HTH.

回复收藏 0 原文

~没有更多了~