[Linux]
Bison/Flex
以前、Go言語でつくるインタプリタをやったが、あれはパーサジェネレータを使わず自力で字句解析と構文解析を行っていた。今回はBison/Flexというパーサジェネレータを使ってそれをやっていく。
- 字句解析(=scanner.ll)
- flexを使う。文字列をトークンに分けるので全てのキーワード（fn, let, if, else, return）などを登録しておく。
- 構文解析(=parser.yy)
- bisonを使う。トークンを抽象構文木に落とし込む。
- 抽象構文木(AST)
- C++のクラスをunionの中に定義しておき、型とトークンを紐づける。
- ASTを作る際の学術的ポイント
- 終端記号と非終端記号 非終端要素ごとに抽象クラスが必要
終端記号は、生成規則の右辺のみに現れ、左辺には現れない。よって、生成規則によってそれ以上は変換されない（これが“終端”と呼ばれる理由である
Flex
Flexの記法
Flexスキャナ定義のほとんどの要素は、 必須要素ではありません。 全体的な定義フォーマットは以下のようになります。
定義、初期Cコード %% ルール %% 他のCコード
上記の「初期Cコード」と「他のCコード」の部分に直接Cのコードを含めることができる。
記法は以下の通り:
%{
C code
...
%}
定義
- Flexが構文解析の際に使う識別子を定義する
// 凡例
definition_name definition
// 実例
DIGIT [0-9]
LETTER [a-z]
IDENT [a-z_][a-z0-9_]*
ALPHANUM {LETTER}|{DIGIT}
ルール
patternが何を認識するべきかを定義し、 actionsがその何かを認識した時に何を実行するべきであるかをスキャナに知らせます。 patternの部分は空白によって区切られます。
// 凡例
pattern actions
// 実例
hi |
bonjour |
hello printf("hello!\n");
goodbye { printf("goodbye!\n"); }
konnichiwa {
line 1
...
line n
}
sayonara printf("lex will not "); printf("print this\n");
- pipeの左にあるパターンを順に下まで見ていくということ
- pattern部分は正規表現で書ける
Bison
Bisonの記法
Bison文法ファイルは4つの主要な部分からなります。 それらを、適切な区切り文字とともに示します。
%{
C宣言部（C declarations）
%}
Bison宣言部（Bison declarations）
%%
文法規則部（Grammar rules）
%%
追加のCプログラム部（Additional C code）
`/* ... */'で囲まれたコメントは、どの部分にも書けます。
api.value.type variant
- bisonのC++の例ではunionを使わずに構文解析するサンプルになっている
- 以下のパラメータを設定している
// 下記２行を設定すると %define api.token.constructor %define api.value.type variant // 以下は上記のアサート？ %define parse.assert
このあたりの記述は 10.1.7.2 Complete Symbols にあった。
api.token.prefix
パーサを生成した際にトークン名にprefixをつける
%define api.token.prefix {TOK_} <-- この部分
%token
END 0 "end of file"
ASSIGN ":="
MINUS "-"
PLUS "+"
STAR "*"
SLASH "/"
LPAREN "("
RPAREN ")"
;
- ドキュメントが見つからないのだけど
- lexerのファイルに以下のように書くと
"=" return yy::parser::make_ASSIGN(loc);
- 生成ファイルに関数が自動的に定義される
return yy::parser::make_ASSIGN(loc);
YY_BREAK
static
symbol_type
make_ASSIGN (location_type l)
{
return symbol_type (token::TOK_ASSIGN, std::move (l));
}