Chapter 12 |
Lexer and parser generators (ocamllex, ocamlyacc) |
|
この章では ocamllex と ocamlyacc の解説をします。ocamllex は、正規表現の集合と、それに対応するセマンティクスから字句解析器を生成し、ocamlyacc は文法と、それに対応するセマンティクスから構文解析器を生成します。
このプログラム生成ツールは、C 言語環境で有名な lex と yacc ととてもよく似ています。この章は lex と yacc の知識があることを前提としています。ocamllex と ocamlyacc に与えるソースの文法や lex と yacc との主な相違点などは解説しますが、lex と yacc での字句解析器や構文解析器の基本的な書き方は解説しません。lex と yacc をよく知らない方は、``Compilers: principles, techniques, and tools''(Aho, Sethi and Ullman (Addison-Wesley, 1986)) や ``Lex & Yacc''(Levine, Mason and Brown (O'Reilly, 1992)) などを参照してください。
12.1 |
Overview of ocamllex |
|
ocamllex は lex のように、正規表現の集合と、それに対応するセマンティクスから字句解析器を生成します。入力ファイルが lexer.mll であるとき、以下のようにして字句解析器の Caml コードファイル lexer.ml を生成することができます。
ocamllex lexer.mll
このファイルでは字句解析器の定義で、エントリーポイントあたり 1 つの関数が定義されています。それぞれの関数名はエントリーポイントの名前と同じです。それぞれの字句解析関数は字句解析バッファを引数に取り、それぞれ関連付けられたエントリーポイントの文法属性を返します。
字句解析バッファは標準ライブラリ Lexing モジュール内で絶対データ型 (abstract data type) として実装されています。Lexing.from_channel 、Lexing.from_string 、Lexing.from_function はそれぞれ入力チャンネル、文字列、読み込み関数を読んで、字句解析バッファを返します (Lexing モジュールの解説は 20 章にあります) 。
使用する際は ocamlyacc で生成されるパーザと結合して、構文解析器で定義されている型 token に属する値をセマンティクスに基づいて計算します (ocamlyacc については後述) 。
12.2 |
Syntax of lexer definitions |
|
字句解析の定義の記述法は以下の通りです。
{ header }
let ident = regexp ...
rule entrypoint =
parse regexp { action }
| ...
| regexp { action }
and entrypoint =
parse ...
and ...
{ trailer }
コメントは Caml と同じように (* と *) で区切られます。
ヘッダ(header) と trailer セクションには中カッコでくくって任意の Caml コードを入れることが出来ます。これらはどちらも省略可能です。存在すれば、header は出力ファイルの先頭に、trailer は出力ファイルの終端に置かれます。大抵、header セクションには action で必要な open
指示語を置きます。actions 内で使う補助関数を定義することもあります。
12.2.2 |
Naming regular expressions |
|
header と entry points のあいだで、頻繁に発生する正規表現に名前を与えることが出来ます。let ident = regexp のように書きます。今後、正規表現を書くところに regexp の代わりに識別子 ident を使うことが出来ます。
エントリーポイントの名前は Caml の値の名前 (小文字で始まる) として有効な識別子である必要があります。それぞれのエントリーポイントは型 Lexing.lexbuf の引数をとる Caml の関数となります。文字を Lexing.lexbuf から読み、rule にある正規表現にマッチさせます。その正規表現に対応する action が評価され、関数の結果として返されます。
先頭文字列にマッチする正規表現が複数ある場合は、"最大マッチ" する正規表現が適用され、先頭文字列を長くして最後までマッチする正規表現を選択します。それでもふるいきれないときは、rule のなかで先に出現したものが優先されます。
正規表現は lex と同じですが、より Caml らしい文法です。
- ' char '
-
文字定数。Objective Caml の文字定数と同じ文法です。その文字とマッチします。
- _
-
(アンダースコア) どんな文字とでもマッチします。
- eof
-
入力終端にマッチします。
警告: システムによっては対話式入力において、end-of-file のあとにさらに文字列が続く場合がありますが、ocamllex では eof の後に何かが続く正規表現を正しく扱うことは出来ません。
- " string "
-
文字列定数。Objective Caml の文字列定数と同じ文法です。文字列にマッチします。
- [ character-set ]
-
指定された文字集合に属する 1 文字とマッチします。有効な文字集合は、文字定数 1 つの ' c ' 、文字幅 ' c1 ' - ' c2 ' (c1 と c2 自身を含むその間の文字すべて) 、または 2 つ以上の文字集合を結合したもののどれかです。
- [ ^ character-set ]
-
指定された文字集合に属さない 1 文字とマッチします。
- regexp *
-
(反復) regexp とマッチする文字列が 0 個以上連なった文字列にマッチします。
- regexp +
-
(厳しい反復) regexp とマッチする文字列が 1 個以上連なった文字列にマッチします。
- regexp ?
-
(オプション) 空文字列か、regexp とマッチする文字列にマッチします。
- regexp1 | regexp2
-
(どちらか) regexp1 にマッチする文字列か、 regexp2 にマッチする文字列のどちらかにマッチします。
- regexp1 regexp2
-
(結合) regexp1 にマッチする文字列のあとに regexp2 にマッチする文字列を結合した文字列にマッチします。
- ( regexp )
-
regexp と同じです。
- ident
-
前もって let ident = regexp で定義された ident に割り当てられている正規表現になります。
演算子の優先順位は、* と + が最優先、次に ? 、次に結合、最後に | になります。
action は Caml の任意な式です。これらの式は lexbuf 識別子に現在の字句解析バッファが割り当てられた環境で評価されます。lexbuf の主な利用法を、Lexing 標準ライブラリモジュールの字句解析バッファ処理関数と関連付けながら以下に示します。
-
Lexing.lexeme lexbuf
-
マッチした文字列を返します。
- Lexing.lexeme_char lexbuf n
-
マッチした文字列の n 番目の文字を返します。最初の文字は n = 0 になります。
- Lexing.lexeme_start lexbuf
-
マッチした文字列の先頭文字が入力文字列全体において何番目の文字であるかを返します。入力文字列の先頭は 0 です。
- Lexing.lexeme_end lexbuf
-
マッチした文字列の終端文字が入力文字列全体において何番目の文字であるかを返します。入力文字列の先頭は 0 です。
- entrypoint lexbuf
-
(entrypoint には、同じ字句解析器の定義内にある別のエントリーポイント名が入ります) 字句解析器の指定されたエントリーポイントを再帰的に呼びます。入れ子のコメントなどの字句解析に便利です。
__ocaml_lex で始まるすべての識別子は ocamllex が予約しています。プログラム中にそのような識別子は使用しないでください。
12.3 |
Overview of ocamlyacc |
|
ocamlyacc コマンドは yacc のように、文脈自由文法の記述とそれに対応するセマンティクスから構文解析器を生成します。入力ファイルが grammar.mly であるとき、以下のようにして構文解析器の Caml コードファイル grammar.ml とそのインターフェイスファイル grammar.mli を生成することができます。
ocamlyacc options grammar.mly
生成されたモジュールには文法で、エントリーポイントあたり 1 つの関数が定義されています。それぞれの関数名はエントリーポイントの名前と同じです。構文解析関数は字句解析器と字句解析バッファをとり、対応するエントリーポイントの意味属性を返します。字句解析関数は普通、字句解析記述から ocamllex プログラムによって作られたものを用います。字句解析バッファは標準ライブラリ Lexing モジュール内で絶対データ型 (abstract data type) として実装されています。トークンは ocamlyacc が生成するインターフェイスファイル grammar.mli 内で定義されている型 token の値です。
12.4 |
Syntax of grammar definitions |
|
文法定義は以下のようなフォーマットになります。
%{
header
%}
declarations
%%
rules
%%
trailer
コメントは declarations と rules セクションでは C のように /*
と */
でくくり、header と trailer セクションでは Caml のように (*
と *)
でくくります。
header と trailer セクションの Caml コードは grammar.ml ファイルにそのままコピーされます。どちらのセクションも省略できます。header は出力ファイルの先頭に置かれます。大抵 rule の action で必要な open 指示語を置き、また action 内で必要な補助関数を置きます。trailer は出力ファイルの終端に置かれます。
宣言は行単位で与えます。すべて %
で始めます。
- %token symbol ... symbol
-
指定されたシンボルをトークン (終端シンボル) として定義します。これらのシンボルは型 token に定数コンストラクタとして追加されます。
- %token < type > symbol ... symbol
-
指定されたシンボルを、指定された型の属性を持つトークンとして定義します。これらのシンボルは、指定された型を引数に取るコンストラクタとして型 token に追加されます。type は Caml の任意な型を置くことが出来ます。ただし全ての型のコンストラクタ名は、built-in 型を除いて Modname.typename のように全て指定しなければなりません。たとえ header セクションに open 指示語があっても (Modname.typename) です。これは header が .ml 出力ファイルにのみコピーされ、.mli 出力ファイルにはコピーされない一方、
%token
定義の type 部分は両方にコピーされるためです。
- %start symbol ... symbol
-
指定されたシンボルを文法のエントリーポイントとして定義します。それぞれのエントリーポイントは、同名の構文解析関数として出力モジュールに定義されます。エントリーポイントとして定義されない非終端記号は構文解析関数を持ちません。初期シンボルは以下の
%type
指示語を用いて型を指定する必要があります。
- %type < type > symbol ... symbol
-
指定されたシンボルにセマンティクス属性の型を割り当てます。これは初期シンボルだけの命令です。他の非終端シンボルに手動で型指定する必要はありません。これらの型は出力ファイルを実行する際 Objective Caml コンパイラによって推論されます (ただし
-s
オプションを指定しない限り) 。type の部分は Caml の任意な型を置くことが出来ます。ただし %token で説明したように、全ての型のコンストラクタ名は全て指定しなければなりません。
- %left symbol ... symbol
-
- %right symbol ... symbol
-
- %nonassoc symbol ... symbol
指定されたシンボルの優先度や関連性を指定します。同じ行にあるシンボルはすべて同じ優先度になります。この行は、すでに現れていた %left
、%right
、%nonassoc
行のシンボルより高い優先度を、この行より後に現れた %left
、%right
、%nonassoc
行のシンボルより低い優先度を持ちます。シンボルは %left
では左に、%right
では右に関連付けられます。%nonassoc
では関連付けられません。主にシンボルはトークンですが、ダミーの非終端記号を指定することも出来ます。これは rules 内において %prec
指示語を用いることで指定できます。
rules の文法は通常このようになります。
nonterminal :
symbol ... symbol { semantic-action }
| ...
| symbol ... symbol { semantic-action }
;
rules では %prec
symbol 指示語を置くことで、デフォルトの優先度と関連性を、指定されたシンボルのものに上書き出来ます。
semantic-action は任意の Caml の式です。この式は定義される非終端記号に対応するセマンティクス属性を生成するために評価されます。semantic-action ではシンボルのセマンティクス属性に $
(数字) でアクセス出来ます。$1
で第一シンボル (もっとも左) の属性に、$2
で第二シンボルに、という具合です。
rules には yacc と同じように、再同期点を指し示す特殊シンボル error を入れることが出来ます。
rules の間で発生する actions はサポートされていません。
非終端シンボルは通常の Caml シンボルと同じですが、最後の文字に ' (シングルクォート) を用いることは出来ません。
エラー回復は次のようにサポートされます。構文解析器がエラー状態に至ると (どの文法も適用出来なくなると) parse_error という名の関数を、"syntax error" という文字列を引数にして呼び出します。デフォルトの parse_error 関数は何もせずに帰り、それからエラー回復が始まります (後述) 。parse_error 関数は文法ファイルの header セクションで自由に定義することが出来ます。
いずれかの文法 action で例外 Parsing.Parse_error を発生させることでも、構文解析器をエラー回復モードに入らせることが出来ます。
エラー回復モードでは、構文解析器はエラートークンをシフト出来るようになるまでスタックから状態を捨てていきます。その後、連続する 3 つのトークンが受け入れ可能になるまで入力からトークンを捨てていき、これらの先頭トークンから処理を始めます。エラートークンをシフトできるような状態が見つからなかったら、構文解析器は例外 Parsing.Parse_error を発生して異常終了します。
エラー回復の使い方の詳細や手引きは yacc のドキュメントを参照してください。
ocamlyacc コマンドには以下のオプションを指定できます。
-
-v
-
構文解析テーブルの説明や文法のあいまいさに起因する衝突の報告を生成します。説明は grammar.output ファイルに書かれます。
- -bprefix
-
デフォルトの名前規則の代わりに、出力ファイル名を prefix.ml 、prefix.mli 、prefix.output とします。
ocamlyacc に生成された構文解析器は、環境変数 OCAMLRUNPARAM (詳細は 10.2 を参照) に p オプションを指定することで実行時にデバッグ出来ます。これによって構文解析を実行するプッシュダウンオートマトンの挙動 (tokens shifted や rules reduced など) を追跡表示できます。表示されるルール番号や状態番号は、ocamlyacc -v で生成される grammar.output ファイルを見ることでわかります。
よくある例 (The all-time favorite) 、卓上計算機です。このプログラムは標準入力から数式を行単位で読み、その値を表示します。文法定義は以下の通りです。
/* File parser.mly */
%token <int> INT
%token PLUS MINUS TIMES DIV
%token LPAREN RPAREN
%token EOL
%left PLUS MINUS /* lowest precedence */
%left TIMES DIV /* medium precedence */
%nonassoc UMINUS /* highest precedence */
%start main /* the entry point */
%type <int> main
%%
main:
expr EOL { $1 }
;
expr:
INT { $1 }
| LPAREN expr RPAREN { $2 }
| expr PLUS expr { $1 + $3 }
| expr MINUS expr { $1 - $3 }
| expr TIMES expr { $1 * $3 }
| expr DIV expr { $1 / $3 }
| MINUS expr %prec UMINUS { - $2 }
;
対応する字句解析器の定義は以下の通りです。
(* File lexer.mll *)
{
open Parser (* The type token is defined in parser.mli *)
exception Eof
}
rule token = parse
[' ' '\t'] { token lexbuf } (* skip blanks *)
| ['\n' ] { EOL }
| ['0'-'9']+ { INT(int_of_string(Lexing.lexeme lexbuf)) }
| '+' { PLUS }
| '-' { MINUS }
| '*' { TIMES }
| '/' { DIV }
| '(' { LPAREN }
| ')' { RPAREN }
| eof { raise Eof }
構文解析器と字句解析器を合体させるプログラム本体は以下の通りです。
(* File calc.ml *)
let _ =
try
let lexbuf = Lexing.from_channel stdin in
while true do
let result = Parser.main Lexer.token lexbuf in
print_int result; print_newline(); flush stdout
done
with Lexer.Eof ->
exit 0
すべてコンパイルして実行するには以下のコマンドを実行してください。
ocamllex lexer.mll # generates lexer.ml
ocamlyacc parser.mly # generates parser.ml and parser.mli
ocamlc -c parser.mli
ocamlc -c lexer.ml
ocamlc -c parser.ml
ocamlc -c calc.ml
ocamlc -o calc lexer.cmo parser.cmo calc.cmo
- ocamllex: transition table overflow, automaton is too big
ocamllex に生成される決定性オートマトンは最大で 32767 遷移に制限されています。上記のメッセージは字句解析器の定義が複雑すぎてこの制限を越えたことを示しています。言語の基本キーワードをそれぞれ別のルールに持つ字句解析器の定義だと発生しやすいです。以下に例を示します。
rule token = parse
"keyword1" { KWD1 }
| "keyword2" { KWD2 }
| ...
| "keyword100" { KWD100 }
| ['A'-'Z' 'a'-'z'] ['A'-'Z' 'a'-'z' '0'-'9' '_'] *
{ IDENT(Lexing.lexeme lexbuf) }
これらの定義を一般的な「識別子」ルールに書き換えることで生成されるオートマトンを小さくすることが出来ます。このルールではキーワードのハッシュテーブルから識別子を探します。
{ let keyword_table = Hashtbl.create 53
let _ =
List.iter (fun (kwd, tok) -> Hashtbl.add keyword_table kwd tok)
[ "keyword1", KWD1;
"keyword2", KWD2; ...
"keyword100", KWD100 ]
}
rule token = parse
['A'-'Z' 'a'-'z'] ['A'-'Z' 'a'-'z' '0'-'9' '_'] *
{ let id = Lexing.lexeme lexbuf in
try
Hashtbl.find keyword_table s
with Not_found ->
IDENT s }