Q言語コンパイラ
yacc および lex を使用したコンパイラ作成の例として，
単純なプログラミング言語「Q言語」のコンパイラを作成した．
以下にその覚書を記す．
ソース言語 - Q言語
基本的には，C言語類似のシンタックスを持っていると考えてよい．ただし，
- 変数の宣言は，var 変数 ,
… ; という形で行う．
- 配列は，C言語と同様に，配列名の後に配列サイズを [ ]
で括ったものをつけて，var table[256];
などのように宣言する．
- 関数，変数の名前は，英字で始まる英数字からなる．
- データは 32bit 整数と文字列の2種類．
文字列は終端がヌル文字のバイト列へのポインタ (32bit) として扱う．
- 変数も関数も，前方参照を許さない．
したがって，変数も関数も，使用前に宣言・定義されている必要がある．
- 本体のない関数定義 ( 関数名(
… ); ) は，
関数の宣言として扱われる．外部定義の関数を使用する場合や，
前方参照を避けるために使用する．
- 最初に実行される (呼び出される) 関数は main である．
- 制御文は，ブロック ({ 文 … })，
if 文 (if ( 式 )
文 [ else 文 ])，
while 文 (while ( 式 )
文) の3つである．
break，goto などはない
- 使用できる演算子は (代入の)=
|| && (単項の)! == != < <= > >=
+ - * / (単項の)- である．
- 文字列は，二重引用符 (") で括る．
\ をエスケープ文字として，
\n 等も使用できる．
- コメントは，// から行末までである．
/* … */ のタイプのコメントは使えない．
サンプルも参照されたい．
目的言語 - IA-32インテル(R)アーキテクチャのアセンブリ言語
目的言語は，IA-32インテル(R)アーキテクチャのアセンブリ言語である．
gcc に付随しているアセンブラ (gas) で処理できるように，gas
の intel 形式で出力する．そのため，出力されたコード (*.s)
は通常の cc (gcc) を用いて実行ファイルが生成できる．
IA-32インテル(R)アーキテクチャの詳細については下記資料を参照されたい．
命令の一部を以下に簡単に示す．
- .intel_syntax
- インテル形式を指定する．
- .macro マクロ名 引数...
- マクロ命令の定義を始める．
- .endm
- マクロ命令の定義を終了する．
- .comm 領域名, サイズ
- 共有領域 (大域変数) の名前とサイズを定義する．
- .ascii 文字列, …
- 文字列リテラル（定数）を定義する．
- .globl 名前
- 名前を大域的な名前として宣言する．
- jmp ラベル
- ラベルに分岐する (無条件分岐)．
- jnz/jz/jne/je/jge/jg/jle/jl ラベル
- 条件が満たされたとき，ラベルに分岐する (条件分岐)．
- call 手続き
- 手続きを呼び出す．手続きは，
ラベル (ラベルそのものを飛び先とする〈直接〉) や
[ラベル] (ラベルの場所のデータを番地として飛び先とする〈間接〉) や
[レジスタ + 数値] (レジスタの内容に数値を足した結果の番地を飛び先とする〈インデックス〉)
などがある．
- ret
- 手続きから呼び出し元へ戻る．
- mov 先, 元
- 元から先へデータを転送する．先, 元 の表現については後述．
- lea 先, 元
- 元の実効アドレスを先に格納する．
- push 元
- 元の内容をスタックにプッシュする．
- pop 先
- スタックからポップして先に転送する．
- or/add/sub/imul 先, 元
- 先と元で演算（論理和/加算/減算/乗算）して，結果を先へ格納する．
- cdq
- eax の32bit長の数値を（符号を保って）64bit長に拡張し，edx:eax に格納する．
- idiv 元
- edx:eax と元で演算（除算）して， 結果を eax へ格納する．
- cmp 先, 元
- 先と元を比較して，結果をフラグレジスタへ格納する．
- inc 先
- 先の内容に1を足す．
- dec 先
- 先の内容から1を引く．
- neg 先
- 先の内容の正負を反転させる．
また，除算を他の演算と同じ形式で書けるように，
以下のようなマクロ命令 mdiv を定義して用いる．
- mdiv eax, 元
- eax と元で演算して，結果を eax へ格納する．
その定義は以下のとおりである．
.macro mdiv eax, SRC
cdq
idiv \SRC
.endm
なお，上の「先」「元」には以下のようなものがある．(組合せによっては許されないものもある)
- レジスタ
- %eax, %ebx, %ecx, %edx (以上汎用レジスタ), %ebp (ベースポインタ),
%esp (スタックポインタ) など．(いずれも 32bit)〈レジスタ直接〉
- 数値
- 数値を直接用いる〈イミディエイト〉
- ラベル
- ラベルが表わす番地のメモリ上の領域〈直接〉
- [%eax*4+ラベル]
- ラベルが表わす番地に %eax の内容の4倍を加えた番地のメモリ上の領域
〈インデックスの一種〉
- [%ebp+数値]
- ベースレジスタ %ebp の内容に数値を加えた結果を番地として，その番地のメモリ上の領域
〈ベースレジスタ相対〉
- [%ebp+%eax*4+数値]
- ベースレジスタ %ebp の内容に %eax の内容の4倍を加え，更に数値を加えた結果を番地として，
その番地のメモリ上の領域〈ベースレジスタ相対,インデックス〉
開発環境
コンパイラは RedHat Linux 上で bison (GNU版の yacc 類似品)，flex, cc (gcc)
を使用して作成したが，gcc (gas) のバージョンによってはうまく動かないかもしれない．
コンパイラの概略
- コンパイラの作成手順はソースの Makefile を参照されたい．
- 文字列を動的に生成して用いるために，stringf.c で，
printf 関数と同様の形式で文字列を (動的に) 生成する関数 Stringf
を定義して各所で用いている．Stringf 関数で生成した文字列に割り当てられた領域は，
最後に freeStrings 関数を呼び出して解放する．
(qc.y の l.162)
- 作成されたコンパイラ (qc) は，
標準入力から入力されたソース言語をコンパイルした結果を標準出力から出力する．
したがって，以下のようなコマンドで実行されると考えてよい
(サンプルの Makefile 参照)．
qc <hello.p >hello.s
また，qc の引数に以下のオプションが使用可能である．
- -1
- 目的コードの代わりに構文解析結果の構文木を出力する．
- -2
- 目的コードの代わりに意味解析結果の構文木と名前-オブジェクト表を出力する．
- -3 (デフォルト; オプション省略時と同じ)
- (最適化前の) 目的コードを出力する．
- -4
- 最適化された目的コードを出力する．
- コンパイルは，大域的定義 (大域変数の宣言か関数の定義) を単位として行われる．
それらの単位で生成された構文木を，まず bindObj 関数で名前の解決(意味解析)をし，
genCode 関数で目的コードを生成する．
(qc.y の ll.68-71, ll.167-175 参照)
- 生成した目的コードは，一旦，内部のバッファ (asm.c
の配列 CodeBuf) に格納し，文字列定数の生成と最適化 (後述) を施した後，
putCode 関数で出力する．
(qc.y の l.160)
- 除算だけは，他の四則演算とアセンブリ命令の形式が異なるので，initCode 関数で
同じような形式のマクロ命令 (mdiv) の定義を目的コードの冒頭においている．
(qc.y の l.155, code.c の ll.23-29)
- プログラム中の固定した文字列は，いったん表 (asm.c の配列
StringTable) に登録しておき，全ての大域的定義を処理して yyparse()
を抜けた後に，まとめてgenStrings 関数で生成する．
(qc.y の l.158)
- -4 オプションが指定されたときは，optCode 関数を呼び出して，
内部バッファ上の目的コードに，若干の「覗き穴最適化」を施す．
(qc.y の l.159)
- 局所変数 (関数の仮引数を含む) のオブジェクトは，関数定義を単位としたコンパイルの後，
破棄される．(テキスト §5.4 参照)
(bind.c の popLocals 関数)
- プログラムの見通しを良くするため，エラー処理はほとんど行っていない．
また，意味処理においても，型のチェック等は行っていない．
- コード生成と最適化については，「Q言語コンパイラ 関連資料」
も参照されたい．
各ファイルの概略
- qc.y
Q言語の文法と，それに沿った構文木生成の記述．
構文木の中間ノード (非終端記号を表わすノード) の種類を表わすコードも，
ここでトークンとして定義している．
メインルーチンもここに含まれる．
- yylex.l
字句解析ルーチン．( yylex() )
- tree.h
構文木のためのデータ型等．
- tree.c
構文木を操作する関数等．( mkNode(), putTree() )
- bind.h
オブジェクト構造体に関する定義．
- bind.c
名前の解決など．( bindObj(), popLocals(), putObjs() )
- asm.h
アセンブリ命令の構造体に関する定義．
- asm.c
目的コードの生成と，その出力のための関数の定義．文字列リテラルの処理．
( CodeBuf[], I(), putCode(), genStrings() )．
- code.c, code_exp.c
意味解析結果の構文木から目的コードを生成するための関数の定義．
( initCode(), genCode() )
- optimize.c
覗き穴最適化のための関数の定義．( optCode() )
- stringf.c
文字列を生成する関数等．( Stringf()，freeStrings() )
Q言語で書かれたプログラムのサンプル．
- hello.q
いわゆる「Hello world」．
- echo.q
引数の処理，while の使用．
- fact.q
再帰を用いて n の階乗を計算するプログラム．
「式中で配列名のみが現れたときは，その配列領域へのポインタを値とする」
という「裏仕様」の利用．
- facto.q
再帰を用いて n の階乗を計算するプログラム．
n をコマンド引数で与える．
- facts.q
種々の手法で n の階乗を計算するプログラム．
n をコマンド引数で与える．
- hanoi.q
ハノイの塔を解くプログラム．
- string.q
種々の文字列操作のサンプル．
文字列と文字コード(整数)の配列の相互変換をするための関数 pack(), unpack()
の定義も含む．
- twice.q
コマンド引数を2回繰り返して表示．変数のスコープの取り扱いの確認テスト用．
三浦欽也
(miura@mail.kobe-c.ac.jp),
三浦研究室