IoPLMaterials

各モジュールの機能 (2): `Parser`モジュール，`Lexer`モジュール

この節ではParserモジュールとLexerモジュールの機能とparser.mlyとlexer.mllの構成について説明する．字句解析と構文解析を行うための具体的なアルゴリズムは講義の終盤で扱うが，ここではツールを使って（具体的なアルゴリズムがわからなくても）とりあえずこれらのモジュールを作る方法を説明する．

この節はparser.mlyとlexer.mllとを見ながら読むと良い．

ParserとLexerはそれぞれ構文解析と字句解析を行うモジュールである． Parserモジュールは Menhir というツールを用いてparser.mlyというファイルから，Lexerモジュールは ocamllex というツールを用いて lexer.mllというファイルからそれぞれ自動生成される．

Menhir は LR(1)構文解析 (LR(1) parsing) という手法を用いて，BNFっぽく書かれた文法定義（ここではparser.mlyに書かれている文法定義）から，構文解析を行う OCaml のプログラム（ここではparser.mlとparser.mli）を自動生成する．また，ocamllex は 正則表現 (regular expression) を使って書かれたトークンの定義（ここではlexer.mll）から，字句解析を行う OCaml のプログラム（ここではlexer.ml）を自動生成する．生成されたプログラムがどのように字句解析や構文解析を行うかはこの講義の後半で触れる．そのような仕組みの部分を抜きにして，ここでは.mlyファイルや.mll ファイルの書き方を説明する．

`.mly`ファイルの書き方

拡張子.mly文法定義ファイルは一般に，以下のように4つの部分から構成される．

{
  ヘッダ部
}
  宣言部
%%
  文法規則部
%%
  トレイラ部

ヘッダ部とトレイラ部は OCaml のプログラムを書く部分で，Menhir が生成する parser.mlの，それぞれ先頭・末尾にそのまま埋め込まれる．ヘッダ部でParserモジュールの中だけで使用する補助関数を定義したり，トレイラ部でParserモジュールが初めて読み込まれたときに実行すべきプログラムを書いたりする，というように使う．
宣言部はトークン(終端記号)や，開始記号，優先度などの宣言を行う．parser.mly では演習を通して，開始記号とトークンの宣言のみを使用する．
文法規則部には文法記述とアクションを記述する．

それでは parser.mly を見てみよう．

%{
open Syntax
%}

%token LPAREN RPAREN SEMISEMI
%token PLUS MULT LT
%token IF THEN ELSE TRUE FALSE

%token <int> INTV
%token <Syntax.id> ID

%start toplevel
%type <Syntax.program> toplevel
%%

toplevel :
    e=Expr SEMISEMI { Exp e }

Expr :
    e=IfExpr { e }
  | e=LTExpr { e }

LTExpr :
    l=PExpr LT r=PExpr { BinOp (Lt, l, r) }
  | e=PExpr { e }

PExpr :
    l=PExpr PLUS r=MExpr { BinOp (Plus, l, r) }
  | e=MExpr { e }

MExpr :
    l=MExpr MULT r=AExpr { BinOp (Mult, l, r) }
  | e=AExpr { e }

AExpr :
    i=INTV { ILit i }
  | TRUE   { BLit true }
  | FALSE  { BLit false }
  | i=ID   { Var i }
  | LPAREN e=Expr RPAREN { e }

IfExpr :
    IF c=Expr THEN t=Expr ELSE e=Expr { IfExp (c, t, e) }

この文法定義ファイルではトレイラは空になっていて，その前の%%は省略されている．

ヘッダ部

ヘッダにある open Syntax 宣言はモジュールSyntax内で定義されているコンストラクタや型の名前を，Syntax.というプレフィクス無しで使うという OCaml の構文である．^{openについての注}（これがないと，例えばコンストラクタVarを参照するときにSyntax.Varと書かなくてはならない．）

属性を持たないトークンの宣言

