java - 当用户定义变量或函数的类型时，Java CUP（解析器）会产生移位/减少冲突

Question

我的语法需要有用户定义的类型 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]"); :};

Answer 1

我认为这是流行的“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. 因此，如果解析器刚刚到达 a 的末尾VariableDeclaration并且前瞻标记是ID，它无法判断是切换到解析Statements还是继续解析VariableDeclarations。

请注意，如果我们将这两个列表都更改为左递归，情况不会改善，因为在这种情况下，解析器必须Statements在完全相同的点减少一个空的非终结符。避免让解析器猜测在哪里插入空非终结符的唯一方法是将两个空非终结符放在StatementBody. 换句话说，VariableDeclarations必须是左递归的，所以空VariableDeclarations在开头，而Statements必须是右递归，所以空Statements在结尾：

StatementBody        ::= OBRACE VariableDeclarations Statements CBRACE 
VariableDeclarations ::= VariableDeclarations VariableDelaration     | // EMPTY
Statements           ::= Statement Statements                        | // EMPTY

但是，这并不完全奏效，因为（出于其他原因）解析器必须能够通过Statement查看紧跟在. 在那里它将遇到以下不确定性：VariableDeclarationIDID

    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是前瞻时，解析器需要决定是否归约a到Lvalue。可以通过使两个右侧更相似来避免这种情况。