0. はじめに
1. コンパイラ作成例（その１：簡単な宣言と式）
   1. 文法
   2. SimpleDriver.java
   3. Parser
   4. Lexer
   5. コンパイラの実行結果
   6. コンパイル過程の可視化
   7. JFlexとjay以外の生成系について
2. コンパイラ作成例（その２：制御文）
   1. 文法
   2. Parser
3. コンパイラ作成例（その３：関数定義）
   1. 文法
   2. Parser
4. コンパイラ作成例（その４：データ型と配列）
   1. 文法
   2. Parser

０．はじめに

以下では、簡単な言語の例によって、このようなコンパイラの開発の仕方を示すことにする。

１．コンパイラ作成例（その１：簡単な宣言と式）

この例では、lexerとparserは、それぞれJFlex とjayという生成系を使って生成し、コンパイラドライバとしてSimpleDriver.javaが書かれている。JFlex用のファイルsimple1.l、jay用のファイルsimple1.y、それとSimpleDriver.javaの３つのファイルを作成するだけで、この言語Simpleのコンパイラができ上がる。 ターゲットマシンはSimpleDriverを呼び出すときの オプションで指定出来る。たとえば、"target=x86"と指定すれば、x86の機械語コードを生成する Simpleコンパイラができ上がる。

生成系としてJFlexとjayを使うことにした理由は1.6節で述べる。

1.1 文法

<program> ::= <declaration_list> <statement_list>
<declaration_list> ::= empty 
           | <declaration_list> <declaration> ';'
<declaration> ::= 'int' ident
           | <declaration> ',' ident
<statement_list> ::= <statement>
           | <statement_list> <statement>
<statement> ::= <ident> '=' <expression> ';' 
           | 'read' ident ';'
           | 'write' <expression> ';' 
<expression> ::= <expression> '+' <term>
           | <expression> '-' <term>
           | <term>
<term> ::= <term> '*' <factor>
           | <term> '/' <factor>
           | <term> '%' <factor>
           | <factor>  
<factor> ::= '-' <factor>
           | '(' <expression> ')'
           | ident
           | number

1.2 SimpleDriver.java

COINSによるコンパイラ開発を容易にするために、標準のDriverが用意されている。SimpleDriverはそのサブクラスとして作られている。このコンパイラを呼び出すには、例えば、次のようなコマンドを打つ。

　　　$ java SimpleDriver -S -coins:trace=HIR.1,target=x86 expr1.c

"-S"や"-coins:trace"などのオプション指定の詳しい説明は ドライバの使い方のページにある。

このコマンドで最初に実行されるmainメソッドは次のようになっている。

　　public static void main(String[] args) {
　　　　new SimpleDriver().go(args);
　　}

goメソッドから呼び出されるパスには、preprocess、compile、assemble、linkがあり、それらのパスですることは標準のDriverに書かれているから、それと同じでよい場合はSimpleDriverには何も書く必要がない．

SimpleDriverでは、compileの中の最初のparserだけを取り換えて、その他のパスはDriverのものをそのまま使うことにする。そのためには、DriverのメソッドmakeHirFromSourceをオーバライドするだけでよい。

makeHirFromSourceの中では、IoRoot、SymRoot、HirRootなどのインスタンスが参照されているが、それらは、それぞれ、入出力、シンボル（ソースプログラム中の名前など)、HIRに関する情報の根（ルート）となっている。それらの初期値はDriverのcompileメソッドの最初で設定されている。 makeHirFromSourceでは、Parserのインスタンスを作り、そのyyparseメソッドを呼び出すことによって構文解析を行い、HIRの木を作る。

1.3 Parser

SimpleDriverで使われているParserはjayを使って生成してある。jayはBerkeley YACCにJava出力用の機能を追加したものであり、YACC用の構文規則がそのまま使える （ http://www.informatik.uni-osnabrueck.de/alumni/bernd/jay/）。jayはCで書いてあり、unix系のOS，ウィンドウズマシンのcygwin、Mac OS Xなどで使うことが出来る。ただし、チュートリアルはドイツ語で書いてある。英語による説明 をしているところもある。JFlexとjayをまとめて日本語で説明しているところもある。

Parserは、たとえば（cygwinの場合）

　　$ jay.cygwin < skeleton simple1.y > Parser.java

ここでは、たとえば

　　int a, b;
　　read a;
　　b = a + 5;
　　write b;

