移/减杯错误

Question

嗨，我正在为我的大学使用的编程语言写一个解析器，使用jflex和Cup我从第一个基本结构开始，比如进程和变量声明。

我得到以下错误

  Warning : *** Shift/Reduce conflict found in state #4   
  between vardecls ::= (*)  
  and     vardecl ::= (*) IDENT COLON vartyp SEMI   
  and     vardecl ::= (*) IDENT COLON vartyp EQEQ INT SEMI  
  under symbol IDENT  
  Resolved in favor of shifting.      
  Warning : *** Shift/Reduce conflict found in state #2   
  between vardecls ::= (*)    
  and     vardecl ::= (*) IDENT COLON vartyp SEMI    
  and     vardecl ::= (*) IDENT COLON vartyp EQEQ INT SEMI   
  under symbol IDENT  
  Resolved in favor of shifting.   

My Code in Cup是这样的

non terminal programm;
non terminal programmtype;
non terminal vardecl;
non terminal vardecls;
non terminal processdecl;
non terminal processdecls;
non terminal vartyp;

programm ::= programmtype:pt vardecls:vd processdecls:pd
                {: RESULT = new SolutionNode(pt, vd, pd); :} ;

programmtype ::= IDENT:v 
                {: RESULT = ProblemType.KA; :} ;

vardecls ::= vardecl:v1 vardecls:v2
                {:  v2.add(v1);
                    RESULT = v2; :}
            | 
                {:  ArrayList<VarDecl> list = new ArrayList<VarDecl>() ;
                    RESULT = list;   :} 
            ;
vardecl ::= IDENT:id COLON vartyp:vt SEMI
                {: RESULT = new VarDecl(id, vt); :}
            | IDENT:id COLON vartyp:vt EQEQ INT:i1 SEMI
                {: RESULT = new VarDecl(id, vt, i1); :} 
            ;

vartyp ::= INTEGER 
            {: RESULT = VarType.Integer ; :} 
            ;

processdecls ::= processdecl:v1 processdecls:v2
                {:  v2.add(v1);
                    RESULT = v2; :}
            | {:    ArrayList<ProcessDecl> list = new ArrayList<ProcessDecl>() ;
                    RESULT = list;   :} 
            ;
processdecl ::= IDENT:id COLON PROCESS vardecls:vd BEGIN END SEMI
                {: RESULT = new ProcessDecl(id, vd); :}
            ;

我想我得到错误，因为进程声明和变量声明都以标识符开始，然后是":"，然后是终端进程或像INTEGER这样的终端。如果是这样，我想知道我如何告诉我的解析器往前看一点。或者任何可能的解决方案。

谢谢你的回答

Answer 1

您的诊断完全正确。因为解析器无法知道IDENT是启动processdecl还是启动vardecl，如果没有两个前瞻标记，它就无法知道何时它刚刚减少了vardecl并正在查看IDENT，是否即将看到另一个vardecl或processdecl。

在第一种情况下，它必须将IDENT移位为vardecl的一部分。在第二种情况下，它需要首先约简一个空的vardecls，然后依次约简vardecls，直到它构造了完整的列表。

为了摆脱shift - reduce冲突，您需要简化解析器的决策。

最简单的解决方案是允许解析器接受任何顺序的声明。最后你会得到这样的结果:

program ::= program_type declaration_list ;
declaration_list ::=
            var_declaration declaration_list
          | process_declaration declaration_list
          |
          ;
var_declaration_list ::=
            var_declaration var_declaration_list
          |   
          ;
process_declaration ::=
            IDENT:id COLON PROCESS var_declaration_list BEGIN END SEMI ;

(个人而言，我更倾向于声明列表的左递归而不是右递归，但这取决于您是喜欢在列表的操作中追加还是追加。左递归使用更少的解析器堆栈。)

如果你真的想坚持所有变量声明都在任何进程声明之前，你可以在declaration_list的操作中检查这一点。

或者，您可以首先将这两种类型的声明列表设置为左递归而不是右递归。这将使几乎可以工作，但是它仍然会在与原始语法相同的状态下生成shift-reduce冲突，这一次是因为它需要在减少第一个过程声明之前减少一个空的过程声明列表。

幸运的是，这更容易解决。如果进程声明列表不能为空，则没有问题，因此只需重新安排结果:

program ::= program_type var_declaration_list process_declaration_list
          | program_type var_declaration_list
          ;
var_declaration_list ::=
            var_declaration var_declaration_list
          |   
          ;
process_declaration_list ::=
            process_declaration_list process_declaration
          | process_declaration
          ;

最后，一个丑陋但可能的替代方法是使变量声明列表左递归，而使进程声明列表右递归。在这种情况下，在最后一个变量声明和第一个进程声明之间没有空的结果。