[English]

プログラミング言語処理系

データ型として整数型のみを持ち、構文として代入文、if文、while文、for文および逐次結合文を持つプログラミング言語Minila （Mini-language）の処理系である。

例：次のプログラムを考える。

x := 12903;
y := 7735;
while x != y
  do
　　  if x < y　then y := y - x;
             else x := x - y;
    fi
  od

これは12903と7735の最大公約数を求めるプログラムである。 このプログラムは、２つの代入文と１つのwhileから構成される逐次結合文である。while文の内部は１つのif文から成る。

処理系は、字句解析器（lexical analyzer or scanner）、構文解析器（parser）、解釈実行系（interpreter）、コード生成系（code generator）および仮想機械（virtual machine）から構成される。

datatype token =
    Semc             (* ; *)
  | Lpar             (* ( *)
  | Rpar             (* ) *)
  | Mul              (* * *)
  | Div              (* / *)
  | Plus             (* + *)
  | Minus            (* - *)
  | Lt               (* < *)
  | Gt               (* > *)
  | Eq               (* = *)
  | Neq              (* != *)
  | And              (* && *)
  | Or               (* || *)
  | Assign           (* := *)
  | If               (* if *)
  | Then             (* then *)
  | Else             (* else *)
  | Fi               (* fi *)
  | While            (* while *)
  | For              (* for *)
  | Do               (* do *)
  | Od               (* od *)
  | Num of int       (* [0-9]+ *)
  | Var of string    (* [a-zA-Z][a-zA-Z0-9]* except for keywords *)
  | Undef of string  (* undefined tokens *)

区切り文字（delimiters）は以下のとおりである。

' ', ';', '(', ')', '*', '/', '+', '-', '<', '>', '=', '!=', '&&', '||', ':='

予約語（キーワード）は以下のとおりである。

"if", "then", "else", "fi", "while", "for", "do", "od"

例：次の文字列

"x := 12903; y := 7735; while x != y do if x < y then y := y - x; else x := x - y; fi od"

は、以下のトークンのリストに変換される。

[Var "x", Assign, Num 12903, Semc, Var "y", Assign, Num 7735, Semc, While,　Var "x", Neq, Var "y", Do, If, Var "x", Lt, Var "y", Then, Var "y",　Assign, Var "y", Minus, Var "x", Semc, Else, Var "x", Assign, Var "x",　Minus, Var "y", Semc, Fi, Od]

  P ::= S
 
 S ::=   eps                             （空文）
       | var ':=' E ';'                （代入文）
       | 'if' E 'then' S 'else' S 'fi' （if文）
       | 'while' E 'do' S 'od'         （while文）
       | 'for' var E E 'do' S 'od'     （for文）
       | S S                           （逐次結合文）
 
 E ::=   num
       | '-' num
       | var
       | '-' var
       | '(' E ')'
       | '-' '(' E ')'
       | E '*' E | E '/' E
       | E '+' E | E '-' E
       | E '<' E | E '>' E | E '=' E | E '!=' E
       | E '&&' E | E '||' E

Pはプログラム、Sは文、そしてEは式を現 す。

空文はなにもしない。代入 文 var := E;　は、式Eの 計算結果を変数に代入する。if文 if E then S1 else S2 fi は、式Eの計算結果が0で なければ、S1を、0で あれば、S2を実行する。while文 while E do S od は、式Eの 計算結果が0でない限り、Sを 実行し続ける。for文 for var E1 E2 do S od は、式E1の計算結果を変数var に代入し、varの値がE2の 計算結果より大きくない限り、Sを実行し続ける。逐次結合文 S1 S2 は、S1を実行し、S2を実行する。

文の構文木は、（部分）構 文木のリストで表現する。空文の構文木は空リストで表現する。代入文、if文、while文およびfor文の各々の構文木は、要素数１のリストで表現す る。逐次結合文 S1 S2 の構文木は、S1の構文木を現すリストとS2の構文木を表すリストを結合して得られるリストで現す。

代入文、if文、while文およびfor文の構文木のデータ型stmは以下の とおりである。

datatype stm =
  AssignNode of exp*exp
| IfNode of exp*(stm list)*(stm list)
| WhileNode of exp*(stm list)
| ForNode of exp*exp*exp*(stm list)

expは、式の構文木のデータ型である。それは以下のとおりである。

datatype exp =
  NumNode of int
| VarNode of string
| UminusNode of exp
| MulNode of exp*exp
| DivNode of exp*exp
| PlusNode of exp*exp
| MinusNode of exp*exp
| LtNode of exp*exp
| GtNode of exp*exp
| EqNode of exp*exp
| NeqNode of exp*exp
| AndNode of exp*exp
| OrNode of exp*exp

構文解析は、再帰降下法（recursive decent parsing）を用いる。このため、式の文法を以下のとおりに書き換える。

