Shift/Reduce 冲突 Java 杯赛

Question

我收到以下错误：

Warning : *** Shift/Reduce conflict found in state #2
  between ExitLoopStatement ::= EXITLOOP (*) 
  and     VarAccess ::= (*) DOLLAR IDENTIFIER 
  under symbol DOLLAR

这是我使用的语法。目前我有赋值和中断（每个中断语句可以指定要退出的循环级别数）。

start with StatementList;

StatementList
    ::= Statement
    |
        StatementList Statement
    ;

Statement
    ::= AssignmentStatement
    |
        ExitLoopStatement
    ;

AssignmentStatement
    ::= VarAccess EQ_OP VarAccess
    ;

VarAccess
    ::= DOLLAR IDENTIFIER
    ;

ExitLoopStatement
    ::= EXITLOOP
    |
        EXITLOOP VarAccess
    ;

据我了解，问题是在我遇到 EXITLOOP 之后，下一个标记可以是赋值的开始或要退出的级别数。

有什么办法可以解决这个问题吗？

谢谢！

Answer 1

实际上，如果您的语言允许一个语句有选择地以可能开始另一个语句的内容结束，并且该语言不需要语句之间的显式标点符号，那么您将无法使用有限的先行解析器来解析它。

在这种极其简单的情况下，您可以使用 LR(3) 解析器解析您的语言，这意味着存在 LR(1) 语法（尽管它的可读性不是很好）。但是，随着您向该语言添加更多语法，您可能会发现所需的先行查找开始增加，甚至变得无限制。（例如，如果您实现数组并允许下标为任意表达式，就会发生这种情况。）

只要语言实际上没有歧义，您仍然可以使用 GLR 解析器对其进行解析。不幸的是，CUP 不提供这个选项，我不确定 bison 的 Java 框架是否允许它。

总的来说，最简单的解决方案是坚持语句 separators/terminators（如 ; in Java）或删除可选的尾随语法，这可能是与语句的开头混淆。例如，如果您将 exit $x 更改为 exit ($x) 并且不允许语句以 ( 开头，那么您将不会遇到解析冲突。

Shift/Reduce 冲突 Java 杯赛

Shift/Reduce conflict in Java Cup

java

grammar

parsing

cup