プログラム解説(pascc.exe)

目次

  1. はじめに
  2. 開発環境
  3. 概要
  4. 設計
    1. 構文木生成
    2. 関数宣言
    3. Cソース出力
    4. 変数アドレス
    5. 関数呼び出し
    6. 返り値
    7. 演算式
    8. 制御文
  5. クラス解説
    1. 構文木関係
    2. エラー関係
    3. 関数・変数表関係
    4. バイナリデータ関係
    5. Cソースデータ関係
  6. プログラムソース
    1. コンパイル方法
  7. 開発履歴
  8. 参考資料

1 はじめに

以下の説明は執筆時点でのpascc.exeを元にしているため、
最新版では一部仕様が異なる可能性がある。


2 開発環境

開発はC++言語を用いて、Windows 2000上で行っている。
以下のソフトウェアを使用している。


3 概要

このコンパイラは、以下のような処理を行う。

  1. 入力ファイルを字句解析の対象に指定
  2. 構文解析を行う(bison)
  3. 関数宣言部解析のためのparthingを行う
  4. コード生成のためのparthingを行う
  5. エラーメッセージを出力する
  6. バイナリデータを出力する
  7. Cソースファイルを出力する

必要に応じて、以下の管理クラスとやりとりを行う。


4 設計

字句解析はflex,構文解析はbisonによって行われる。
構文木が生成されたあと、意味解析とコード生成を同時に進行する。

意味解析とコード生成は、構文木をParthingすることによって行う。
最初に関数宣言のParthingが行われる。(Generate_FuncDec())
関数宣言のParthingが終わると、本格的なコード生成Parthingを行う。(Generate_Code())

上記全ての段階において出現したエラーや警告は、エラー管理クラスに登録する。


4.1 構文木生成

構文解析時、bisonはflexを呼び出しながら解析を行う。
一致する構文を見つけると、その非終端記号にあたるノードクラスをヒープメモリにとり、親ノードに自らのポインタを渡す。
これを繰り返すことにより、ボトムアップで構文木が生成される。
一致する構文がなければ、文法をいくつか飛ばして復旧を試みる。
このとき、親ノードにはNULLが渡される。
最終的に、構文木のトップのノードはParseTreeクラスが保持する。


4.2 関数宣言

PasCには、関数のプロトタイプ宣言は存在しない。
よって、構文木が作られたあと、関数宣言のためのParthingを行う。(Generate_FuncDec())
関数宣言は、木の根元に近いノードに存在しているため、効率的に巡回することができる。
関数定義に直結する枝だけを巡回し、関数定義にたどり着く。
このParthingでは、主に以下の作業を行う。


4.3 Cソース出力

Cソースコードについては、関数・変数表を参照してアドレスを割り当てる必要はない。
よって、各ノードごとにコードの一部を出力していくだけでよい。

ただし、for文と関数呼び出しについては、バイナリ出力とParthingの順序が異なる。

for ( 代入式1 ; 条件式 ; 代入式2 ) 文

Cソース出力では、「代入式1→条件式→代入式2→文」の順番で巡回する。
バイナリ出力では、「代入式1→条件式→文→代入式2」の順番で巡回する。

関数名 ( 演算式1 , 演算式2 , 演算式3 , … )

Cソース出力では、「演算式1→演算式2→演算式3→…」の順番で巡回する。
バイナリ出力では、「…→演算式3→演算式2→演算式1」の順番で巡回する。

よって、局所的に2度のParthingが必要になる。
Cソース出力時には、一時的にバイナリ出力の機能を停止する。
バイナリ出力時には、一時的にCソース出力、エラー出力の機能を停止する。

また、整形されたCソースを出力できるように、インデント(タブ文字)の処理も行う。


4.4 変数アドレス

関数の再帰呼び出しをサポートするため、変数のアドレスは、その絶対アドレスを静的に決定することは出来ない。
よって、bpレジスタからの相対アドレスをコンパイル時に決定する。
ただし、グローバル変数は、0xFFFFからの相対アドレスとする。