　　main() {
　　　　int a, b;
　　　　scanf("%d", &a);
　　　　b = a + 5;
　　　　printf("%d\n", b);
　　}

同様に変数名などのシンボルに関するインタフェースはcoins.symパッケージのSym.javaに定義されているが、 基本的なものはそのスーパクラスのSym0.javaに定義されている。したがって、ほとんど HIR0.javaとSym0.javaを見るだけで比較的簡単な言語のコンパイラを書くことが出来る。

それらのメソッドはインスタンスメソッドとして定義されているから、そのメソッド呼出しにはインスタンスが必要である。そのためのインスタンスはhirRoot.hirとして用意されているから

　　hir = (HIR0)hirRoot.hir;

　　hir.program(null, symRoot.symTableRoot, null, null);

そのあとは、これから構文解析するプログラムがmainプログラムの中身であるとするための処理である。まず、"main"という名前のシンボルを、サブプログラム型で返す値の型はvoidである、として次のように作る。

　　Subp lMain = sym.defineSubp("main".intern(), symRoot.typeVoid);

HIRノードを作るのにhirというインスタンス変数を使ったように、シンボルを作るのには

　　sym = (Sym0)symRoot.sym;

次に、main用のシンボルテーブルを作る。

　　SymTable lSymTable = symRoot.symTableRoot.pushSymTable(lMain);

　　symRoot.symTableRoot.pushSymTable(lMain);

最後に、mainプログラムのHIRの木をサブプログラムの定義の木として作るために、サブプログラムの定義のノードを作ってそれをルートのノードにつける。

　　lMainDef = hir.subpDefinition(lMain, lSymTable);
　　((Program)hirRoot.programRoot).addSubpDefinition(lMainDef);

以下、ファイルsimple1.yの中身を詳しく見ていく。最初の

