字句解析と構文解析

7
字句解析と構文解析
この章から 「SML で プログラミング言語 を実装 (プログラミング) する」という目標で議論を進める．一般
に言語を解釈するためには最初に，
1. 字句解析
2. 構文解析
を行わなければならない．その後，指定された計算機のコード (機械語または中間言語) に変換する処理系が コ
ンパイラ (compiler) であり，そのまま解釈実行する処理系が インタプリタ (interpreter) である．本章では，こ
の 2 つの段階を SML で書いた例を紹介する．最初に紹介する言語は，簡単に以下の文法 (syntax) (BNF,backus
normal form で定義) としよう．例えば，1 + 2; や，let x be 2 - 1 in x; と言ったプログラムが許される．
プログラム
::=
式 ’;’
式
|
::=
let 識別子 be 式 in 式 ’;’
項
式 ’+’ 項
項
|
|
::=
|
|
基底式
7.1
::=
|
式 ’-’ 項
基底式
項 ’*’ 基底式
項 ’/’ 基底式
整数
識別子
字句解析
プログラム (通常，印刷可能文字 (printable characters) をトークン (tokens)1 に切り分ける処理を字句解析 (lexical
analizer) という．以下のプログラム，
fun twice x=x*2;
を fun，twice，x，=，x，*，2，; のように意味のある単位に切り分ける処理を示す．この例では fun は 予約語
(reserved word) または識別子 (identifier)，twice，x は識別子または変数，=，* は記号 (symbol)，2 は整数 な
どである．トークンの（各言語特有の）組合せについては，次段階の「構文解析」で詳しく行う．
プログラムの最初として上のトークンを分類するユーザ定義型を定義しよう．ユーザ定義型とは，abstype で
紹介したように「∼または∼」の形をした型定義である．構成子 datatype を使う．
プログラム 56: データ型
token
datatype token = LET | BE | ID of string | NUM of int | ONE of string | EOF | IN
1
正確には，字句とトークンは異なった概念であるが，本書では同一に扱う．
79
7. 字句解析と構文解析
80
プログラム 57: 関数
gettoken(1)
fun read ISTREAM = case TextIO.input1 ISTREAM of SOME x => String.str x
| NONE
=> ""
(* 整数の認識 *)
and integer ISTREAM i =
let val c = TextIO.lookahead ISTREAM in
case c of NONE => 0
|
SOME v => (if (Char.isDigit v) then
integer ISTREAM (10*i+ord(String.sub(read ISTREAM,0))-ord(#"0"))
else i)
end
(* 識別子の認識 *)
and identifier ISTREAM id =
let val c = TextIO.lookahead ISTREAM in
case c of NONE => ""
| SOME v => if (Char.isLower v) orelse (Char.isUpper v)
orelse (Char.isDigit v) orelse v = #"_" then
identifier ISTREAM (id^(read ISTREAM))
else id
end
(* 字句解析本体 *)
and native_token ISTREAM =
let val c = TextIO.lookahead ISTREAM in
case c of NONE => EOF
| SOME v =>
if (Char.isLower v) orelse (Char.isUpper v) then
let val id = identifier ISTREAM "" in
case id of
"let" => LET
| "be" => BE
| "in" => IN
| _
=> ID (id)
end
else if (Char.isDigit v) then NUM (integer ISTREAM 0)
else ONE (read ISTREAM)
end
(* ホワイトスペースの読飛ばし含む *)
and gettoken ISTREAM =
let val token = native_token ISTREAM in
case token of
ONE " " => gettoken ISTREAM
| ONE "\t"=> gettoken ISTREAM
| ONE "\n"=> gettoken ISTREAM
| _ => token
end
7.1. 字句解析
81
この token 型は，引数をもたない LET，BE，EOF，IN か，string，int， char の各型の値を引数としてもつ
ID，NUM，ONE かのいずれかの値を持つことを示す．引数をもつ値は ID("fun")，Num(1001)，ONE(#";") のよ
うに表現する．要は，プログラムをこの token 型の値に分解すればよい．
一般に datatype 構成子は以下のように定義する．
プログラム 58: datatype 構成子
datatype 名前 = 構成子 1 of 型 1 | · · · | 構成子 n of 型 n
構成子 i of 型 i で値 構成子 i (型 i の値) を表現することができる．また datatype の定義で 構成子 i of 型 i の
代りに 構成子 i と宣言することもできる．その場合は 構成子 i で値を示す．
字句解析を行う関数を gettoken としよう．ここで関数 TextIO.lookahead は，引数で指定した入力ストリー
ム ISTREAM から「次に取り出されるだろう文字を，実際には取り出さずに覗く」機能を果たす．この処理のこと
を 先読み (look ahead) という．TextIO.lookahead は，返値の型として ’a option 型を用いる．この型は，構
成子 NONE か SOME(’a 型の値) を返す．関数 TextIO.lookahead のように，値を返す場合と返さない場合がある
関数にしばしば用いられる．
構成子 datatype によるユーザ定義型は「∼または∼」というバリアント型 (variant types) であった (C 言語
での union 型または列挙型に相当)．これに対して レコード型 (record type) は，
「∼かつ∼」という形をした型
である (後述)．バリアント型は同時に一つの値しか示すことができないので，処理する場合には「場合分け」が
必要である．case · · · of · · · 式を使う．以下の形をしている．
プログラム 59: case · · · of · · ·
case 式 of
パターン 1 => 式 1
パターン 2 => 式 2
···
パターン n => 式 n
関数 Char.isLower は引数として受渡される文字が小文字かどうか，関数 Char.isUpper は引数として受渡され
る文字が大文字かどうかを調べる関数である．同様に Char.isDigit は引数として受渡される文字が数字かどう
かを調べる関数である．
関数 TextIO.input1 入力ストリーム によって「入力ストリーム」から 1 文字の文字列を取り出す．返値は，
lookahead と同様 ’a option 型なので，文字列が返値になる read という新しい関数を用意して，そこから呼び
出すようにしている．read ISTREAM は，取り出す文字が存在すれば，ISTREAM から 1 文字分の文字列を取り出
(アンダースコア) を
使う．上の例では，関数 native token, gettoken の定義中で指定している．上のプログラムを実行すると，
し，存在しなければ，空の文字列 "" を返す．パターンとして「その他」を示す場合には
7. 字句解析と構文解析
82
操作 83: 関数 gettoken の実行
- gettoken TextIO.stdIn;←- +←- val it = ONE "+" : token
- gettoken TextIO.stdIn;←- 1←- val it = NUM 1 : token
- gettoken TextIO.stdIn;←- abd←- val it = ID "abd" : token
のようになる．しかし，このプログラムでは関数 gettoken は 1 トークン取り出す毎に一回呼出されるだけであ
る．そこでこの関数を連続して呼び出すように変更しよう．以下の関数 run0() を用意する．
プログラム 60: 字句解析のための関数
run0
fun print token (LET) = print "LET"
| print token (BE) = print "BE"
|
|
|
print token (IN) = print "IN"
print token (ID i) = (print "ID("; print i; print ")")
print token (NUM n) = (print "NUM("; print (Int.toString n); print ")")
|
|
print token (ONE c) = (print "ONE("; print c; print ")")
print token (EOF) = ()
exception End of system
fun run () =
let val ISTREAM = TextIO.stdIn in
while true do (
TextIO.flushOut TextIO.stdOut;
let val rlt = gettoken ISTREAM in
case rlt of
ONE "$" => raise End of system
|
=> (print token rlt; print "\n")
end)
end
関数 gettoken から返る token 型の値は，そのままでは表示できない (直接呼び出す場合はシステムが表示) の
で表示するための関数 print token を定義している．関数 run の中では，関数 gettoken を連続的に呼び出すた
めに while 式を用いている2 ．while 式は，“$” が入力されるまで，gettoken を繰り返し呼び出す．この関数を
実行すると以下のようになる．
2
実は SML にも「繰り返し」を行う while が用意されている．
7.2. 構文解析
83
操作 84: 関数 run() の実行
- run();←- 1+2;←- NUM(1)
ONE(+)
NUM(2)
ONE(;)
let x be 10 in x;←- LET
ID(x)
BE
NUM(10)
IN
ID(x)
ONE(;)
$
uncaught exception End of system
以上のプログラムが完成したらこれらのプログラムを structure で囲もう．その結果以下のプログラムでは
structure Lexer の中の関数としてアクセスすることができる．
プログラム 61:
structure Lexer
structure Lexer = struct
字句解析のプログラム
end
7.2
構文解析
構文解析とは，字句解析から受渡されるトークンの組合せが文法を満たしているかどうか検査し，返値として
木構造 (構文木 (parser tree) という) に変換する処理を示す．ここで扱う文法は以下のようであった．
フレーズ
::=
式 ’;’
Expr(式)
式
|
::=
’let’ 識別子 ’be’ 式 ’in’ 式 ’;’
項
Def(識別子, 式, 式)
項
式 ’+’ 項
項
|
|
::=
App(Var +,Pair(式, 項))
App(Var -,Pair(式, 項))
基底式
|
|
基底式
::=
|
式 ’-’ 項
基底式
項 ’*’ 基底式
項 ’/’ 基底式
整数
識別子
App( Var *,Pair(項, 基底式))
App( Var /,Pair(項, 基底式))
Num(トークン)
Var(トークン)
一般に構文解析は (文法の) 木構造のルートから解析するトップダウンパーサ (top down parser) と，リーフか
ら解析する ボトムアップ パーサ (bottom up parser) の 2 種類がある．本章ではトップダウンパーサを用いた
7. 字句解析と構文解析
84
構文解析を紹介する．各パーサは，Knuth によって各 LL(k)(Left-to-right parse, Leftmost-derivation, k-symbol
lookahead)，LR(k)(Left-to-right parse, Rightmost-derivation, k-symbol lookahead) パーサと名付けられた．
この文法をより抽象的に表現すると以下のようになる．記述を容易にするために，フレーズ，式，項，基底式
に対して，P ，E ，T ，F で表現する．
P → let 識別子 be E in E ;
P → E;
E → T
E → E + T
E → E − T
T → F
T → T ∗ F
T → T /F
F → 整数
F → 識別子
しかし，この文法の，
E → T
E → E + T
E → E − T
と，
T → F
T → T ∗ F
T → T /F
の第 2, 第 3 のルールは，→ 右辺の先頭に，左辺と同じ記号が出現することから，左再帰 (left recursive) といわ
れる．この文法のままでは LL(1) でないことが知られている．しかし，これを右再帰の文法に変換することによっ
て LL(1) 文法にすることができる．この文法では以下のようになる．
E → T E0
E0 → + T E0
E0 → − T E0
E0 →
同様に，T に対しては以下のようになる．
T → F T0
T0 → ∗ F T0
T0 → / F T0
T0 →
本書では，左再帰の文法は，必ず右再帰に変換してプログラミングする．
それでは，実際に，文法から構文解析部を実装してみることにしよう．トップダウンパーサの生成は，文法中の
各記号に着目することによって，機械的に行うことができる．ここで，文法中の記号を，トークンを表す終端記
号（terminal symbol）と，文法中で定義される非終端記号（non-terminal symbol）とに区別することにする．
1. 文法の左辺に現われる非終端記号に対応して，関数を定義する．
2. 関数の本体の記述は，右辺の記号列から導かれる．各記号に対応して，次のようなコードを記述．
7.2. 構文解析
85
非終端記号 ： 対応する関数定義があるので，関数呼出しを記述．
終端記号 ： 入力トークンが，その終端記号と一致しているかチェックする操作を記述する．
右辺の複数選択 ：トークンを 1 つ先読みして，適切なものを選択するように記述．
文法上，複数選択できる場合は，先頭に来るべきトークンで判別を行う．プログラム中では，!tok 内に次のトー
クンが入っているので，case · · · of · · · 式によって，判別を行うようにする．tok は，何度も上書きできる参照
型を用いているので，引数の受渡しと関係なく，!tok で参照できる（後述）．tok には，構文解析を始める段階
でトークンが入っていることが必要なので，関数 parse の先頭で，advance() を呼び出していることに注意が必
要である．
特定のトークンが来ているかチェックするために，x が来ているかどうか調べる eat(x)，識別子が来ているか
調べる eatID，数字が来ているか調べる eatNUM を定義した．これらの関数は，チェック後，関数 advance を呼出
し，tok 内のトークンを更新させる．
関数 parse を実行すると次のようになる．
操作 85: 関数 prase の実行
- parse ();←- let x be 20 in x; $←- val it = () : unit
- parse ();←- 1+2; $←- val it = () : unit
ここで，入力プログラムの最後にある “$” は，E0F（ファイルの終わり）の代わりになる 1 文字である．特に，$ である必要はない．
7. 字句解析と構文解析
86
プログラム 62: 関数
parse
(* ストラクチャ名の省略 *)
structure L = Lexer
(* デフォルトストリーム（ref 型だから後で変更可） *)
val ISTREAM = ref TextIO.stdIn
(* 新しいトークンを取得し，tok に入れる *)
fun getToken () = Lexer.gettoken (!ISTREAM)
val tok = ref (L.ONE "")
fun advance () = tok := getToken()
(* エラー出力 *)
exception Syntax error
fun error () = raise Syntax error
(* 特定のトークンが来ているかチェックする *)
fun eat t = if (!tok=t) then advance() else error()
fun eatID () = case !tok of (L.ID ) => advance()
|
=> error()
fun eatNUM () = case !tok of (L.NUM ) => advance()
|
=> error()
(* 文法チェック *)
fun parse () = (advance (); P())
and P () = case !tok of
L.LET => (eat(L.LET); eatID(); eat(L.BE); E();
eat(L.IN); E(); eat(L.ONE ";"))
|
=> (E(); eat (L.ONE ";"))
and E () = (T(); E’())
and E’ () = case !tok of
(L.ONE "+") => (eat(L.ONE "+"); T(); E’())
| (L.ONE "-") => (eat(L.ONE "-"); T(); E’())
|
=> ()
and T () = (F(); T’())
and T’ () = case !tok of
(L.ONE "*") => (eat(L.ONE "*"); F(); T’())
| (L.ONE "/") => (eat(L.ONE "/"); F(); T’())
=> ()
|
and F () = case !tok of
(L.ID ) => eatID()
| (L.NUM ) => eatNUM()
|
=> error()
7.2. 構文解析
87
関数 parse はプログラムが構文と一致しているかどうかをチェックするだけなので，構文が正しい場合には何も
有用な値を返さない．
次に構文木を生成するように parse を拡張しよう．最初に構文木を定義するためのユーザ定義型を定義しよう．
構文木とは，文法の「要素を成す意味」終端記号 (構文木のリーフに相当) または 非終端記号 (構文木のリーフ以
外のノードに相当) からなる木である．したがって，型 definition(‘定義’ の意味) と 型 expr (‘式’ の意味) を定
義する．
プログラム 63: データ型
definition と
expr
datatype definition = Def of (string * expr * expr) | Expr of expr
and expr = Num of int | Var of string | App of expr * expr | Pair of expr * expr
構文木は，字句解析部と構文解析部との間でインタフェースの役割をする．よって，字句解析部や構文解析部に
属さないことを明示するために，新しい structure として定義しよう．
プログラム 64:
structure Ast
structure Ast = struct
構文木のデータ型
end
操作 86: 構文木
## let x be 10 in x ; $←- Def(x,Num 10,Var x)
## 1+2; $←- Expr(App(Var +,Pair(Num 1,Num 2)))
## let y be 10-3 in y/2; $←- Def(y,App(Var -,Pair(Num 10,Num 3)),App(Var /,Pair(Var y,Num 2)))
例えば，上のように let x be 10 in x; というプログラムを入力すれば Def(x,Num 10,Var x) という構文木
に変換し，1+2 というプログラムを入力すれば Expr(App(Var +,Pair(Num 1,Num 2))) という構文木に変換す
る．また let y be 10-3 in y/2; というプログラムを入力すれば Def(y,App(Var -,Pair(Num 10,Num 3)),
App(Var /,Pair(Var y,Num 2))) という構文木に変換する．Def(x,Num 10,Var x) を実際に木構造に表現す
ると以下のようになる．
Def
/ |
\
x Num 10 Var x
7. 字句解析と構文解析
88
プログラム 65: 関数 拡張 parse
structure L = Lexer
structure A = Ast
val ISTREAM = ref TextIO.stdIn
fun getToken () = L.gettoken (!ISTREAM)
val tok = ref (L.ONE "")
fun advance () = tok := getToken()
exception Syntax error
fun error () = raise Syntax error
(* 特定のトークンが来ているかチェックする *)
fun eat t = if (!tok=t) then advance() else error()
fun eatID () = case !tok of (L.ID str) => (advance(); str)
|
=> error()
fun eatNUM () = case !tok of (L.NUM ) => advance()
|
=> error()
(* 文法チェック *)
fun parse () = (advance(); P())
and P () = case !tok of
L.LET => (eat(L.LET);
let val str = eatID() in (eat(L.BE);
let val e1 = E() in (eat (L.IN);
let val e2 = E() in (eat(L.ONE ";"); A.Def (str, e1, e2)) end)
|
end)
end)
=> let val e = E() in (eat (L.ONE ";"); A.Expr e) end
and E () = let val t = T() in (E’ t) end
and E’ e = case !tok of
(L.ONE "+") => (eat(L.ONE "+");
let val pre = A.App(A.Var "+", A.Pair(e,T())) in
| (L.ONE "-") => (eat(L.ONE "-");
|
let val pre = A.App(A.Var "-", A.Pair(e,T())) in
=> e
E’(pre) end)
E’(pre) end)
and T () = let val f = F() in (T’ f) end
and T’ t = case !tok of
(L.ONE "*") => (eat(L.ONE "*");
let val pre = A.App(A.Var "*", A.Pair(t,F())) in T’(pre) end)
| (L.ONE "/") => (eat(L.ONE "/");
let val pre = A.App(A.Var "/", A.Pair(t,F())) in T’(pre) end)
=> t
|
and F () = case !tok of
(L.ID str) => (eatID(); A.Var str)
| (L.NUM num) => (eatNUM(); A.Num num)
|
=> error()
7.2. 構文解析
89
Expr(App(Var +,Pair(Num 1,Num 2))) は，
Expr
|
App
/
Var
\
+
Pair
/ \
Num 1 Num 2
の木構造となり，
Def(y,App(Var -,Pair(Num 10,Num 3)),
App(Var /,Pair(Var y,Num 2))) は，
Def ______
/ |
\
y App
App
/
\
/ \
Var - Pair Var / Pair
/
Num 10
\
Num 3
/
\
Var y Num 2
となる．
ここで 拡張前の関数 parse と見比べて欲しい．各関数は，対応する構文木の節を返す．節を表現する値構成子
が引数を必要とする場合は，対応する関数呼出しの結果を与える必要がある．これは，let で変数に束縛して引き
渡すように記述した．多くの場合，この方法で，左から右，下から上へという計算順序を表す構文木ができあが
ある．例外は，左再帰を取り除いた文法である．例えば，次の文法において，
E
→
T E0
E0
→
+ T E0
E0
→
T が生成する木は，E’ が生成する木の左下に継らなければならない（構文木では左下が先に計算されるとみなす
ことを思いだそう）．そこで，E’ に対応する関数に，それ以前に作成された木を引数で渡すようにする．E’ の本
体では，引数でもらった木と+と T が返してきた木から新しい節を構成し，E’ の引数として渡すように記述する．
…
and E’ e = case !tok of
(L.ONE "+") => (eat(L.ONE "+");
let val pre = A.App(A.Var "+", A.Pair(e,T())) in
…
上の関数 parse を実行すると，
E’(pre) end)
7. 字句解析と構文解析
90
操作 87: 関数 parse の実行
- parse ();←- let x be 20 in x; $←- val it = Def ("x",Num 20,Var "x") : definition
- parse ();←- 1+2; $←- val it = Expr (App(Var "+",Pair (#,#))) : definition
となる．ここで，値の表示に関して表示が長くなる場合は # によって省略されていることに注意しよう．
プログラム 66: 関数
print def と
print expr
fun print def x = case x of
Ast.Def(s,e1,e2) => (print "Def("; print s; print ",";
print_expr e1; print ","; print_expr e2; print ")")
| Ast.Expr (e) => (print "Expr("; print expr e; print ")")
and print expr x = case x of
Ast.Var s => (print "Var "; print s)
| Ast.App(e1,e2) => (print "App("; print expr e1;
print ","; print expr e2; print ")")
| Ast.Pair(e1,e2) => (print "Pair("; print expr e1;
print ","; print expr e2; print ")")
| Ast.Num n => (print "Num "; print (Int.toString(n)))
関数 print def は，データ型 definition に関するコンストラクタ を表示し，関数 print expr はデータ型
expr のコンストラクタ を表示するための関数である．
プログラム 67: 関数
print def を用いた実行
- print def (parse());←- let y be 10 in y; $←- Def(y,Num 10,Var y)val it = () : unit
最後に，字句解析部と同様に structure で囲もう．そして，以下のプログラムでは structure Parser の中
の関数としてアクセスすることができる．
プログラム 68:
structure Parser
structure Parser = struct
構文解析のプログラム
end
7.3. 参照型
7.3
91
参照型
新しい型 参照型 (referential type) を紹介する．この型は，次章の実装の際に使う．参照型は，関数プログラミ
ングの範囲を逸脱した概念である．今まで扱ってきた変数は，以下のように使った．
プログラム 69: 値を束縛する変数
val it = () : unit
- val x = 10;←- val x = 10 : int
- val f = fn x => x;←- val f = fn : ’a -> ’a
この例では整数型の値 10 に x という名前が付き，関数という値 (fn x => x) に f という値がつくと解釈でき
る．つまり，値に対して名前がつくのである．一方，他の手続き型言語 (procedural language) または 命令型言
語 (imperative language) では，値を格納する箱 (メモリの箱) ができ，その中に値が格納されている．
+--------+
x |
10
|
+--------+
このように，
「変数という箱」に名前がついていると考えることができる．このような場合，名前を x という参照
(reference) と考えて，
+---------+
x --> |
10
|
+---------+
と同等であることがわかる．--> は参照を表す (C 言語と同様)．x は，値を持つのではなく，x は参照を持つと解
釈できる．SML では，このように参照を表す変数は以下のように扱うことができる3
操作 88: 参照型
- val x = ref 10;←- val x = ref 10 : int ref
- x;←- val it = ref 10 : int ref
- val y = !x;←- val y = 10 : int
- y;←- val it = 10 : int
変数 x は，ref 10 のように整数型の値の前に ref をつけた値を持っている．結果として x は，整数への参照型
となる．参照型の変数はそのままでは，値を取り出すことはできない．その場合 ! という演算子 (dereference す
る演算子) を使ってのみ値を取り出すことができる．結果として変数 y は参照型ではなく整数型となる．参照型の
変数は，上で説明したように 箱が生成される のでその箱に対して 代入 (assignment) ができる．この代入は，以
下のように使う．
3 ここで注意したいのは，箱はどの参照からも「参照される」ことがなくなることが あり得る ことである．その様な箱はごみ (garbage)
といいごみ集め機能 (garbage collector) により自動的に削除される．ごみ集め機能は SML の処理系に標準で備わっている．
7. 字句解析と構文解析
92
操作 89: 代入
- x := 33;←- val it = () : unit
- x;←- val it = ref 33 : int ref
- !x;←- val it = 33 : int
- x := "true";←- std in:15.1-15.11 Error: operator and operand don’t agree (tycon
mismatch) operator domain: int ref * int operand: int ref * string in
expression: := (x,"true")
代入演算子 := を使って代入することができる．また，参照型の場合は型が宣言時に固定されている (箱の型) の
で左辺の変数の中身の型 (この場合は x の中身の型 int) と異なる型を代入しようとするとエラーとなる4 ．参照
型を示す ref は構成子 (constructor) であるが SML では関数として実装されていることに注意しよう．
操作 90: 関数 ref
- ref;←- val it = fn : ’1a -> ’1a ref
ここで，’1a という新しい多相型が推論されているがこれを弱い多相型 (weak polymorphic type) という．一方，
通常の多相型を強い多相型 (strong polymorphic type) という．強い型，弱い型の概念は後述する型推論の知識が
必要なのでここではこれ以上詳しく説明しない (後述)．しかし，通常の参照型を使うためには上の知識があれば
十分である．
4
let 式を使わなくてもよいことに注意しよう