変数のアドレスは、bpから、0,-1,-2…となる。
引数のアドレスは、bpから、+3,+4,+5…となる。

配列が宣言された時は、その領域だけアドレスを確保する。


4.5 関数呼び出し

関数呼び出しの前にその関数が定義されているとは限らない。
よって、関数呼び出しの時点で、呼び出し先のアドレスがわからない場合がある。
このような時は以下のように処理する。

実際の関数呼び出しは、以下の手順をコード化する。

  1. 引数の処理
    関数呼び出しの前に、引数を処理する。
    各引数は演算式(expression)なので、その結果は、スタックにおかれる。
    その際、1番初めの引数が、スタックの1番上に来るようにする。
  2. Call命令
    Call命令は、Ret命令実行時に戻るべきアドレス(リターンアドレス)をスタックに積む。
  3. 初期化処理
    呼び出した関数のbpは保存され、呼び出された関数のために、新たにbpが設定される。
    また、spも正しく設定される。
  4. 関数の実行
  5. 終了処理
    3. と逆の動作をする。
    bpは呼び出した関数のものにリストアされ、spも同様である。

3. が終了した時点での、スタックの1部は以下のようになる。


<-- sp
変数3
変数2
変数1<--- bp
呼び出し元の関数でのbp
リターンアドレス
引数1
引数2
引数3

このように、bpを設定することで、関数内での相対アドレスで正しく動くようになる。
また、このようにspを設定することで、変数用の領域が、これ以降のPUSHやPOPによって破壊されない。

5. は呼び出し元の関数についての、この状態をリストアする処理である。


4.6 返り値

返り値は、return文によって、GR0に、その値が格納される。
演算式(expression)の中で関数が呼ばれたときは、この値をPUSHしなければならない。
文(statement)の中で呼ばれたときは、特別な処理は必要ない。


4.7 演算式

演算式(expression、定数、変数、関数呼び出し)は、全てスタックを介して行う。
前の演算結果を得たいときはスタックからPOPし、演算結果は必ずスタックにPUSHする。
なお、構文解析の段階で、演算子の優先順位のとおりに構文木が生成されている。

5 + a * 8
  1. 定数5の値をスタックにPUSHする。
  2. 変数aの値をスタックにPUSHする。
  3. 定数8の値をスタックにPUSHする。
  4. POPした値とPOPした値を*演算し、演算結果をPUSHする。
  5. POPした値とPOPした値を+演算し、演算結果をPUSHする。

4.8 制御文

制御文は、演算式の結果が0かどうかでJUMPを行う。(JZE,JNZ)。
制御文の中でbreakやcontinueがあったとき、どのアドレスまでJUMPするのか不定である。
よって、制御文のなかの文を呼び出す前に、breakで飛ぶ先のアドレスをコード化しておく。

JUMP break_address
JUMP continue_address

そして、このbreak_addressのアドレスを関数表に追加登録しておく。
break文があった時には、このアドレス位置にJUMPすればよい。
continue文があった時には、このアドレス位置 + 2にJUMPすればよい。


5 クラス解説

プログラム自体が非常に巨大なものになっているので、主要なクラスについて説明を行う。


5.1 構文木関係

構文木の構造をクラス化するにあたり、文法の各非終端記号に対してクラスを一つづつ定義している。
構文解析時に、bisonのアクションプログラムによって木構造を形成する。
すなわち、構文木のノード一つずつがクラスインスタンスに対応する。

TreeNodeクラス

全てのノードクラスのベースクラスである。
自分のノードの種別(enum unterm)、行番号を保持する。
関数宣言のParthingを行うGenerate_FuncDec()を持つ。
コード生成のParthingを行うGenerate_Code()を持つ。

各ノードクラス

各ノードクラスはTreeNodeクラスから派生する。

各ノードクラスは文法仕様に従った、子ノードのポインタを保持する。

必要に応じてGenerate_FuncDec()がオーバーライドされ、関数宣言の処理コードが実装される。
この関数内では、必要に応じて子ノードのGenerate_FuncDec()が呼び出す。
これにより、構文木のトップのGenerate_FuncDec()を呼び出すと、再帰的に子ノードのGenerate_FuncDec()が呼び出される。