F   ::= ['-'] num | ['-'] var | ['-'] '(' E ')'
E1  ::= F E11
E11 ::= eps | '*' F E11 | '/' F E11
E2  ::= E1 E22
E22 ::= eps | '+' E1 E22 | '-' E1 E22
E3  ::= E2 E33
E33 ::= eps | '<' E2 E33 | '>' E2 E33 | '=' E2 E33 | '!=' E2 E33
E4  ::= E3 E44
E44 ::= eps | '&&' E3 E44 | '||' E3 E44
E   ::= E4

例：次のトークンのリスト

[Var "x", Assign, Num 12903, Semc, Var "y", Assign, Num 7735, Semc, While,　Var "x", Neq, Var "y", Do, If, Var "x", Lt, Var "y", Then, Var "y",　Assign, Var "y", Minus, Var "x", Semc, Else, Var "x", Assign, Var "x",　Minus, Var "y", Semc, Fi, Od]

から、以下の構文木が生成される。

[AssignNode(VarNode "x", NumNode 12903),
 AssignNode(VarNode "y", NumNode 7735),
 WhileNode(NeqNode(VarNode "x", VarNode "y"),
           [IfNode(LtNode(VarNode "x", VarNode "y"),
                   [AssignNode(VarNode "y",
                               MinusNode(VarNode "y", VarNode "x"))],
                   [AssignNode(VarNode "x",
                               MinusNode(VarNode "x", VarNode "y"))])])]

構文木を現すリストの先頭が AssignNode (VarNode var, EN) の場合：式の構文木ENを処理し、その結果nと変数の識別子である文字列varの対応を環境に保存する。

構文木を現すリストの先頭が IfNode (EN,SN1,SN2) の場合：式の構文木ENの処理結果が0でなければ、文の構文木SN1を処理し、そうでなければ、文の構文木SN2を処理する。

構文木を現すリストの先頭が WhileNode (EN,SN) の場合：式の構文木ENの処理結果が0でない限り、文の構文木SNを処理し続ける。

構文木を現すリストの先頭が ForNode (VarNode var,EN1,EN2,SN) の場合：変数の識別子である文字列varと式の構文木EN1の処理結果の対応を環境に保存する。環境に保存されている変数（の識別子である文字列）の値が式の構文木EN2の処理結果より小さいか等しい限り、文の構 文木SNを処理し続ける。

結果として環境の情報（変数と整数の組のリスト）を返す。

例：次の構文木

[AssignNode(VarNode "x", NumNode 12903),
 AssignNode(VarNode "y", NumNode 7735),
 WhileNode(NeqNode(VarNode "x", VarNode "y"),
           [IfNode(LtNode(VarNode "x", VarNode "y"),
                   [AssignNode(VarNode "y",
                               MinusNode(VarNode "y", VarNode "x"))],
                   [AssignNode(VarNode "x",
                               MinusNode(VarNode "x", VarNode "y"))])])]

の処理結果は以下の変数と整数の組のリストである。

[("x", 17), ("y", 17)]

12903と7735の最大公約数は17である。

コード生成系

構文木から仮想機械の命令列を生成する。用いる命令のデータ型commandは以下の とおりである。仮想機械は整数のスタックと変数（文字列）と整数の対応を保存する環境を用いる。それらをStkとEnvで現す。また、プログラムカウンタ をpcで現す。Jump、JumpOnCondお よびQuitを除く命令の実行後、pcの値を１増やす。

datatype command =
  Push of int        （Stkに整数を積む。）
| Load of string     （Envに保存されている変数の値（整数）をStkに積む。）
| Store of string    （Stkの先頭nを取り、変数とnの対応をEnvに保存する。）
| MulMinusOne        （Stkの先頭nを取り、-1*nをStkに積む。）
| Multiply           （Stkの先頭から値を２つn1,n2とり、n2*n1をStkに積む。）
| Divide             （Stkの先頭から値を２つn1,n2とり、n2/n1をStkに積む。）
| Add                （Stkの先頭から値を２つn1,n2とり、n2+n1をStkに積む。）
| Subtract           （Stkの先頭から値を２つn1,n2とり、n2-n1をStkに積む。）
| LessThan           （Stkの先頭から値を２つn1,n2とり、lt(n2,n1)をStkに積む。）
| GreaterThan　   　　    （Stkの先頭から値を２つn1,n2とり、gt(n2,n1)をStkに積む。）
| Equal              （Stkの先頭から値を２つn1,n2とり、eq(n2,n1) をStkに積む。）
| NotEqual           （Stkの先頭から値を２つn1,n2とり、neq(n2,n1)をStkに積む。）
| And                （Stkの先頭から値を２つn1,n2とり、and(n2, n1)をStkに積む。）
| Or                 （Stkの先頭から値を２つn1,n2とり、or(n2,n1) をStkに積む。）
| Jump of int        （pcに整数を加える。）
| JumpOnCond of int  （Stkの先頭nをとり、n<>0で あれば、pcに整数を加える。）
| Quit               （実行を終了する。）

