Bison语法中的移位减少冲突

Question

我刚开始和Bison合作，我面临着几个问题。我语法的目标是识别一种“命令管道”语言，其中一个命令的输出可以管道化为另一个命令的输入。每个命令还可以有一个具有可选值的参数列表。下面是一个示例：

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

在前面的示例中，command1接受两个参数，一个是值test的param1参数，一个是值test2的param2参数。然后，command1的输出被“管道化”到不接受参数的command2。最后，将command2的结果传递到command3，该参数只接受一个参数(没有值的参数被视为开关)。

相应的野牛语法如下：

%{

#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 {
                                $2->accept(eval);
                                delete $2;
                                std::cout << eval.result() << std::endl;
                            }                        
    | input EOL             {}
    ;



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


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

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

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

            ;




%%


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

以前的语法有一个转变--减少冲突，现将其转载如下：

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

我想消除冲突，但我不知道该如何进行(我的理解是，移位/减少冲突表示一个模糊的语法)。然而，从我最初的测试来看，一切似乎都如期而至。另一点令我困惑的是Bison评估终端的方式。例如，如果我按如下方式重写cmdletCall和paramList规则，语法就会中断：

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

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

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

如果如上面所示重写语法，那么输入如下：

command1 --param1

在cmdletCall规则中，$1的值(对应于IDENTIFIER令牌)将是command1 --param1，而不是command1。

Answer 1

您对cmdletCall的定义实际上是IDENTIFIER paramList* (使用标准的正则语言Kleene运算符)。但paramList是paramDef+。因此，这显然是模棱两可的；没有办法知道有多少paramList遵循IDENTIFIER，因为没有指示出结束的位置和下一个开始的位置。

实际上，您希望只拥有(或最多)一个paramList。有几种选择，但最简单的是：

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

另一个选项是保持paramList非空，并添加一个cmdletCall选项，该选项仅由一个IDENTIFIER组成。实际上，只有当您需要为语义规则分离用例时，这才是有用的，但这当然是可能的。

或者为了更简单的语法，只需去掉paramList

cmdletCall: IDENTIFIER
          | cmdletCall parameterDef

由于bison生成的解析器更喜欢shift而不是reduce，因此从模糊语法生成的解析器将按照您的预期执行:每个命令只生成零或一个paramList。但你最好还是消除模棱两可。

相关语义值的问题在于没有从扫描仪复制yytext的内容；yytext是flex构建的扫描器中的内部数据结构，它的内容不属于您，因为扫描仪可以并将根据自己的意愿修改它们。