如何在序列中解决移位/减少冲突模式检测？

Question

我无法消除yacc类解析器中语法中的shift/reduce冲突( C# v. 1.5.2中的GPPG)。

挑战是典型的，我们有一个以逗号分隔的元素序列: a，b，c，d，…，k。

除了"a“、"b”、"c“等个别元素外，我还想在序列中检测出单独的文字模式，例如"a，b，c”或"a，b“。语法如下：

main   : list { Console.WriteLine("Rule -> main"); }    
       ;

list       : element | list separator element
       ;

element :
        | number
        | element_multiple %prec list
        | element_single
        ;



element_single :        a       | b     | c     | d     | e     | f     | g     | h     | i     | j     | k
        ;

element_multiple : abc | ab
        ;

ab      : a separator b  { Console.WriteLine("Rule -> literal: ab"); }  
        ;
abc     : a separator b separator c { Console.WriteLine("Rule -> literal: abc"); }  
        ;

separator : SEPARATOR                   { Console.WriteLine("Rule -> separator"); } 
        ;

a       : A                             { Console.WriteLine("Rule -> literal: {0}", $1.s); }    
        ;
b       : B                             { Console.WriteLine("Rule -> literal: {0}", $1.s); }    
        ;
c       : C                             { Console.WriteLine("Rule -> literal: {0}", $1.s); }    
        ;
d       : D                             { Console.WriteLine("Rule -> literal: {0}", $1.s); }    
        ;

语法正在产生两次移位/减少冲突(无上限)：

1>移位/减少冲突，分隔符上的状态10

1>移位/减少冲突，分隔符上的状态12

但是当更多的解析器面对像"a，f“这样的序列时，就会失败。

语法错误，意外F，期望B

Answer 1

这是可以做到的，但它很丑陋。

如果您使用的是bison，那么您可以使用GLR解析器，这将允许您处理歧义。(尽管您仍然需要做一些事情来处理歧义，因为天真的语法是模糊的。)否则，您将需要跳过一些圈，以消除语法歧义。

如前所述，您的语法可以通过固定的前瞻性(4个令牌)进行解析，这意味着有一个LALR(1)语法。这种语法甚至可以机械地创建，因为我们知道所需的展望是什么，但是自动生成的语法会非常臃肿。手工操作是乏味的，但结果更容易管理(但仍然臃肿)。

查找消除算法的本质是通过k令牌延迟约简(其中k是要消除的前瞻量)。这是通过在每个非终端上保留最新的k语义值来完成的，这样延迟约简就有了产生其(延迟)语义值所需的语义值。幸运的是，如果我们能够识别出哪些产品需要额外的前瞻性，那么我们只需要对这些产品这样做。(在一般情况下，没有有效的算法，更糟糕的是，如果不知道k，但它通常或多或少是显而易见的。)

在这种情况下，我们最想避免的是，在list, a有机会与后续的, b组合之前，a会被简化为list, element，然后再转换为list。(我们还需要避免将list, a, b还原为list, element_multiple，但稍后我们将讨论这个问题。)

我们通过创建一个非终端list plus a来实现这一点，它保存了列表和a。如果这个非终端后面跟着, b，那么我们仍然需要保留这个b，这就是我们使用list plus a plus b非终端时所做的。

另一方面，如果list plus a后面跟着(比方说) , c，那么我们将不得不执行等效于追溯性地将原始list, a还原为list，然后将该list, c还原为list。

还有一种可能性，那就是list plus a后面跟着另一个a。在这种情况下，我们首先追溯地减少原始的list和a，然后创建一个新的list plus a。

下面是实现。

由于我从未使用过GPPG或C#，所以我用香草C编写了这篇文章，使用的是野牛。我希望这一切都足够基本，你可以把它翻译成你的目标语言。

首先，(简单)数据结构：

struct List {
  List*   prev;
  Element elt;
};

struct OneHold {
  List*   prev;
  char    held;
};

struct TwoHold {
  List*   prev;
  char    held1;
  char    held2;
};

}

OneHold和TwoHold用于保存语义值，直到实际需要为止。

这样，语义类型声明和语法：

%union {  
  char    token;
  OneHold one_hold;
  TwoHold two_hold;
  List*   list;
}

%token <token> 'a' 'b' 'c' 'd' 'e' 'f' 'g' 'h' ...
%%

start   : expr              { print_list($1); putchar('\n'); free_list($1); }

%type <list> expr;
expr    : list
        | lista             { $$ = push_single($1.prev, $1.held); }
        | listab            { $$ = push_seqab($1.prev, $1.held1, $1.held2); }
%type <list> list;
list    : nota              { $$ = push_single(NULL, $1); }
        | list ',' nota     { $$ = push_single($1, $3); }
        | lista ',' notab   { $$ = push_single(push_single($1.prev, $1.held), $3); }
        | listab ',' notac  { $$ = push_single(push_seqab($1.prev, $1.held1, $1.held2), 
                                               $3);
                            }
        | listab ',' 'c'    { $$ = push_seqabc($1.prev, $1.held1, $1.held2, $3); }
%type <one_hold> lista;
lista   : 'a'               { $$ = (OneHold){ .prev = NULL, .held = $1}; }
        | list ',' 'a'      { $$ = (OneHold){ .prev = $1,   .held = $3}; }
        | lista ',' 'a'     { $$ = (OneHold){ .prev = push_single($1.prev,
                                                                  $1.held),
                                              .held = $3};
                            }
        | listab ',' 'a'    { $$ = (OneHold){ .prev = push_seqab($1.prev,
                                                                 $1.held1,
                                                                 $1.held2),
                                              .held = $3};
                            }
%type <two_hold> listab;
listab  : lista ',' 'b'     { $$ = (TwoHold){ .prev = $1.prev,
                                              .held1 = $1.held,
                                              .held2 = $3};
                            }
%type <token> letter nota notab notac;
letter  : 'd' | 'e' | 'f' | 'g' | 'h' ...
nota    : 'b' | 'c' | letter
notab   : 'c' | letter
notac   : 'b' | letter