Generate_Code()をオーバーライドし、その関数の中で、意味解析、コード生成等を行う。
この関数内では、必ず子ノードのGenerate_Code()を呼び出す。
これにより、構文木のトップのGenerate_Code()を呼び出すと、再帰的に全ての子ノードのGenerate_Code()が呼び出される。

各ノードクラスのデストラクタでは、子ノードのポインタをdeleteする。 これにより、再帰的に子ノードのデストラクタが呼ばれ、全てのノードが正しく破棄される。

expression派生クラス

const_value(定数)、exp_variable(変数)、func_call(関数呼び出し)は、expression(演算式)クラスから派生される。
TreeNodeクラスに加え、型情報を保持する。

ParseTreeクラス

bisonから受け取った、構文木のトップのノードを保持する。
このクラスのGenerate_FuncDec()、Generate_Code()を呼び出すことで、Parthingが始まる。
Generate_FuncDef()は、関数宣言に必要な子ノードのみを巡回するので、無駄がない。


5.2 エラー関係

コンパイラが出すエラーメッセージは、致命的エラー、エラー、警告の3種類ある。
これらの情報を効率よく管理するためにたくさんのクラスが存在する。

エラーメッセージは、errorフォルダ内だけに集中させたため、ここを修正するだけで、メッセージを英語にしたりすることを可能にする。

base_errorクラス

全てのエラークラスのベースクラスである。

このクラスは、エラーメッセージを保持する。
純粋仮想関数what()を持つ。エラーメッセージの出力に使われる。

FatalErrorクラス

base_errorクラスから派生させた、全ての致命的エラークラスのベースクラスである。
名前空間fatal_errorの中に存在する。

全ての致命的エラークラスに共通の「コンパイルを中断します」を付け加える。

Errorクラス

base_errorクラスから派生させた、全てのエラークラスのベースクラスである。
名前空間errorの中に存在する。

全てのエラークラスに共通の「エラー(line): pos:」を付け加える。

Warningクラス

base_errorクラスから派生させた、全ての警告クラスのベースクラスである。
名前空間warningの中に存在する。

全ての警告クラスに共通の「警告(line): pos:」を付け加える。

各致命的エラー、エラー、警告クラス

それぞれ、FatalError,Error,Warningクラスから派生している。
名前空間fatal_error,Error,Warningの中に存在する。

個々のメッセージをwhat()によって生成する。

ErrorManagerクラス

エラー、警告クラスを蓄え、一括して標準エラーに出力するクラスである。

ErrorManager << new error::all_BadParseTree(line,"xxx");    // エラーを追加
ErrorManager << new warning::NotUseVar(line,"xxx",name);    // 警告を追加

ErrorManager.OutError();                                    // エラーを標準エラーに一括出力
ErrorManager.OutErrorCount();                               // エラーの個数を標準エラーに出力

なお、致命的エラーは、ErrorManagerが管理せず、致命的エラークラスを「throw」する。
throwされた例外は、main関数で「catch」され、表示を行う。


5.3 関数・変数表関係

意味解析の段階で、関数表や変数表を参照する必要が出てくる。
以下のクラスでこれらをサポートする。

func_elementクラス

関数表の一要素に相当するクラスである。

戻り値の型、アドレス、引数の型(複数)を保持する。

関数内で宣言されたローカル変数名(複数)を保持する。
関数のスコープを抜けたとき、一括して変数を削除するためである。

アドレス未定義時に、関数呼び出しを行ったアドレス(複数)を保持する。
関数のアドレスが決定したときに、その関数を参照していたアドレスを一括して書き換えるためである。

制御文の入れ子の数(コントロールパス)を保持する。
返り値を持つ関数の時、return文があったかを判断するためである。

break文での飛び先アドレス(複数)を保持する。
入れ子になった繰り返し文からでも正確にbreak(continue)できるようにするためである。

var_elementクラス

変数表の一要素に相当するクラスである。