%token <トークン名>は，属性 (attribute) を持たないトークンの宣言である．属性とは，トークンに関連付けられた値のことである．parser.mly中では

開き括弧 ( に対応する LPAREN
閉じ括弧 ) に対応する RPAREN
入力の終了を示す ;; に対応する SEMISEMI
プリミティブな演算子 (+, *, <) にそれぞれ対応するトークン PLUS, MULT, LT
予約語if, then, else, true, false にそれぞれ対応するトークン

が宣言されている．(parser.mlyに現れる構文木のコンストラクタ Plus などとの区別に注意すること．トークン名は全て英大文字としている．) %tokenで宣言されたトークン名はMenhirの出力する parser.ml 中で，ヴァリアント型として定義されている token 型の(引数なし)コンストラクタになる．字句解析プログラムは文字列を読み込んで，この型の値(の列)を出力することになる．

属性を持つトークンの宣言

%token <型> <トークン名> は，属性つきのトークン宣言である．数値のためのトークン INTV（属性はその数値情報なので int 型）と変数のための ID（属性は識別子を表す Syntax.id 型^{Syntax.についての注}）を宣言している．この宣言で宣言されたトークン名は parser.ml 中で，<型>型の値を引数とする token 型のコンストラクタになる．

開始記号の宣言

%start <開始記号名> で(一つ以上の)開始記号の名前を指定する．Menhir が生成する parser.ml ファイルでは，同名の関数が構文解析を行うためのメイン関数として宣言される．ここでは toplevel という名前を宣言しているので，cui.ml では Parser.toplevel という関数を使用して構文解析をしている．開始記号の名前は，次の %type宣言でも宣言されていなくてはならない．

非終端記号の型の宣言

%type <型> <名前> は名前の属性を指定する宣言である，toplevel はひとつのプログラムの抽象構文木を表すので属性はSyntax.program 型となっている．

文法規則の記述

Menhir においては，文法規則は

<非終端記号名>:
  <変数名>=<記号名> ... <変数名>=<記号名>
  { <還元時アクション> }
| <変数名>=<記号名> ... <変数名>=<記号名>
  { <還元時アクション> }

のように記述する．<記号名>の場所にはそれぞれ非終端記号か終端記号を書くことができる．<変数名>=の部分は省略してもよい．<還元時アクション>の場所には OCaml の式を記述する．

構文解析器は，開始記号から始めて，与えられたトークン列を生成するために適用すべき規則を適切に発見し，それぞれの規則の還元時アクションを評価して，評価結果を規則の左辺の非終端記号の属性とすることで，開始記号の属性を計算する．と言われてもよく分からないと思うので，parser.mlyの文法定義を例にとって説明する．この文法定義から生成される構文解析器にTRUE SEMISEMIというトークン列が与えられたとしよう．（このトークン列はtrue;;という文字列をlexer.mllから生成される字句解析器に与えることで生成される．）このトークン列は開始記号toplevelから始めて以下のように規則を適用すると得られることが分かる．（ちなみに，なぜこのような順番で規則を適用すべきと分かるのか，が構文解析アルゴリズムの大きなテーマである．構文解析アルゴリズムについては講義の後半で扱うので，それまでは何らかの方法でこれが分かるのだと流してほしい．）

--（規則 toplevel: Expr SEMISEMI を用いて）-->
_Expr_ SEMISEMI
--（規則 Expr: LTExpr を用いて）-->
_LTExpr_ SEMISEMI
--（規則 LTExpr: PExpr を用いて）-->
_PExpr_ SEMISEMI
--（規則 PExpr: MExpr を用いて）-->
_MExpr_ SEMISEMI
--（規則 MExpr: AExpr を用いて）-->
_AExpr_ SEMISEMI
--（規則 AExpr: TRUE を用いて）-->
TRUE SEMISEMI

各ステップで規則が適用された非終端記号の両端に_を付した．各ステップで用いられた規則を確認してほしい．

