Bison 解析器无法识别替代语法

Question

我正在尝试编写一个识别特定语法的解析器。我很远，大部分东西都能用。我在尝试使 Bison 解析器能够识别两个相似但不同的结构时遇到了一个问题。这是我希望它识别的两个结构：

type_1 IS ENUMERATION OF 
BEGIN
    element_1,
    element_2 := 4
END type_1;

type_2 IS ENUMERATION SIZE 8 OF 
BEGIN
    element_1,
    element_2 := 4
END type_2;

基本上这是针对类似枚举的声明，可以为元素提供或不提供位大小参数。

我写的 Bison 文件包含两个版本的两个备选方案。他们每个人分开，无论是独自一人，还是在另一个人之前，效果都很好。但是，当我将两个描述都放入 Y 文件时，它只能识别我的声明之一或另一个。

以下是 Bison 代码行：

    enum_type : sized_enum_type                 { $$=; P3; }
          | nonsized_enum_type              { $$=; P3; }
          ;

sized_enum_type : identifier[L]             {P1(37,$L->Get_Line(),$L->Get_Column());} 
                IS[I]                       {P2(38,$I.ln,$I.clmn);} 
                ENUMERATION[N]              {P2(43,$N.ln,$N.clmn);} 
                SIZE[Z]                     {P2(42,$Z.ln,$Z.clmn);} 
                INTEGER_VALUE[V]            {P2(39,$V.ln,$V.clmn);} 
                OF[O]                       {P2(40,$O.ln,$O.clmn);} 
                TBEGIN[B]                   {P2(16,$B.ln,$B.clmn);} 
                enum_element_list[S]        {P2(41,$S->Get_Line(),$S->Get_Column());} 
                TEND[E]                     {P2(16,$E.ln,$E.clmn);} 
                identifier[R]               {P2(15,$R->Get_Line(),$R->Get_Column());}
                SEMICOLON                   {$$= new AST::AST_Type_Enum( (AST::AST_Code_Identifier *) $L, $V.value ); $$->_Set_Line_And_Column(  $I.ln, $I.clmn); P3;}
                ;

nonsized_enum_type : identifier[L]              {P1(37,$L->Get_Line(),$L->Get_Column());} 
                     IS[I]                       {P2(38,$I.ln,$I.clmn);} 
                     ENUMERATION[N]              {P2(39,$N.ln,$N.clmn);} 
                     OF[O]                       {P2(40,$O.ln,$O.clmn);} 
                     TBEGIN[B]                   {P2(16,$B.ln,$B.clmn);} 
                     enum_element_list[S]        {P2(41,$S->Get_Line(),$S->Get_Column());} 
                     TEND[E]                        {P2(16,$E.ln,$E.clmn);} 
                     identifier[R]              {P2(15,$R->Get_Line(),$R->Get_Column());}

                     SEMICOLON                  {$$= new AST::AST_Type_Enum( (AST::AST_Code_Identifier *) $L, -1 ); $$->_Set_Line_And_Column(  $I.ln, $I.clmn); P3;}
                     ;
enum_element_list   : one_enum                                                          { $$=; }
                   | one_enum COMMA enum_element_list                                   { ((AST::AST_Enum_Value *))->Append( (AST::AST_Enum_Value *) ); $$=; }
                   ;

one_enum    : identifier[L]                 {$$= new AST::AST_Enum_Value( (AST::AST_Code_Identifier *) $L, -1 ); $$->_Set_Line_And_Column( $L->Get_Line(),$L->Get_Column()); P3;}
           | identifier[L]                  {P1(17,$L->Get_Line(),$L->Get_Column());} 
             ASSIGNMENT_SHALLOW_COPY[A]    {P2(42,$A.ln, $A.clmn);} 
             INTEGER_VALUE[I]               {$$= new AST::AST_Enum_Value( (AST::AST_Code_Identifier *) $L, $I.value ); $$->_Set_Line_And_Column( $L->Get_Line(),$L->Get_Column()); P3;}
             ;

我认为每个规则部分右侧的 C 语句不是必需的，但我还是将它们包含在这里。

当我运行在我的源代码上编译解析器时，它抱怨它需要令牌 SIZE。当我交换 nonsized_enum_type 和 sized_enum_type 的规则时（不是 enum_type 规则的右侧，规则的完整源代码顺序，将一个规则移到另一个规则下方）然后它识别没有大小的其他形式。当我在我的代码中包含 SIZE 8 部分时，它会抱怨它期待其他形式（OF expected）。

所以我的问题是：如何编写一个能够识别这两个部分的解析器规则？

生成的代码难道不应该识别出一条规则行不通然后再尝试另一条吗？看来第二条规则从未尝试过。

谢谢大家

Answer 1

将所有这些中间规则操作 (MRA) 插入到您的语法中会削弱解析器。由于您不包含 P1 和 P2 的定义，因此很难知道为什么需要 MRA，但实际上似乎不太可能需要执行特定的减少操作在标记 IS 和 ENUMERATION 之间，而不是稍后执行缩减操作。

具体来说，问题可以归结为以下几点。考虑这两个作品（只到他们的第一个 MRA）：

sized_enum_type : identifier[L]     {P1(37,$L->Get_Line(),$L->Get_Column());} 
nonsized_enum_type : identifier[L]  {P1(37,$L->Get_Line(),$L->Get_Column());}

这些 MRA 中的每一个都是通过标签生产实施的。从左到右解析的逻辑是所有归约必须在之前移动下一个标记之前执行。在上述两种情况下，下一个标记是 IS，但是看到 IS 并没有说明 应该执行哪个 缩减。结果bison会报reduce/reduce冲突，然后选择定义文件中先出现的产生式。另一个减少将被有效地消除，这使得它的其余生产无法达到。

这两个归约动作碰巧是相同的，但是野牛不知道。从野牛的角度来看，所有 MRA 都是独一无二的。实际上，使用 MRA 需要语法——至少在那个特定点——是 LL(1)，从而消除了 LR(1) 解析算法的所有优势。

你可以通过左因式分解来避免这个问题，但我强烈建议你尽量减少对 MRA 的依赖。对于构建 AST，MRA 实际上从来都不是必需的，它们具有不小的成本，并且会降低解析器处理非 LL(1) 语法的能力。

Bison 解析器无法识别替代语法

Bison parser does not recognize alternative syntax

grammar

bison

yacc