Previous Contents Next
Chapter 12 Lexer and parser generators (ocamllex, ocamlyacc)

この章では2つのプログラム生成器について説明する。: ocamllex, 正規表現の集合とそれに関連付けされた解析方法から字句解析器をつくる。ocamlyacc, 文法とそれに対応した意味解析方法から構文解析器を生成する。

これらのプログラムは周知のCプログラムの環境に見られる。 lexyaccコマンドと近い働きをする。 この章ではlexyaccの知識があるものと仮定して話を進める(ocamllexやocamlyaccの基本的な書き方やlex,yaccとの違いは説明するが、lexとyaccによるlexerやparserの書き方については説明しない。)。 lexyaccをよく知らない読者は``Compilers: principles, techniques, and tools'' by Aho, Sethi and Ullman (Addison-Wesley, 1986), もしくは ``Lex & Yacc'', by Levine, Mason and Brown (O'Reilly, 1992)を参照すること。.

12.1 Overview of ocamllex

ocamllexは正規表現から字句解析器をつくる。
        ocamllex lexer.mll
を実行することにより字句解析のためのMLコードlexer.mlをつくる。
Lexer buffersとはライブラリモジュールで定義された抽象データ型で、Lexing.from_channel, Lexing.from_stringLexing.from_function などの関数からchannel,文字列,読み込み関数などこれらに応じたデータからつくられる。

ocamlyaccにより作られたパーザと同時に使うと, tokenに属するものに対して意味解析を行う。. (これに関してはocamlyacc に.)

12.2 Syntax of lexer definitions

lexerのフォーマットの定義の仕方は以下の通り
{ header }
let ident = regexp ...
rule entrypoint =
  parse regexp { action }
      | ...
      | regexp { action }
and entrypoint =
  parse ...
and ...
{ trailer }
コメントはCamlと同様 (* and *)で行う.

12.2.1 Header and trailer
headerとtrailerには{}でくくり、任意のCamlのコードを書くことができる。headerに書かれたコードは出力ファイルの最初に書かれ、trailerに書いたコードは最後に書かれる。
12.2.2 Naming regular expressions

headerとエントリポイントの間には正規表現の略記を書くことができる。 let ident =  regexpと書くことにより、これ以下の identregexpに展開される。

12.2.3 Entry points

エントリポイントの名前はCamlの識別子として正しいものでなくてはならない。(小文字から始まること).

12.2.4 正規表現

lex中の正規表現はCamlの様な形式で記述する。
' char '
文字定数。Ocamlと同じ構文。指定した文字とマッチする。
_

(Underscore.) 任意の文字とマッチする。.

eof
入力の終りとマッチ。
Note:システムによってはユーザーからのインタラクティブな入力によりend-of-fileのあとにさらに文字列が続くことがありうる。しかし、ocamllexでは eofの後に他の文字列が続くような場合の正規表現への操作は正確には動作しない。

" string "
文字列定数。Ocamlの構文と同じ。対応する文字のならびとマッチする。
[ character-set ]
文字セットに含まれる任意の文字にマッチ。 Valid character sets are: single character constants ' c '; ranges of characters ' c1 ' - '  c2 ' (all characters between c1 and c2, inclusive); and the union of two or more character sets, denoted by concatenation.

[ ^ character-set ]
文字セットに含まれない任意の文字にマッチ。
regexp *
regexpにマッチする0文字以上の文字列にマッチ.

regexp +
regexpにマッチする1文字以上の任意の文字列にマッチ.

regexp ?
空文字か regexpにマッチ.

regexp1 |  regexp2
regexp1regexp2にマッチ。

regexp1  regexp2
regexp1にマッチする文字列とregexp2にマッチする文字列の結合にマッチ。.

( regexp )
regexpにマッチ。.

ident
先に定義された略記 let ident =  regexp にマッチ。.
優先順位は*+ が最も高く , 続いて ?, 次が結合, | となる。.

12.2.5 Actions

アクションは任意のCamlの表現でよい。現在のlexer bufferは識別子lexbufにバインドされている。lexbufの典型的な使い方としてはlexer bufferを操作する以下のようなライブラリモジュールと一緒に使う。
Lexing.lexeme lexbuf
マッチしたストリングを返す。

Lexing.lexeme_char lexbuf n
マッチした文字列のn番目の文字を返す。最初の文字を0とする。
Lexing.lexeme_start lexbuf
マッチした文字列の最初の入力テキストにおける絶対的な位置を返す。テキストの最初の文字を0とする。
Lexing.lexeme_end lexbuf
マッチした文字列の終りの入力テキストにおける絶対的な位置を返す。テキストの最初の文字を0とする。
entrypoint lexbuf
このエントリポイントのlexerを再帰的に呼び出す。同じ定義内の異なる名前のエントリポイントも呼び出してくれる。
12.2.6 Reserved identifiers

識別子が __ocaml_lex で始まるものは ocamllexで使用するため予約してあるのでこのような識別子は使ってはならない。

12.3 Overview of ocamlyacc

ocamlyaccコマンドはyaccのスタイルで記述された構文解析アクションで指定された文脈自由文法を作る。 例えば入力ファイルが grammar.mlyならば,
        ocamlyacc options grammar.mly
を実行することでパーザーgrammar.mlとインタフェースgrammar.mliが作られる。
生成されたモジュールはエントリポイント当たり一つの文法解析機能を与える。これらの文法解析関数はエントリポイントと同じになる。 このファンクションはlexical analyzerとlexer bufferを引数としてとり エントリポイントニ対応したsemantic attributeを返す。 lexical analyzerはocamllex により指定されたlexerにより作られる。 Lexer bufferはスタンダードライブラリLexingで定義された抽象データタイプである。トークンはocamlyaccにより作られたインタフェースgrammar.mliに定義されている具体的な型の値である。
12.4 Syntax of grammar definitions

文法定義は以下のフォーマットに従い作られる。
%{
  header
%}
  declarations
%%
  rules
%%
  trailer
コメントは``declarations'' と``rules''セクションではCの様に /**/ となり、。``header'' と ``trailer''のセクションでは (**)の間となる。

12.4.1 Header and trailer

header とtrailerはCamlのコードでそれぞれgrammar.mlの最初と最後に入れられる。headerでは構文解析に用いる補助関数の入ったファイルを開くためなどに使われる。またオプショナルであるのでなくてもよい。
12.4.2 Declarations

Declarations は1行につき一つで % で始まる行で与えられる.

%token symbol ...  symbol
Symbolを具体的な定数として終端記号として扱う。
%token < type >  symbol ...  symbol
型付きのトークンとして定義する。Symbolはこれらの型の具体的なコンストラクタとして与えられる。typeはCamlの型で、基本型か Modname.typenameのように完全に指定されてなければならない。 ヘッダでオープンされたモジュールの型であっても直接指定してはならないのはヘッダは.mlでは展開されるが.mliで展開されないためである。(type部分は両方に展開される。)

%start symbol ...  symbol
このSymbolを文法のエントリポイントとする。エントリポイントごとに同じ名前の関数が作られる。エントリポイントとして定義されていない非終端記号は関数が提供されない。スタートシンボル下のtypeで型を与えられなければならない。

%type < type >  symbol ...  symbol
与えられたシンボルに型を指定する。 スタートシンボルにはこれが必要である。その他の非終端記号にはこの型付けはしなくてもよい。これらの型は(-sオプションがなければ)Camlのコンパイラによってつけられるでしょう。typeはCamlの任意の型でなければならない。tokenの型のところと同じ。

%left symbol ...  symbol
%right symbol ...  symbol
%nonassoc symbol ...  symbol


与えられたシンボルの優先度、結合性の関連付けを行う。 同じラインにあるシンボルは同じ優先度。これらは %left%right%nonassoc のラインよりも前に定義されたシンボルよりも優先度が高い。 これらのシンボルは 左結合(%left), 右結合(%right), 結合なし (%nonassoc)と宣言される。 シンボルはたいていトークンだが rule内のprec規則により誘導された非終端記号でもよい。
12.4.3 Rules

ルール用のシンタックスはいつもどおり
nonterminal :
    symbol ... symbol { semantic-action }
  | ...
  | symbol ... symbol { semantic-action }
;
ルールは右側部分に%prec symbolを含むことができる。 このシンボルによりデフォルトの優先度と結合性を与えられたシンボルの優先度と結合性で上書きする。

semantic actionsは任意のCamlの表現でよく、それが任意の非終端記号に付属する手続きとして評価されます。 $1$2と書くことにより右側のシンボルにアクセスできます。

ルールには非同期点であるシンボルerrorを含んでいてもよい。(yaccと同じ)

ルールの途中でおこるような動作はサポートされていない。

非終端の記号はCamlのシンボルと同様でよいが' (single quote)で終わってはいけない。

12.4.4 Error handling

エラーからの回復は以下の通り。 パーザーがエラー状態(適用できるルールがない)に到達すると parse_error関数に "syntax error"が引数として適用され呼び出される。デフォルトでは parse_errorは何もせず何も返さない。このようにしてエラーから復帰を行う(以下を参照)。またユーザーはgrammarファイルのヘッダで parse_errorのカスタマイズができる。

またパーザーはアクションがParsing.Parse_error exceptionを起こしたときもエラー復帰モードになる。

エラー復帰モードに入るとパーザはそのトークンが読まれた可能性のあるところまでの状態をスタックから捨てる。次に3つの連続した受理されるトークン列が現れるまで入力から破棄する。どうにもならないときはParsing.Parse_error exceptionをraiseする。

エラー回復についてはyaccのドキュメントに詳しく掲載してある。

12.5 Options

ocamlyaccには以下のオプションがある。

-v
構文解析表と文法の曖昧な部分についての情報をgrammar.outputに吐く。

-bprefix
出力ファイルをデフォルトの名前の代わりに prefix.ml, prefix.mli, prefix.outputに指定。
12.6 A complete example

The all-time favorite: a desk calculator. This program reads arithmetic expressions on standard input, one per line, and prints their values. Here is the grammar definition:
        /* 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 }
        ;
Here is the definition for the corresponding lexer:
        (* 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 }
Here is the main program, that combines the parser with the lexer:
        (* 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
To compile everything, execute:
        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
12.7 Common errors

ocamllex: transition table overflow, automaton is too big


The deterministic automata generated by ocamllex are limited to at most 32767 transitions. The message above indicates that your lexer definition is too complex and overflows this limit. This is commonly caused by lexer definitions that have separate rules for each of the alphabetic keywords of the language, as in the following example.
rule token = parse
  "keyword1"   { KWD1 }
| "keyword2"   { KWD2 }
| ...
| "keyword100" { KWD100 }
| ['A'-'Z' 'a'-'z'] ['A'-'Z' 'a'-'z' '0'-'9' '_'] *
               { IDENT(Lexing.lexeme lexbuf) }
To keep the generated automata small, rewrite those definitions with only one general ``identifier'' rule, followed by a hashtable lookup to separate keywords from identifiers:
{ 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 }

Previous Contents Next