Как решить сдвиг уменьшить конфликты в моей грамматике? - PullRequest
Новая
       22

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

2 голосов
/ 16 октября 2010

Я пишу компилятор из (уменьшенного) Паскаля в 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
    ;

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

Спасибо.

1 Ответ

5 голосов
/ 16 октября 2010

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

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

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

...