SmallPascalコンパイラ

■SmallPascalコンパイラ

1. SmallPascalの概要

2. 文法の記述

3. パーサの生成

2006年6月19日 14:04 更新

1. SmallPascalの概要

簡単なSmallPascalコンパイラ（翻訳・コード生成プログラム）をSableCCを用いて作成する。

【使用上の注意】
対象としているPascalのサブセット（SmallPascal）は、SableCCプロジェクトが評価用サンプルプロジェクトとして配布している SmallPascal.grammar を利用したものである。ライセンス／配布条件等についてはこのLGPL文書を参照のこと。

なお、full-set仕様のP4コード生成Pascalコンパイラについては、ここから参照されたい。
Pascal-S/P4-code Compiler (http://www.ulis.ac.jp/￣nakai/)

1.1 SmallPascal言語の仕様
 1.2 SmallPascal言語のプログラム例

1.1 SmallPascal言語の仕様

ここで対象としているPascalのサブセット（以下、SmallPascalと呼ぶ）は、以下のようなデータ型と演算子、変数と代入、予約語、プログラム制御、ならびに組み込み関数（built-in function）を有するものである。

A. データ型と演算子

・定数は０を含む正整数とする
・数値演算可能なデータ型は、整数型とする
・数値演算子は、加減乗除（'+','-','*','div'）の４種類とする
・数値演算式は、括弧（'(',')'）を用いることができる
・数値演算子と括弧の優先順位は考慮する
・数値演算の結果は、整数値を返す。

B. 変数と代入

・変数の型宣言は必要（var）
・代入前の変数の値は不定とする
・変数への式評価値の代入は、代入記号 ':=' を用いて行う

C. 予約語

・演算子と括弧 '+','-','*','div','(',')'
・コメント文括弧 '{','}'
・代入記号 ':='
・プログラム構造 'program','begin','end'
・変数型宣言 'var', 'integer'
・組み込み関数名 'writeln'
・セパレータ ',',':',';','.'

D. 変数型宣言

・変数の型宣言は、'program ... ;'から'begin'の間に記述する
・var 変数名 : integer; という書式で型宣言する

E. プログラム制御

・'begin'から'end''.'までの範囲を順番に実行する。
・各命令の終わりは　セミコロン ';'　である
・プログラム終端（.）に達したら、プログラムは終了する

F. 組み込み関数

・関数名 writeln　引数数値演算式
　式の値を、標準出力へ表示する

G. コメント行

・'{' .... '}' で囲まれた部分は、コメントである

1.2 SmallPascal言語のプログラム例

例１：整数値リテラルの表示 (test0.pas)

program test0;

begin 
  writeln(32); 
end.

例２：変数を用いた加算と表示 (test1.pas)

program test1;
var x, y : integer;

begin 
  x := 3;
  y := 5;
  writeln(x + y); 
end.

例３：変数を用いた括弧付き加算／乗算と表示 (test2.pas)

program test2;
var x, y, z : integer;

begin 
  x := 3;
  y := 5;
  z := 4;
  writeln( ( x + y ) * z ); 
end.

2. 文法の記述

SmallPascal言語の文法について、以下に示す。

＜SmallPascal言語の文法＞

記号の定義

        l_curly_bracket = '{' コメント用左括弧
        r_curly_bracket = '}' コメント用右括弧
        ascii_char = ASCIIキャラクタコードの有効文字範囲

        letter = 英文字 ('a'..''z' + 'A'..'Z')
        digit  = 数字 ('0'..'9')
        tab = TABタブコード (9);
        cr  = CR改行コード (13);
        lf  = LF改行コード (10);
 
 
終端記号

  ・プログラム構造
        'program','begin','end'

  ・変数型宣言
        'var', 'integer'

  ・組み込み関数名
        'writeln'

  ・演算子と括弧
        plus  = '+'
        minus = '-'
        mult  = '*'
        div   = 'div'
        l_paren = '('
        r_paren = ')'

  ・代入記号
        assignop = ':='

  ・セパレータ
        comma = ','
        colon = ':'
        semicolon = ';'
        dot = '.'

　・変数名、リテラル
        identifier = 英文字で開始し２文字目以降が英文字あるいは数字の列
        number     = 数字が１文字以上の列

　・コメント
        comment = '{' .... '}' で囲まれた文字列


非終端記号

　・プログラム構造
        Program, Program_heading

　・変数型宣言部
        Declarations
        Variables_declaration, Variables_definition_list
        Variables_definition, Identifier_list, Type

　・プログラム本体
        Body
        Statement_sequence, Statement
        
　・数値演算式
		Expression, Term

　・リテラル、変数、括弧付き式の評価値
        Factor

開始記号
        Program


生成規則：
    (1)  Program → Program_heading Declarations Body '.'
    (2)  Program_heading → 'program' identifier ';'

    (3)  Declarations → Variables_declaration?
    (4)  Variables_declaration → 'var' Variables_definition_list
    (5)  Variables_definition_list → Variables_definition
    (6)  Variables_definition_list → Variables_definition_list
                                      variables_definition
    (7)  Variables_definition → Identifier_list ':' Type ';'
    (8)  Identifier_list → identifier
    (9)  Identifier_list → Identifier_list ',' identifier
   (10)  Type → 'integer'

   (11)  Body → 'begin' Statement_sequence 'end'
   (12)  Statement_sequence → Statement
   (13)  Statement_sequence → Statement_sequence ';' Statement
   (14)  Statement → 'writeln' '(' Expression ')'
   (15)  Statement → identifier ':=' Expression
   (16)  Statement → empty

   (17)  Expression → Term
   (18)  Expression → Expression '+' Term
   (19)  Expression → Expression '-' Term

   (20)  Term → Factor
   (21)  Term → Term '*' Factor
   (22)  Term → Term 'div' Factor

   (23)  Factor → identifier
   (24)  Factor → number
   (25)  Factor → '(' Expression ')'

3. パーサの生成

3.1 文法ファイル（pascal.grammar）
3.2 pascal.grammarの説明
 3.3 SableCCによる構文解析器の生成とテスト

3.1 文法ファイル（pascal.grammar）

2. SmallPascalの文法の定義に基づいて、SableCC用 pascal.grammar 文法ファイルを作成する。
（説明上、左端に行番号を付した。実際の文法ファイル中に行番号は付されていない）

＜文法ファイル：pascal.grammar＞

    14  Package org.sablecc.pascal; // package name
    15
    16  Helpers

           ....中略....

    40    l_curly_bracket = '{' ;
    41    r_curly_bracket = '}' ;    
    42    ascii_char = [32 .. 127] ;
    43
    44    // letters and digits
    45    letter = [['a' .. 'z'] + ['A' .. 'Z']];
    46    digit = ['0' .. '9'] ;
    47
    48    // un-printable characters
    49    tab = 9 ;
    50    cr = 13 ;
    51    lf = 10 ;
    52    blank = ' ' ;
    53
    54  Tokens

           ....中略....

    67    // arithmetic symbols
    68    plus = '+' ;
    69    minus = '-' ;
    70    mult = '*' ;
    71    assignop = ':=' ;
    72      
    73    // symbols separators
    74    comma = ',' ;
    75    colon = ':' ;
    76    semicolon = ';' ;
    77    dot = '.' ;
    78    l_paren = '(' ;
    79    r_paren = ')' ;
    80
    81    // identifiers
    82    identifier = letter (letter | digit)* ;
    83
    84    // numbers
    85    number = digit+ ; // integer numbers only
    86
    87    // comments
    88    comment = l_curly_bracket [ascii_char - [l_curly_bracket +
                                                  r_curly_bracket]]*
    89              r_curly_bracket ;
    90
    91    // blanks 
    92    blanks = blank | cr lf | cr | lf | tab ;
    93
    94  Ignored Tokens
    95    comment, 
    96    blanks ;
    97
    98  Productions
    99
   100    program =
   101      program_heading
   102        declarations
   103      body
   104      dot ;
   105
   106    program_heading =
   107      // program must be prefixed with T. because there is 
                                    a token and a production with
   108      // the same name
   109      T.program identifier semicolon ;
   110
   111    // declarations
   112
   113    declarations = 
   114      variables_declaration? ;
   115
   116    variables_declaration =
   117      var variables_definition_list ;
   118
   119    variables_definition_list =
   120      {single} variables_definition |
   121      {multiple} variables_definition_list variables_definition ;
   122
   123    variables_definition =
   124      identifier_list colon type semicolon ;
   125
   126    identifier_list =
   127      {single} identifier |
   128      {multiple} identifier_list comma identifier ;
   129
   130    type =
   131      integer ; // only data type allowed is the integer data type
   132
   133    // body definition
   134    body =
   135      begin
   136        statement_sequence
   137      end ;
   138
   139    // statements
   140    statement_sequence =
   141      {single} statement |
   142      {multiple} statement_sequence semicolon statement ;
   143
   144    statement =
   145      {writeln} writeln l_paren expression r_paren |
   146      {assignment} identifier assignop expression |
   147      {empty} ;
   148
   149    // expressions
   150
   151    expression =
   152      {term} term |
   153      {plus} expression plus term |
   154      {minus} expression minus term ;
   155
   156    term =
   157      {factor} factor |
   158      {mult} term mult factor |
   159      {div} term div factor ;
   160
   161    factor =
   162      {identifier} identifier |
   163      {number} number |
   164      {expression} l_paren expression r_paren;
   165
   166  // end of grammar.

3.2 pascal.grammarの説明

14行目（Packageディレクティブ）

パッケージ名を指示している。これは org.sablecc.pascal パッケージである。

16--52行目（Helpersディレクティブ）

字句規則ならびに構文規則中で使用する記号の定義（マクロ）を行っている。
各記号の意味は、2.文法を参照のこと。

54--92行目（Tokensディレクティブ）

字句規則を指定している。
各記号の意味は、2.文法を参照のこと。

94--96行目（Ignored Tokensディレクティブ）

字句解析時に無視するトークンを指定している。
ここでは　blank ならびに comment を指定している。

98-166行目（Productionsディレクティブ）：

構文規則を指定している。
各生成規則の意味は、2.文法を参照のこと。

3.3 SableCCによる構文解析器の生成とテスト

pascal.grammar試験用プロジェクトファイルをビルドして、SableCCによる構文解析器を生成してみよう。

SmallPascalプロジェクトファイルはここからダウンロード（smallpascal-src.tar.gz）
ビルド済みプロジェクトファイルはここからダウンロード（smallpascal-build.tar.gz）

実際に、プログラム例を解析器（pascal.jar）に入力した場合の実行結果を以下に示す。プログラム例は、上記プロジェクトファイルに含まれている。
実行結果は、org.sablecc.pascal.tool.PrintTreeクラスによって、導出木全体を深さ優先探索した結果で表示されている。

実行時には、classpath（-cp）として生成した pascal.jar を指定し、更に、開始時mainメソッドが含まれているクラスとして org.sablecc.pascal.tool.PrintTreeクラスを指定することに注意する。このmainメソッドは、コマンドライン引数の最後として、入力プログラムが格納されたテキストファイルを指定されることを仮定している。詳しくは、PrintTreeクラスのソースファイルを参照のこと。

＜実行結果１：プログラム test0.pas＞

program test0;

begin 
  writeln(32); 
end.

$ java -cp pascal.jar org.sablecc.pascal.tool.PrintTree test0.pas

Small Pascal  (smallpascal)    version 1.0
Copyright (C) 2001 Fidel Viegas (viegasfh@hotmail.com).
All Rights Reserved.

Start
 AProgram
  AProgramHeading
   TProgram: program
   TIdentifier: test0
   TSemicolon: ;
  ADeclarations
  ABody
   TBegin: begin
   AMultipleStatementSequence
    ASingleStatementSequence
     AWritelnStatement
      TWriteln: writeln
      TLParen: (
      ATermExpression
       AFactorTerm
        ANumberFactor
         TNumber: 32
      TRParen: )
    TSemicolon: ;
    AEmptyStatement
   TEnd: end
  TDot: .
 EOF:

＜実行結果２：プログラム test2.pas＞

program test1;
var x, y : integer;

begin 
  x := 3;
  y := 5;
  writeln(x + y); 
end.

$ java -cp pascal.jar org.sablecc.pascal.tool.PrintTree test1.pas

Small Pascal  (smallpascal)    version 1.0
Copyright (C) 2001 Fidel Viegas (viegasfh@hotmail.com).
All Rights Reserved.

Start
 AProgram
  AProgramHeading
   TProgram: program
   TIdentifier: test1
   TSemicolon: ;
  ADeclarations
   AVariablesDeclaration
    TVar: var
    ASingleVariablesDefinitionList
     AVariablesDefinition
      AMultipleIdentifierList
       ASingleIdentifierList
        TIdentifier: x
       TComma: ,
       TIdentifier: y
      TColon: :
      AType
       TInteger: integer
      TSemicolon: ;
  ABody
   TBegin: begin
   AMultipleStatementSequence
    AMultipleStatementSequence
     AMultipleStatementSequence
      ASingleStatementSequence
       AAssignmentStatement
        TIdentifier: x
        TAssignop: :=
        ATermExpression
         AFactorTerm
          ANumberFactor
           TNumber: 3
      TSemicolon: ;
      AAssignmentStatement
       TIdentifier: y
       TAssignop: :=
       ATermExpression
        AFactorTerm
         ANumberFactor
          TNumber: 5
     TSemicolon: ;
     AWritelnStatement
      TWriteln: writeln
      TLParen: (
      APlusExpression
       ATermExpression
        AFactorTerm
         AIdentifierFactor
          TIdentifier: x
       TPlus: +
       AFactorTerm
        AIdentifierFactor
         TIdentifier: y
      TRParen: )
    TSemicolon: ;
    AEmptyStatement
   TEnd: end
  TDot: .
 EOF:

＜実行結果３：プログラム test3.pas＞

program test2;
var x, y, z : integer;

begin 
  x := 3;
  y := 5;
  z := 4;
  writeln( ( x + y ) * z ); 
end.

$ java -cp pascal.jar org.sablecc.pascal.tool.PrintTree test2.pas

Small Pascal  (smallpascal)    version 1.0
Copyright (C) 2001 Fidel Viegas (viegasfh@hotmail.com).
All Rights Reserved.

Start
 AProgram
  AProgramHeading
   TProgram: program
   TIdentifier: test2
   TSemicolon: ;
  ADeclarations
   AVariablesDeclaration
    TVar: var
    ASingleVariablesDefinitionList
     AVariablesDefinition
      AMultipleIdentifierList
       AMultipleIdentifierList
        ASingleIdentifierList
         TIdentifier: x
        TComma: ,
        TIdentifier: y
       TComma: ,
       TIdentifier: z
      TColon: :
      AType
       TInteger: integer
      TSemicolon: ;
  ABody
   TBegin: begin
   AMultipleStatementSequence
    AMultipleStatementSequence
     AMultipleStatementSequence
      AMultipleStatementSequence
       ASingleStatementSequence
        AAssignmentStatement
         TIdentifier: x
         TAssignop: :=
         ATermExpression
          AFactorTerm
           ANumberFactor
            TNumber: 3
       TSemicolon: ;
       AAssignmentStatement
        TIdentifier: y
        TAssignop: :=
        ATermExpression
         AFactorTerm
          ANumberFactor
           TNumber: 5
      TSemicolon: ;
      AAssignmentStatement
       TIdentifier: z
       TAssignop: :=
       ATermExpression
        AFactorTerm
         ANumberFactor
          TNumber: 4
     TSemicolon: ;
     AWritelnStatement
      TWriteln: writeln
      TLParen: (
      ATermExpression
       AMultTerm
        AFactorTerm
         AExpressionFactor
          TLParen: (
          APlusExpression
           ATermExpression
            AFactorTerm
             AIdentifierFactor
              TIdentifier: x
           TPlus: +
           AFactorTerm
            AIdentifierFactor
             TIdentifier: y
          TRParen: )
        TMult: *
        AIdentifierFactor
         TIdentifier: z
      TRParen: )
    TSemicolon: ;
    AEmptyStatement
   TEnd: end
  TDot: .
 EOF:

4. 意味的解析

パーサにより導出木を生成した後、即座にコード生成を行うことは出来ない。入力列が文法に正しく記述されていても、コンパイラによるコード生成以前に、以下のような「意味的解析（Semantic Analisys）」に合格しなければ、正しいコードを生成することが出来ないからである。

今回のSmallPascal言語については、例えば変数の扱いについて、意味的解析のチェックポイントとして以下のようなものが挙げられる。

・同じ変数名で、重複して型宣言を行っていないか（duplication）
・型宣言を行っていない変数名に、値を代入しようとしていないか（left）
・型宣言を行っていない変数名から、値を参照しようとしていないか（right）

これらの解析処理を行う機能モジュールを、意味的解析器（Semantic Analyzer）と呼ぶ。これは、生成された導出木を探索し、各チェックポイントを通過できるか否かを検査するものである。

実際のプログラミング言語では、扱うデータ型が多種に渡り、またプログラム制御構造も様々なものが定義されているので、これよりも沢山なポイントの意味的解析が必要である。

4.1 Visitorによる意味的解析器の実装
 4.2 変数管理表
 4.3 変数型宣言の重複チェック用Visitor
4.4 未宣言変数への代入チェック用Visitor
4.5 未宣言変数からの値参照チェック用Visitor

4.1 Visitorによる意味的解析器の実装

SableCCにて意味的解析プログラム（Semantic Analyzer）を実装するため、DFS探索エンジン（DepthFirstAdapterクラス）への Visitor を実装する。

探索時の変数宣言の有無を管理するため、Hashtableオブジェクトを流用して変数管理表を構成する。次に、変数宣言部、変数への値代入、変数値の参照といった各命令のノードについて、変数宣言の有無を検査するためのVisitorを実装する。

SemanticAnalyzerクラス（ソースファイル）

SemanticAnalyzerクラスのVisitor一覧

4.2 変数管理表

SmallPascalの、各ノードにおける変数管理は、表を用意して行う。

表は、以下を用意する（ハッシュ表の機能を流用）。

・変数管理表（variables）：key 変数名 --> value 変数名

変数の管理操作向けに、２つの操作（セット／読み出し）を用意する。

変数管理用
　セット操作：put (引数変数名, 変数名)
　読み出し　：containsKey (引数変数名)　→ 返り値：宣言済みか否か（論理値）

4.3 変数型宣言の重複チェック用Visitor

変数宣言部において、同じ変数名が重複して宣言されていないかをチェックするVisitorを実装する。

この誤りを含むようなプログラム例と、導出木の変数宣言部分の抜粋を以下に示す。

＜プログラム例４：変数型宣言の重複（2行目がエラー）＞

program error1;
var x, x : integer;
begin 
  x := 3;
  writeln ( x ); 
end.

＜例４：導出木の変数宣言部の抜粋＞

  ADeclarations
   AVariablesDeclaration
    TVar: var
    ASingleVariablesDefinitionList
     AVariablesDefinition
      AMultipleIdentifierList
       ASingleIdentifierList
        TIdentifier: x
       TComma: ,
       TIdentifier: x
      TColon: :
      AType
       TInteger: integer
      TSemicolon: ;

重複チェックのために、ここでは、AMultipleIdentifierList の各childについて、Identifier が現れる度に、変数管理表をチェックし、それ以前に宣言が行われているか否かを検査する。
・重複宣言の場合には、解析エラーとする。
・未宣言の場合には、変数管理表へ登録する。

以下、DepthFirstAdapterクラスを継承した Visitor側 SemanticAnalyser.java における、outAMultipleIdentifierListメソッド（Visitor側）の抜粋を以下に示す。

SemanticAnalyser :: outAMultipleIdentifierListの抜粋

  public void outAMultipleIdentifierList(AMultipleIdentifierList node) {

    String key = node.getIdentifier().getText().toUpperCase();

    if (table.containsKey(key)) {
      error(0, node.getIdentifier()); // generate an error
    }
    else { // this is a new one, then
      table.put(key, key); // put the identifier in the table
    }

  }

具体的には、変数宣言部のノードに到達した後、Identifierの文字列を getIdentifier().getText() によって取得し、これと同じキーが、変数管理表に存在するか否かを、 containsKey(key) によってチェックする。重複宣言の場合には、解析エラーとする。未宣言の場合には、変数管理表へ put(key) によって登録する。

4.4 未宣言変数への代入チェック用Visitor

型宣言を行っていない変数名に、値を代入しようとしていないかをチェックするVisitorを実装する。

この誤りを含むようなプログラム例と、導出木の変数代入部分の抜粋を以下に示す。

＜プログラム例５：未宣言変数への代入（4行目がエラー）＞

program error2;
var y : integer;
begin 
  x := 3;
  writeln ( x ); 
end.

＜例５：導出木の変数代入部の抜粋＞

     ASingleStatementSequence
      AAssignmentStatement
       TIdentifier: x
       TAssignop: :=
       ATermExpression
        AFactorTerm
         ANumberFactor
          TNumber: 3
     TSemicolon: ;

変数代入時の未宣言チェックのために、ここでは、AAssignmentStatement の各childについて、[left] Identifier が現れる度に、変数管理表をチェックし、それ以前に宣言が行われているか否かを検査する。未宣言の場合には、解析エラーとなる。

以下、DepthFirstAdapterクラスを継承した Visitor側 SemanticAnalyser.java における、outAAssignmentStatementメソッド（Visitor側）の抜粋を以下に示す。

SemanticAnalyser :: outAAssignmentStatementの抜粋

  public void outAAssignmentStatement(AAssignmentStatement node) {

    String key = node.getIdentifier().getText().toUpperCase();

    if (!table.containsKey(key)) {
      error(1, node.getIdentifier());
    }

  }

具体的には、変数代入部のノードに到達した後、[left] Identifierの文字列を getIdentifier().getText() によって取得し、これと同じキーが、変数管理表に存在するか否かを、 containsKey(key) によってチェックする。未宣言の場合には、解析エラーとする。

4.5 未宣言変数からの値参照チェック用Visitor

型宣言を行っていない変数名から、値を参照しようとしていないかをチェックするVisitorを実装する。

この誤りを含むようなプログラム例と、導出木の変数参照部分の抜粋を以下に示す。

＜プログラム例６：未宣言変数からの値参照（5行目がエラー）＞

program error3;
var y : integer;
begin 
  y := 3;
  y := x;
  writeln ( y ); 
end.

＜例５：導出木の変数代入部の抜粋＞

      AAssignmentStatement
       TIdentifier: y
       TAssignop: :=
       ATermExpression
        AFactorTerm
         AIdentifierFactor
          TIdentifier: x
     TSemicolon: ;

変数参照時の未宣言チェックのために、ここでは、AIdentifierFactor の各childについて、[right] Identifier が現れる度に、変数管理表をチェックし、それ以前に宣言が行われているか否かを検査する。未宣言の場合には、解析エラーとなる。

以下、DepthFirstAdapterクラスを継承した Visitor側 SemanticAnalyser.java における、outAIdentifierFactorメソッド（Visitor側）の抜粋を以下に示す。

SemanticAnalyser :: outAIdentifierFactorの抜粋

  public void outAIdentifierFactor(AIdentifierFactor node) {

    String key = node.getIdentifier().getText().toUpperCase();

    if (!table.containsKey(key)) {
      error(1, node.getIdentifier());
    }

  }

具体的には、変数参照部のノードに到達した後、[right] Identifierの文字列を getIdentifier().getText() によって取得し、これと同じキーが、変数管理表に存在するか否かを、 containsKey(key) によってチェックする。未宣言の場合には、解析エラーとする。

5. コード生成

意味的解析の検査に合格した後、ターゲットに見合ったコード生成処理を行う。コード生成の方法は、ターゲットに応じて以下の２種類に大別される。

・ターゲットとなるプロセッサ用の機械語を直接生成する
・ターゲットとなるプロセッサ用のアセンブリコードを生成する

後者の場合、生成したアセンブリコードを更にアセンブラに通して、最終的な機械語に変換する必要がある。しかし、この方法の場合、対象となるプロセッサ（あるいは仮想マシン）用のアセンブラの（マクロ）記述能力、あるいはプロセッサ上で稼働しているOSや、仮想マシン自体のランタイムライブラリが充実している場合に、元のプログラム表現からの変換処理（コンパイル）が簡単に済むため、よく用いられている手法である。

今回対象としているターゲットは、以下のような仮想マシンならびに仮想マシン用のアセンブラである。

仮想マシン：Java Virtual Machime (JVM)
アセンブラ：Jasmin JVM assembler

これらの仕様の詳細、ならびに Jasmin JVM assemblerのインストール方法については、こちらの参考文献を参照していただきたい。

5.1 Jasmin JVM アセンブラ用のコード生成
 5.2 Jasmin JVM アセンブラ用のソースファイル例
 5.3 コード生成器の実装
 5.4 Mainの実装

5.1 Jasmin JVM アセンブラ用のコード生成

JVM仮想マシン用の、アセンブリソースファイルは、概して以下のような各セクションに分割され構成されている。

（１）プリアンブル（.source, .class, .super）
（２）変数宣言部（.field）
（３）初期化メソッド（.method <init> .... .end）
（４）開始メソッド（.method main .... .end）

コンパイラによるプログラム変換対象は、上記（２）ならびに（４）である。
具体的には、SmallPascalプログラムからの変換の場合、

・生成規則：Program_heading       → （１）の部分を生成
・生成規則：Variables_declaration → （２）の部分を生成
・　　　　　                      → （３）の部分を（固定的に）生成
・生成規則：Body                  → （４）の部分を生成

といった順番になる。

5.2 Jasmin JVM アセンブラ用のソースファイル例

プログラム例２：test1.pas と同等の処理内容を有する、Jasmin アセンブラ用アセンブリソースファイル test1.j を以下に示す。
＃実際に、これは test1.pas からコード生成されたものである。

＜SmallPascalプログラム：test1.pas＞

program test1;
var x, y : integer;

begin 
  x := 3;
  y := 5;
  writeln(x + y); 
end.

＜アセンブリソースファイル例：test1.j＞

     4  .source test1.pas
     5  .class public test1
     6  .super java/lang/Object
     7
     8  .field public static x I = 0
     9  .field public static y I = 0
    10
    11  .method public <init>()V
    12    aload_0
    13    invokenonvirtual java/lang/Object/<init>()V
    14    return
    15  .end method
    16
    17  .method public static main([Ljava/lang/String;)V
    18    .limit stack 5
    19    .limit locals 1
    20
    21    iconst_3
    22    putstatic test1/x I
    23    iconst_5
    24    putstatic test1/y I
    25    getstatic java/lang/System/out Ljava/io/PrintStream;
    26    getstatic test1/x I
    27    getstatic test1/y I
    28    iadd
    29    invokevirtual java/io/PrintStream/println(I)V
    30    return
    31  .end method

＜説明＞

4--6行目：（１）プリアンブル

.source, .class, .superディレクティブを宣言している

8--9行目：（２）変数宣言部

.fieldディレクティブによって、整数型(I) の変数 x, y を宣言している。
初期値はゼロをセットしている。

11--15行目：（３）初期化メソッド

.methodディレクティブによる、JVM初期化メソッド <init> の実装である。
これは固定的である。

17--31行目：（４）開始メソッド

.methodディレクティブによる、mainメソッドの実装である。21--29行目までの各ステップの動作は以下の通り。

・整数値リテラル３をスタックにpushする
・スタックからpopし、変数 x へロードする（ x := 3; ）

・整数値リテラル５をスタックにpushする
・スタックからpopし、変数 y へロードする（ y := 5; ）

・標準出力ライブラリ java/io/PrintStream を準備
・変数 x の値を参照し、スタックへpushする
・変数 y の値を参照し、スタックへpushする
・スタックから２値をpopして加算し、結果をスタックへpushする（ x ＋ y ）
・スタックからpopし、標準出力クラス println によって整数値表示

5.3 コード生成器の実装

SableCCにてコード生成器（Code Generator）を実装するため、DFS探索エンジン（DepthFirstAdapter クラス）への Visitor を実装する。

変数管理表を利用して、コード生成を行うための、Visitor (CodeGeneratorクラス) の、具体的な実装について、以下に説明する。

CodeGeneratorクラス（ソースファイル）

CodeGeneratorクラスのVisitor一覧

CodeGeneratorクラス（ソースファイル）抜粋

    16  package org.sablecc.pascal.code;
    17
    18  import org.sablecc.pascal.node.*;
    19  import org.sablecc.pascal.analysis.*;

        ...............

    24  public class CodeGenerator extends DepthFirstAdapter {

    34    private Hashtable table = new Hashtable();
    37    private String source;
    41    private String class_name;

    47    PrintWriter out;

          .... コンストラクタ定義 (foo.pas --> foo.j生成)....

    53    public CodeGenerator(String source) {
    54      this.source = source; // name of the source file to be ....
    55
    56      // class name of the file to be generated
    57      class_name = source.substring(0, source.length() - 4);
    58
    59      // create an instance of the PrintWriter class whose ....
    60      // filename is .j
    61      try{
    62        out = new PrintWriter(
    63              new BufferedWriter(
    64                new FileWriter(class_name + ".j")));
    65       }
    66       catch(IOException exc) {
    67         System.out.println(exc);
    68       }
    69    }

          .... コード生成（１）プリアンブルの出力 ....

    79    public void inAProgram(AProgram node) {
    80      // write some comments at the top of the file
    81      out.println("; This file was generated by SmallPascal.....");
    82      out.println("; author: Fidel Viegas (viegasfh@hotmail.com)");
    83      out.println(); // leave a space
    84
    85      // generate the object file headings
    86      // this indicates the source from which the file was compiled
    87      out.println(".source " + source);
    88      out.println(".class public " + class_name);
	89      // all the generated classes are subclasses of class Object
    90      out.println(".super java/lang/Object"); 
    91      out.println(); // leave a space 
    92    }

          .... コード生成（２）変数領域宣言の出力 (.field) ....

    99    public void outASingleIdentifierList(
                                           ASingleIdentifierList node) {

   102      String key = node.getIdentifier().getText().toUpperCase();
   105      String var_name = node.getIdentifier().getText();
   109      String var_image = class_name + "/" + var_name;

   111      // translate to jasmin source code and initialise it to zero
   112      out.println(".field public static " + var_name + " I = 0");
   113
   114      // store the variable in the symbol table for later reference
   115      table.put(key, var_image);
   116    }

   119    public void outAMultipleIdentifierList(
                                         AMultipleIdentifierList node) {
   122      String key = node.getIdentifier().getText().toUpperCase();
   125      String var_name = node.getIdentifier().getText();
   129      String var_image = class_name + "/" + var_name;
   130
   131      // translate to jasmin source code and initialise it to zero
   132      out.println(".field public static " + var_name + " I = 0");
   133
   134      // store the variable in the symbol table for later reference
   135      table.put(key, var_image);
   136    }

          .... コード生成（３）（４）プログラム本体のオープニング出力  ....

   138    // this method generates the default constructor and heading
                                                           of main method
   139    public void inABody(ABody node) {
   140      // leave a space after the variables declaration
   141      out.println();
   142
   143      // generate the code for the default constructor  [K.W]
   144      out.println(".method public ()V");
   145      out.println("  aload_0");
   146
   147  //  out.println("  invokevirtual java/lang/Object/()V");
   148      out.println("  invokenonvirtual java/lang/Object/()V");
                                                                 // [K.W]
   149
   150      out.println("  return");
   151      out.println(".end method");
   152      out.println(); // leave a space 
   153
   154      // generate the heading for the main method
   155      out.println(".method public static 
                                            main([Ljava/lang/String;)V");
   156
   157      // we also set the size of the stack to 5
   158      // assuming that we will never have more than
   159      // 5 values on the stack
   160      // this would be ok to pass the JVM requirements
   161      out.println("  .limit stack 5");
   162
   163      // we don't declare local variable, so we set the
   164      // limit of the local variables to 1, which corresponds
   165      // to the args[] passed to the main method
   166      out.println("  .limit locals 1");
   167      out.println(); // leave some space
   168    }

          .... コード生成（４）プログラム本体のフィナーレ出力  ....

   172    public void outABody(ABody node) {

   176      out.println("  return");
   177
   178      // this is the end of the method
   179      out.println(".end method");
   180
   181      // this is the last method to be traversed, so we write
   182      // to the file here
   183      out.flush(); // dump all the code to the file
   184    }

          .... コード生成（４）変数代入文の出力....

   190    public void outAAssignmentStatement(
                                          AAssignmentStatement node) {
   191      // we need the key to get the image of the variable
   192      String key = node.getIdentifier().getText().toUpperCase();
   193
   194      // get the image of the variable
   195      String var_image = (String) table.get(key);
   196
   197      // in JVM assembly we use putstatic to store the value
   198      // on top of the stack in a field
   199      // the I at the end indicates that the field is of type
   200      // integer
   201      out.println("  putstatic " + var_image + " I");
   202    }

          .... コード生成（４）writeln組み込み関数の出力　....

   208    public void inAWritelnStatement(AWritelnStatement node) {
   209      out.println("  getstatic java/lang/System/out 
                                               Ljava/io/PrintStream;");
   210    }

   215    public void outAWritelnStatement(AWritelnStatement node) {
   219      out.println("  invokevirtual java/io/PrintStream/
                                                        println(I)V");
   220    }

          .... コード生成（４）数値演算命令の出力　....

   224    // this method generates the code for the addition operation
   225    public void outAPlusExpression(APlusExpression node) {
   226      //this instruction is used to add two integers
   227      out.println("  iadd");
   228    }
   229
   230    // this method generates the instruction for the subtraction
   231    public void outAMinusExpression(AMinusExpression node) {
   232      // this instruction is used to subtract two integers
   233      out.println("  isub");
   234    }
   235
   236    // this method generates the instruction for the 
                                                        multiplication
   237    public void outAMultTerm(AMultTerm node) {
   238      // this instruction is used to multiply two integers
   239      out.println("  imul");
   240    }
   241
   242    // this method generates the instruction for the
   243    // integer division, that is for the div operator
   244    public void outADivTerm(ADivTerm node) {
   245      // generate the instruction for integer division
   246      out.println("  idiv");
   247    }

          .... コード生成（４）整数値のスタックへのpush操作　....

   255    public void outANumberFactor(ANumberFactor node) {
   256      // value of the number
   257      String value = node.getNumber().getText();
   258
   259      push(value); // call push method to generate the appropriate
   260                   // instruction
   261    }

          .... コード生成（４）変数の値参照　....

   267    public void outAIdentifierFactor(AIdentifierFactor node) {
   268      // get the key whose image is to be retrieved
   269      String key = node.getIdentifier().getText().toUpperCase();
   270
   271      // store the image of the variable
   272      String var_image = (String) table.get(key);
   273
   274      // generate the code
   275      out.println("  getstatic " + var_image + " I");
   276    }

          .... コード生成（４）スタックへのpush操作　....

   280    private void push(String value) {
   281      try {
   282        // this may generate an exception if the number
   283        // is malformed
   284        int int_value = Integer.parseInt(value);
   285
   286        switch(int_value) {
   287          case 0:
   288          case 1:
   289          case 2:
   290          case 3:
   291          case 4:
   292          case 5:
   293            // generate iconst_X if X is between 0 and 5
   294            out.println("  iconst_" + value);
   295            break;
   296          default:
   297            // this generates the instruction to push a byte
   298            if ((int_value >= -128) && (int_value <= 127)) {
   299              out.println("  bipush " + value);
   300            } // this generates the instruction to push a short integer
   301            else if ((int_value >= -32768) && (int_value <= 32767)) {
   302              out.println("  sipush " + value);
   303            } // this generates the code to push an integer
   304            else {
   305              out.println("  ldc " + value);
   306            }
   307            break;
   308        }
   309      }
   310      catch(Exception exc) {
   311        System.out.println(exc);
   312      }
   313    }
   314  }

＜説明＞

24行目：CodeGeneratorクラス宣言（DepthFirstAdapterクラスから継承）

34行目：変数管理表のインスタンス table の生成

53--69行目：コンストラクタ定義（生成コードの出力ファイル名を決定）

79--92行目：（１）プリアンブルの出力

クラス名等をファイル名から生成（inAProgram Visitor）

99--136行目：（２）変数領域宣言の出力

変数が宣言される度に、.fieldディレクティブによる変数領域の確保を行う。
（outASingleIdentifierList, outAMultipleIdentifierList Visitor）

138--152行目：（３）初期化メソッドの出力

.method public <init> メソッドを固定で生成する

154--168行目：（４）開始メソッドのオープニング出力

.method public static main メソッドの、オープニング部分を固定で生成する
（以上、inABody Visitor）

172--184行目：（４）開始メソッドのフィナーレ出力

.method public static main メソッドの、フィナーレ部分を固定で生成する
（outABody Visitor）

190--202行目：（４）変数代入文の出力

Identifierをキーとして変数管理表からクラス名付きの変数フィールド名を取得し、"putstatic"命令にてコード生成
（outAAssignmentStatement Visitor）

208--220行目：（４）writeln組み込み関数の出力

まず"getstatic"命令にてPrintStreamライブラリを取得した後、Expression leafを評価後（評価値はスタックに入る）、"println"命令にてスタックの内容を出力
（inAWritelnStatement, outAWritelnStatement Visitor）

224--247行目：（４）数値演算命令の出力

加減乗除算について、iadd, isub, imul, idiv 命令にて演算を行うコードを生成する。
Expression, Term あるいは Factor評価後、演算に必要な２数はスタックに入っている。
（outAPlusExpression, ...., outADivTerm Visitor）

255-261行目：（４）整数値のスタックへのpush操作

整数値の評価（Number-->Factor）後、JVM仮想マシンのスタックへ、その数値をpush する命令を出力する。値の範囲によって出力する命令が異なるため、push()操作関数（後述）にてwrapしている。
（outANumberFactor Visitor）

267--276行目：（４）変数の値参照

変数の値評価（Identifier-->Factor）後、Identifierをキーとして変数管理表からクラス名付きの変数フィールド名を取得し、"getstatic"命令にてコード生成
（outAIdentifierFactor Visitor）

280--313行目：スタックへのpush操作のwrap関数

JVM仮想マシンのスタックへ整数値をpushする際、値の範囲によって出力する命令が異なるため、場合に分けて 'iconst_*', 'bipush', 'sipush' ならびに　'ldc' 命令を出力している

5.4 Mainの実装

SableCCにおいて、文法ファイルに基づいて生成された lexer/parser, ならびに先に実装した Visitor（SemanticAnalyzer, CodeGeneratorクラス）を駆動するため、Mainを実装する。

Mainクラス（ソースファイル）

Mainクラスの実装（抜粋）

    12  package org.sablecc.pascal.compiler;

    14  import org.sablecc.pascal.node.*;
    15  import org.sablecc.pascal.tool.*;
    16  import org.sablecc.pascal.semantic.*;
    17  import org.sablecc.pascal.code.*;

        ...............

    21  public class Main {
    22    public static void main(String[] args) {

            .... オープニングメッセージ出力 .....

            .... コマンドライン引数の個数をチェック .....

    35      try {
    36        // parse the program and assign the generated AST to node root
    37        System.out.println("Parsing " + args[0] + "...");
    38        Node root = TreeBuilder.getNode(
    39                        new PushbackReader(
    40                          new BufferedReader(
    41                            new FileReader(args[0])), 1024));
    42
    43        
    44        // process semantic analysis
    45        System.out.println("Checking identifiers...");
    46        root.apply(new SemanticAnalyser());
    47
    48        // process code generation
    49        System.out.println("Generating " +
    50                args[0].substring(0, args[0].length() - 4) + ".j");
    51        root.apply(new CodeGenerator(args[0]));
    52
    53        // finished compilation
    54        System.out.println("done.");
    55      }
    56      catch(Exception exc) {
    57        System.out.println(exc);  // output the exception
    58      }
    59    }

    60  }

＜説明＞

14--17行目：node, lexer, parserクラスパッケージの利用を宣言

38--41行目：ファイル入力ストリームから PushbackReader を使用して入力列を読み込み、TreeBuilderクラスのgetNodeメソッドによって、導出木のインスタンス root を得る。

46行目：Visitorクラスの SemanticsAnalyzer のインスタンスを new し、導出木 rootに対して意味的解析を実行する。

51行目：Visitorクラスの CodeGenerator のインスタンスを new し、導出木 rootに対してコード生成を実行する。

6. プログラムの実行

SmallPascalプロジェクトファイルはここからダウンロード
smallpascal-src.tar.gz

ビルド済みプロジェクトファイルはここからダウンロード
smallpascal-build.tar.gz

ビルド後、SmallPascalコンパイラ pascal.jar を得る。

以下のコンパイル／実行例では、次のSmallPascalプログラム例（test2.pas）を使用する。

＜SmallPascalプログラム：test2.pas＞

program test2;
var x, y, z : integer;

begin 
  x := 3;
  y := 5;
  z := 4;
  writeln( ( x + y ) * z ); 
end.

【コンパイル】

最初に、プログラム test2.pas を、SmallPascalコンパイラ pascal.jar にてコンパイルし、Jasminアセンブラ用のアセンブリソースファイル test2.j を得る。

＜コンパイルの実施＞

$ java -jar pascal.jar test2.pas 

Small Pascal  (smallpascal)    version 1.0
Copyright (C) 2001 Fidel Viegas (viegasfh@hotmail.com).
All Rights Reserved.


This software comes with ABSOLUTELY NO WARRANTY.
Please read the LICENSE file for license information.

Parsing test2.pas...
Checking identifiers...
Generating test2.j
done.

＜Jasmin アセンブリソースプログラム：test2.j＞

; This file was generated by SmallPascal compiler.
; author: Fidel Viegas (viegasfh@hotmail.com)

.source test2.pas
.class public test2
.super java/lang/Object

.field public static x I = 0
.field public static y I = 0
.field public static z I = 0

.method public ()V
  aload_0
  invokenonvirtual java/lang/Object/()V
  return
.end method

.method public static main([Ljava/lang/String;)V
  .limit stack 5
  .limit locals 1

  iconst_3
  putstatic test2/x I
  iconst_5
  putstatic test2/y I
  iconst_4
  putstatic test2/z I
  getstatic java/lang/System/out Ljava/io/PrintStream;
  getstatic test2/x I
  getstatic test2/y I
  iadd
  getstatic test2/z I
  imul
  invokevirtual java/io/PrintStream/println(I)V
  return
.end method

【アセンブル】

次に、アセンブリソースファイル test2.j を Jasminアセンブラを用いてアセンブルし、JVM仮想マシン用のクラスファイル test2.class を得る。

Jasmin JVM assemblerのインストールや使用方法については、こちらを参照していただきたい。※Jasminアセンブラ jasmin.jar は、/usr/local/jasmin/jasmin.jar に存在すると仮定している。

＜アセンブルの実施＞

$ java -jar /usr/local/jasmin/jasmin.jar test2.j
Generated: test2.class

【実行】

最後に、生成された test2.class クラスファイルを、JVM上で実行する。

＜JVM上で実行＞

$ java -cp . test2
32

....お疲れ様でした。