无法弄清楚如何解决 reduce/reduce 冲突

Question

我正在尝试从 glpk 包中为 GNU MathProg 语言创建语法 https://www3.nd.edu/~jeff/mathprog/glpk-4.47/doc/gmpl.pdf
不幸的是，到目前为止我写的语法是模棱两可的。当使用某些标识符时，我不知道如何告诉 bison 解析树的哪个分支是正确的。例如：

numericExpression : numericLiteral
              | identifier
              | numericFunctionReference
              | iteratedNumericExpression
              | conditionalNumericExpression
              | '(' numericExpression ')' %prec PARENTH
              | '-' numericExpression %prec UNARY
              | '+' numericExpression %prec UNARY
              | numericExpression binaryArithmeticOperator numericExpression
              ;

symbolicExpression : stringLiteral
               | symbolicFunctionReference
               | identifier
               | conditionalSymbolicExpression
               | '(' symbolicExpression ')'  %prec PARENTH
               | symbolicExpression '&' symbolicExpression
               ;

indexingExpression : '{' indexingEntries '}'
               | '{' indexingEntries ':' logicalExpression '}'
               ;

setExpression : literalSet
          | identifier
          | aritmeticSet
          | indexingExpression
          | iteratedSetExpression
          | conditionalSetExpression
          | '(' setExpression ')'  %prec PARENTH
          | setExpression setOperator setExpression
          ;


numericLiteral : INT
           | FLT
           ;

 linearExpression : identifier
             | iteratedLinearExpression
             | conditionalLinearExpression
             | '(' linearExpression ')'  %prec PARENTH
             | '-' linearExpression  %prec UNARY
             | '+' linearExpression  %prec UNARY
             | linearExpression '+' linearExpression
             | linearExpression '-' linearExpression
             | linearExpression '*' numericExpression
             | numericExpression '*' linearExpression
             | linearExpression '/' numericExpression
             ;

logicalExpression : numericExpression
              | relationalExpression
              | iteratedLogicalExpression
              | '(' logicalExpression ')'  %prec PARENTH
              | NOT logicalExpression %prec NEG
              | logicalExpression AND logicalExpression
              | logicalExpression OR logicalExpression
              ;

identifier : SYMBOLIC_NAME
       | SYMBOLIC_NAME '[' listOfIndices ']'
       ;

listOfIndices : SYMBOLIC_NAME
    | listOfIndices ',' SYMBOLIC_NAME
    ;

标识符只是 'variable' 的名称。变量具有特定类型（参数、集合、决策变量）并且可能被索引。在代码中，程序员必须在 eg 等语句中声明变量类型。

param p1;
param p2{1, 2} >=0;
set s1;
set s2{i in 1..5};
var v1 >=0;
var v2{S1,S2};

但是当 bison 看到标识符时不知道应该使用哪个规则，我遇到了 reduce/reduce 冲突，例如

113 numericExpression: identifier .
123 symbolicExpression: identifier .

'&'          reduce using rule 123 (symbolicExpression)
ELSE         reduce using rule 113 (numericExpression)
ELSE         [reduce using rule 123 (symbolicExpression)]
INTEGER      reduce using rule 113 (numericExpression)
INTEGER      [reduce using rule 123 (symbolicExpression)]
BINARY       reduce using rule 113 (numericExpression)
BINARY       [reduce using rule 123 (symbolicExpression)]
ASIGN        reduce using rule 113 (numericExpression)
ASIGN        [reduce using rule 123 (symbolicExpression)]
','          reduce using rule 113 (numericExpression)
','          [reduce using rule 123 (symbolicExpression)]
'>'          reduce using rule 113 (numericExpression)
'>'          [reduce using rule 123 (symbolicExpression)]
'}'          reduce using rule 113 (numericExpression)
'}'          [reduce using rule 123 (symbolicExpression)]

113 numericExpression: identifier .
123 symbolicExpression: identifier .
130 setExpression: identifier .

UNION           reduce using rule 130 (setExpression)
DIFF            reduce using rule 130 (setExpression)
SYMDIFF         reduce using rule 130 (setExpression)
ELSE            reduce using rule 113 (numericExpression)
ELSE            [reduce using rule 123 (symbolicExpression)]
ELSE            [reduce using rule 130 (setExpression)]
WITHIN          reduce using rule 130 (setExpression)
IN              reduce using rule 113 (numericExpression)
IN              [reduce using rule 123 (symbolicExpression)]

我还有其他问题，但这个对我来说是个障碍

Answer 1

基本上问题是 identifier 出现在多个规则中：

numericExpression : identifier
symbolicExpression : identifier
setExpression: identifier

这可能适用于相同的上下文。解决这个问题的一种方法是为集合名称和标量（参数和变量）名称引入不同的标记类型：

symbolicExpression : SCALAR_NAME
setExpression: SET_NAME

这将解决与集合名称的冲突。我认为你不需要这条规则

numericExpression : identifier

因为 AMPL 中有从字符串到数字的自动转换，因此 MathProg 是 AMPL 的一个子集，所以 symbolicExpression 应该允许在 numericExpression 的上下文中.

请注意，语法不是上下文无关的，因此您需要从符号 table 中提取其他信息（如上面的名称类别）来解决此类问题。

我的 flex 有点生疏，但我认为你可以在标识符规则中做类似的事情：

return is_setname(...) ? TOK_SET_NAME : TOK_SCALAR_NAME;

其中is_setname是检查当前标识符是否为集合的函数。您需要定义这样的函数并从符号 table.

中获取必要的信息

无法弄清楚如何解决 reduce/reduce 冲突

Can't figure out how to resolve reduce/reduce conflict

grammar

bison

yacc

glpk

mathprog