構文解析器は，この導出列を遡りながら，還元時アクションを評価し，各規則の左辺にある非終端記号の属性を計算する．例えば，

_AExpr_ SEMISEMI
--（規則 AExpr: TRUE を用いて）-->
TRUE SEMISEMI

の規則が適用されている場所では，左辺の非終端記号AExprの属性が還元時アクションBLit trueの評価結果（すなわち，BLit trueという値）となる．ここで計算された属性は，その一つ手前の導出

_MExpr_ SEMISEMI
--（規則 MExpr: AExpr を用いて）-->
_AExpr_ SEMISEMI

でMExprの属性を計算するのに使われる．ここでparser.mlyの対応する規則の右辺はe=AExprとなっているが，これは先程計算したAExprの属性をeという名前で還元時アクションの中で参照できることを表している．ここでは還元時アクションはeなので，MExprの属性はe，すなわちAExprの属性であるBLit trueとなる．これを繰り返すと，開始記号toplevelの属性がExp (BLit true)と計算され，これがトークン列TRUE SEMISEMIに対する構文解析器の出力となる．

openについて: openはモジュール内の名前に容易にアクセスすることを可能にするが，外のモジュールで定義されている名前との衝突も起きやすくするという諸刃の剣である．

ヘッダ部の open のスコープについてヘッダ部の open 宣言はトークン宣言部分では有効ではないという Menhir の決まりがあるので，属性を持つトークンの型を宣言する箇所では Syntax. をつけることが必要である．

parser.mlyの文法規則が，MiniML1のシンタックスの箇所で述べた結合の強さ，左結合などを実現していることを確かめてもらいたい．

`.mll`ファイルの書き方

さて，この構文解析器への入力となるトークン列を生成するのが字句解析器である．より正確には，字句解析器は文字の列を受け取って，その文字列をトークン列に変換する関数である．この関数のアルゴリズムの実装には，文字をアクションとする有限状態オートマトンを用いることが多い．ただし，必要な有限状態オートマトンとその実行を一から実装するのは大変なので，どの文字列をどのトークンに対応付けるべきかを記述したファイルから，有限状態オートマトンを用いて字句解析を行うプログラムを自動生成する lex や flex と呼ばれるツールを使うことが多い．本講義では実装言語として OCaml を用いる関係上，OCaml から使うのに便利な ocamllex と呼ばれるツールを用いることにする．

ocamllex は正則表現を使ってどのような文字列からどのようなトークンを生成すべきかを指定する．（正則表現は lex や flex においても同様に用いられる．）この指定は拡張子 .mll を持つファイルに記述する．今回用いる lexer.mllを見てみよう．

{
let reservedWords = [
  (* Keywords *)
  ("else", Parser.ELSE);
  ("false", Parser.FALSE);
  ("if", Parser.IF);
  ("then", Parser.THEN);
  ("true", Parser.TRUE);
]
}

rule main = parse
  (* ignore spacing and newline characters *)
  [' ' '\009' '\012' '\n']+     { main lexbuf }

| "-"? ['0'-'9']+
    { Parser.INTV (int_of_string (Lexing.lexeme lexbuf)) }

| "(" { Parser.LPAREN }
| ")" { Parser.RPAREN }
| ";;" { Parser.SEMISEMI }
| "+" { Parser.PLUS }
| "*" { Parser.MULT }
| "<" { Parser.LT }

| ['a'-'z'] ['a'-'z' '0'-'9' '_' '\'']*
    { let id = Lexing.lexeme lexbuf in
      try
        List.assoc id reservedWords
      with
      _ -> Parser.ID id
     }
| eof { exit 0 }

.mllファイルは以下の形をしている．

{ <ヘッダ部> }

let <名前> = <正則表現>
...

rule <エントリポイント名> =
  parse <正則表現> { <アクション> }
  | <正則表現> { <アクション> }
  |   ...
