Java杯：Shift/Reduce冲突

Question

我正在尝试使用 JFlex 和 Cup 编写解析器，但我在处理递归指向符号时遇到一些问题，例如具有递归属性访问的函数调用，例如：

var x = obj.property1.functionCall(p1, p2).property2;

这里是相关的解析器定义：

unary_exp ::= postfix_exp
              | ADD2 unary_exp
              | SUB2 unary_exp
              | unary_operator unary_exp;

unary_operator ::=  ADD
                    | SUB
                    | BIT_NOT
                    | NOT;

postfix_exp ::= primary_exp
                | postfix_exp LPAR_SQ right_value_exp RPAR_SQ
                | postfix_exp LPAR optional_postfix_exp_list RPAR
                | postfix_exp DOT postfix_exp
                | postfix_exp SUB2
                | postfix_exp ADD2;

primary_exp ::= BOOL
                | STRING
                | INTEGER
                | NUMBER
                | NULL;

我遇到了以下 shift/reduce 冲突：

Warning : *** Shift/Reduce conflict found in state #190
  between postfix_exp ::= postfix_exp DOT postfix_exp (*) 
  and     postfix_exp ::= postfix_exp (*) LPAR optional_postfix_exp_list RPAR 
  under symbol LPAR
  Resolved in favor of shifting.

Warning : *** Shift/Reduce conflict found in state #190
  between postfix_exp ::= postfix_exp DOT postfix_exp (*) 
  and     postfix_exp ::= postfix_exp (*) LPAR_SQ right_value_exp RPAR_SQ 
  under symbol LPAR_SQ
  Resolved in favor of shifting.

Warning : *** Shift/Reduce conflict found in state #190
  between postfix_exp ::= postfix_exp DOT postfix_exp (*) 
  and     postfix_exp ::= postfix_exp (*) DOT postfix_exp 
  under symbol DOT
  Resolved in favor of shifting.

Warning : *** Shift/Reduce conflict found in state #190
  between postfix_exp ::= postfix_exp DOT postfix_exp (*) 
  and     postfix_exp ::= postfix_exp (*) ADD2 
  under symbol ADD2
  Resolved in favor of shifting.

Warning : *** Shift/Reduce conflict found in state #190
  between postfix_exp ::= postfix_exp DOT postfix_exp (*) 
  and     postfix_exp ::= postfix_exp (*) SUB2 
  under symbol SUB2
  Resolved in favor of shifting.

Error : *** More conflicts encountered than expected -- parser generation aborted

有人可以向我解释如何处理这些冲突或在哪里可以找到使用 java cup、yacc 或 bison 的工作示例吗？

Answer 1

你的语法包括这个产生式：

postfix_exp ::= postfix_exp DOT postfix_exp

你觉得这样准确吗？ . 的右操作数可以是任意的 postfix_exp 吗？如果是这样，a.3 是什么意思？ x.false怎么样？（primary_exp 是 postfix_exp，对吧？语法就是这么说的。）

言归正传，a.b++是什么意思？ b++ 是 . 的操作数有什么意义吗？ b肯定是a成员的名字，不是自变量。

语法 传达意义，即使它们不实现语义。它们指定表达式的不同部分相互关联的方式。（“Parse”和“parts”听起来很相似，因为动词“parse”来自名词“part”，如“to split into parts”。）所以你应该努力使你的语法符合语言的结构。

现在，任何时候你看到这样的作品：

foo ::= foo OPERATOR foo;

你知道语法有歧义。它是不明确的，因为它为 OPERATOR 生成左解析和 right-associative 解析。例如，如果 OPERATOR 是 -，它将把 (1 - 1) - 1（假设 foo 可以产生 1）与 1 - (1 - 1) 混为一谈。语法歧义总是表现为解析table冲突。

解决歧义很重要，因为这两个表达式具有不同的值。这就是为什么我们要么必须使用表达式类型的层次结构，要么必须使用运算符优先级声明。（所以我们知道如何解决结合性问题。）

但是在 . 运算符的情况下，我们确实没有未指定结合性的二元运算符。我们实际上根本没有二元运算符，这就是为什么这里的产生式称为 postfix_exp。该运算符是一个字段选择器，我们可以将其视为不同后缀运算符的集合，一个对应于适当复合类型的每个成员名称。

这就是简单的答案。一旦我们说字段选择器具有 DOT IDENTIFIER 形式，歧义就消失了。

Java杯：Shift/Reduce冲突

Java cup: Shift/Reduce conflict

yacc

bison

shift-reduce-conflict

cup