Как разрешить смещение Уменьшить конфликты в своей грамматике?

Question

Я пишу компилятор от (уменьшенного) Паскаля в ASM ASM. Я на втором этапе процесса - после написания лексического анализатора сейчас я работаю над синтаксическим анализом с Чашка Java.

Я написал свою грамматику, но получил 5 с / г конфликтов, которые все очень похожи. Пример:

   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
    ;

Как я могу устранить этот конфликт?

Спасибо.

Answer 1

Ваша грамматика неоднозначная, а также правая, так и левая рекурсивная. Из моих (ограниченных) знаний о парсерах, я знаю, что это невозможно разбираться в том, что большинство генераторов парсеров.

Это неоднозначно, потому что 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, но вот как я сделал подобное, используя другой генератор парсеров:

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

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

Это делает грамматику однозначной и только правой рекурсивной, которая может быть обработана всеми генераторами парсеров, о которых я знаю.

Негативный аспект этой грамматики заключается в том, что у вас нет ни одного приоритета, но чашка Java, вероятно, имеет другой способ указать приоритет.

Редактировать: Исправлено первое правило грамматики.