串联移位-减少冲突

Question

我有一个简单的语法来识别标识符和字符串的 LR（1） 解析器。我还想添加一些空函数调用作为可能的串联参数。但是，当我尝试这样做时，它会导致转移/减少冲突。

语法：

precedence left PLUS;
e ::= e exp
      | exp;
exp ::= concat
      | literal;
concatenation ::= exp PLUS exp
                | LPAREN exp RPAREN;

literal ::= IDENTIFIER
          | STRING
          | IDENTIFIER LPAREN RPAREN; // THIS PRODUCES THE ERROR

输入：

x + x + (x)            // match
"foo" + x              // match
(("goo") + (((y))))    // match
function_name() + x + "foo" + (other_func())    // what I also want

冲突：

Warning : *** Shift/Reduce conflict found in state #12
between literal ::= IDENTIFIER (*) 
and     literal ::= IDENTIFIER (*) LPAREN RPAREN  
under symbol LPAREN

我已经尝试了很多不同的事情，例如在文字和second ::= | LPAREN RPAREN;中隐藏标识符，例如IDENTIFIER second，但我无法使其工作。

Answer 1

这似乎出现在这样的表达中

x + x()

解析器在看到x + x后无法判断它是否应该将x + x减少回exp或移动(。换句话说，它无法判断是否将表达式解释为

x + [x()]

或作为

[x + x]()

我认为您可以通过添加优先规则来解决这个问题，该规则使此特定上下文中的左括号比加法具有更高的优先级。这样，当解析器看到这种状态下的移位和减少操作时，它知道在左括号上移位而不是减少。

Answer 2

Bison处理以下语法，没有移位/减少冲突：

%token IDENTIFIER STRING
%left IDENTIFIER
%left '('
%left '+'
%%
e      : e exp
       | exp
exp    : concat
       | literal
concat : exp '+' exp
       | '(' exp ')'
literal: IDENTIFIER
       | IDENTIFIER '(' ')'
       | STRING

有必要为IDENTIFIER提供优先声明，以便为literal: IDENTIFIER生产提供优先权。

我发现语法有点奇怪，因为它似乎不允许将连接放在括号中。但我相信这是有原因的。

只要函数调用没有参数，上述方法就可以正常工作，但它不允许使用参数调用函数，因为那样会模棱两可。（这可能被认为是不允许不可见串联运算符的一个很好的理由。值得一提的是，awk ，它既有函数又有连接，没有运算符，在词法上解决了这种歧义：一个标识符紧跟着 （，不干预空格，被标记为FUNC_NAME，而标识符后跟空格或 （ 以外的任何符号被标记为 NAME .

另一种可能的解决方案是要求在使用前声明函数，然后使用符号表和词法反馈（即将信息从解析器传递回词法分析器;在这种情况下，给定标识符是一个函数的事实）。