杯子移位/减少错误 [英] shift/reduce Error with Cup

问题描述

我正在用jflex和Cup为大学使用的编程语言编写解析器 我从最初的基本结构开始，例如处理变量声明".

Hi i am writing a Parser for a Programming language my university uses, with jflex and Cup I started with just the first basic structures such as Processes an Variable Declarations.

我收到以下错误消息

  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.   

我在Cup中的代码如下:

My Code in Cup looks like this :

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

我猜我得到了错误，因为Process声明和VariableDeclaration都以标识符开头，然后以:"开头，然后是Terminal PROCESS或诸如INTEGER之类的终端.如果是这样，我想知道如何告诉我的解析器再向前看一点.或任何可能的解决方案.

I Guess i get the Errors because the Process Declaration and the VariableDeclaration both start with Identifiers then a ":" and then either the Terminal PROCESS or a Terminal like INTEGER. If so i'd like to know how i can tell my Parser to look ahead a bit more. Or whatever Solution is possible.

感谢您的回答.

推荐答案

您的诊断是绝对正确的.由于解析器无法知道IDENT是启动processdecl还是vardecl而没有另外两个前瞻标记，因此它无法知道何时仅缩减了vardecl并正在查看IDENT是否即将看到另一个vardecl或processdecl.

Your diagnosis is absolutely correct. Because the parser cannot know whether IDENT starts a processdecl or a vardecl without two more lookahead tokens, it cannot know when it has just reduced a vardecl and is looking at an IDENT whether it is about to see another vardecl or a processdecl.

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

In the first case, it must just shift the IDENT as part of the following vardecl. In the second case, it needs to first reduce an empty vardecls and then successively reduce vardecls until it has constructed the complete list.

要摆脱这种减少冲突的行为，您需要简化解析器的决策.

To get rid of the shift reduce conflict, you need to simplify the parser's decision-making.

最简单的解决方案是允许解析器以任何顺序接受声明.然后，您将得到如下结果:

The simplest solution is to allow the parser to accept declarations in any order. Then you end up with something like this:

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 ;

(就个人而言，我将使声明列表左递归而不是右递归，但这取决于您是希望在列表的动作中追加还是添加前缀.左递归使用较少的解析器堆栈.)

(Personally, I'd make the declaration lists left-recursive rather than right-recursive, but it depends whether you prefer to append or prepend in the list's action. Left-recursion uses less parser stack.)

如果您真的要坚持所有变量声明都在任何进程声明之前，则可以在declaration_list的操作中进行检查.

If you really want to insist that all variable declarations come before any process declaration, you can check for that in the action for declaration_list.

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

Alternatively, you can start by making both types of declaration list left-recursive instead of right recursive. That will almost work, but it will still generate a shift-reduce conflict in the same state as the original grammar, this time because it needs to reduce an empty process declaration list before the first process declaration can be reduced.

幸运的是，这更容易解决.如果流程声明列表不能为空，则没有问题，所以这只是重新排列生产的问题:

Fortunately, that's easier to work around. If the process declaration list cannot be empty, there is no problem, so it's just a question of rearranging the productions:

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
          ;

最后，一个丑陋但可行的选择是使变量声明列表向左递归，使过程声明列表向右递归.在这种情况下，最后一个变量声明和第一个过程声明之间不会有空生产.

Finally, an ugly but possible alternative is to make the variable declaration list left-recursive and the process declaration list right-recursive. In that case, there is no empty production between the last variable declaration and the first process declaration.

这篇关于杯子移位/减少错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！