消除可选else块上的移位/减少冲突 [英] Removing shift/reduce conflict on optional else block

问题描述

我正在与Bison定义语法，我偶然发现了我想消除的转移/减少冲突.冲突是由旨在匹配if/else语句的规则引起的:

I'm in the process of defining a grammar with Bison and I stumbled upon a shift/reduce conflict I'd like to eliminate. The conflict is caused by a rule that aims to match if/else statements:

state 17

   13 Stmt: IfBlock . OptionalElseBlock

    ELSE  shift, and go to state 42

    ELSE      [reduce using rule 16 (OptionalElseBlock)]
    $default  reduce using rule 16 (OptionalElseBlock)

    OptionalElseBlock  go to state 43

OptionalElseBlock的定义如下:

   16 OptionalElseBlock: /* empty */
   17                  | ELSE Stmt

状态42和43看起来像这样，但省略了移位并减少了信息:

States 42 and 43 look like this with the shift and reduce info omitted:

state 42
   17 OptionalElseBlock: ELSE . Stmt

state 43
   13 Stmt: IfBlock OptionalElseBlock .

我以前使用过可选标记，但是我猜测由于解析器的超前缓冲区仅包含1个终端OptionalElseBlock会导致冲突.有解决此冲突的简便方法吗?

I've used optional tokens before, but I'm guessing that since the parser's lookahead buffer only contains 1 terminal OptionalElseBlock causes a conflict. Is there an easy way to resolve this conflict?

推荐答案

这是经典的移位/减少冲突.问题如下:

This is the classic shift/reduce conflict. The problem is the following:

if (c1) if (c2) stmt1; else stmt2;

问题是else属于哪个if.如果它不是可选的，则不会有问题，或者必须终止if语句(例如，使用fi或end选择两个流行的替代方法)，但是C语法似乎具有赢了，因此我们有转移/减少冲突.

The question is which if the else belongs to. If it were not optional, there would be no problem, or if the if statement had to be terminated (say with fi or end, to choose two popular alternatives), but the C syntax seems to have won, and hence we have shift/reduce conflicts.

写一个语法不出现此问题的语法是可能的，但并非易事.您可以隐藏冲突，方法是使用具有优先级规则的游戏或仅预期"移位/减少冲突. (我更喜欢后者，但是有很多人会说优先破解比较好，尽管这与恕我直言是一样的.)

It is possible but non-trivial to write a grammar which does not exhibit this problem. You can hide the conflict, either by playing games with precedence rules or by simply "expecting" the shift/reduce conflict. (I prefer the latter but there are many who would say that the precedence hack is better, although it amounts to the same thing imho.)

重写的语法是龙书中的一种练习，可能还包含其他解析文本，因此出于学习目的可能值得这样做，但这在语法维护方面确实是一个痛苦，并且使语法难以阅读，如果这完全是个问题.

The rewritten grammar is an exercise in the dragon book, and probably other parsing texts, so it might be worth doing for learning purposes, but it's a real pain in terms of grammar maintenance and it makes the grammar much harder to read, if that's at all a concern.

有关如何使用优先级和移位首选项简化解析的经典论文是Aho，Johnson和Ullman于1975年左右出版的模棱两可的语法的确定性解析".如果您没有好的图书馆的访问权限，Google可能会找到您可以在线阅读的副本.

The classic paper on how to use precedence and shift-preference to simplify parsing is "Deterministic parsing of ambiguous grammars" by Aho, Johnson and Ullman, published in 1975 or so. Google will probably find you a copy you can read online if you don't have access to a good library.

这篇关于消除可选else块上的移位/减少冲突的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！