シフトを解決する方法私の文法の競合を減らす?
-
08-10-2019 - |
質問
(redument)PascalからARM ASMにコンパイラを書いています。私はプロセスの2番目のステップにいます - 語彙分析装置を書いた後、私は構文分析に取り組んでいます ジャワカップ.
私は文法を書きましたが、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
;
どうすればこの紛争を排除できますか?
ありがとう。
解決
あなたの文法はあいまいで、右再帰的と左再帰的です。パーサーに関する(限られた)知識から、これはほとんどのパーサージェネレーターによって解析することが不可能であることを知っています。
それはあいまいだからです 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にはおそらく優先順位を指定する別の方法があります。
編集: :最初の文法ルールを修正しました。
所属していません StackOverflow