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

Question

我的语法师需要具有用户定义的Type 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产品。我也尝试过使用类型产生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只报告两个冲突，因为按照您的语法，您的语法中有四个冲突。也许您粘贴的版本不是生成包含在问题中的错误消息的版本。

错误消息中报告的冲突是由于对变量声明列表和组成语句块的语句列表都使用了右递归的结果。

传统知识将告诉您，应尽可能避免进行右递归，因为它使用了无限数量的解析器堆栈。相比之下，左递归使用恒定数量的解析器堆栈。这是一个很好的经验法则，但是在大多数情况下，左递归和右递归之间的选择将由语法决定。因此，例如，如果您在不使用优先级声明的情况下为算术表达式编写语法，则将对左关联运算符（几乎全部使用左递归）和对右递归运算符（例如赋值运算符）使用右递归C，C ++和Java）。

项目列表通常可以以任何一种方式编写，因为它们通常会折叠成一个向量，而不是停留在二叉树上，因此正常情况下将保留递归：

x_list ::= x_list x_element |
           // EMPTY
           ;

您还将看到上述模式的许多变体。例如，如果itmes列表不能为空，则第一个生产为 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。

请注意，如果将这两个列表都更改为left-recursion，情况将不会得到改善，因为在这种情况下，解析器必须在完全相同的点上减少空的 Statements非终结符。避免使解析器猜测要在何处插入空非终端的唯一方法是将两个空非终端都放在 StatementBody的末尾。换句话说， VariableDeclarations必须是左递归的，以便空的 VariableDeclarations在开头，而 Statements必须是右递归的，以便空的 Statements在结尾：

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

不过，这并不太奏效，因为（出于其他原因）解析器必须能够通过查看紧随其后的标记来知道是解析 Statement还是以 VariableDeclaration开头的 ID。 ID。在那里，它将遇到以下不确定性：

    b [ ] a;      // Declaration
    b [ 3 ] = a;  // Assignment

在看到第三个标记之前，无法区分这两种可能性。但是解析器需要更早地知道一个令牌，以便它可以决定是否将 b转换为 Lvalue。

解决这一冲突更令人讨厌。我相信通常的方法是通过将 [ ]作为单个标记返回来强制词法扫描器执行此工作。可以肯定地解决了这个问题-有了这一更改，单个开括号始终表示解析器正在查看表达式，而 [ ]对始终表示声明。但这在扫描仪中很尴尬。特别是，扫描仪将需要能够处理类似

[ /* A comment */
  /* Another comment */ ]

作为单个 [ ]令牌。 （我们希望没有人会编写这样的代码，但这是合法的。）

这将我们引向第三次转移-减少冲突，这是区分点分配和点调用的结果：

a . b ( 3 ) ;
a . b = 3 ;

但是，这是一个简单得多的问题，可以通过仔细阅读Decaf的参考语法来解决。对于您的语法，调用需要匹配产生的 ID DOT ID OPAREN ...，而分配将匹配 Lvalue DOT ID。换句话说，当 DOT为超前时，解析器需要确定是否将 a缩小为 Lvalue。可以通过使两个右侧更加​​相似来避免这种情况。