3

論理式を解析するための次の単純な文法は、reduce/reduceの競合を引き起こします。

%token AND OR
%token NUMBER VARIABLE
%%
logical_expr
    : logical_expr AND logical_term
    | logical_expr OR logical_term
    | logical_term
    ;
logical_term
    : VARIABLE
    | comparison
    | '(' logical_expr ')'
    ;
comparison
    : expr '<' expr
    | expr '>' expr
    ;
expr
    : expr '+' term
    | expr '-' term
    | term
    ;
term
    : NUMBER
    | VARIABLE
    | '(' expr ')'
    ;
%%

バイソンからのステータスレポートには次のものがあります。

state 2

    4 logical_term: VARIABLE .
   13 term: VARIABLE .

    ')'       reduce using rule 4 (logical_term)
    ')'       [reduce using rule 13 (term)]
    '<'       reduce using rule 13 (term)
    '>'       reduce using rule 13 (term)
    '+'       reduce using rule 13 (term)
    '-'       reduce using rule 13 (term)
    $default  reduce using rule 4 (logical_term)

問題は、「(a)+1<2」の解析方法がわからないことだと思います。この文法をどのように明確にしますか?出来ますか?

4

1 に答える 1

5

文法の基本的な問題は( VARIABLE、次のトークンがである場合、パーサーはこれを括弧で囲む必要があるか)どうかを判断できないことです。これは、後の次のトークンに依存します。その次のトークンが。、またはそのexpr、または(またはEOF)の場合は、。exprlogical_expr)+-<>ANDORlogical_expr

これに対する通常の解決策は、文法で型チェックを行わないことです。可能ではありますが、追加の先読みが必要であり、マルチレベルの文法またはそのような複雑さが必要になる場合があります。

あなたの場合、logical_termルールをに変更すると

logical_term
    : comparison
    | expr
    ;

a > 3 AND 2競合は解消されますが、パーサーは、またはなど、タイプが正しくないものを受け入れます 2 + 2 OR 7。結果の解析ツリー(または作成しているデータ構造)の型チェックを実行して正確にする必要がありますが、とにかく(少なくともVARIABLE、変数が数値であることを確認するためにすでに型チェックする必要があります)コンテキストに応じて、またはブール値。)

于 2012-10-14T23:55:36.177 に答える