2

我正在编写一个从(简化的)Pascal 到 ARM asm 的编译器。我正处于该过程的第二步 - 在编写词法分析器之后,现在我正在使用java cup进行语法分析。

我写了我的语法,但有 5 个 S/R 冲突,它们都非常相似。例子:

   Warning : *** Shift/Reduce conflict found in state #150
between assign_stmt ::= val_expr ASSIGN val_expr (*) 
  and     val_expr ::= val_expr (*) LBRACKET val_expr RBRACKET 
  under symbol LBRACKET
  Resolved in favor of shifting

我本节的语法:

assign_stmt ::=
 val_expr ASSIGN val_expr;

val_expr ::=
     NIL | BOOL_CONST | INT_CONST | CHAR_CONST | PTR val_expr %prec MEM | ADD val_expr %prec UADD |
     SUB val_expr %prec USUB | NOT val_expr | val_expr PTR %prec VAL | val_expr MUL val_expr |
     val_expr DIV val_expr | val_expr ADD val_expr | val_expr SUB val_expr | val_expr EQU val_expr |
     val_expr NEQ val_expr | val_expr LTH val_expr | val_expr GTH val_expr | val_expr LEQ val_expr |
     val_expr GEQ val_expr | val_expr AND val_expr | val_expr OR val_expr | IDENTIFIER | 
     val_expr LBRACKET val_expr RBRACKET | val_expr DOT IDENTIFIER | IDENTIFIER LPARENTHESIS params_list RPARENTHESIS |
     LBRACKET type_desc RBRACKET | LPARENTHESIS val_expr RPARENTHESIS
    ;

我怎样才能消除这种冲突?

谢谢。

4

1 回答 1

5

你的语法是模棱两可的,而且是左右递归的。根据我对解析器的(有限)知识,我知道大多数解析器生成器都无法解析。

这是模棱两可的,因为val_expr ADD val_expr SUB val_expr可以解析为:

       ADD
      /   \
val_expr  SUB
         /   \
   val_expr  val_expr

        SUB
       /   \
     ADD  val_expr
    /   \
val_expr  val_expr

我从未使用过 Java CUP,但这是我使用另一个解析器生成器做类似事情的方式:

val_expr ::=
    expr1 (SUB | ADD | <add all your operators here>) val_expr
    | expr1 ;

expr1 ::=
    NIL | BOOL_CONST | INT_CONST | CHAR_CONST | <etc> ;

这使得语法明确且只有右递归,可以由我知道的所有解析器生成器处理。

该语法的一个负面方面是您没有任何优先级,但 Java CUP 可能有另一种指定优先级的方法。

编辑:修正了第一个语法规则。

于 2010-10-16T15:10:16.857 回答