野牛减少/减少，转移/减少冲突

Question

嘿伙计们，我在处理一些野牛代码时遇到了麻烦...编译这段代码后，我得到了 58 个移位/归约和 40 个归约/归约冲突...有关如何约束它们的任何提示，或者给我指出一个好的方法指导如何做？提前致谢！！（所有以 T_ 开头的内容，例如 T_get 都是此代码上方定义的标记）

start:T_get G
  |T_head G
  |T_post G
;
G:url canon
;
url: T_http T_dslash T_host T_abs_path
;
canon:GH canon|RH canon|EH canon|MB
;
GH:T_con T_akt T_seq GH|T_date T_akt D GH|T_trans T GH| 
;
D:T_day T_slash T_month T_slash T_year T_hour T_akt T_min
;
T:T_chunked |T_gzip |T_deflate
;
RH:T_acc T_akt T_seq RH|T_ref T_akt T_seq RH|T_user T_akt T_seq RH| 
;
EH:T_content T_akt T_seq EH|T_exp T_akt T_seq EH|
;
MB:T_seq| 
;


%%
int main(){
yyparse();
}

即使您没有时间研究代码中的逻辑，我也会感谢这些冲突的一般帮助，例如它们是如何生成的等

Answer 1

使用 bison 的-v选项获取详细输出，给出生成的解析器中的所有状态和冲突。如果你这样做，你会看到类似以下的状态：

state 7

    4 G: url . canon

    T_acc      shift, and go to state 12
        :
    T_trans    shift, and go to state 19
    T_user     shift, and go to state 20

    $end       reduce using rule 13 (GH)
    $end       [reduce using rule 21 (RH)]
    $end       [reduce using rule 24 (EH)]
    $end       [reduce using rule 26 (MB)]
    T_acc      [reduce using rule 13 (GH)]
         :

这告诉您，当解析器看到 aurl并希望识别 a时canon，它无法判断要做什么 - 它应该识别空GH, RH, EH, 或MB，还是应该移动标记以识别非空其中一个？

这些冲突都来自语法中的基本歧义——您的canon规则由 0 次或多次重复GH,RH和/或组成EH，并且每个规则都由 0 次或多次重复组成。因此它无法告诉有多少空的东西插入到解析树中（因为它们不消耗输入，所以可以添加任意数量），并且它不知道是否将相似的东西分组为单个GH（或RH或EH）或分成多个不同的。

因此，要解决这个问题，您需要决定您想要什么。最有可能的是，您不关心GH//RH结构的分组EH，也不关心空的结构，因此您应该摆脱这些规则的递归：

GH:T_con T_akt T_seq|T_date T_akt D|T_trans T;
RH:T_acc T_akt T_seq|T_ref T_akt T_seq|T_user T_akt T_seq;
EH:T_content T_akt T_seq|T_exp T_akt T_seq;

现在，每个规则都将匹配一个构造，如果有多个，它们将按规则分组在一起canon。这解决了您遇到的所有冲突，但仍然留下了一个潜在的问题——您的canon规则是右递归的，因此在减少任何规则之前会将整个输入吸到堆栈中（因为对于右递归，它会减少从右到左的规则） 。您可能希望使规则成为左递归 - bison 中的一般规则是始终使用左递归而不是右递归，除非您出于某种原因需要右递归。这给你一个语法：

start : T_get G | T_head G | T_post G ;
G : url canon MB ;
url : T_http T_dslash T_host T_abs_path ;
canon : canon GH | canon RH | canon EH | ;
GH : T_con T_akt T_seq | T_date T_akt D | T_trans T ;
D : T_day T_slash T_month T_slash T_year T_hour T_akt T_min ;
T : T_chunked | T_gzip  | T_deflate ;
RH : T_acc T_akt T_seq | T_ref T_akt T_seq | T_user T_akt T_seq ;
EH : T_content T_akt T_seq | T_exp T_akt T_seq ;
MB : T_seq | ;