【flex&bison】1 Introducing Flex and Bison

* flex & bison
 - ソースは公開されている。
   ftp://ftp.iecc.com/pub/file/flexbison.zip
 - はじめのうちは慣れるためにソースを写経する。また
   このメモにも掲載する。先々は公開ソースをそのまま
   使う。その場合は公開ソースのファイル名だけ掲載し
   て、ソース自体は掲載しないこともある。
 - ソースコードの著作権は次のとおり。

------
Copyright (c) 2009, Taughannock Networks. All rights reserved.
------

** 1 Introducing Flex and Bison
 - Flex and Bison はコンパイラやインタプリタのため
   のものだが、入力のパターンを取り扱うようなソフ
   トウエア開発一般に使える。
 - いろいろなDSLにも使われている。
  
*** Lexical Analysis and Parsing
 - コンパイラの研究によって、syntax analysisという
   のはwell-understoodとなった。
 - そこで重要なアイデアは、処理を次の2つにわけると
   いうこと。
   1. lexical analysis (lexing,scanning or 字句解析)
   2. syntax analysis (parsing or 構文解析)
 - scanningは、入力をぶつ切りにする。ただしそれぞ
   れの塊が意味をもつように。この塊をtokensと呼ぶ。
 - parsingは、tokensが御互いにどういう関係にあるか
   を決定する。

*** Regular Expressions and Scanning
 - flexは通常、入力から文字の並びのパターンを探す。
 - a flex programは基本的には、正規表現とan action
   との組のリストである。actionsは、その正規表現に
   マッチしたときに何をすべきかを記述している。

*** Our First Flex Program
 - flexのプログラムの大部分はCである。
 - %%行で3つの部分に区切られている。
   1. 宣言とオプション設定。%{と%}の間は、生成する
      Cのコードの先頭付近にそのまま採用される。
   2. パターンとアクションの組のリスト
   3. Cのコード。生成するCのコードにそのまま採用さ
      れる。

 - 例

/* file: fb1-1.l */
/* just like Unix wc */
%{
     int chars = 0;
     int words = 0;
     int lines = 0;
%}

%%

[a-zA-Z]+ { words++; chars += strlen(yytext); }
\n        { chars++; lines++; }
.         { chars++; }

%%

main(int argc, char **argv)
{
     yylex();
     printf("%8d%8d%8d\n", lines, words, chars);
}
/* end of file */

 - 使ってみる

flex&bison $ flex fb1-1.l
flex&bison $ cc lex.yy.c -lfl
flex&bison $ ./a.out
The boy stood on the burning deck
chelling peanuts by the peck
       2      12      63
flex&bison $ 

*** Programs in Plain Flex
 - 単純なアプリケーションは、flexだけで書ける。
   flexだけ、というのはCのコードを含まない、という
   こと。
 - 例

/* file: fb1-2.l */
/* English -> American */
%%
"colour" { printf("color"); }
"flavour" { printf("flavor"); }
"clever" { printf("smart"); }
"conservative" { printf("liveral"); }
. { printf("%s", yytext); }
%%
/* end of file */

 - 使ってみる。

flex&bison $ flex fb1-2.l
flex&bison $ cc lex.yy.c -lfl
flex&bison $ ./a.out
He is clever and conservative
He is smart and liberal
flex&bison $ 

*** Putting Flex and Bison Together
 - この節からflexとbisonの両方を使う例を構築してい
   くようだ。お題は算術計算。
 - とりあえずflex。

/* file: fb1-3.l */
/* recognize tokens for the calculator and print them out */
%%
"+"    { printf("PLUS\n"); }
"-"    { printf("MINUS\n"); }
"*"    { printf("TIMES\n"); }
"/"    { printf("DIVIDE\n"); }
"|"    { printf("ABS\n"); }
[0-9]+ { printf("NUMBER %s\n",yytext); }
\n     { printf("NEWLINE\n"); }
[ \t]  { }
.      { printf("Mystery chracter %s\n",yytext); }
%%
/* end of file */

 - 使ってみる

flex&bison $ flex fb1-3.l
flex&bison $ cc lex.yy.c -lfl
flex&bison $ ./a.out
12+34
NUMBER 12
PLUS
NUMBER 34
NEWLINE
 5 6 / 7q
NUMBER 5
NUMBER 6
DIVIDE
NUMBER 7
Mystery chracter q
NEWLINE
flex&bison $ 

*** The Scanner as Coroutine
 - yylex()はcoroutine。
 - coroutineはどこまで処理をしたか覚えていて、再度
   呼ばれるとそこから処理を再開する。
 - actionがreturnするなら、yylex()はそこでいったん
   returnし待機する。
 - 違う言い方をすると、actionがreturnするまで、
   yylex()は処理(マッチ)を続ける。
 - coroutineは、継続のクロージャみたいなものかな。

*** Tokens and Values
 - 

/* file: fb1-4.l */
/* recognize tokens for the calculator and print them out */

