Ex.14 の変更点

• 追加された行はこの色です。
• 削除された行はこの色です。
• Ex.14 へ行く。

#author("2023-05-20T17:27:08+09:00","","")
#author("2024-02-14T20:13:12+09:00;2023-05-20T17:27:08+09:00","","")
** 構文解析ツールbison3 [#l3170f53]
bisonの動作原理は知りたいけど、一方で難しい専門用語やbison.cの中身は知りたくない。そんないいとこ取りはないものでしょうか・・・。悩んだ挙句、.yファイルを使うということは非終端記号、終端記号をうまく組み合わせて、構文ルールを作成するということに着目します。つまり、組み合わせを一定量理解すれば、動作原理を知ったも当然かも？・・・ようするに、帰納法で話を進めていこうと思います。

** 急がば回れるか？（汗 [#ga4c0c61]
サンプルとしてよく取り上げられる「電卓」を扱います。書籍「コンパイラ構成法（p25ページ）」に書かれているものを少し改造しました。

・prog2-2.y
 %{
 /*  構文解析の過程をトレース */
 
 #define EOF                    -1
 
 //---------------------------------------------------------------------------
 // #define YYDEBUG             1
 // #define YYERROR_VERBOSE     1
 // int yydebug = 1;
 
 
 //---------------------------------------------------------------------------
 int  yylex();
 void yyerror(char* str);
 
 %}
 
 
 %%
 input  : expr '\n'        { printf("correct expression\n"); YYACCEPT; }
        ;
 
 expr   : expr '+' term    { printf("expr + term   -> expr\n");   }
        | expr '-' term    { printf("expr - term   -> expr\n");   }
        | term             { printf("term          -> expr\n");   }
        ;
 
 term   : term '*' factor  { printf("term * factor -> term\n");   }
        | term '/' factor  { printf("term / factor -> term\n");   }
        | factor           { printf("factor        -> term\n");   }
        ;
 
 factor : 'i'              { printf("i             -> factor\n"); }
        | '(' expr ')'     { printf("( expr )      -> factor\n"); }
        ;
 %%
 
 
 //---------------------------------------------------------------------------
 int yylex()
 {
    int c = getchar();
 
    switch (c)
    {
    case EOF:
        printf("EOF detected\n");
        break;
 
    case '\n':
        printf("--> '\\n'\n");
        break;
 
    default:
        printf("--> '%c'\n", c);
        break;
    }
 
    return c;
 }
 //---------------------------------------------------------------------------
 void yyerror(char* str)
 {
    printf("!! yyerror !! = %s\n", str);
 }
 //---------------------------------------------------------------------------
 int main(int argc, char** argv)
 {
    for(;;)
    {
        yyparse();
    }
 
    return 0;
 }

コードを大雑把に眺めてみると、re2cも必要なく、.yファイル1つで完結・・・今までとは異なる印象を与えてしまうかもしれません。色々な書き方があるということでご容赦ください。ちなみにトークンが全く宣言されていませんが、実はASCII文字でも問題なかったりします。Doc.20の記事のトークンが、258番目から定義されているのはそのせいです。あとYYACCEPTマクロは、bisonの状態をリセットするというおまじないとなっています（＾＾；。

・実行
 $ bison -l -d prog2-2.y
 $ gcc prog2-2.tab.c
 $ ./a.exe

早速、例を上げつつ内部でどういう順番に実行されるのか見ていきましょう。ここは特に、実際に入力してみることをおすすめします。電卓といえば数字計算ですが、とりあえず数字は文字'i'ということにして読んでください。

 i                        # 入力文字列
 --> 'i'
 i             -> factor  # (A)
 factor        -> term    # (B)
 --> '\n'
 term          -> expr    # (C)
 correct expression       # (D)

入力文字列は「'i' と '\n'（改行）」です。始めにbisonは、'i'で終わる記号部分（終端記号）を構文から探します。input->expr->termと状態を内部へ見ていき、factor内で発見します(A)。このことによりfactorが確定したので、term内の３番目のアクションを実行します(B)。次の文字は'\n'です。'\n'はterm内にはないので１つ前のexprに戻ります(C)。最後のinputでようやく見つけて「correct expression」を表示する、といった流れです(D)。

#br

今の話はイメージとしてなので、実際の処理は違います。スタックと解析表でやっているらしいけれど・・・そのあたりは本を読んでください（キーワードは、LR構文解析法）。さあ、後は読んでいる方におまかせです。大変面倒なことは承知ですが、１つ１つを脳内トレースしていただければと思っています。

 (i)
 --> '('
 --> 'i'
 i             -> factor
 factor        -> term
 --> ')'
 term          -> expr
 ( expr )      -> factor
 factor        -> term
 --> '\n'
 term          -> expr
 correct expression

 i+i
 --> 'i'
 i             -> factor
 factor        -> term
 --> '+'
 term          -> expr
 --> 'i'
 i             -> factor
 factor        -> term
 --> '\n'
 expr + term   -> expr
 correct expression

 i+i*i
 --> 'i'
 i             -> factor
 factor        -> term
 --> '+'
 term          -> expr
 --> 'i'
 i             -> factor
 factor        -> term
 --> '*'
 --> 'i'
 i             -> factor
 term * factor -> term
 --> '\n'
 expr + term   -> expr
 correct expression

 (i+i)*i
 --> '('
 --> 'i'
 i             -> factor
 factor        -> term
 --> '+'
 term          -> expr
 --> 'i'
 i             -> factor
 factor        -> term
 --> ')'
 expr + term   -> expr
 ( expr )      -> factor
 factor        -> term
 --> '*'
 --> 'i'
 i             -> factor
 term * factor -> term
 --> '\n'
 term          -> expr
 correct expression

電卓の例がすばらしいのは、終端記号を巧みに使い、計算順位をコントロールしていることです。アクションにスタックを積む処理を追加すれば、必然的に逆ポーランドの出来上がり。よくわからない方は[[Wikipedia:http://ja.wikipedia.org/wiki/%E9%80%86%E3%83%9D%E3%83%BC%E3%83%A9%E3%83%B3%E3%83%89%E8%A8%98%E6%B3%95]]をご覧ください。この変換を知っていればTinyBasicぐらいは作れるようになります。
電卓の例がすばらしいのは、終端記号を巧みに使い、計算順位をコントロールしていることです。アクションにスタックを積む処理を追加すれば、必然的に逆ポーランドの出来上がり。よくわからない方は[[Wikipedia:https://ja.wikipedia.org/wiki/%E9%80%86%E3%83%9D%E3%83%BC%E3%83%A9%E3%83%B3%E3%83%89%E8%A8%98%E6%B3%95]]をご覧ください。この変換を知っていればTinyBasicぐらいは作れるようになります。

** 履歴 [#r21bc3ba]
- 2008/11/11