2

I have a simple grammar for JavaCUP's LR(1) parser that recognises concatenation expressions of identifiers and strings. I also want to add some empty function calls as a possible concatenation argument. However, when I try that, it leads to a shift/reduce conflict.

Grammar:

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

Input:

x + x + (x)            // match
"foo" + x              // match
(("goo") + (((y))))    // match

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

Conflict:

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

I have tried many different things like hiding identifier like IDENTIFIER second at literal and second ::= | LPAREN RPAREN; but I can't make it work.

4

2 回答 2

1

这似乎出现的上下文是这样的表达式

x + x()

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

x + [x()]

或作为

[x + x]()

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

于 2016-03-17T01:22:04.973 回答
0

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。

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

于 2016-03-20T04:10:08.820 回答