%{
   enum yytokentype {
     NUMBER = 258,
     ADD = 259,
     SUB = 260,
     MUL = 261,
     DIV = 262,
     ABS = 263,
     EOL = 264 /* end of line */
   };

   int yylval;

%}

%%
"+" { return ADD; }
"-" { return SUB; }
"*" { return MUL; }
"/" { return DIV; }
"|"     { return ABS; }
[0-9]+ { yylval = atoi(yytext); return NUMBER; }
\n      { return EOL; }
[ \t]   { /* ignore white space */ }
. { printf("Mystery character %c\n", *yytext); }
%%
main()
{
  int tok;

  while(tok = yylex()) {
    printf("%d", tok);
    if(tok == NUMBER) printf(" = %d\n", yylval);
    else printf("\n");
  }
}
/* end of file */

*** Grammars and Parsing
 - parserの仕事は、tokensの関係を決定することだっ
   た。
 - 関係の表現は、通常、parse treeにて行う。
 - bisonは、tokensのstreamから逐次処理をしていく。
   bisonプログラムのかきぶりによって、parse treeを
   メモリ上のデータとして現出させることもできるし、
   逐次処理＝具体的な操作として、データとして保持
   しなこともある。

*** BNF Grammars
 - CFGとBNFの簡単な説明。
*** Bison's Rule Input Language
 - bisonのプログラムのかきぶりについて。
 - まず、大枠の構造はflexと同じ。
 - flexのpattern-actionの部分が、BNFチックになる。
 - bisonにもactionがあり、ここにCコードを書くのが
   意味の定義になる。
 - 例

/* file: fb1-5.y */
/* simplest version of calculator */
%{
# include 
%}

/* declare tokens */
%token NUMBER
%token ADD SUB MUL DIV ABS
%token EOL

%%

calclist: /* noshing */
 | calclist exp EOL { printf("= %d\n", $2); }
 ;

exp: factor
 | exp ADD exp { $$ = $1 + $3; }
 | exp SUB factor { $$ = $1 - $3; }
 | exp ABS factor { $$ = $1 | $3; }
 ;

factor: term
 | factor MUL term { $$ = $1 * $3; }
 | factor DIV term { $$ = $1 / $3; }
 ;

term: NUMBER
 | ABS term  { $$ = $2 >=0? $2 : - $2; }
 ;
%%
main(int argc, char **argv)
{
     yyparse();
}

yyerror(char *s)
{
     fprintf(stderr, "error: %s\n", s);
}
/* end of file */

 - 宣言部の%tokenは、それらsymbolsがこのプログラム
   のなかでtokensであることを宣言している。
 - tokensとなるsymbolは大文字にするのが慣例。
 - tokensではないsymbolはBNFの左側にくるべき。(変
   項ということだろう)
 - bisonのルールにでてくるsymbolsはそれぞれ値を持
   つ。左側(ターゲット)のsymbolの値は$$で表す。右
   側のsymbolsの値は、$1,$2,...で表す。
   
*** Compiling Flex and Bison Programs Together
 - flexプログラムをbisonと協調するように変更。

/* file: fb1-5.l */
/* recognize tokens for the calculator and print them out */

%{
# include "fb1-5.tab.h"
%}

%%
"+" { return ADD; }
"-" { return SUB; }
"*" { return MUL; }
"/" { return DIV; }
"|"     { return ABS; }
[0-9]+ { yylval = atoi(yytext); return NUMBER; }
\n      { return EOL; }
[ \t]   { /* ignore white space */ }
. { printf("Mystery character %c\n", *yytext); }
%%
/* end of file */

 - コンパイルが若干複雑になるのでMakefileを用意す
   る。該当ルールは次のとおり。

fb1-5: fb1-5.l fb1-5.y
 bison -d fb1-5.y
 flex fb1-5.l
 cc -o $@ fb1-5.tab.c lex.yy.c -lfl

 - 使ってみる。

1-5 $ make fb1-5
bison -d fb1-5.y
fb1-5.y: conflicts: 3 shift/reduce
flex fb1-5.l
cc -o fb1-5 fb1-5.tab.c lex.yy.c -lfl
1-5 $ ./fb1-5
3 * 2
= 6
55 + 3 * 5
= 70
1-5 $ 

*** Ambiguous Grammars: Not Quite
 - bisonもprologのようにbinary operatorsに対する
   operator precedenceの指定ができるようだ。

*** Adding a Few More Rules
 - 括弧を取り扱えるようにする。
 - プロンプトを出す。

*** Flex and Bison vs. Handwritten Scanners and Parsers
 - (flexの)パターンマッチは記述力が強力なので、Cで
   scannerを書くよりメリットがある。とくに拡張性な
   ど。

*** Exercise
 - 割愛

もしかして、Chapter 1だけでスタックから抜けられるかも？
せっかくだからChapter 2 Using FlexとChapter 3 Using Bisonもやっておこうかどうしようか。

こつこつ。