野牛移位用平衡括号语法减少冲突

Question

我在做一个平衡括号的语法练习。

S -> (S)

S-> SS

S-> ()

编译器返回一个shiftreduce冲突。这是我的bison语法。

%%
prog:
  srule
;

srule 
    : ( srule )
    | srule srule 
    | ( )
;
%%

有谁能给我解释一下原因吗？ 我怎样才能在不改变语法的情况下解决这个问题？

Answer 1

你的语法是模棱两可的，而模棱两可的语法是 始终 产生冲突。这是因为歧义意味着会有一个点，在这个点上会有两种不同的解析，也就是说会有两种不同的解析操作。这就是解析冲突的定义。

歧义是非常明显的。S: S S 说，将两个 S 是一个有效的 S. 但是... () 和 ()() 均为有效 S. 所以你可以做一个新的 S 连缀 () 与 ()()，或者你可以做一个新的 S 连缀 ()() 与 (). 不幸的是，这些都将是 一样 新的 S而语法中并没有指定使用哪种分解方式。

修复语法是一种方法，修复的方法很简单。我们只需要规定，当连接两个平衡句时，第一个句子本身不能是连接句。这意味着 ()•()() 是一个有效的组成，但 ()()•() 不是。

正如您在评论中所指出的，修改有此要求的语法很简单，只要将连词规则替换为 S: ( S ) S. 该规则中的两个括号是匹配的，这意味着该规则中第一个 S 不能是一个连词。

但是我们可以使用正常的yaccbison机制来代替处理模棱两可的语法。我们所需要做的就是要求解析器总是解决冲突，以支持还原操作。(这不是一个通用的解决方案，但它在这里是可行的。)

为了使yaccbison优先规则生效，可能被缩减的右边必须比可能被移位的lookahead字符有更高的优先性。右手边的优先级被指定为右手边第一个标记的优先级，但不幸的是，我们感兴趣的右手边--连接规则--根本没有任何标记。所以我们需要用 %prec 标记。因为我们知道，看前符号将永远是一个 ( 毫不含糊 )，因为解析器必须减少直到把 ) 可以移动），我们可以直接将生产标记为具有优先于 ( 进而宣布 ( 是右联，也就是说，减法优于移法。

%right '('
%%
%%
srule: '(' srule ')'
     | '(' ')'
     | srule srule %prec '('

事实上，使用 %right 以上完全是武断的。如果我们从毫不含糊的语法开始的话 S → S ( S ) | ε 而不是 S → ( S ) S | ε我们将创建一个左联构图，其中包括 ()()() 必须分解为 ()()•() 而非 ()•()(). 这将通过改变 %right 在上述拜辛的片段中，以 %left，这将导致在生成的解析器中更有效地使用解析器栈。