and <エントリポイント名> =
  parse ...
and ...
{ <トレイラ部> }

ヘッダ・トレイラ部には，OCaml のプログラムを書くことができる．このプログラムは，ocamllex が生成する lexer.ml ファイルの先頭・末尾に埋め込まれる．次の let を使った定義部は，よく使う正則表現に名前をつけるための部分で，lexer.mll では何も定義されていない．続く部分がエントリポイント，つまり字句解析の規則の定義で，同名の関数が ocamllex によって生成される．規則としては正則表現とそれにマッチした際のアクションを(OCaml式で)記述する．アクションは，基本的には(parser.mly で宣言された)トークン(Parser.token 型)を返すような式を記述する．また，字句解析に使用する文字列バッファが lexbuf という名前で使えるが，通常は以下の使用法でしか使われない．

Lexing.lexeme lexbuf で，正則表現にマッチした文字列を取り出す．
Lexing.lexeme_char lexbuf n で，マッチした文字列の n 番目の文字を取り出す．
Lexing.lexeme_start lexbuf で，マッチした文字列の先頭が入力文字列全体でどこに位置するかを返す．末尾の位置は Lexing.lexeme_end lexbuf で知ることができる．
<エントリポイント> lexbuf で，<エントリポイント> で定義された字句解析関数を呼び出す．

具体的に lexer.mllを見てみよう．ヘッダ部では，予約語の文字列と，それに対応するトークンの連想リストである，reservedWords を定義している．後でみるように，List.assoc関数を使って，文字列からトークンを取り出すことができる．

エントリポイント定義部分では，main という(唯一の)エントリポイントが定義されている．最初の正則表現は空白やタブなど文字の列にマッチする．これらは MiniML では区切り文字として無視するため，トークンは生成せず，後続の文字列から次のトークンを求めるために main lexbuf を呼び出している．次は，数字の並びにマッチし，int_of_string を使ってマッチした文字列をint 型に直して，トークン INTV (属性は int 型)を返す．続いているのは，記号に関する定義である．次は識別子のための正則表現で，英小文字で始まる名前か，演算記号にマッチする．アクション部では，マッチした文字列が予約語に含まれていれば，予約語のトークンを，そうでなければ(例外Not_found が発生した場合は) ID トークンを返す．最後の eof はファイルの末尾にマッチする特殊なパターンである．ファイルの最後に到達したらexit するようにしている．

なお，この部分は，今後もあまり変更が必要がないので，正則表現を記述するための表現についてはあまり触れていない．興味のあるものは lex を解説した本やOCamlマニュアルを参照すること．

Exercise 3.2.1 [必修]

MiniML1 インタプリタのプログラムをコンパイル・実行し，インタプリタの動作を確かめよ．大域環境として i, v, x の値のみが定義されているが，ii が 2，iii が 3，iv が 4 となるようにプログラムを変更して，動作を確かめよ．例えば，iv + iii * iiなどが正しく評価されるかを試してみよ．

Exercise 3.2.2 [**]

このインタプリタは文法にあわない入力を与えたり，束縛されていない変数を参照しようとすると，プログラムの実行が終了してしまう．このような入力を与えた場合，適宜メッセージを出力して，インタプリタプロンプトに戻るように改造せよ．

Exercise 3.2.3 [*]

論理値演算のための二項演算子 &&, || を追加せよ．

Exercise 3.2.4 [**]

lexer.mllを改造し，(*と*)で囲まれたコメントを読み飛ばすようにせよ．なお，OCamlのコメントは入れ子にできることに注意せよ．ocamllex のドキュメントを読む必要があるかもしれない．（ヒント1: (*と*)が正しく入れ子になっている語の集合は正則言語ではないので，正則表現を工夫するだけで頑張るのは無理．）（ヒント2：commentという再帰的なルールをlexer.mllに新しく定義するとよい．）

This site is open source. Improve this page.