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インテル®アーキテクチャのアセンブリ言語
目的言語は，IA-32インテル®アーキテクチャのアセンブリ言語である．
gcc に付随しているアセンブラ (gas) で処理できるように，gas
の intel 形式で出力する．そのため，出力されたコード (*.s)
は通常の cc (gcc) を用いて実行ファイルが生成できる．
IA-32インテル®アーキテクチャの詳細については下記資料を参照されたい．
- 「IA-32インテル®アーキテクチャ・ソフトウェア・デベロッパーズ・マニュアル」
命令の一部を以下に簡単に示す．
.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倍を加え，更に数値を加えた結果を番地として，
その番地のメモリ上の領域〈ベースレジスタ相対,インデックス〉
コンパイラの概略
- コンパイラの作成手順はソースの 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),
三浦研究室