1

私の目的は、小さな言語のパーサーを作成することです。現在、1 つのシフト/リデュース エラーが発生しています。

私のCFGはどこかがあいまいですが、どこにあるのかわかりません

prog:    PROGRAM beg                   {$$ = "program" $2;}
    |   PROGRAM stmt beg               {$$ = "program" $2 $3;}

beg:    BEG stmt END                   {$$ = "begin" $2 "end";}
    | BEG END                      {$$ = "begin" "end";}


stmt:   beg             {$$ = $1;}
    | if_stmt                   {$$ = $1;}/*
    | IF expr THEN stmt                 {$$ = $1 $2 $3 $4;}*/
    | WHILE expr beg                    {$$ = "while" $2 $3;}
    | VAR COLEQUALS arithexpr SEMI      {$$ = $1 ":=" $3 ";";}
    | VAR COLON INTEGER SEMI            {$$ = $1 ":" "integer" ";";} /*Declaring an integer */
    | VAR COLON REAL SEMI               {$$ $1 ":" "real" ";";}   /*declaring a real */

if_stmt:  IF expr THEN stmt            {$$ = "if" $2 "then" $4;}
    | IF expr THEN stmt ELSE stmt      {$$ = "if" $2 "then" $4 "else" $6;}

expr:   NOT VAR                        {$$ = "!" $2;}
| VAR GREATERTHAN arithexpr        {$$ = $1 ">" $3;}
    | VAR LESSTHAN arithexpr           {$$ = $1 "<" $3;}
    | VAR GREATERTHANEQUALTO arithexpr {$$ = $1 ">=" $3;}
    | VAR LESSTHANEQUALTO arithexpr    {$$ = $1 "<=" $3;}
    | VAR EQUALS arithexpr             {$$ = $1 "==" $3;}
    | VAR NOTEQUALS arithexpr          {$$ = $1 "!=" $3;}
    | arithexpr AND arithexpr          {$$ = $1 "&&" $3;}
    | arithexpr OR arithexpr           {$$ = $1 "||" $3;}


arithexpr:  arithexpr PLUS term            {$$ = $1 + $3;}
    |  arithexpr MINUS term            {$$ = $1 - $3;}
    |   term                   {$$ = $1;}

term:   term TIMES factor          {$$ = $1 * $3;}
    | term DIVIDE factor           {$$ = $1 / $3;}
    | factor               {$$ = $1;}

factor:   VAL                              {$$ = $1;}
4

1 に答える 1

1

「エラー」は、if_stmt のelse部分のあいまいさから来ています: stmtif_stmt である可能性があり、else-part がどちらに属しているかが明確ではありません。たとえば、次のように記述した場合:

if y1 then if y2 then x=1 else x=2

その場合、else-part は最初の if または 2 番目の if に属する可能性があります。

この質問は、さまざまな形で何度も尋ねられています。if then else shift reduce

診断のために(あなたもそのif then else shift reduce問題の犠牲者であることを知るために)、バイソンに出力ファイルを生成するように指示できます

bison -r all  myparser.y

これにより、ファイル myparser.output が生成されます。このファイルで、あなたのケースを見つけることができます。

State 50 conflicts: 1 shift/reduce
....
state 50

   11 if_stmt: IF expr THEN stmt .  [ELSE, BEG, END]
   12        | IF expr THEN stmt . ELSE stmt

    ELSE  shift, and go to state 60

    ELSE      [reduce using rule 11 (if_stmt)]
    $default  reduce using rule 11 (if_stmt)


state 51
...

これに対する 1 つの解決策は、ブロック ステートメントを導入し、これらを if および else 部分のステートメントとしてのみ許可することです。

stmt: ...
    | blk_stmt
blk_stmt: BEGIN stmt END
if_stmt:  IF expr THEN blk_stmt
    | IF expr THEN blk_stmt ELSE blk_stmt

修正されたC言語の場合、これは次のことだけを意味します

if x1 then {if x2 then {y=1}} else {y=2}

( {BEGIN トークンを}表し、END トークンを表すことで) 可能になり、あいまいさが解決されます。

于 2013-03-12T21:02:03.407 に答える