2

Flex と Lemon を使用して、制約を解析する小さなパーサーを作成しています。Lemon は、私が取り除くことができなかったいくつかの構文解析の競合を報告しています。文脈自由文法で構文解析の競合を取り除くための特定のトリックはありますか?

文法は次のとおりです。

// Reprint of input file "Constraint_grammar.y".
// Symbols:
//   0 $          5 NE        10 PLUS        15 NOT         20 error
//   1 IFF        6 GT        11 MINUS       16 LPAREN      21 constraint
//   2 AND        7 GTE       12 TIMES       17 RPAREN      22 bool_expr 
//   3 OR         8 LT        13 DIVIDE      18 VARIABLE    23 int_expr
//   4 EQ         9 LTE       14 POWER       19 INTEGER   
constraint ::= bool_expr.
bool_expr ::= LPAREN bool_expr RPAREN.
int_expr ::= LPAREN int_expr RPAREN.
bool_expr ::= int_expr LT int_expr.
bool_expr ::= int_expr GT int_expr.
bool_expr ::= int_expr EQ int_expr.
bool_expr ::= int_expr NE int_expr.
bool_expr ::= int_expr GTE int_expr.
bool_expr ::= int_expr LTE int_expr.
bool_expr ::= bool_expr AND bool_expr.
bool_expr ::= bool_expr OR bool_expr.
bool_expr ::= bool_expr IFF bool_expr.
int_expr ::= int_expr PLUS int_expr.
int_expr ::= int_expr MINUS int_expr.
int_expr ::= int_expr TIMES int_expr.
int_expr ::= int_expr DIVIDE int_expr.
int_expr ::= int_expr POWER int_expr.
bool_expr ::= NOT bool_expr.
int_expr ::= MINUS int_expr.
int_expr ::= VARIABLE.
bool_expr ::= VARIABLE.
int_expr ::= INTEGER.
%nonassoc IFF.
%left AND.
%left OR.
%nonassoc EQ NE GT GTE LT LTE.
%left PLUS MINUS.
%left TIMES DIVIDE.
%right POWER NOT.
%nonassoc LPAREN RPAREN.

エラーは次のとおりです。

State 28:
     (19) int_expr ::= VARIABLE *
     (20) bool_expr ::= VARIABLE *

                             $ reduce 20
                           IFF reduce 20
                           AND reduce 20
                            OR reduce 20
                            EQ reduce 19
                            NE reduce 19
                            GT reduce 19
                           GTE reduce 19
                            LT reduce 19
                           LTE reduce 19
                          PLUS reduce 19
                         MINUS reduce 19
                         TIMES reduce 19
                        DIVIDE reduce 19
                         POWER reduce 19
                        RPAREN reduce 19
                        RPAREN reduce 20  ** Parsing conflict **
State 40:
          bool_expr ::= bool_expr * AND bool_expr
          bool_expr ::= bool_expr * OR bool_expr
          bool_expr ::= bool_expr * IFF bool_expr
     (11) bool_expr ::= bool_expr IFF bool_expr *

                             $ reduce 11
                           IFF shift  4
                           IFF reduce 11  ** Parsing conflict **
                           AND shift  1
                            OR shift  3
                        RPAREN reduce 11

パーサー ジェネレーターのレポート全体はここにあります。http://pastebin.com/TRsV3WvK

ここで私が間違っていることを知っている人はいますか？これらの競合を無視できますか?

4

2 に答える 2

1

ブール変数と整数変数を区別し、シンボル テーブルを使用して返されるトークンのタイプを判断することで、「状態 28」の競合を修正することを期待します。おそらく、BOOL_VARIABLE と INT_VARIABLE があるでしょう。テストでは、この変更により「状態 28」の競合が解消されることが示されています。

'State 40' の競合は、IFF の結合性を からnonassocに変更することで簡単に除去できleftます。連想させない正当な理由はありますか？

于 2011-01-03T21:41:09.587 に答える
0

パーサーの競合があります。指定した文法が明確ではありません。つまり、終端記号の特定の入力に対して複数の解析ツリーが存在します。これは非常に一般的ですが、明確な文法が必要な場合は、結合性や優先順位などの曖昧さをなくす規則を指定して、常に解析ツリーの 1 つだけを選択できるようにする必要があります。

文法をどのような制約で解析しているのかはわかりませんが、ここで巨大な文法が必要だと確信しています.プログラミング言語は（ほとんど）常に曖昧ではありません。（ただし、制約が何らかの自然言語ソースからのものである場合は、おそらくより適切なパーサーを使用する必要があります）あいまいな文法を与えた場合にパーサーレモンが何をするかわかりません。おそらく遷移の1つを好むだけですそのオートマトンでは、望ましくないツリーにつながる可能性があります。

于 2011-01-03T21:56:44.770 に答える