0

我正在使用 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.

  1. stmt ::= ID LBRACKET exp RBRACKET ASSIGN exp SEMI用于分配数组中的元素，例如arr[key] = value;
    exp :: exp LBRACKET exp RBRACKET用于从数组中获取元素的表达式，例如arr[key]

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

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

4

1 回答 1

3

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

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

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

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

exp [ exp ] = exp

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

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

于 2018-12-08T06:17:45.827 回答