Shift 减少 Bison 语法中的冲突

Question

我刚开始使用 Bison，我遇到了一些问题。我的语法的目标是识别一种 "command pipeline" 语言，其中一个命令的输出可以通过管道传输为另一个命令的输入。每个命令还可以有一个带有可选值的参数列表。这是一个例子：

command1 --param1 test --param2 test2 | command2 | command3 --param3

在前面的示例中，command1 有两个参数，param1 的值为 test 和 param2 的值为 test2。 command1 的输出是 "piped" 到 command2，它不带参数。最后 command2 的结果通过管道传递给 command3，它接受一个参数（没有值的参数被认为是一个开关）。

对应的bison语法如下：

%{

#include <string>
#include <iostream>
#include "AST.h"
#include "Evaluator.h"

void yyerror (const char *error);
int  yylex();

%}

%code{
    Evaluator eval;
}

%union {
  char* s;
  double d;
  AbstractNode* abstractnode;
  CmdletCall* cmdletdef;
  ParameterDef* parameterdef;
  ParameterListDef* paramlistdef;
}

/* declare tokens */

%token EOL
%token<s> PARAMETERNAME
%token<s> BUILTIN
%token<s> IDENTIFIER


%type <parameterdef> parameterDef
%type <cmdletdef> cmdletCall
%type <abstractnode> pipeLineDef    
%type <paramlistdef> paramList
%%

input: /* nothing */
    | input pipeLineDef EOL {
                                ->accept(eval);
                                delete ;
                                std::cout << eval.result() << std::endl;
                            }                        
    | input EOL             {}
    ;



pipeLineDef: cmdletCall                  {$$ = ;}      
    | pipeLineDef '|' cmdletCall         {$$ = new PipeLineDef(, );}   
    ;


cmdletCall: IDENTIFIER                   {$$ = new CmdletCall();}                 
          | cmdletCall paramList         {->setParameterList();}   
          ;

paramList: parameterDef                 {  
                                            $$ = new ParameterListDef;
                                            $$->addChildNode();
                                        }  
         | paramList parameterDef       {
                                            ->addChildNode();
                                            $$ = ;
                                        }
         ;

parameterDef: PARAMETERNAME             {$$ = new ParameterDef();}
            | parameterDef IDENTIFIER   {
                                            ->setValue();
                                        }         

            ;




%%


void yyerror (const char *error)
{
  std::cout << error << std::endl;
}

之前的文法有一处shift-reduce冲突，转载如下：

Terminals unused in grammar

BUILTIN

State 10 conflicts: 1 shift/reduce
State 10

7 cmdletCall: cmdletCall paramList .
9 paramList: paramList . parameterDef

PARAMETERNAME  shift, and go to state 9

PARAMETERNAME  [reduce using rule 7 (cmdletCall)]
$default       reduce using rule 7 (cmdletCall)

parameterDef  go to state 13

我想消除冲突，但我不确定应该如何进行（我的理解是 shift/reduce 冲突表示语法不明确）。然而，从我最初的测试来看，一切似乎都按预期工作。令我困惑的另一点是 Bison 评估终端的方式。例如，如果我按如下方式重写 cmdletCall 和 paramList 规则，语法就会中断：

cmdletCall: IDENTIFIER paramList         {$$ = new CmdletCall();    $$->setParameterList();}   
          ;

paramList: /*nothing*/ 
                                        {  
                                            $$ = new ParameterListDef;

                                        }  
         | paramList parameterDef       {
                                            ->addChildNode();
                                            $$ = ;
                                        }
         ;

如果我重写如上所示的语法，那么对于这样的输入：

command1 --param1

在cmdletCall规则中，对应IDENTIFIER标记的</code>的值将是<code>command1 --param1，而不仅仅是command1 .

Answer 1

您对 cmdletCall 的定义实际上是 IDENTIFIER paramList*（使用标准 regular-language Kleene 星号运算符）。但是 paramList 是 paramDef+。所以这显然是模棱两可的；无法判断 IDENTIFIER 之后有多少 paramList，因为没有指示一个结束和下一个开始的位置。

事实上，您只想（或最多）一个 paramList。有多种选择，但最简单的是：

cmdletCall: IDENTIFIER paramList
paramList : /* empty */
          | paramList parameterDef

另一种选择是保留 paramList non-nullable，并添加仅包含 IDENTIFIER 的 cmdletCall 选项。确实，这仅在您需要为语义规则区分大小写时才有用，但肯定是可能的。

或者对于更简单的语法，只需去掉 paramList:

cmdletCall: IDENTIFIER
          | cmdletCall parameterDef

由于 bison-generated 解析器更喜欢 shift 而不是 reduce，因此从您的歧义语法生成的解析器将按照您的预期进行：只为每个命令生成零个或一个 paramList。但无论如何，你最好还是消除歧义。

您在相关语义值方面遇到的问题是由于未从您的扫描仪复制 yytext 的内容造成的； yytext 是 flex-built 扫描器中的一个内部数据结构，它的内容不属于您，因为扫描器可以并且会根据需要修改它们。

Shift 减少 Bison 语法中的冲突

Shift Reduce Conflict in Bison Grammar

parsing

bison