変数の型、定数かどうか、配列かどうかを保持する。

アドレス、ベースレジスタを保持する。
変数のアドレスは相対的に決まるため、グローバル変数、ローカル変数によって使用するレジスタ番号が異なるからである。

MapManagerクラス

変数・関数表を管理するクラスである。

変数・関数の登録や参照を行う際に、表全体が渡されるのでは大変なだけでなく、他の要素を書き換えてしまう危険性もある。
よって、変数名・関数名をキーに、MapManagerにアクセスし、その一要素だけを得るようにしている。

MapManagerは、変数表、関数表、現在のスコープ(関数名)の情報を保持する。

MapManager.AddFunc(name);                       // 関数を関数表に追加
MapManager.AddVar(name,1);                      // 変数を変数表に追加
MapManager.ExitScope();                         // 現在のスコープから抜ける(ローカル変数を削除)

func_element* func = MapManager.FuncElem(name); // 関数表の要素を得る
func->SetType(_INT);                            // 得た要素を使って関数表にアクセスできる

var_element* var = MapManager.VarElem(name);    // 関数表の要素を得る
if (var->IsConst()){ ... };                     // 得た要素を使って変数表にアクセスできる

5.4 バイナリデータ関係

Generate_Code()での、バイナリコードの生成をサポートする。

ASM構造体

アセンブラ命令を指定すると、それに応じたバイナリコードを返すインライン関数の集まりである。
この構造体を修正すれば、新しい命令を追加することが容易にできる。

ASM.Load(GR0,GR1)         // 0x1412を返す

BinOutクラス

バイナリコードを蓄え、一度にファイルに出力するクラスである。

BinOut.SetOutFile(filename);               // 出力ファイル名を設定
BinOut << ASM.Move(GR0) << 100;            // 0x1300 0100 を追加
WORD addr = BinOut.GetAddr();              // 次の実行アドレスを取得
BinOut[addr - 1] = 0x1234;                 // バイナリデータの修正
BinOut.WriteToFile();                      // 出力ファイルへ一括書き出し

5.5 Cソースデータ関係

Generate_Code()での、Cソースデータの生成をサポートする。

SrcOutクラス

Cのソースを蓄え、一度にファイルに出力するクラスである。

SrcOut.SetOutFile(filename);               // 出力ファイル名を設定
SrcOut << "#include <stdio.h>\n";          // "#include <stdio.h>\n" を追加
WORD pos = SrcOut.GetLength();             // 次の実行アドレスを取得
SrcOut.Insert(pos - 3,"abc");              // 文字列の挿入
SrcOut.WriteToFile();                      // 出力ファイルへ一括書き出し

6 プログラムソース

C++言語を用いて設計を行っているため、ソースファイルは、ヘッダファイル(.hpp)とソースファイル(.cpp)部分に分かれる。
ヘッダファイルには、主にクラス定義が、ソースファイルには、主にメンバ関数の実装が書かれている。
クラス名とソースファイル名は、たいてい同じか、似た名前が使われている。

TreeNodeクラス、及びその派生クラスは、treenodeフォルダ内に格納している。
エラークラス関係のファイルは、errorフォルダ内に格納している。
flex用ファイルはpasc.l、bison用ファイルはPasc.yである。


6.1 コンパイル方法


7 開発履歴

2002/01/24 2002/01/23 2002/01/20 2002/01/19 2002/01/18 2002/01/17 2002/01/15 2002/01/14 2002/01/13 2002/01/10 2002/01/08 2002/01/07 2002/01/06 2002/01/05 2002/01/04 2002/01/02 2002/01/01 2001/12/31 2001/12/30 2001/12/29 2001/12/28 2001/12/27 2001/12/24 2001/12/20 2001/12/19 2001/12/18 2001/12/17 2001/12/16 2001/12/15 2001/12/14 2001/12/13 2001/12/12 2001/12/11 2001/12/10 2001/12/09 2001/12/07 2001/12/06 2001/12/05 2001/12/04 2001/12/03 2001/12/02以前

8 参考資料

他、授業ノート(前・後期)を参考にした。