0. はじめに
1. PL/0'コンパイラ（関数のネストなし）
   1. PL/0'の文法
   2. PL0Driver.java
   3. Lexer/Parser
   4. コンパイラの実行結果
   5. コンパイル過程の可視化
2. PL/0'コンパイラ（関数のネストあり：その１）
   1. PL/0'の文法
   2. Lexer/Parser
3. PL/0'コンパイラ（関数のネストあり：その２）
   1. PL/0'の文法
   2. Lexer/Parser

０．はじめに

以下では、PL/0'言語の例によって、このようなコンパイラの開発の仕方を示すことにする。コンパイラの開発の仕方を示したもう一つのページではyaccのJava版を使った方法を示したが、ここではrecursive descent parserを生成するJavaCCを使った例を示す。

１．PL/0'コンパイラ（関数のネストなし）

  　　中田育男著「コンパイラ」オーム社、1995

ここでは、そのコンパイラのフロントエンドはJavaCCという生成系を使って生成し、コンパイラドライバPL0Driver.javaによってそれを駆動することにする。JavaCC用のファイルpl0.jjとPL0Driver.javaの２つのファイルを作成するだけで、PL/0'コンパイラができ上がる。ターゲットマシンはPL0Driverを呼び出すときの オプションで指定出来る。たとえば、"target=x86"と指定すれば、x86の機械語コードを生成する PL/0'コンパイラができ上がる。

JavaCCでは、字句規則と構文規則を一つのファイルに記述する。構文規則は、recursive descent parser を記述するような形で書けばよく、その構文規則の途中に意味規則を書いていけばよい。 各非終端記号には一つのrecursiveな関数が対応する。 （JavaCCの簡単な説明は、ここ にある）

yaccのようなLRパーサ生成系では、基本的には合成属性しか使えず、相続属性が書きにくい。 それに対して recursive descent parserでは、相続属性は非終端記号に対応する関数の引数とすればよい。 さらに、recursive descent parserとする場合は、構文規則を正規右辺文法の形で書くことが出来るので、 圧縮した形で書くことが出来る。

もう一つのページでyaccのJava版を取り上げた理由は、 yaccがすでに広く使われていて、それで使える文法が蓄積されていること、カバーする文法の範囲が広いこと、 Fortranの文法をyaccで書いたものがあったこと（それを少し修正したものをもとにしてFortranコンパイラも書いている）、である。

1.1 PL0'の文法

<program> ::= <block> '.'
<block> ::=  ( <declaration> )* <statement>
<declaration> ::= <const_decl> | <var_decl> | <func_decl>
<const_decl> ::= 'const' <const_def> ( ',' <const_def> )* ';'
<const_def> ::= ident '=' number
<var_decl> ::= 'var' ident ( ',' ident )* ';'
<func_decl> ::= 'function' ident '(' [ ident ( ',' ident )* ]  ')' <block> ';'
<statement> ::= [ ident ':=' <expression>
             | 'begin' <statement> ( ';' <statement> )* 'end'
             | 'if' <condition> 'then' <statement>
             | 'while' <condition> 'do' <statement>
             | 'return' <expression>
             | 'write' <expression>
             | 'writeln' ]
