Java 当用户定义变量或函数的类型时，CUP（解析器）产生 shift/reduce 冲突
Java CUP (Parser) produces shift/reduce conflict when Type of variable or function is user defined
我的语法需要有用户定义的类型 ID 组合。以下代码的问题在于它生成以下内容：
[java] Warning : *** Shift/Reduce conflict found in state #67
[java] between VariableDecls ::= (*)
[java] and Type ::= (*) ID
[java] under symbol ID
[java] Resolved in favor of shifting.
[java] Warning : *** Shift/Reduce conflict found in state #65
[java] between VariableDecls ::= (*)
[java] and Type ::= (*) ID
[java] under symbol ID
[java] Resolved in favor of shifting.
[java] Error : *** More conflicts encountered than expected -- parser generation aborted
[java] ------- CUP v0.11b 20160615 (GIT 4ac7450) Parser Generation Summary -------
[java] 1 error and 4 warnings
[java] 51 terminals, 34 non-terminals, and 93 productions declared,
[java] producing 190 unique parse states.
[java] 2 terminals declared but not used.
[java] 0 non-terminals declared but not used.
[java] 0 productions never reduced.
[java] 2 conflicts detected (0 expected).
[java] No code produced.
我曾尝试在 VariableDecls 和 Stmts 作品中摆脱语法中的 E 作品，但没有成功。我也试过用type生产ID，然后生产e生产。
包裹 cup.example；
import java_cup.runtime.*;
import java.io.IOException;
import java.io.File;
import java.io.FileInputStream;
parser code {:
TScanner scanner;
Parser(TScanner scanner) { this.scanner = scanner; }
public void syntax_error(Symbol cur_token) {
System.out.println("WE ARE HERE");
done_parsing();
}
public void unrecovered_syntax_error(Symbol cur_token) {
System.out.println(cur_token.sym);
System.out.println("[reject]");
}
:}
scan with {: return scanner.next_token(); :};
/* Terminals (tokens returned by the scanner). */
terminal BOOLN, DBL, _INT, STRING, NUL;
terminal _IF, ELS, FR, WHLE;
terminal INTCONST, DBLCONST, STRINGCONST, BOOLCONST;
terminal ADDOP, SUBOP, MULOP, DIV, MOD;
terminal LFTPRN, RTPRN, LFTBRACKET, RTBRC, LFTBRACE, RTBRACE;
terminal LESS, LESSEQ, GRT, GRTEQ, EQL, NEQ;
terminal AND, OR, NOT;
terminal ASSIGN, SEMICOL, COMMA, DOT;
terminal BRK, CLS, EXTNDS, IMPL, INTRFC, NEWAR;
terminal PRNTLN, READLN, RTRN, _VOID, NW;
terminal ID;
/* Non terminals */
non terminal Program, Decls, Decl;
non terminal VariableDecl, FunctionDecl, ClassDecl, InterfaceDecl;
non terminal Variable, Type, Formals, Variables, Extends, Implements, Implement;
non terminal Field, Fields, Prototype, StmtBlock, VariableDecls, Stmts, Stmt;
non terminal OptionExpr, WhileStmt, ForStmt, BreakStmt;
non terminal ReturnStmt, PrintStmt, Expr, Exprs, Lvalue, Call, Actuals, Constant;
non terminal IfStmt;
/* Precedences */
precedence right ASSIGN;
precedence left OR;
precedence left AND;
precedence left EQL, NEQ;
precedence left LESS, LESSEQ, GRT, GRTEQ;
precedence left ADDOP, SUBOP;
precedence left MULOP, DIV, MOD;
precedence left NOT;
precedence left LFTBRACKET, DOT;
precedence left ELS;
/* Toy grammar */
start with Program;
Program ::=
Decls
{: System.out.print("[reduce 1]"); System.out.print("[accept]"); done_parsing(); :};
Decls ::=
Decl
{: System.out.print("[reduce 2]"); :}
| Decl Decls
{: System.out.print("[reduce 3]"); :} ;
Decl ::=
VariableDecl
{: System.out.print("[reduce 4]"); :}
| FunctionDecl
{: System.out.print("[reduce 5]"); :}
| ClassDecl
{: System.out.print("[reduce 6]"); :}
| InterfaceDecl
{: System.out.print("[reduce 7]"); :} ;
VariableDecl ::=
Variable SEMICOL
{: System.out.print("[reduce 8]"); :} ;
Variable ::=
Type ID
{: System.out.print("[reduce 9]"); :} ;
Type ::=
_INT
{: System.out.print("[reduce 10]"); :}
| DBL
{: System.out.print("[reduce 11]"); :}
| BOOLN
{: System.out.print("[reduce 12]"); :}
| STRING
{: System.out.print("[reduce 13]"); :}
| Type LFTBRACKET RTBRC
{: System.out.print("[reduce 14]"); :}
| ID {: System.out.print("[reduce 15]"); :};
FunctionDecl ::=
Type ID LFTPRN Formals RTPRN StmtBlock
{: System.out.print("[reduce 16]"); :}
| _VOID ID LFTPRN Formals RTPRN StmtBlock
{: System.out.print("[reduce 17]"); :} ;
Formals ::=
// EMPTY
{: System.out.print("[reduce 18]"); :}
| Variables
{: System.out.print("[reduce 19]"); :} ;
Variables ::=
Variable
{: System.out.print("[reduce 20]"); :}
| Variable COMMA Variables
{: System.out.print("[reduce 21]"); :} ;
ClassDecl ::=
CLS ID Extends Implements LFTBRACE Fields RTBRACE
{: System.out.print("[reduce 22]"); :} ;
Extends ::=
// EMPTY
{: System.out.print("[reduce 23]"); :}
| EXTNDS ID
{: System.out.print("[reduce 24]"); :};
Implements ::=
// EMPTY
{: System.out.print("[reduce 25]"); :}
| Implement
{: System.out.print("[reduce 26]"); :};
Implement ::=
IMPL ID
{: System.out.print("[reduce 27]"); :}
| IMPL ID COMMA Implement
{: System.out.print("[reduce 28]"); :};
Fields ::=
// EMPTY
{: System.out.print("[reduce 29]"); :}
| Field Fields
{: System.out.print("[reduce 30]"); :};
Field ::=
VariableDecl
{: System.out.print("[reduce 31]"); :}
| FunctionDecl
{: System.out.print("[reduce 32]"); :};
InterfaceDecl ::=
INTRFC ID LFTBRACE Prototype RTBRACE
{: System.out.print("[reduce 33]"); :};
Prototype ::=
// EMPTY
{: System.out.print("[reduce 34]"); :}
| Type ID LFTPRN Formals RTPRN SEMICOL Prototype
{: System.out.print("[reduce 35]"); :}
| _VOID ID LFTPRN Formals RTPRN SEMICOL Prototype
{: System.out.print("[reduce 36]"); :};
StmtBlock ::=
LFTBRACE VariableDecls Stmts RTBRACE
{: System.out.print("[reduce 37]"); :};
VariableDecls ::=
//EMPTY
{:System.out.print("[reduce 38]"); :}
|
VariableDecl VariableDecls
{: System.out.print("[reduce 39]"); :};
Stmts ::=
// EMPTY
{: System.out.print("[reduce 40]"); :}
| Stmt Stmts
{: System.out.print("[reduce 41]"); :};
Stmt ::=
OptionExpr SEMICOL
{: System.out.print("[reduce 42]"); :}
| IfStmt
{: System.out.print("[reduce 43]"); :}
| WhileStmt
{: System.out.print("[reduce 44]"); :}
| ForStmt
{: System.out.print("[reduce 45]"); :}
| BreakStmt
{: System.out.print("[reduce 46]"); :}
| ReturnStmt
{: System.out.print("[reduce 47]"); :}
| PrintStmt
{: System.out.print("[reduce 48]"); :}
| StmtBlock
{: System.out.print("[reduce 49]"); :};
IfStmt ::=
_IF LFTPRN Expr RTPRN Stmt
{: System.out.print("[reduce 50]"); :}
| _IF LFTPRN Expr RTPRN Stmt ELS Stmt
{: System.out.print("[reduce 51]"); :};
WhileStmt ::=
WHLE LFTPRN Expr RTPRN Stmt
{: System.out.print("[reduce 52]"); :};
ForStmt ::=
FR LFTPRN OptionExpr SEMICOL Expr SEMICOL OptionExpr RTPRN Stmt
{: System.out.print("[reduce 53]"); :};
BreakStmt ::=
BRK SEMICOL
{: System.out.print("[reduce 54]"); :};
ReturnStmt ::=
RTRN OptionExpr SEMICOL
{: System.out.print("[reduce 55]"); :};
PrintStmt ::=
PRNTLN LFTPRN Exprs RTPRN SEMICOL
{: System.out.print("[reduce 56]"); :};
Expr ::=
Lvalue ASSIGN Expr
{: System.out.print("[reduce 57]"); :}
| Constant
{: System.out.print("[reduce 58]"); :}
| Lvalue
{: System.out.print("[reduce 59]"); :}
| Call
{: System.out.print("[reduce 60]"); :}
| LFTPRN Expr RTPRN
{: System.out.print("[reduce 61]"); :}
| Expr ADDOP Expr
{: System.out.print("[reduce 62]"); :}
| Expr SUBOP Expr
{: System.out.print("[reduce 63]"); :}
| Expr MULOP Expr
{: System.out.print("[reduce 64]"); :}
| Expr DIV Expr
{: System.out.print("[reduce 65]"); :}
| Expr MOD Expr
{: System.out.print("[reduce 66]"); :}
| Expr LESS Expr
{: System.out.print("[reduce 68]"); :}
| Expr LESSEQ Expr
{: System.out.print("[reduce 69]"); :}
| Expr GRT Expr
{: System.out.print("[reduce 70]"); :}
| Expr GRTEQ Expr
{: System.out.print("[reduce 71]"); :}
| Expr EQL Expr
{: System.out.print("[reduce 72]"); :}
| Expr NEQ Expr
{: System.out.print("[reduce 73]"); :}
| Expr AND Expr
{: System.out.print("[reduce 74]"); :}
| Expr OR Expr
{: System.out.print("[reduce 75]"); :}
| NOT Expr
{: System.out.print("[reduce 76]"); :}
| READLN LFTPRN RTPRN
{: System.out.print("[reduce 77]"); :}
| NEWAR LFTPRN INTCONST COMMA Type RTPRN
{: System.out.print("[reduce 78]"); :};
Lvalue ::=
ID
{: System.out.print("[reduce 79]"); :}
| Lvalue LFTBRACKET Expr RTBRC
{: System.out.print("[reduce 80]"); :}
| Lvalue DOT ID
{: System.out.print("[reduce 81]"); :};
Call ::=
ID LFTPRN Actuals RTPRN
{: System.out.print("[reduce 82]"); :}
| ID DOT ID LFTPRN Actuals RTPRN
{: System.out.print("[reduce 83]"); :};
Actuals ::=
// EMPTY
{: System.out.print("[reduce 84]"); :}
| Exprs
{: System.out.print("[reduce 85]"); :};
Exprs ::=
Expr
{: System.out.print("[reduce 86]"); :}
| Expr COMMA Exprs
{: System.out.print("[reduce 87]"); :};
Constant ::=
INTCONST
{: System.out.print("[reduce 88]"); :}
| DBLCONST
{: System.out.print("[reduce 89]"); :}
| STRINGCONST
{: System.out.print("[reduce 90]"); :}
| BOOLCONST
{: System.out.print("[reduce 91]"); :};
OptionExpr ::=
//EMPTY
{: System.out.print("[reduce 92]"); :}
| Expr
{: System.out.print("[reduce 93]"); :};
我认为这是流行的 "Decaf" 语言的一些变体，经常用于 CS 入门课程。
我不太清楚为什么 CUP 只报告两个冲突，因为 afaics 在你的语法中有四个冲突。也许您粘贴的版本不是生成您在问题中包含的错误消息的版本。
错误消息中报告的冲突是您对变量声明列表和构成语句块的语句列表使用右递归的结果。
常识会告诉您应尽可能避免右递归，因为它使用无限量的解析器堆栈。相比之下，左递归使用恒定数量的解析器堆栈。这是一个很好的经验法则，但大多数情况下，左递归和右递归之间的选择将由语法决定。因此，例如，如果您在不使用优先级声明的情况下为算术表达式编写语法，您将对左结合运算符（几乎所有运算符）使用左递归，对右递归运算符（例如赋值运算符）使用右递归在 C、C++ 和 Java).
项目列表通常可以用任何一种方式编写，因为它们通常会折叠成一个向量而不是保留为二叉树，所以正常情况下将保留递归：
x_list ::= x_list x_element |
// EMPTY
;
您还会看到上述模式的许多变体。例如，如果项目列表不能为空，则第一个产品将是 x_list: x_element。如果元素后跟或由标记分隔，您还必须进行修改，因此您经常会看到类似这样的内容：
// In the language this comes from, statements are *always* followed by
// a semicolon. Most languages don't work that way, though.
statement_list ::= statement_list statement T_SEMICOLON |
// EMPTY
;
// Parameter lists (and argument lists) are either empty or have the items
// *separated* by commas. Because the comma is only present if there are at
// least two items, we need to special-case the empty list:
parameter_list ::= T_OPAREN T_CPAREN |
T_OPAREN parameters T_CPAREN
;
parameters ::= parameter |
parameters T_COMMA parameter
;
虽然我把这些都写成左递归，但在这些特殊情况下我也可以使用右递归。但是左递归解析和右递归解析之间有一个细微的区别，这也会影响解析器动作的执行顺序。考虑两者之间的区别：
id_list ::= id_list ID | id_list ::= ID id_list |
// EMPTY // EMPTY
; ;
他们都接受a b c，但是他们接受的方式不同：
ε•
•3 •3
/ \ / \
•2 c a •2
/ \ / \
•1 b b •1
/ \ / \
ε a c ε
因为在这两种情况下解析器都是自下而上的，所以解析器操作总是从底部开始执行。这将导致第一个（左递归）解析器按输入顺序执行操作，而第二个解析器将从右到左执行操作。
不管怎样，回到问题上来。实际上，您有以下语法，它将派生一个可能为空的声明序列，然后是一个可能为空的语句序列：
StatementBody ::= OBRACE VariableDeclarations Statements CBRACE
VariableDeclarations ::= VariableDeclaration VariableDelarations | // EMPTY
Statements ::= Statement Statements | // EMPTY
考虑到上面导出的解析树，Statements 和 Declarations 都需要有效地以空产生式结束。换句话说，在解析器可以移动 Statements 中的第一个标记之前，它需要减少一个空的 VariableDeclarations 非终结符。这意味着它需要确切地知道哪个标记将是 Statements.
中的第一个标记
不幸的是，这是不可能的，因为 Statement 和 VariableDeclaration 都可以以 ID 开头。因此，如果解析器刚刚到达 VariableDeclaration 的末尾并且前瞻标记为 ID，则它无法判断是切换到解析 Statements 还是继续解析 VariableDeclarations .
请注意，如果我们将这两个列表都更改为左递归，情况不会改善，因为在那种情况下，解析器将不得不在完全相同的点减少一个空的 Statements 非终结符。避免让解析器猜测在何处插入空非终结符的唯一方法是将两个空非终结符都放在 StatementBody 的末尾。也就是说，VariableDeclarations一定是左递归的，所以空的VariableDeclarations在开头，而Statements一定是右递归的，所以空的Statements在最后：
StatementBody ::= OBRACE VariableDeclarations Statements CBRACE
VariableDeclarations ::= VariableDeclarations VariableDelaration | // EMPTY
Statements ::= Statement Statements | // EMPTY
不过，这不太可行，因为（出于其他原因）解析器必须能够知道它是在解析 Statement 还是以 [= 开头的 VariableDeclaration 28=] 通过查看紧跟在 ID 之后的标记。在那里它会 运行 进入以下非确定性：
b [ ] a; // Declaration
b [ 3 ] = a; // Assignment
在看到第三个标记之前，无法区分这两种可能性。但是解析器需要更早地知道一个标记，以便它可以决定是否将 b 变成 Lvalue.
解决这个冲突比较烦人。我相信通常的方法是通过返回 [ ] 作为单个标记来强制词法扫描器完成工作。可以肯定的是，这解决了问题——有了这个改变，一个左括号总是意味着解析器正在查看一个表达式，而 [ ] 对总是意味着一个声明。但这在扫描仪中很尴尬；特别是，扫描仪需要能够处理类似
[ /* A comment */
/* Another comment */ ]
作为单个 [ ] 令牌。 （我们希望没有人会写这样的代码，但这是合法的。）
这就引出了第三个shift-reduce冲突，这是区分点分赋值和点分调用的结果：
a . b ( 3 ) ;
a . b = 3 ;
虽然这是一个简单得多的问题，但可以通过仔细查看 Decaf 的参考语法来解决。使用您的语法，调用需要匹配产生式 ID DOT ID OPAREN ...，而赋值将匹配 Lvalue DOT ID。换句话说，当 DOT 是 lookahead 时，解析器需要决定是否将 a 减少到 Lvalue。这可以通过使两个右侧更相似来避免。
我的语法需要有用户定义的类型 ID 组合。以下代码的问题在于它生成以下内容：
[java] Warning : *** Shift/Reduce conflict found in state #67 [java] between VariableDecls ::= (*) [java] and Type ::= (*) ID [java] under symbol ID [java] Resolved in favor of shifting. [java] Warning : *** Shift/Reduce conflict found in state #65 [java] between VariableDecls ::= (*) [java] and Type ::= (*) ID [java] under symbol ID [java] Resolved in favor of shifting. [java] Error : *** More conflicts encountered than expected -- parser generation aborted [java] ------- CUP v0.11b 20160615 (GIT 4ac7450) Parser Generation Summary ------- [java] 1 error and 4 warnings [java] 51 terminals, 34 non-terminals, and 93 productions declared, [java] producing 190 unique parse states. [java] 2 terminals declared but not used. [java] 0 non-terminals declared but not used. [java] 0 productions never reduced. [java] 2 conflicts detected (0 expected). [java] No code produced.
我曾尝试在 VariableDecls 和 Stmts 作品中摆脱语法中的 E 作品，但没有成功。我也试过用type生产ID，然后生产e生产。 包裹 cup.example；
import java_cup.runtime.*;
import java.io.IOException;
import java.io.File;
import java.io.FileInputStream;
parser code {:
TScanner scanner;
Parser(TScanner scanner) { this.scanner = scanner; }
public void syntax_error(Symbol cur_token) {
System.out.println("WE ARE HERE");
done_parsing();
}
public void unrecovered_syntax_error(Symbol cur_token) {
System.out.println(cur_token.sym);
System.out.println("[reject]");
}
:}
scan with {: return scanner.next_token(); :};
/* Terminals (tokens returned by the scanner). */
terminal BOOLN, DBL, _INT, STRING, NUL;
terminal _IF, ELS, FR, WHLE;
terminal INTCONST, DBLCONST, STRINGCONST, BOOLCONST;
terminal ADDOP, SUBOP, MULOP, DIV, MOD;
terminal LFTPRN, RTPRN, LFTBRACKET, RTBRC, LFTBRACE, RTBRACE;
terminal LESS, LESSEQ, GRT, GRTEQ, EQL, NEQ;
terminal AND, OR, NOT;
terminal ASSIGN, SEMICOL, COMMA, DOT;
terminal BRK, CLS, EXTNDS, IMPL, INTRFC, NEWAR;
terminal PRNTLN, READLN, RTRN, _VOID, NW;
terminal ID;
/* Non terminals */
non terminal Program, Decls, Decl;
non terminal VariableDecl, FunctionDecl, ClassDecl, InterfaceDecl;
non terminal Variable, Type, Formals, Variables, Extends, Implements, Implement;
non terminal Field, Fields, Prototype, StmtBlock, VariableDecls, Stmts, Stmt;
non terminal OptionExpr, WhileStmt, ForStmt, BreakStmt;
non terminal ReturnStmt, PrintStmt, Expr, Exprs, Lvalue, Call, Actuals, Constant;
non terminal IfStmt;
/* Precedences */
precedence right ASSIGN;
precedence left OR;
precedence left AND;
precedence left EQL, NEQ;
precedence left LESS, LESSEQ, GRT, GRTEQ;
precedence left ADDOP, SUBOP;
precedence left MULOP, DIV, MOD;
precedence left NOT;
precedence left LFTBRACKET, DOT;
precedence left ELS;
/* Toy grammar */
start with Program;
Program ::=
Decls
{: System.out.print("[reduce 1]"); System.out.print("[accept]"); done_parsing(); :};
Decls ::=
Decl
{: System.out.print("[reduce 2]"); :}
| Decl Decls
{: System.out.print("[reduce 3]"); :} ;
Decl ::=
VariableDecl
{: System.out.print("[reduce 4]"); :}
| FunctionDecl
{: System.out.print("[reduce 5]"); :}
| ClassDecl
{: System.out.print("[reduce 6]"); :}
| InterfaceDecl
{: System.out.print("[reduce 7]"); :} ;
VariableDecl ::=
Variable SEMICOL
{: System.out.print("[reduce 8]"); :} ;
Variable ::=
Type ID
{: System.out.print("[reduce 9]"); :} ;
Type ::=
_INT
{: System.out.print("[reduce 10]"); :}
| DBL
{: System.out.print("[reduce 11]"); :}
| BOOLN
{: System.out.print("[reduce 12]"); :}
| STRING
{: System.out.print("[reduce 13]"); :}
| Type LFTBRACKET RTBRC
{: System.out.print("[reduce 14]"); :}
| ID {: System.out.print("[reduce 15]"); :};
FunctionDecl ::=
Type ID LFTPRN Formals RTPRN StmtBlock
{: System.out.print("[reduce 16]"); :}
| _VOID ID LFTPRN Formals RTPRN StmtBlock
{: System.out.print("[reduce 17]"); :} ;
Formals ::=
// EMPTY
{: System.out.print("[reduce 18]"); :}
| Variables
{: System.out.print("[reduce 19]"); :} ;
Variables ::=
Variable
{: System.out.print("[reduce 20]"); :}
| Variable COMMA Variables
{: System.out.print("[reduce 21]"); :} ;
ClassDecl ::=
CLS ID Extends Implements LFTBRACE Fields RTBRACE
{: System.out.print("[reduce 22]"); :} ;
Extends ::=
// EMPTY
{: System.out.print("[reduce 23]"); :}
| EXTNDS ID
{: System.out.print("[reduce 24]"); :};
Implements ::=
// EMPTY
{: System.out.print("[reduce 25]"); :}
| Implement
{: System.out.print("[reduce 26]"); :};
Implement ::=
IMPL ID
{: System.out.print("[reduce 27]"); :}
| IMPL ID COMMA Implement
{: System.out.print("[reduce 28]"); :};
Fields ::=
// EMPTY
{: System.out.print("[reduce 29]"); :}
| Field Fields
{: System.out.print("[reduce 30]"); :};
Field ::=
VariableDecl
{: System.out.print("[reduce 31]"); :}
| FunctionDecl
{: System.out.print("[reduce 32]"); :};
InterfaceDecl ::=
INTRFC ID LFTBRACE Prototype RTBRACE
{: System.out.print("[reduce 33]"); :};
Prototype ::=
// EMPTY
{: System.out.print("[reduce 34]"); :}
| Type ID LFTPRN Formals RTPRN SEMICOL Prototype
{: System.out.print("[reduce 35]"); :}
| _VOID ID LFTPRN Formals RTPRN SEMICOL Prototype
{: System.out.print("[reduce 36]"); :};
StmtBlock ::=
LFTBRACE VariableDecls Stmts RTBRACE
{: System.out.print("[reduce 37]"); :};
VariableDecls ::=
//EMPTY
{:System.out.print("[reduce 38]"); :}
|
VariableDecl VariableDecls
{: System.out.print("[reduce 39]"); :};
Stmts ::=
// EMPTY
{: System.out.print("[reduce 40]"); :}
| Stmt Stmts
{: System.out.print("[reduce 41]"); :};
Stmt ::=
OptionExpr SEMICOL
{: System.out.print("[reduce 42]"); :}
| IfStmt
{: System.out.print("[reduce 43]"); :}
| WhileStmt
{: System.out.print("[reduce 44]"); :}
| ForStmt
{: System.out.print("[reduce 45]"); :}
| BreakStmt
{: System.out.print("[reduce 46]"); :}
| ReturnStmt
{: System.out.print("[reduce 47]"); :}
| PrintStmt
{: System.out.print("[reduce 48]"); :}
| StmtBlock
{: System.out.print("[reduce 49]"); :};
IfStmt ::=
_IF LFTPRN Expr RTPRN Stmt
{: System.out.print("[reduce 50]"); :}
| _IF LFTPRN Expr RTPRN Stmt ELS Stmt
{: System.out.print("[reduce 51]"); :};
WhileStmt ::=
WHLE LFTPRN Expr RTPRN Stmt
{: System.out.print("[reduce 52]"); :};
ForStmt ::=
FR LFTPRN OptionExpr SEMICOL Expr SEMICOL OptionExpr RTPRN Stmt
{: System.out.print("[reduce 53]"); :};
BreakStmt ::=
BRK SEMICOL
{: System.out.print("[reduce 54]"); :};
ReturnStmt ::=
RTRN OptionExpr SEMICOL
{: System.out.print("[reduce 55]"); :};
PrintStmt ::=
PRNTLN LFTPRN Exprs RTPRN SEMICOL
{: System.out.print("[reduce 56]"); :};
Expr ::=
Lvalue ASSIGN Expr
{: System.out.print("[reduce 57]"); :}
| Constant
{: System.out.print("[reduce 58]"); :}
| Lvalue
{: System.out.print("[reduce 59]"); :}
| Call
{: System.out.print("[reduce 60]"); :}
| LFTPRN Expr RTPRN
{: System.out.print("[reduce 61]"); :}
| Expr ADDOP Expr
{: System.out.print("[reduce 62]"); :}
| Expr SUBOP Expr
{: System.out.print("[reduce 63]"); :}
| Expr MULOP Expr
{: System.out.print("[reduce 64]"); :}
| Expr DIV Expr
{: System.out.print("[reduce 65]"); :}
| Expr MOD Expr
{: System.out.print("[reduce 66]"); :}
| Expr LESS Expr
{: System.out.print("[reduce 68]"); :}
| Expr LESSEQ Expr
{: System.out.print("[reduce 69]"); :}
| Expr GRT Expr
{: System.out.print("[reduce 70]"); :}
| Expr GRTEQ Expr
{: System.out.print("[reduce 71]"); :}
| Expr EQL Expr
{: System.out.print("[reduce 72]"); :}
| Expr NEQ Expr
{: System.out.print("[reduce 73]"); :}
| Expr AND Expr
{: System.out.print("[reduce 74]"); :}
| Expr OR Expr
{: System.out.print("[reduce 75]"); :}
| NOT Expr
{: System.out.print("[reduce 76]"); :}
| READLN LFTPRN RTPRN
{: System.out.print("[reduce 77]"); :}
| NEWAR LFTPRN INTCONST COMMA Type RTPRN
{: System.out.print("[reduce 78]"); :};
Lvalue ::=
ID
{: System.out.print("[reduce 79]"); :}
| Lvalue LFTBRACKET Expr RTBRC
{: System.out.print("[reduce 80]"); :}
| Lvalue DOT ID
{: System.out.print("[reduce 81]"); :};
Call ::=
ID LFTPRN Actuals RTPRN
{: System.out.print("[reduce 82]"); :}
| ID DOT ID LFTPRN Actuals RTPRN
{: System.out.print("[reduce 83]"); :};
Actuals ::=
// EMPTY
{: System.out.print("[reduce 84]"); :}
| Exprs
{: System.out.print("[reduce 85]"); :};
Exprs ::=
Expr
{: System.out.print("[reduce 86]"); :}
| Expr COMMA Exprs
{: System.out.print("[reduce 87]"); :};
Constant ::=
INTCONST
{: System.out.print("[reduce 88]"); :}
| DBLCONST
{: System.out.print("[reduce 89]"); :}
| STRINGCONST
{: System.out.print("[reduce 90]"); :}
| BOOLCONST
{: System.out.print("[reduce 91]"); :};
OptionExpr ::=
//EMPTY
{: System.out.print("[reduce 92]"); :}
| Expr
{: System.out.print("[reduce 93]"); :};
我认为这是流行的 "Decaf" 语言的一些变体，经常用于 CS 入门课程。
我不太清楚为什么 CUP 只报告两个冲突，因为 afaics 在你的语法中有四个冲突。也许您粘贴的版本不是生成您在问题中包含的错误消息的版本。
错误消息中报告的冲突是您对变量声明列表和构成语句块的语句列表使用右递归的结果。
常识会告诉您应尽可能避免右递归，因为它使用无限量的解析器堆栈。相比之下，左递归使用恒定数量的解析器堆栈。这是一个很好的经验法则，但大多数情况下，左递归和右递归之间的选择将由语法决定。因此，例如，如果您在不使用优先级声明的情况下为算术表达式编写语法，您将对左结合运算符（几乎所有运算符）使用左递归，对右递归运算符（例如赋值运算符）使用右递归在 C、C++ 和 Java).
项目列表通常可以用任何一种方式编写，因为它们通常会折叠成一个向量而不是保留为二叉树，所以正常情况下将保留递归：
x_list ::= x_list x_element |
// EMPTY
;
您还会看到上述模式的许多变体。例如，如果项目列表不能为空，则第一个产品将是 x_list: x_element。如果元素后跟或由标记分隔，您还必须进行修改，因此您经常会看到类似这样的内容：
// In the language this comes from, statements are *always* followed by
// a semicolon. Most languages don't work that way, though.
statement_list ::= statement_list statement T_SEMICOLON |
// EMPTY
;
// Parameter lists (and argument lists) are either empty or have the items
// *separated* by commas. Because the comma is only present if there are at
// least two items, we need to special-case the empty list:
parameter_list ::= T_OPAREN T_CPAREN |
T_OPAREN parameters T_CPAREN
;
parameters ::= parameter |
parameters T_COMMA parameter
;
虽然我把这些都写成左递归，但在这些特殊情况下我也可以使用右递归。但是左递归解析和右递归解析之间有一个细微的区别，这也会影响解析器动作的执行顺序。考虑两者之间的区别：
id_list ::= id_list ID | id_list ::= ID id_list |
// EMPTY // EMPTY
; ;
他们都接受a b c，但是他们接受的方式不同：
ε•
•3 •3
/ \ / \
•2 c a •2
/ \ / \
•1 b b •1
/ \ / \
ε a c ε
因为在这两种情况下解析器都是自下而上的，所以解析器操作总是从底部开始执行。这将导致第一个（左递归）解析器按输入顺序执行操作，而第二个解析器将从右到左执行操作。
不管怎样，回到问题上来。实际上，您有以下语法，它将派生一个可能为空的声明序列，然后是一个可能为空的语句序列：
StatementBody ::= OBRACE VariableDeclarations Statements CBRACE
VariableDeclarations ::= VariableDeclaration VariableDelarations | // EMPTY
Statements ::= Statement Statements | // EMPTY
考虑到上面导出的解析树，Statements 和 Declarations 都需要有效地以空产生式结束。换句话说，在解析器可以移动 Statements 中的第一个标记之前，它需要减少一个空的 VariableDeclarations 非终结符。这意味着它需要确切地知道哪个标记将是 Statements.
不幸的是，这是不可能的，因为 Statement 和 VariableDeclaration 都可以以 ID 开头。因此，如果解析器刚刚到达 VariableDeclaration 的末尾并且前瞻标记为 ID，则它无法判断是切换到解析 Statements 还是继续解析 VariableDeclarations .
请注意，如果我们将这两个列表都更改为左递归，情况不会改善，因为在那种情况下，解析器将不得不在完全相同的点减少一个空的 Statements 非终结符。避免让解析器猜测在何处插入空非终结符的唯一方法是将两个空非终结符都放在 StatementBody 的末尾。也就是说，VariableDeclarations一定是左递归的，所以空的VariableDeclarations在开头，而Statements一定是右递归的，所以空的Statements在最后：
StatementBody ::= OBRACE VariableDeclarations Statements CBRACE
VariableDeclarations ::= VariableDeclarations VariableDelaration | // EMPTY
Statements ::= Statement Statements | // EMPTY
不过，这不太可行，因为（出于其他原因）解析器必须能够知道它是在解析 Statement 还是以 [= 开头的 VariableDeclaration 28=] 通过查看紧跟在 ID 之后的标记。在那里它会 运行 进入以下非确定性：
b [ ] a; // Declaration
b [ 3 ] = a; // Assignment
在看到第三个标记之前，无法区分这两种可能性。但是解析器需要更早地知道一个标记，以便它可以决定是否将 b 变成 Lvalue.
解决这个冲突比较烦人。我相信通常的方法是通过返回 [ ] 作为单个标记来强制词法扫描器完成工作。可以肯定的是，这解决了问题——有了这个改变，一个左括号总是意味着解析器正在查看一个表达式，而 [ ] 对总是意味着一个声明。但这在扫描仪中很尴尬；特别是，扫描仪需要能够处理类似
[ /* A comment */
/* Another comment */ ]
作为单个 [ ] 令牌。 （我们希望没有人会写这样的代码，但这是合法的。）
这就引出了第三个shift-reduce冲突，这是区分点分赋值和点分调用的结果：
a . b ( 3 ) ;
a . b = 3 ;
虽然这是一个简单得多的问题，但可以通过仔细查看 Decaf 的参考语法来解决。使用您的语法，调用需要匹配产生式 ID DOT ID OPAREN ...，而赋值将匹配 Lvalue DOT ID。换句话说，当 DOT 是 lookahead 时，解析器需要决定是否将 a 减少到 Lvalue。这可以通过使两个右侧更相似来避免。