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_stmtelse部分的歧义：stmt可以是 if_stmt，如果 else-part 属于哪个则不清楚，例如，如果你写：

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

那么 else 部分可以属于第一个 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
...

对此的一种解决方案是引入一个块语句，并且仅在 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-token和}代表END-token）从而解决歧义。

于 2013-03-12T21:02:03.407 回答