<condition> ::= 'odd' <expression>
             | <expression> ( '=' | '<>' | '<" | '<=' | '>' | '>=' ) <expression>
<expression> ::= [ ( '-' | '+' ) ] <term> ( ( '-' | '+' ) <term> )*
<term> ::= <factor> ( ( '*' | '/' ) <factor> )*
<factor> ::= ident '(' [ <expression> ( ',' <expression> )* ] ')'
             | number
             | ident
             | '(' <expression> ')'

1.2 PL0Driver.java

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

　　　$ java PL0Driver -coins:trace=HIR.1,target=sparc mult.p

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

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

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

       p,     PL0,       PL0 source,        -,s,o

       $HOME/coins/suffixes

       C:¥Documents and Settings¥yourname¥coins¥suffixes

goメソッドから呼び出されるパスには、preprocess、compile、assemble、linkがあり、それらのパスですることは標準のDriverに書かれているが、それとは違うことをする場合はそれをPL0Driverに書いておく必要がある。

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

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

1.3 Lexer/Parser

PL0Driverで使われているLexer/Parserは JavaCCを使って生成してある。 JavaCCはJavaで書いてあり、Javaの使えるマシンならそれを 使うことが出来る。日本語の簡単なチュートリアルもある。

PL0Parser.javaは、

　　$ javacc pl0.jj

PL/0'言語の各機能は、ほとんどそのままHIRで表現できるので、pl0.jjの記述はHIRの各メソッドの 使い方が分かれば簡単である。

なお、PL/0'言語では関数のネストが許され、HIRでもそれをそのまま 表現できるようにはなっているが、LIRではネストした関数が表現できるようにはなっていないので、 この節のPL/0'コンパイラでは関数のネストがあるとエラーとするようになっている。

以下、pl0.jjの内容を順次見ていく。先頭の

 
 　　STATIC=false;

 　　PARSER_BEGIN(PL0Parser)

　　 PARSER_END(PL0Parser)

　　public class PL0Parser {

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

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

　　hir = (HIR0)hirRoot.hir;

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

なお、関数の型（SubpType）を作るときは、引数の型のリストを作る必要がある。printfの第１引数の型としてpointer to char型を指定しているが、 第２引数以降は一定ではないので、 そのことをprintSym.setOptionalParam();で指定している。 定数"%d"などはprintfの第１引数として使われる定数である。

その次にトークンの定義が続く。JavaCCでは、一般的に先に書かれた定義が優先されるので、 IDENTの定義はキーワードの定義の後にしてある。

それ以後に構文規則とそれに付随した意味規則が続く。最初の例（行番号は説明のためにつけてある） でその書き方の説明をする。

1:void program() : 
2:{
3:	Subp mainSubp;
4:	BlockStmt mainBlock;
5:}
6:{ 	{ 
7:	  mainSubp = sym.defineSubp("main".intern(), symRoot.typeVoid);
8:	  mainSubp.setVisibility(Sym0.SYM_PUBLIC);
9:	  SymTable lSymTable = symRoot.symTableCurrent.pushSymTable(mainSubp);
10:	  mainSubp.closeSubpHeader(); 
11:	}
12:mainBlock = block(0) "." 
13:	{ 
14:	  SubpDefinition mainSubpDef = 
15:			hir.subpDefinition(mainSubp, symRoot.symTableCurrent);
16:	  mainSubpDef.setHirBody(mainBlock);
17:	  ((Program)hirRoot.programRoot).addSubpDefinition(mainSubpDef);
18:	}
19:}

　　program → block "."

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

String型の文字列に対してinternメソッドを呼んでいるのは、coinsでは、文字列の比較にはequalsメソッドではなく、「==」を使っているからである。

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

　　sym = (Sym0)symRoot.sym;

9行目で、main用のシンボルテーブルを作っている。 シンボルテーブルは新しいスコープに入る/出るときにpush/popする必要がある。10行目でシンボルとしての mainSubpの定義が完成する。

14行から17行までは、HIRのノードを作るための文である。サブプログラムmainSubpの定義のノードmainSubpDefを作って、16行目でそれに本体のブロックを付加し、17行目でそれをルートのノードにつけている。

JavaCCでの書き方がわかれば、これ以後の部分についてあまり説明しなくても分かると思われるが、 ここで、エラーメッセージの出力のために用意されているメソッドについて説明する。
たとえば

　　ioRoot.msgRecovered.put("undeclared " + t.image ); 

なお、JavaCCはLL(k)文法を扱うことが出来るが、デフォールトではlookaheadは１つしかしていない。 したがって、LL(1)文法になっていない部分についてはlookaheadの仕方を指定する必要がある。 PL/0'の文法では、非終端記号factorについて2トークンのlookaheadが必要であるので、 factorメソッドでそれを指定している。

1.4 コンパイラの実行結果

-----ソースプログラムmult.p-----

 function multiply(x, y)
     var a,b,c;
    begin
      a:=x; b:=y; c:=0;
      while b>0 do
        begin
          if odd b then c:=c+a;
          a:=2*a; b:=b/2;
        end;
      return c;
    end; 

const m=7,n=85;
var x,y;

begin
  x:=m; y:=n; 
  write x; write y; writeln; write multiply(x,y); writeln
end.

このHIRツリーには説明のためのコメントがつけてある。また、ステートメント に対応する場所にはソースの行番号が入っているが、これは
　　-coins:trace=HIR.1
で出力されるHIRツリーには入っていない。行番号の入ったHIRツリーを プリントするためには、たとえば、PL0Driver.javaの最後の部分で
　　hirRoot.programRoot.print(0, true);
とすれば良い。なお、可視化ツールCoVisでは行番号が見やすく表示される。
なお、シンボルテーブルは
　　-coins:trace=Sym.1
を指定すれば出力される。HIR.1とSym.1の両方を指定する時は
　　-coins:trace=HIR.1/Sym.1
とすればよい。

--------目的コードmult.s--------

      .section      ".text"
      .align      4
multiply.2:
      save      %sp,-96,%sp
.L2:
      mov      0,%i2
.L3:
      cmp      %i1,0
      ble      .L8
      nop      
.L4:
      and      %i1,1,%i3
      cmp      %i3,1
      bne      .L6
      nop      
.L5:
      add      %i2,%i0,%i2
.L6:
      sll      %i0,1,%i0
      mov      2,%o1
      mov      %i1,%o0
      call      .div
      nop      
      mov      %o0,%i1
      ba      .L3
      nop      
.L8:
.L9:
      mov      %i2,%i0
      ret
      restore

      .align      1
string.13:
      .byte      37
      .byte      100
      .byte      0
      .align      1
string.16:
      .byte      10
      .byte      0

      .align      4
      .global      main
main:
      save      %sp,-96,%sp
.L11:
      mov      7,%i0
      mov      85,%i0
      sethi      %hi(string.13),%o0
      or      %o0,%lo(string.13),%o0
      mov      7,%o1
      call      printf
      nop      
      sethi      %hi(string.13),%o0
      or      %o0,%lo(string.13),%o0
      mov      85,%o1
      call      printf
      nop      
      sethi      %hi(string.16),%o0
      or      %o0,%lo(string.16),%o0
      call      printf
      nop      
      mov      7,%o0
      mov      85,%o1
      call      multiply.2
      nop      
      mov      %o0,%o1
      sethi      %hi(string.13),%o0
      or      %o0,%lo(string.13),%o0
      call      printf
      nop      
      sethi      %hi(string.16),%o0
      or      %o0,%lo(string.16),%o0
      call      printf
      nop      
.L12:
      ret
      restore

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

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

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

2．PL/0'コンパイラ（関数のネストあり：その１）

ところで、実行時に内側の関数から外側の関数のローカル変数にアクセスするためには、 ローカル変数が実行時フレームに入っているとすれば、そのフレームにアクセス する手段が必要になる。しかし、LIRにはそのようなものを直接表現する機能は 用意されていない。

そこで、ここでは、それを実現する一つの方法として、実行時フレームに相当するものをＣ言語の structに相当する形で作っておいて、それへのポインタをグローバル変数として用意し、 それを通してアクセスすることにした。

具体的には、たとえば

var x,y;
function abc(z)
　　var a, b;
　　function fgh(w)
　　　　var u;
　　　　begin
　　　　　　u := x+a+z;
　　　　　　return u+w
　　　　end;
　　begin
　　　　a:=z+x;
　　　　return fgh(a)
　　end;
x:=abc(y)
. 

void *display_0;
void *display_1;
void *display_2;

struct main_frame{
    int x; int y;
};

struct abc_frame{
    int z; int a; int b;
};

struct fgh_frame{
    int w; int u;
};

int fgh(int w){
  struct fgh_frame frame_; 
  void *saveDisplay_;
  int ret_val_var;
  saveDisplay_ = display_2;
  display_2 = &frame_;
  frame_.w = w;
  frame_.u = (((struct main_frame *)display_0) -> x) 
            + (((struct abc_frame *)display_1) -> a)
            + (((struct abc_frame *)display_1) -> z);
  ret_val_var = frame_.u + frame_.w;
  display_2 = saveDisplay_;
  return ret_val_var;
  display_2 = saveDisplay_;
  return 0;
}

int abc(int z){
  struct abc_frame frame_; 
  void *saveDisplay_;
  int ret_val_var;
  saveDisplay_ = display_1;
  display_1 = &frame_;
  frame_.z = z;
  frame_.a = frame_.z + (((struct main_frame *)display_0) -> x);
  ret_val_var = fgh(frame_.a);
  display_1 = saveDisplay_;
  return ret_val_var;
  display_1 = saveDisplay_;
  return 0; 
}

main(){
  struct main_frame frame_;
  void *saveDisplay_;
  saveDisplay_ = display_0;
  display_0 = &frame_;
  frame_.x = abc(frame_.y);
  display_0 = saveDisplay_;
  return 0;
}

2.1 PL0'の文法

文法の変更点は以下の部分だけである。

<block> ::=  ( <decl> )* ( <func_decl> )* <statement>
<decl> ::= <const_decl> | <var_decl>

2.2 Lexer/Parser

Lexer/Parserは JavaCCを使って記述してあり、PL0Parser.javaは、

　　$ javacc pl02.jj

3．PL/0'コンパイラ（関数のネストあり：その２）

そこで、ここでは、それを実現するもう一つの方法として、 関数型言語の実現の際に使われている、ラムダ・リフティング（λlifting）という 方法を使うことにした。 この方法は、内側の関数で使われているグローバル変数（外側の関数のローカル変数） を、内側の関数への引数として渡す方法である。

その場合、HIRでは引数は値呼び出し（call by value）であるが、もとの プログラムでは外側の関数の変数への代入もあり得るから、引数としては アドレス呼び出し（call by address）にする必要がある。 具体的には、たとえば

var x,y;
function abc(z)
　　var a, b;
　　function fgh(w)
　　　　var u;
　　　　begin
　　　　　　u := x+a+z;
　　　　　　return u+w
　　　　end;
　　begin
　　　　a:=z+x;
　　　　return fgh(a)
　　end;
x:=abc(y)
. 

main(){
    int x,y;
    x = abc(y, &x);
}

int abc(int z, int *x){
    int a, b;
    a = z + *x;
    return fgh(a, x, &a, &z);
}

int fgh(int w, int *x, int *a, int *z){
    int u;
    u = *x + *a + *z;
    return u+w;
}

PL/0'はワンパスでコンパイルできるように考えられている言語で、関数を呼び出す前に はその関数の宣言がなければならないから、一般的な相互再帰はないが、 内側の関数から、それを含む外側の関数を呼び出すことによって、その二つの関数は 相互再帰になる。従って、外側の関数を再帰的に呼び出すことによって引数が追加され得る ことに対処する必要がある。

3.1 PL0'の文法

2.1では、PL0'の文法に少し制限を加えたが、ここではその必要はない。 文法は1.1の文法のままとした。

3.2 Lexer/Parser

Lexer/Parserは JavaCCを使って記述してあり、PL0Parser.javaは、

　　$ javacc pl03.jj

実現に当たっては、１，２節の場合と同じように、ワンパスでHIRを作成する方法をとった。 しかし、関数の引数はワンパスでは決まらない。そこで、最初は、引数が未定のままSymの SubpとHIRの SubpDefinitionを作ってしまって、後でその型（引数の個数と型）を変更することを考えたが、 HIRでは、ノードを作るときにそのノードの型は決定しているものと決めているので、その方法は 使えない。

結局、ワンパスでHIRを作成するときは、ダミーのSubpシンボルとSubpDefinitionノード を作っておいて、 後で引数が確定したときに本当のSubpとSubpDefinitionを作って置き換えることとし、 その後で、関数呼び出しのHIRノードも作り直すことにした。