ocamllex lexer.mll

{ header }
let ident = regexp ...
rule entrypoint =
  parse regexp { action }
      | ...
      | regexp { action }
and entrypoint =
  parse ...
and ...
{ trailer }

' char '

文字定数。Objective Caml の文字定数と同じ文法です。その文字とマッチします。

_

(アンダースコア) どんな文字とでもマッチします。

eof

入力終端にマッチします。
警告: システムによっては対話式入力において、end-of-file のあとにさらに文字列が続く場合がありますが、ocamllex では eof の後に何かが続く正規表現を正しく扱うことは出来ません。

" string "

文字列定数。Objective Caml の文字列定数と同じ文法です。文字列にマッチします。

[ character-set ]

指定された文字集合に属する 1 文字とマッチします。有効な文字集合は、文字定数 1 つの ' c ' 、文字幅 ' c₁ ' - '  c₂ ' (c₁ と c₂ 自身を含むその間の文字すべて) 、または 2 つ以上の文字集合を結合したもののどれかです。

[ ^ character-set ]

指定された文字集合に属さない 1 文字とマッチします。

regexp *

(反復) regexp とマッチする文字列が 0 個以上連なった文字列にマッチします。

regexp +

(厳しい反復) regexp とマッチする文字列が 1 個以上連なった文字列にマッチします。

regexp ?

(オプション) 空文字列か、regexp とマッチする文字列にマッチします。

regexp₁ |  regexp₂

(どちらか) regexp₁ にマッチする文字列か、 regexp₂ にマッチする文字列のどちらかにマッチします。

regexp₁  regexp₂

(結合) regexp₁ にマッチする文字列のあとに regexp₂ にマッチする文字列を結合した文字列にマッチします。

( regexp )

regexp と同じです。

ident

前もって let ident =  regexp で定義された ident に割り当てられている正規表現になります。

Lexing.lexeme lexbuf

マッチした文字列を返します。

Lexing.lexeme_char lexbuf n

マッチした文字列の n 番目の文字を返します。最初の文字は n = 0 になります。

Lexing.lexeme_start lexbuf

マッチした文字列の先頭文字が入力文字列全体において何番目の文字であるかを返します。入力文字列の先頭は 0 です。

Lexing.lexeme_end lexbuf

マッチした文字列の終端文字が入力文字列全体において何番目の文字であるかを返します。入力文字列の先頭は 0 です。

entrypoint lexbuf

(entrypoint には、同じ字句解析器の定義内にある別のエントリーポイント名が入ります) 字句解析器の指定されたエントリーポイントを再帰的に呼びます。入れ子のコメントなどの字句解析に便利です。

        ocamlyacc options grammar.mly

%{
  header
%}
  declarations
%%
  rules
%%
  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 指示語を用いることで指定できます。

nonterminal :
    symbol ... symbol { semantic-action }
  | ...
  | symbol ... symbol { semantic-action }
;

-v

構文解析テーブルの説明や文法のあいまいさに起因する衝突の報告を生成します。説明は grammar.output ファイルに書かれます。

-bprefix

デフォルトの名前規則の代わりに、出力ファイル名を prefix.ml 、prefix.mli 、prefix.output とします。

        /* 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 }