1

次の yacc のコードを参照してください。生産要素を削除すると: '!' expr を使用すると、解析の競合がなくなります。ここで何が起きてるの？

%{
#include <stdio.h>
#include <ctype.h>

%}


%token TRUE
%token FALSE


%%
line    : line expr '\n'    {   printf("%d\n", $2); }
    | line '\n'
|
;
expr    :   expr "or" term  {   printf("expr : expr or term\n"); $$ = $1 | $3; }
|   term        {   printf("expr : term\n");     }
;
term    :   term "and" factor   {   printf("term : term and factor\n"); $$ = $1 & $3; }
|   factor      {   printf("term : factor\n");  }
;
factor  :   '(' expr ')'    {   printf("factor : (expr)\n"); $$ = $2; }
|   '!' expr    {   printf("factor : !expr\n"); $$ = !$2;   }
|   TRUE        {   printf("factor : TRUE\n");  }
|   FALSE       {   printf("factor : FALSE\n"); }
;
%%

#include "lex.yy.c"

int main(int argc, char** argv)
{
while (yyparse() == 0) {
    }

    return 0;
}
4

2 に答える 2

2

パーサーが「!」を検出すると、「expr」の書き換えで問題が発生するため、おそらく競合が発生するように見えます。「factor」の他のプロダクションを無視して、具体的には次の 2 つのプロダクションを見てください。

expr    : expr "or" term  { printf("expr : expr or term\n"); $$ = $1 | $3; }
        | term            { printf("expr : term\n"); }
        ;

factor  : '!' expr        { printf("factor : !expr\n"); $$ = !$2; }

expr は再帰的であるため、パーサーは '!' を検出すると、次の expr に否定が適用されることを認識しますが、「! TRUE OR TRUE」と記述した場合、その否定は最初の true のみに適用されますか、それとも論理和全体に適用されますか? ?

編集: つまり、「or」をシフトする必要があるか、「expr」を減らす必要があるかを判断できません。

yacc で -v コマンド ライン オプションを設定すると、shift/reduce 競合の診断情報を含む、あらゆる種類の機能を含む .output ファイルが生成されます。DFA のすべての状態と競合が発生する場所が表示され、場合によっては正確な理由が表示されます。

独自の生成物に否定を論理的に「term」と「factor」の間に入れると、うまくいくはずです。

于 2009-11-14T18:54:37.280 に答える
1

競合に変更factor: ! exprすると factor: ! factor、競合がなくなります。

最初の衝突だけを分析すると、問題は、termが に縮小するexprか、より複雑になる可能性があることtermです。がない!場合、この決定は先読みの 1 つのシンボルのみで行うことができます。

shift/reduce 競合は必ずしもエラーではないことに注意してください。競合は、シフトを実行することで解決されます。これは、あなたが望むものかもしれません。ほとんどの実際のプロダクション文法には、多数のシフト/リデュースの競合が含まれています。

于 2009-11-14T19:11:06.407 に答える