　　%{
　　package simple;
　　
　　import java.io.IOException;
　　...
　　import coins.HirRoot;
　　...
　　public class Parser {
　　%}

その次の構文規則の書き方はyaccと同じである。アクション記述の中の$$や$1などの意味もyaccと同じである。アクション記述としては、$$や$1などの関係を出来るだけ簡潔に表現するために、多くのアクションはメソッド呼出しの形にしてある。これらのアクションで、HIRの木を下から（葉の方から根に向かって）作っていく。最後に、開始記号のprogramに還元されたところで、でき上がった木を、finalizeメソッドにある以下の文によってmainの本体としてセットする。

　　lMainDef.setHirBody((BlockStmt)blockStmt);

　　static final int ADD = HIR0.OP_ADD;
　　static final int SUB = HIR0.OP_SUB;
　　.....

その後にあるprivate宣言されている変数は、いくつかのメソッドにまたがって使われるものである。

その後に、アクション記述で使われているメソッドの定義が並んでいる。それらの意味は構文規則から考えられる意味と各メソッドにつけられているコメントから分かるであろう。

少し複雑なメソッドになっているmakeWriteStmtNode（とmakeReadStmtNode）についてだけ説明する。これらのメソッドではprintf（またはscanf）をcallするノードを作成する。 実引数のリストparamListの第１引数は"%d\n"（または"%d"）であり、第２引数はプリントされる 値の式（あるいは読んだものを代入する変数）である。このステートメントのノード には、対応するソースプログラムの行番号を付加する。これがあると、HIRやLIRを 表示した時にソースプログラムとの対応が分かりやすくなる。

yaccではソースプログラムに構文エラーがあった場合、エラー処理の状態から通常の状態に 復帰するのにyyerrokというマクロが使われる。そのマクロに相当することは

　　yyErrorFlag = 0;

ここで、エラーメッセージの出力のために用意されているメソッドについて説明する。
メソッドsearchAndMakeVarNodeの中の

　　ioRoot.msgRecovered.put("undeclared " + id ); 

なお、この構文規則は、下記の参考書の第7章のプログラム7.1をもとにしている。ただし、そこにあった、代入文を式としても扱う機能、'?'と':'を使った条件式、演算子"++"、"--"などは除いてある。それに直接対応するノードはHIRにはないからである。HIR-Cにはそれがある。そのような機能を持った言語のコンパイラを作る場合は、まずHIR-C（C言語用の一時的なHIR）の木を作り、それからHIRの木に変換する方法が考えられる（そのモジュールはもちろんcoinsに用意されており、Cコンパイラではそれを使っている）。

原田賢一著「コンパイラ構成法」共立出版、1999

1.4 Lexer

LexerはJFlexを使って生成した。JFlexを選んだ理由は後で述べる。simple1.lの最初のpackage文、import文の後の

　　%public
　　%class	Scanner
　　%implements  Parser.yyInput

　　boolean advance () // トークンを１つ読み進めend of fileでなかったらtrueを返す。
　　int token () 　　　　// トークンを返す。
　　Object value ()  　　// トークンの値を返す。

　　int token; 
　　Object value;

記述の仕方はlexとほぼ同じであるが、パターン名の定義の仕方がlexでは

　　　パターン名　　パターン　改行

　　　パターン名　=　パターン　改行

simple1.lは上記の参考書のプログラム7.3をもとにして書いたものであるので、両者を比較すればその違いがわかる。

最後の部分の

　　{id}　　{ value = (new String(yytext())).intern();
　　　　　　　return Parser.ID; }

なお、プログラム7.3では

　　{ws}+

　　{ws}

1.5 コンパイラの実行結果

-----ソースプログラムexpr1.c-----

　　int a, b;
　　read a;
　　b = a + 5;
　　write b;

シンボルテーブルは
　　-coins:trace=Sym.1
を指定すれば出力される。HIR.1とSym.1の両方を指定する時は
　　-coins:trace=HIR.1/Sym.1
とすればよい。
なお、可視化ツールCoVisでは行番号が見やすく表示される。

--------expr1.s--------

	.section ".text"
	.align	1
string.6:
	.byte	37
	.byte	100
	.byte	0
	.align	1
string.8:
	.byte	37
	.byte	100
	.byte	10
	.byte	0

	.align	4
	.global	main
main:
	save	%sp,-104,%sp
	sethi	%hi(string.6),%o0
	or	%o0,%lo(string.6),%o0
	add	%fp,-4,%o1
	call	scanf
	nop
	ld	[%fp-4],%i0
	add	%i0,5,%o1
	sethi	%hi(string.8),%o0
	or	%o0,%lo(string.8),%o0
	call	printf
	nop
.L3:
	ret
	restore

1.6 コンパイル過程の可視化

COINSを使ったコンパイラでは、通常は、まずソースプログラムをHIRに変換し、 次にそれをLIRに変換し、LIRからマシン語のコードが生成される。HIR上やLIR上で 各種の最適化を適用することも出来る。それらの最適化をするためには、基本的には 制御やデータのフローを解析する必要があるので、HIRやLIRで表現されているプログラム から制御フローグラフが作られる。

そのフローグラフや、フローグラフとソースプログラム、HIR、LIRなどとの対応をグラフィカル に表示するツールCoVisがある。 次の図はそれを使って前節のプログラムmult.pの コンパイル過程を表示した例である。
ただし、この例は簡単であるのでフローグラフのノードは１つしかない。

1.7 JFlexとjay以外の生成系について

当初は、JFlexと Byaccを使ってみた。ByaccもjayもBerkeley yaccをベースにしているが、 jayのmakeが最初はうまくいかなかったので、Byaccを使うことにし、 Byaccとの連携が考えられているJFlexを使うことにした。

ByaccはCで書いてあり、速いのが自慢であるらしい。ただし、ウィンドウズマシンのcygwinやlinux上のByaccでこの例題のParserを作ることは出来たが、Byaccは64ビットSolarisには対応していないようで、「バスエラー」となってしまう。また、Mac OS Xでも"Segmentation Fault"となってしまう。さらに、 コンパイラ作成例の4番目でByaccのバグらしきものに遭遇したので、別のものを検討することにした。

再びjayのmakeを試みたところ、新しいバージョンでは簡単にmakeをすることが出来た。 そのjayの例題ではlexerを作るのにJLexを使っていたので、 ByaccとJFlexの代わりにjayとJLexを使って同じようにコンパイラを作ってみた。ところが、作成例の１はうまく出来たが、作成例の2でJLexがlexerの生成に失敗した（エラー表示は出なかったが、ある定数表の作成に失敗していた）。そこで、JLexをやめることにし、 JFlexはJLexの機能を含んでいるという説明があったので、JLex用に作ったファイルをJFlexに与えてみたら、lexerが生成できた。以上のような経過で、最初に述べたようにJFlexとjayを使うことにした。

JFlexとJLexでは、空白などの文字の指定の仕方が異なるが、それ以外はほぼ同じである。

Byaccではトークンの値はint, double, String, Objectなどとすることが出来たが、jayでは 値はObject（とそのサブクラス）だけである（intやdoubleは使えない。Integerなどとする必要がある）。Byaccでは、非終端記号の値のクラスとしてObjectのいろんなサブクラスを指定する方法が分からなかったが、jayではそれが出来ている。 Byaccの場合のlexerとのつなぎの方法はjayとは違う。そのやり方はByaccのホームページを見れば分かる。一方jayについては、英語の説明があまりなく、チュートリアルはドイツ語で書かれている。

なお、Byaccではたとえば次のように書くことが出来るが、jayではそのままではうまくいかない。

   a : b  {$<obj>$ = .... ;} c { $$ = f($<obj>2); } ;

　　 { ((obj)yyVal)= .... ;}

   a : b  {$$ = .... ;} c { $$ = f($<obj>2); } ;

2. コンパイラ作成例（その２：制御文）

この例でも、lexerとparserは、それぞれJFlexとjayという生成系を使って生成し、コンパイラドライバとしては前節の例のSimpleDriver.javaをそのまま使う。言語は前節の言語の拡張になっているから、JFlex用のファイルsimple1.lを拡張したsimple2.l、jay用のファイルsimple1.yを拡張したsimple2.y、の２つのファイルを作成するだけで、この言語のコンパイラができ上がる。

2.1 文法

<program> ::= <declaration_list> <statement_list>
<declaration_list> ::= empty 
           | <declaration_list> <declaration> ';'
<declaration> ::= 'int' ident 
           | <declaration> ',' ident
<statement_list> ::= <statement>
           | <statement_list> <statement>
<assign> ::= ident '=' <expression>
<opt_assign> ::= empty
           | <assign>
<statement> ::= <assign> ';' 
           | empty ';'
           | 'read' ident ';' 
           | 'write' <expression> ';' 
           | '{' <statement_list> '}' 
           | <if_part>
           | <if_part> 'else' <statement>
           | 'while' '(' <expression> ')' <statement>
           | 'do' <statement> 'while' <expression> ';' 
           | 'for' '(' <opt_assign> ';' <test_exp> ';' <opt_assign> ')' <statement>
           | 'switch' '(' <expression> ')' '{' <case_list> <default_case> '}' 
           | 'break' ';' 
           | 'continue' ';' 
<case_list> ::= <case_item>
           | <case_list> <case_item>
<case_item> ::= 'case' number ':'
           | <case_item> <statement>
<default_case> ::= empty
           | <default_item>
<default_item> ::= 'default' ':'
           | <default_item> <statement>
<if_part> ::= 'if' '(' <expression> ')' <statement>
<test_exp> ::= empty
           | <expression>     
<expression> ::= <expression1> '||' <expression1>
           | <expression1>
<expression1> ::= <expression2> '&&' <expression2>
           | <expression2>
<expression2> ::= <expression3> <relational_op> <expression3> 
           | <expression3> 
<relational_op> ::= '<' | '<=' | '==' | '!=' | '>=' | '>'
<expression3> ::= <expression3> '+' <term>
           | <expression3> '-' <term>
           | <term> 
<term> ::= <term> '*' <factor>
           | <term> '/' <factor>
           | <term> '%' <factor>
           | <factor>  
<factor> ::= '-' <factor>
           | '!' <factor> 
           | '(' <expression> ')'
           | ident
           | number

2.2 Parser

Parserはjayのプログラムsimple2.yから生成される。その際、１つのshift/reduceコンフリクトを指摘されるが、それはif文のdangling elseによるものであり、shift優先で処理される。それは、「elseはそれに最も近いifで、まだどのelseとも対応付けられていないifに対応付けられる」ことになるのでokである。

if文のノードの作り方は、プログラムを見れば分かるであろう。その他の制御文については少し説明が必要である。

break文は、それを含む一番内側のループまたはswitch文を抜け出す文である。また、continue文は、それを含む一番内側のループの次の繰り返しに飛ぶ文である。HIRでは、これらはJumpStmtのノードとして表現されるので、JumpStmtの飛び先のラベルを指定する必要がある。そのようなJumpStmtを構文解析時に作ってしまうことにすると、例えばあるループの構文解析を始めたときには、そのループの中のbreak文やcontinue文の飛び先のラベルを作っておく必要がある。break文やcontinue文の飛び先は、その文を含む一番内側のループやswitch文に付けられているラベルのところである。一番内側のものを見つけるために、それらをスタックに入れている。

それらのラベルを入れておくクラスとしてBseLabelを作り、スタックはBseLabelの配列として実現している。また、switch文の場合は、break文の飛び先だけでなく、caseラベルの情報や実行文の情報もそこに蓄積していくようにしている。

たとえば、

　　stmt  : 
　　　　　...
　　　　　| WHILE　　　　　　　{ nestIn(WHILE); }　// ループ文やswitch文のネストを記録
　　　　　　'(' expr ')'  stmt　　{ $$ = makeWhileStmt( $1.intValue(), $4, $6 ); }

while文の中にbreak文などが現れたら、スタックのトップのラベルを使ってJumpStmtを作る。そのwhile文が閉じられたら、makeWhileStmtメソッドからnestOutメソッドを呼び出して、スタックからBseLabelのインスタンスをポップして、while文の本体をセットする。

switch文の場合は少し複雑である。

　　stmt  : 
　　　　　...
　　　　　| SWITCH '(' expr ')' 　　　　　　　{ nestIn(SWITCH); } 
　　　　　　'{' case_list default_case '}'　　{ $$ = makeSwitchStmt( $1.intValue(), $3 ); }

3. コンパイラ作成例（その３：関数定義）

プログラム全体は、関数の定義、関数プロトタイプの宣言、および変数の宣言からなる。これらは大域宣言と呼ばれる。 関数定義またはブロックの中でも関数プロトタイプの宣言および変数の宣言をすることが出来る。これらは局所宣言と呼ばれる。ただし、変数の型はintだけであり、関数の返す型はintかvoidだけである。

この例でも、lexerとparserは、それぞれJFlexとjayという生成系を使って生成し、コンパイラドライバとしては前節の例のSimpleDriver.javaをそのまま使う。言語は前節の言語の拡張になっているから、JFlex用のファイルsimple2.lを拡張したsimple3.l、jay用のファイルsimple2.yを拡張したsimple3.y、の２つのファイルを作成するだけで、拡張された言語のコンパイラができ上がる。

3.1 文法

<program> ::= <global_declarations>
<global_declarations> ::= empty
           | <global_declarations> <declaration> ';'
           | <global_declarations> <function_def> ';'
<declaration> ::= <type> ident
           | <type> <function_head>
           | <declaration> ',' ident
           | <declaration> ',' <function_head>
<type> ::= 'void' | 'int'
<param_list> ::= empty
           | <param_decl>
           | <param_list> ',' <param_decl>
<param_decl> ::= <type> ident
<function_head> ::= ident '(' <param_list> ')'
<function_def> ::= <type> <function_head> <block> 
<block> ::= '{' <declaration_list> <statement_list> '}'
<declaration_list> ::= empty 
           | <declaration_list> <declaration> ';'
<statement_list> ::= <statement>
           | <statement_list> <statement>
<assign> ::= ident '=' <expression> 
<opt_assign> ::= empty
           | <assign>
<statement> ::= <block>
           | 'return' ';'
           | 'return' <expression> ';'
           | <assign> ';' 
           | empty ';'
           | 'read' ident ';' 
           | 'write' <expression> ';' 
           | <if_part>
           | <if_part> 'else' <statement>
           | 'while' '(' <expression> ')' <statement>
           | 'do' <statement> 'while' <expression> ';' 
           | 'for' '(' <opt_assign> ';' <test_exp> ';' <opt_assign> ')' <statement>
           | 'switch' '(' <expression> ')' '{' <case_list> <default_case> '}' 
           | 'break' ';' 
           | 'continue' ';' 
<case_list> ::= <case_item>
           | <case_list> <case_item>
<case_item> ::= 'case' number ':'
           | <case_item> <statement>
<default_case> ::= empty
           | <default_item>
<default_item> ::= 'default' ':'
           | <default_item> <statement>
<if_part> ::= 'if' '(' <expression> ')' <statement>
<test_exp> ::= empty
           | <expression>     
<expression> ::= <expression1> '||' <expression1>
           | <expression1>
<expression1> ::= <expression2> '&&' <expression2>
           | <expression2>
<expression2> ::= <expression3> <relational_op> <expression3> 
           | <expression3> 
<relational_op> ::= '<' | '<=' | '==' | '!=' | '>=' | '>'
<expression3> ::= <expression3> '+' <term>
           | <expression3> '-' <term>
           | <term> 
<term> ::= <term> '*' <factor>
           | <term> '/' <factor>
           | <term> '%' <factor>
           | <factor>  
<factor> ::= '-' <factor>
           | '!' <factor> 
           | '(' <expression> ')'
           | ident '(' <argument_list> ')'
           | ident
           | number
<argument_list> ::= empty
           | <expression>
           | <argument_list> <expression>

3.2 Parser

Parserはjayのプログラムsimple3.yから生成される。その際、１つのshift/reduceコンフリクトを指摘されるが、それは前節と同様にif文のdangling elseによるものである。

今までの例では、Parserで最初に"main"という名前のSubpを作っていたが、今度は、 "main"という名前の関数定義があったときにそれが作られる。

関数定義の外側での宣言は 大域宣言であり、内側での宣言は局所宣言である。 大域宣言や局所宣言を処理するためには、関数定義やブロックに入ったときにシンボルテーブルを プッシュし、出たときにポップすればよい。

前節までの例では、構文解析をしながら、ある構文を認識したら直ちにそれのHIRノードを作成するようにしていた。それが簡単にできるならば、一番手っ取り早いし、分かりやすいからである。 しかし、関数の宣言に関しては、関数のプロトタイプ宣言と関数定義があり、 その前半の形（f_head）は同じ構文規則で定義されているので、その方式が簡単ではなくなる。

そこで、非終端記号f_headに対応するクラスFHeadを作り、f_headの構文解析の結果はFHeadオブジェクトとして表現し ておいて、それがプロトタイプ宣言であるのか、関数定義の初めであるのかが分かった時点で その意味解析を行っている。

プロトタイプ宣言の場合は、その関数のシンボルを現在のシンボルテーブルに登録し、 戻り値の型、仮引数の型のリスト、引数の数は固定か否か、の情報をその関数の 型として関数のシンボルに付ける。

関数定義の場合は、まず、 プロトタイプ宣言がなかったときは新たに関数シンボルを作り、宣言があったときは、宣言時の関数シンボルを使う。 次に、シンボルテーブルをプッシュしてその関数のシンボルテーブルを作り、 関数定義のシンボルを作る（現在の実装では関数の戻り値の型だけは最初にセットしておく必要がある）。

その後、仮引数の名前と型を関数シンボルに登録する。 プロトタイプ宣言があったときは、プロトタイプ宣言と関数定義での引数の数を比較する。

最後に、関数の定義ノードを作ってそれをprogramRootに追加する。

その後、関数定義の中の変数宣言が処理され、ステートメントが処理されてblockとしてまとめられ、そのblockを関数定義の本体としてセットする。

関数呼出しの処理の方法は特に説明しなくても分かるであろう。実引数と仮引数の対応のチェックは、ここでは簡単にその個数だけを比較している。

なお、宣言されていない関数を呼び出した場合は、その呼出しを整数定数１で置き換えている。よく使われそうな定数は初期設定でシンボルテーブルに入れてある。それを使うには「symRoot.intConst1」のように書けばよい。

なお、Byaccでは

func_def : type_spec f_head '{'  {  $<SubpDefinition>$  = makeFuncDef($1, $2);} 
             decl_list                    
             s_list '}'        { setFuncBody($<SubpDefinition>4 , $6); popTable(); }
         ;

　　$<SubpDefinition>$  = ...

　　(SubpDefinition)yyVal  = ...

func_def : type_spec f_head '{'  {  $$  = makeFuncDef($1, $2);} 
             decl_list                    
             s_list '}'        { setFuncBody($<SubpDefinition>4 , $6); popTable(); }
         ;

4. コンパイラ作成例（その４：データ型と配列）

この例でも、lexerとparserは、それぞれJFlexとjayという生成系を使って生成し、コンパイラドライバとしては前節の例のSimpleDriver.javaをそのまま使う。言語は前節の言語の拡張になっているから、JFlex用のファイルsimple3.lを拡張したsimple4.l、jay用のファイルsimple3.yを拡張したsimple4.y、の２つのファイルを作成するだけで、拡張された言語のコンパイラができ上がる。

4.1 文法

<program> ::= <global_declarations>
<global_declarations> ::= empty
           | <global_declarations> <declaration> ';'
           | <global_declarations> <function_def> ';'
<declaration> ::= <type_spec> <declarator>
           | <type_spec> <function_head>
           | <declaration> ',' <declarator>
           | <declaration> ',' <function_head>
<type_spec> ::= <type>
           | 'static' <type>
<type> ::= 'void' | 'int' | 'double'
<declarator> ::= ident <dimension_list>
<dimension_list> ::= empty
           | '[' ']' <dimension_list>
           | '[' number ']' <dimension_list>
<param_list> ::= empty
           | <param_decl>
           | <param_list> ',' <param_decl>
<param_decl> ::= <type> <declarator>
           | <type> '&' <declarator>
<function_head> ::= ident '(' <param_list> ')'
<function_def> ::= <type_spec> <function_head> <block> 
<block> ::= '{' <declaration_list> <statement_list> '}'
<declaration_list> ::= empty 
           | <declaration_list> <declaration> ';'
<statement_list> ::= <statement>
           | <statement_list> <statement>
<assign> ::= ident '=' <expression>
           | ident <subscript_list> '=' <expression>
<opt_assign> ::= empty
           | <assign>
<statement> ::= <block>
           | 'return' ';'
           | 'return' <expression> ';'
           | <assign> ';' 
           | empty ';'
           | 'read' ident ';' 
           | 'write' <expression> ';' 
           | <if_part>
           | <if_part> 'else' <statement>
           | 'while' '(' <expression> ')' <statement>
           | 'do' <statement> 'while' <expression> ';' 
           | 'for' '(' <opt_assign> ';' <test_exp> ';' <opt_assign> ')' <statement>
           | 'switch' '(' <expression> ')' '{' <case_list> <default_case> '}' 
           | 'break' ';' 
           | 'continue' ';' 
<case_list> ::= <case_item>
           | <case_list> <case_item>
<case_item> ::= 'case' number ':'
           | <case_item> <statement>
<default_case> ::= empty
           | <default_item>
<default_item> ::= 'default' ':'
           | <default_item> <statement>
<if_part> ::= 'if' '(' <expression> ')' <statement>
<test_exp> ::= empty
           | <expression>     
<expression> ::= <expression1> '||' <expression1>
           | <expression1>
<expression1> ::= <expression2> '&&' <expression2>
           | <expression2>
<expression2> ::= <expression3> <relational_op> <expression3> 
           | <expression3> 
<relational_op> ::= '<' | '<=' | '==' | '!=' | '>=' | '>'
<expression3> ::= <expression3> '+' <term>
           | <expression3> '-' <term>
           | <term> 
<term> ::= <term> '*' <factor>
           | <term> '/' <factor>
           | <term> '%' <factor>
           | <factor>  
<factor> ::= '-' <factor>
           | '!' <factor> 
           | '(' <expression> ')'
           | ident '(' <argument_list> ')'
           | ident <subscript_list>
           | ident
           | number
           | string
           | character
           | real_number
<subscript_list> ::= '[' <expression> ']'
           | '[' <expression> ']' <subscript_list>
<argument_list> ::= empty
           | <expression>
           | <argument_list> <expression>
 

4.2 Parser

Parserはjayのプログラムsimple4.yから生成される。その際、１つのshift/reduceコンフリクトを指摘されるが、それは前節と同様にif文のdangling elseによるものである。

引数に参照渡し（call by reference）も使えるようにした。仮引数宣言で"&"をつけると参照渡しになる。配列は常に参照渡しとする。配列の書き方はCのそれと同じである。

今回の例では、宣言の形や配列の添字の形が複雑になってきたので、構文解析と同時にシンボルやHIRを作るのが簡単ではない。そこで、構文解析の結果をある程度まとめておいてから、まとめてHIRノードを作成するようにした。具体的には、非終端記号type_spec、declatr、dim_list、sub_listを認識した結果を、それぞれクラスTypeSpec、Declatr、DimList、SubListのオブジェクトとして作っておいてからHIRノードを作成するようにした。

なお、データ型の種類が増えたので、型のチェックをするようにした。int型からdouble型への自動変換もするようにした。それらの型にはrankが設定されているので（Type.KIND_RANKS[]）、getTypeRankメソッドによってそれをとりだし、自動変換はrankの大きいほうに向かってするようにしている。