2

嗨，我正在为我的大学使用的编程语言编写解析器，使用 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.

我的杯中代码如下所示：

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); :}
            ;

我想我得到了错误，因为进程声明和变量声明都以标识符开头，然后是“：”，然后是终端进程或像整数这样的终端。如果是这样，我想知道如何告诉我的解析器向前看一点。或任何可能的解决方案。

感谢您的回答。

4

1 回答 1

3

你的诊断是绝对正确的。因为解析器在没有两个前瞻标记的情况下无法知道是IDENT开始 aprocessdecl还是开始 a ，所以它不知道它何时刚刚减少了 a并正在查看 a是否即将看到另一个或 a 。vardeclvardeclIDENTvardeclprocessdecl

在第一种情况下，它必须只是将 转移IDENT为以下 的一部分vardecl。第二种情况，需要先reduce一个空的vardecls，然后依次reduce vardecls，直到构造出完整的链表。

为了摆脱移位减少冲突，您需要简化解析器的决策。

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

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 ;

（就个人而言，我将声明列表设为左递归而不是右递归，但这取决于您是更喜欢在列表的操作中追加还是前置。左递归使用较少的解析器堆栈。）

如果您真的想坚持所有变量声明都在任何流程声明之前，您可以在 for 的操作中检查这一点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
          ;

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

于 2014-08-07T17:03:21.357 回答