←課題4.4の確認 | ↑目次 | →課題5.1のヒント

情報科学実験II　コンパイラ作成

第4回

bisonの警告メッセージについて

警告 nonterminals(rules) useless in grammar

bisonを実行したときに、 
picoc.y: 警告: 14 nonterminals useless in grammar [-Wother]
picoc.y: 警告: 28 rules useless in grammar [-Wother]
picoc.y:30.14-20: 警告: nonterminal useless in grammar: st_list [-Wother]
 %type  st_list stmt if_part
...
picoc.y:135.11-38: 警告: rule useless in grammar [-Wother]
        | decl_lvar_list decl_lvar ';'
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
...
のように、useless in grammarを含む警告が出た場合

まず、%startが適切に設定されているかどうかを確認する。今回の実験では、本サイトにしたがって課題4.3、4.4.4節を確認している場合に、設定不要である。課題4.4については、 

%start program
が必要である。bisonはBNFで書かれた文法(ルール)に従って、構文解析を実行するが、開始記号(解析すべきプログラム、式、または文などの全体を表す記号)は、%startで指定するか、ルールの最上部に記す。%startの指定がない場合に、多くの場合、ルールの最上部にはlistかexprがあると思われる。開始記号が左辺にあるルールから開始して、各ルールの左辺を右辺に置き換えてたどっていくことで到達することができないルールや記号はuselessである。

これでもうまくいかないときには、ルール部をよく見て確認する。気づきにくいミスとして、「各ルールでは、右辺のうち少なくとも1つには左辺の非終端記号が含まれないものが存在しなければならない」ことへの違反がある。空白で区切られた引数を表すルールで、 

args: 
    | args expr
    ;
は正しいが、 
args: args expr
    ;
は誤りである。前者は、1行目のルールでargsを空列に置き換えることができる。したがって、 
args → args expr → args expr expr → expr expr
のように、どこかでargsを空列に置き換えることで、置き換えを止めることができる。後者は、 
args → args expr → args expr expr → args expr expr expr → ...
のように、いつまでも置き換えが止まらない。

警告 shift/reduce conflict

bisonを実行したときに、 
picoc.y: 警告: 4 shift/reduce conflict [-Wconflicts-sr]
というconflictを含む警告が出た場合 新しいバージョンのbisonには、-Wcounterexamplesというオプションがあって、問題点を指摘してくれる。 
bison -t -d -Wcounterexamples picoc.y
演習室のbisonは少しバージョンが古くて、このオプションに対応していないので、とりあえずこちらで勝手に用意してみた。 
/cis/sensei/ohta/dm2/linux/bin/bison -t -d -Wcounterexamples picoc.y
のようにするとどの辺が怪しいかがわかる…かもしれない。

無視できない警告の例

以下が-Wcounterexamplesの出力例である。 
$ /cis/sensei/ohta/dm2/linux/bin/bison -t -d -Wcounterexamples picoc.y
picoc.y: 警告: 4 個のシフト/還元競合 [-Wconflicts-sr]
picoc.y: 警告: トークン '+' のシフト/還元競合 [-Wcounterexamples]
  例: '-' expr • '+' expr
  シフト派生
    expr
    ↳ 8: '-' expr
             ↳ 4: expr • '+' expr
  還元派生
    expr
    ↳ 4: expr            '+' expr
         ↳ 8: '-' expr •
...
これは、-expr+exprを-(expr+expr)と解釈するか(-expr)+exprと解釈するかの間で競合が発生したことを警告している。bisonは上に書かれた方、すなわち、-(expr+expr)と解釈することを選択したが、この選択は望ましくないものであろう。

無視できる警告

if文に対する記述のある.yファイルを処理した結果、競合が1か所である場合の出力例を示す。 
$ /cis/sensei/ohta/dm2/linux/bin/bison -t -d -Wcounterexamples picoc.y
picoc.y: 警告: 1 個のシフト/還元競合 [-Wconflicts-sr]
picoc.y: 警告: トークン ELSE のシフト/還元競合 [-Wcounterexamples]
  例: IF '(' expr ')' if_part • ELSE stmt
  シフト派生
    if_part
    ↳ 33: IF '(' expr ')' stmt
                          ↳ 29: if_part • ELSE stmt
  還元派生
    stmt
    ↳ 29: if_part                               ELSE stmt
          ↳ 33: IF '(' expr ')' stmt
                                ↳ 28: if_part •
これは、if (expr1) if (expr2) stmt1 else stmt2を if (expr1) { if (expr2) stmt1 else stmt2 }と解釈するか if (expr1) { if (expr2) stmt1 } else stmt2と解釈するかの間で競合が発生したことを警告している。bisonは上に書かれた方、すなわち、if (expr1) { if (expr2) stmt1 else stmt2 }と解釈することを選択した。これは望ましいものである。この競合が起こらないように.yファイルを記述することもできるが、記述が複雑になるため、わざと警告を残すことにしてある。今回の実験では、if文に関するもの以外の警告は対応が必要である。
トップページ