注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

gmd20的个人空间

// 编程和生活

 
 
 

日志

 
 

bison文法的冲突  

2014-10-20 21:44:21|  分类: 程序设计 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
当匹配到两条都可能的完整规则时,叫做reduce/reduce冲突。
当匹配到一条完整规则,也匹配另外一条规则的一部分时,叫做 shift/reduce冲突。

reduce,是指规则的匹配完成,shift是指指针继续玩下搜寻规则的下一个匹配。

定义bison语法时,要完全解决这个规则冲突才行,就是要保证同样的内容只能确定的匹配到一种规则。

下面内容来自“flex & bison     Unix Text Processing Tools       作者John R. Levine” 一书。

bison的文档也有说。

Chapter 7 Ambiguities and Conflicts



There are two kinds of conflicts, reduce/reduce and shift/reduce. Conflicts are categorized
based upon what is happening with the other pointer when one pointer is reducing.
If the other rule is also reducing, it is a reduce/reduce conflict. The following example
has a reduce/reduce conflict in rules x and y:

start: x
| y;
x: A ↑ ;
y: A ↑ ;


If the other pointer is not reducing, then it is shifting, and the conflict is a shift/reduce
conflict. The following example has a shift/reduce conflict in rules x and y:


start: x
| y R;
x: A ↑ R;
y: A ↑ ;

After the parser reads A, rule y needs to reduce to rule start, where R can then be
accepted, while rule x can accept R immediately.


If there are more than two pointers at the time of a reduce, bison lists the conflicts. The
following example has a reduce/reduce conflict in rules x and y and another reduce/
reduce conflict in rules x and z:

start: x
| y
| z;
x: A ↑ ;
y: A ↑ ;
z: A ↑ ;

Let’s define exactly when the reduction takes place with respect to token lookahead
and pointers disappearing so we can keep our simple definition of conflicts correct.
Here is a reduce/reduce conflict:

start: x B
| y B;
x: A ↑ ;
y: A ↑ ;

But there is no conflict here:

start: x B
| y C;
x: A ↑ ;
y: A ↑ ;

The reason the second example has no conflict is that a bison parser can look ahead
one token beyond the A. If it sees a B, the pointer in rule y disappears before rule x is
reduced. Similarly, if it sees a C, the pointer in rule x disappears before rule y is reduced.
A bison parser can look ahead only one token. The following would not be a conflict
in a parser that could look ahead two tokens, but in a bison parser, it is a reduce/reduce
conflict:

start: x B C
| y B D;
x: A ↑ ;
y: A ↑ ;

A GLR parser can resolve this kind of conflict in situations where it’s impractical to
rewrite the grammar to avoid the conflict. See Chapter 9.


  评论这张
 
阅读(497)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017