lex / yacc (パーサジェネレータ)

字句解析器・構文解析器を、宣言的な仕様ファイルから自動生成するツール群。自作言語処理系の定番フロントエンド。

lex / flex (字句解析器生成)

• .l ファイルに「正規表現 → 返すトークン/アクション」を並べると、トークナイザの C コードを生成する。
• 例: "%" return MOD;、"[" return L_SQBRACKET; のように記号や予約語をトークン種別へ写す。
• flex は lex の GNU 実装 (今回の環境は flex 2.5.35)。

yacc / bison (構文解析器生成)

• .y ファイルに BNF 風の文法規則と、各規則の 意味アクション (C コード) を書く。LALR(1) パーサを生成する。
• 規則右辺の各シンボルは $1, $3 … で参照でき、$$ が左辺の属性。属性に AST や命令列 (cptr*) を載せて 構文主導翻訳 を行う。
• bison は yacc の GNU 実装 (今回の環境は bison 2.3)。yacc -dv で y.tab.c とデバッグ情報を生成。
• 優先順位・結合性は %left/%right/%prec の宣言で解決でき、左再帰をそのまま扱える (operator-precedence-parsing)。

racc (Ruby 版 yacc)

• Ruby 標準添付ライブラリ。.y に Ruby アクションを書いて Ruby のパーサを生成する。自作言語 arcturus-interpreter (Arcturus) の構文解析に使用。当初は .y 内に意味解析まで直書きし、後にパーサと Traverser (評価器) を分離した。

使われ方

• C サブセット言語 cmm のコンパイラ cmm-pl0-compiler は lex/yacc ベースで、.l/.y を書き換えるだけで多くの言語機能拡張ができた。生成した構文木/命令列を pl0 スタックマシンへ落とす流れは stack-machine-codegen。
• 対比として、文法をホスト言語の関数で書く parser-combinator (nom 等, toy-llvm-compiler) がある。

関連

• operator-precedence-parsing、automata-formal-languages。