reduce/reduce 银联冲突

Question

我正在使用 Java CUP 为 Java 的一个子集实现解析器。

语法好像

vardecl ::= type ID
type    ::= ID | INT | FLOAT | ...
exp     ::= ID | exp LBRACKET exp RBRACKET | ...
stmt    ::= ID ASSIGN exp SEMI

这很好用，但是当我添加

stmt ::= ID ASSIGN exp SEMI
        |ID LBRACKET exp RBRACKET ASSIGN exp SEMI

CUP 不工作，警告是：

Warning : *** Shift/Reduce conflict found in state #122
  between exp ::= identifier (*) 
  and     statement ::= identifier (*) LBRACKET exp RBRACKET ASSIGN exp SEMI 
  under symbol LBRACKET
  Resolved in favor of shifting.

Warning : *** Reduce/Reduce conflict found in state #42
  between type ::= identifier (*) 
  and     exp ::= identifier (*) 
  under symbols: {}
  Resolved in favor of the first production.

Warning : *** Shift/Reduce conflict found in state #42
  between type ::= identifier (*) 
  and     statement ::= identifier (*) LBRACKET exp RBRACKET ASSIGN exp SEMI 
  under symbol LBRACKET
  Resolved in favor of shifting.

Warning : *** Shift/Reduce conflict found in state #42
  between exp ::= identifier (*) 
  and     statement ::= identifier (*) LBRACKET exp RBRACKET ASSIGN exp SEMI 
  under symbol LBRACKET
  Resolved in favor of shifting.

我觉得有两个问题：
1、type ::= ID和exp ::= ID，解析器看到一个ID，想减去，不知道减哪个，type还是exp.

stmt ::= ID LBRACKET exp RBRACKET ASSIGN exp SEMI用于对数组中的元素进行赋值，如arr[key] = value;
exp :: exp LBRACKET exp RBRACKET 表示从数组中取一个元素，如arr[key]

所以在arr[key]的情况下，当解析器看到arr时，它知道它是一个ID，但不知道它是否应该移位或减少到exp.

但是，我不知道如何解决这个问题，如果有请给我一些建议，非常感谢。

Answer 1

您的分析是正确的。语法是 LR(2)，因为在看到 ] 标记之前无法识别声明，这将是 ID 中的第二个下一个标记，它可能是一种类型。

一个简单的解决方案是当括号显示为连续标记时，将词法分析器破解为 return [] 作为单个标记。（词法分析器可能也应该允许括号之间有空格，所以它不是很简单但也不复杂。）如果 [ 后面没有紧跟 ]，词法分析器将 return 它作为一个普通的 [。这使得解析器很容易区分对数组的赋值（将具有 [ 标记）和数组声明（将具有 [] 标记）。

也可以重写语法，但那真的很麻烦。

第二个问题——数组索引赋值与数组索引表达式。通常编程语言允许赋值形式：

exp [ exp ] = exp

而且不仅仅是 ID [ exp ]。进行此更改将延迟减少的需要，直到解析器识别正确减少的时间足够晚。根据语言的不同，此语法可能在语义上没有意义，但检查属于类型检查（语义）而非语法领域。但是，如果该形式的某些语法有意义，则没有明显的理由禁止它。

一些解析器生成器实现了 GLR 解析器。 GLR 解析器不会对这个语法有任何问题，因为它没有歧义。但 CUP 不是这样的生成器。

reduce/reduce 银联冲突

reduce/reduce conflict in CUP

parsing

compiler-construction

grammar

shift-reduce-conflict

cup