lt(n2,n1)は、n2<n1ならば1を、そうでなければ 0を返す。gt(n2,n1)は、n2>n1ならば1を、そうでなければ0を返す。eq(n2,n1)は、n2=n1ならば1を、そうでなければ0 を返す。neq(n2,n1)は、n2<>n1ならば1を、そうでなければ0を返す。and(n2,n1)は、n2<>0かつ n1<>0ならば1を、そうでなければ0を返す。or(n2,n1)は、n2<>0またはn1<>0ならば1を、そ うでなければ0を返す。

構文木を現すリストの先頭が AssignNode (VarNode var, EN) の場合：式の構文木ENから生成される命令列をCLとすると、生成される命令列は以下のようなものである。

CL @ [Store var]

構文木を現すリストの先頭が IfNode (EN,SN1,SN2) の場合：式の構文木ENから生成される命令列をCL1、文の構文木SN1とSN2から生成され る命令列をCL2とCL3と すると、生成される命令列は以下のようなものである。

CL1 @ [JumpOnCond 2, Jump (CL3の先頭までの長さ)] @ CL2 @ [Jump (CL3の次までの長さ)] @ CL3

構文木を現すリストの先頭が WhileNode (EN,SN) の場合：式の構文木ENから生成される命令列をCL1、文の構文木SNから生成される命令列をCL2と すると、生成される命令列は以下のようなものである。

CL1 @ [JumpOnCond 2, Jump (CL2の次のJump命令の次までの長さ)] @ CL2 @ [Jump -1 * (CL1の次までの長さ)]

構文木を現すリストの先頭が ForNode (VarNode var,EN1,EN2,SN) の場合：式の構文木EN1とEN2から生成される命令列をCL1とCL2とし、文の構 文木SNから生成される命令列をCL3と すると、生成される命令列は以下のようなものである。

CL1 @ [Store var, Load var] @ CL2 @ [LessThan, Load var] @ CL2 [Equal, Or, JumpOnCond 2, Jump (最後のJump命令の次までの長さ)] @ CL3 @ [Load var, Push 1, Add, Store var, Jump -1 * (最初のCL2の直前のLoad命令までの長さ)]

生成する命令列の最後にQuit命令を加える。

式の構文木から生成される命令列：NumNode n か ら生成される命令列は、[Push n]である。VarNode var から生成される命令列は、[Load var]である。UminusNode EN から生成される命令列は、式の構文木ENから生成される命令列をCLとすると、CL @ [MulMinusOne]である。MulNode (EN1,EN2) か ら生成される命令列は、式の構文木EN1とEN2から生成される命令列をCL1とCL2とすると、CL1 @ CL2 @ [Multiply]である。残りの式の構文木からも同じように命令列が生成される。

例：次の構 文木

[AssignNode(VarNode "x", NumNode 12903),
 AssignNode(VarNode "y", NumNode 7735),
 WhileNode(NeqNode(VarNode "x", VarNode "y"),
           [IfNode(LtNode(VarNode "x", VarNode "y"),
                   [AssignNode(VarNode "y",
                               MinusNode(VarNode "y", VarNode "x"))],
                   [AssignNode(VarNode "x",
                               MinusNode(VarNode "x", VarNode "y"))])])]

から、以下のコード列が生 成される。

[Push 12903, Store "x", Push 7735, Store "y", Load "x", Load "y", NotEqual,
 JumpOnCond 2, Jump 16, Load "x", Load "y", LessThan, JumpOnCond 2, Jump 6,
 Load "y", Load "x", Subtract, Store "y", Jump 5, Load "x", Load "y",
 Subtract, Store "x", Jump ~19, Quit]

命令列に従った処理をする。実行後、結果として環境の情報（変数と整数の組のリスト）を返す。

例：次の命令列

[Push 12903, Store "x", Push 7735, Store "y", Load "x", Load "y", NotEqual,
 JumpOnCond 2, Jump 16, Load "x", Load "y", LessThan, JumpOnCond 2, Jump 6,
 Load "y", Load "x", Subtract, Store "y", Jump 5, Load "x", Load "y",
 Subtract, Store "x", Jump ~19, Quit]

の処理結果は以下の変数と整数の組のリストである。

[("x", 17), ("y", 17)]

プログラム

解釈実行系およびコード生成系のfor文に関する箇所は未実装である。

Env.sig
Env.sml
Scanner.sig
Scanner.sml
Parser.sig
Parser.sml
Interpreter.sig
Interpreter.sml
Compiler.sig
Compiler.sml
VirtualMachine.sig
VirtualMachine.sml