P言語(仮称)コンパイラ
yacc および lex を使用したコンパイラ作成の例として,
単純なプログラミング言語「P言語(仮称)」のコンパイラを作成した.
以下にその覚書を記す.
ソース言語 - P言語(仮称)
基本的には,C言語類似のシンタックスを持っていると考えてよい.ただし,
- 変数の宣言は,var 変数 , … ;
という形で行う.
- 配列も同様に定義できる.
- 関数,変数の名前は,英字で始まる8文字以内の英数字で,大文字小文字を区別しない.
- データは2バイト整数のみ.文字列は2バイト整数の配列(終端はヌル文字)として扱う.
(1文字を2バイト整数1つで表わす)
- 変数も関数も,前方参照を許さない.
したがって,変数も関数も,使用前に宣言・定義されている必要がある.
- 最初に実行される(呼び出される)のは main() である.
- 制御文は,ブロック ({ 文 … }),
if文 (if ( 式 )
文 [ else 文 ]),
while文 (while ( 式 )
文) の3つである.
break,goto などはない
- 使用できる演算子は (代入の)=
| ^ & (単項の)~ == != < <= > >=
+ - * / (単項の)- である.
- 文字列は,一重の引用符 (') で括る.
文字列中の ' は2個並べて表わす.
(CASLII準拠)
- 組み込み関数は以下の4つである.(ファイル runtime.cas 中で定義されている)
- int2str(s, n)
十分な大きさの配列の名前 s と数値 n
を引数として取り,数値を文字列に変換したものを配列sに書き込む.
戻り値はsと同じ.
- str2int(s)
数値を表わす文字列またはそれを格納した配列の名前を引数に取り,
それを数値に変換したものを戻り値として返す.
- readln(s)
十分な大きさの配列の名前 s を引数として取り,
そこに,キーボードから入力した1行の文字列を格納する.
戻り値はsと同じ.
- writeln(s1 , …)
任意個数の配列と文字列を引数として取り,それらを順に画面出力して最後に改行する.
戻り値に意味はない.
- コメントは,// から行末までである.
/* … */ のタイプのコメントは使えない.
サンプルも参照されたい.
目的言語 - CASLII
詳細は以下を参照されたい.
開発環境
コンパイラは Windows XP 上に Cygwin を導入し,その上で yacc,flex, cc を使用して作成したが,
UNIX 上でも(おそらく)同じソースで作成可能と思われる.(古い Linux で確認済み)
yacc は bison (GNU版yacc) と byacc (バークレー版yacc) のいずれでも可能と思われる.
目的言語の CASLII は,下記の CCaslII
(山口秀昭氏作成の CASLII アセンブラと COMETII シミュレータ) で動作確認を行った.
(いずれも Windows版を使用.Linux版での動作は未確認)
コンパイラの概略
- コンパイラの作成手順は Makefile を参照されたい.
- 作成されたコンパイラ (pc) は,
標準入力から入力されたソース言語をコンパイルした結果を標準出力から出力する.
したがって,以下のようなコマンドで実行されると考えてよい.
pc <hello.p >hello.cas
また,pc の引数には,syntax, semantics,
optimize のいずれかをつけることができる.その場合,それぞれ,
構文解析結果,意味解析結果,最適化適用結果の出力が得られる.
- コンパイルは,大域変数の宣言か関数の定義を単位として行われる.
それらの単位で作成された構文木を,まず bindObj 関数で名前の解決(意味解析)をし,
code 関数で CASLII のコードを生成する.(pc.y 参照)
optimize が指定されたときは,
コード生成時に若干の最適化を施す.
- 局所変数 (関数の仮引数を含む) のオブジェクトは,関数定義を単位としたコンパイルの後,
破棄される.(テキスト §5.4 参照) (syntax_tree.c の popScope())
- CASLII(COMETII) の特性上,関数の戻り番地の保存に用いる通常のスタック上に,
局所変数のための領域を割り当てるのは困難なので,生成するコードでは,
GR7をスタックポインタ兼ベースポインタとして用いて,局所変数用のスタックを
(通常のスタックとは別に) プログラムコードの末尾に取るようにしている.
(runtime.cas の DSTACK)
- プログラム中の固定した文字列は,いったん表 (CASL.c の StringTable[])
に登録しておいて,モジュール(関数)の最後にまとめてデータを生成する.
- プログラムの見通しを良くするため,エラー処理はほとんど行っていない.
また,意味処理においても,型のチェック等は行っていない.
各ファイルの概略
- pc.y
P言語(仮称)の文法と,それに沿った構文木生成の記述.
構文木の中間ノード(非終端記号を表わすノード)の種類を表わすコードも,
ここでトークンとして定義している.
メインルーチンもここに含まれる.
- lexer.l
字句解析ルーチン.
- syntax_tree.h
構文木・オブジェクト(関数・変数)のためのデータ型等.
- syntax_tree.c
構文木・オブジェクト(関数・変数)を操作する関数等.
- bind.c
構文木の終端の名前を表すノード(SYM)に,それが表すオブジェクトを結びつける
(= 名前の解決) 関数など.
- CASL.h
CASLII の内部コードに関する定義.
- CASL.c
CASLII の内部コードの生成と,その出力の関数(C3(), dumpCode() 等).
若干の最適化 (optimize()).文字列リテラルの処理.
- code.c,code_exp.c
意味解析結果の木からCASLII内部コードを生成する関数.
- debug.h
syntax, semantics, optimize のモードに関する定義.
- debug.c
構文木・オブジェクトを出力するための関数など.
- runtime.cas
掛け算,割り算,組み込み関数のプログラム等.
P言語(仮称)で書かれたプログラムのサンプル.
- hello.p
writeln のサンプル.
- fact.p
再帰を用いて階乗を計算するプログラム.
文字列の長さを求める関数 strlen や文字列を連結する関数 strcat も定義している.
- facts.p
種々の手法で階乗を計算するプログラム.
- string.p
種々の文字列操作のサンプル.
文字列の長さを求める関数 strlen や文字列を連結する関数 strcat も定義している.
三浦欽也
(miura@mail.kobe-c.ac.jp),
三浦研究室