前回の続き

前回、GOTO文の分ができたので、条件分岐のIF文の実装について

IF B=1 THEN A=2
というTinyBasicのソースをコード生成の仕方を説明する。

まず、
比較演算子(=)について、左辺と右辺のコードを生成する。

	%1 = load i32* %_V1, align 4
	store i32 %11, i32* %acc
	%2 = load i32* %acc, align 4
	store i32 1 , i32* %acc, align 4
	%3 = load i32* %acc, align 4

として、変数Bの中身をレジスタ的な使い捨て変数の%2に取り出し、即値の1を%3に入れる。

そして、icmp命令で比較を行う。

	%4 = icmp eq i32 %2, %3

比較した結果はBool値で%4に入る。
続きを読む →

前回の続き

先週は、TinyBasicの変数の定義とか代入文のLLVM-IRコード生成部分を説明した。
今週は、行番号とかGOTO文などを説明する。

行番号については、コード生成は簡単だ。
LLVM-IRアセンブラでは、他のアセンブリ言語と同様にラベル定義ができるので、行番号の数字を含んだラベルを生成すればよい。
行番号が10なら「_L10」、
行番号が20なら「_L20」、
とか。
続きを読む →

前回の続き

Tiny Basicの代入文「A=A+10」のコード生成で、
(1)変数Aを定義、ゼロで初期化
(2)変数Aのメモリをレジスタ1に取り出す
(3)定数10をレジスタ2に入れる
(4)レジスタ1とレジスタ2を加算し、結果をレジスタ1に入れる
(5)レジスタ1の内容を変数Aのメモリに書き込む
というのを、実際にLLVM-IR中間コードアセンブラで書いてみる。
続きを読む →

前回の続き

前回の構文の処理で、「命令」と書いていた部分を細かく書く。

構文として、
　命令 = 代入文　または
　命令 = PRINT命令 + 数式 または
　命令 = GOTO命令 + 行番号
などと、定義する。
他にも命令文は増えるのだけど、今は省略。

そして、代入文は
　代入文 = 変数 + 「=」 + 数式
　数式 = 項 + 演算子 + 数式　または 数式 = 項
　項 = 単項演算子 + 項 または
　項 = 「(」 + 数式 + 「)」　または
　項 = 変数　または
　項 = 定数
というように定義する。
続きを読む →

前回の続き

yaccで作成した構文解析ソフトを加工して「骨組み(スケルトン)に肉付け」する形でコンパイラを作っていく。

例えば、文法の一部の、
　行 = 行番号 + 命令群
　命令群 = 命令 + 「：」 + 命令群　または　命令群 = 命令
と言う部分について、
構文を定義したyaccソースコード部分に追加で、その構文に対してどのような処理をするのかを書くことが出来る。

しかし、解釈した構文の処理は、コンパイラが出力すべき命令語の順番になっていない。
上記の例の場合には大きく順番が狂うことはないが、数式の処理の部分だと演算子の優先順位や括弧の処理で大きく順番が狂う。

これを解決するには”構文木”という二分木のツリー構造を使う。
続きを読む →

前回の続き

yaccを使って、コンパイラを作るためにコンパイラ言語の文法を定義しなくてはならない。
今回のTiny Basicの場合、

10 INPUT X
20 Y= x*x + 6*x + 9
30 PRINT Y
というようなBASICの言語の文法を定義する。
続きを読む →

LLVM-IR(LLVM中間コード)を生成するTiny BASICコンパイラを作ったという話の補足。

コンパイラを作るのは、いくつか作らなければならない部品がある。

主に、「構文解析」と「コード生成」に分けられる。
まずは構文解析について。(追記 – コード生成については「その4」から)

構文解析は、コンパイラの言語の文法のルールに沿って、入力されたソースコードを解読して、解読した結果を出力する。

これがアセンブリ言語のような単純な文法の言語ならば、構文解析のソフトは1から手作りをして作ることができる。
予約語と変数(ラベル)と定数だけで、文法の並び順も単純だからだ。
解読した結果も、基本的には1次元の配列のようなものに順番に入れていけば良い。

BASICみたいな言語の場合、構文解析は少し複雑になるが、手作りで作ることはできる。
再帰下降パーサーという作り方で、文法要素を再帰のソフトで組んでいく方法だ。
中間言語を使う方式のBASICの場合、ソースコードの1行分だけを独立してパーサーに書けて1行分のコード出力を得るというのを、行数分だけ繰り返すという作り方もできる。

C言語やPascalみたいな言語の場合、構文解析はかなり複雑になるので手作りで作るのは困難になる。
そこでyaccやbisonというようなコンパイラコンパイラを用いる。(単純なBASICみたいな言語にも用いることができる)
コンパイラを作るためのメタコンパイラだ。
コンパイラ言語の文法のルールを、それ用の記述方式でソースコードに記述してコンパイラコンパイラに掛けると、構文解析用のパーサーソフトの部分を自動生成してくれるものだ。
解析して解読した結果は構文木というツリー構造のデータに入れるとよい。

コンパイラコンパイラについては、
古い参考書だけど、yaccによるCコンパイラプログラミングという本で自分はマスターした。
→ コンパイラ「Cm」を改造してみる

—
続く

LLVM-IR(LLVM中間コード)の参考書や参考にしたwebサイトのメモ。

参考書。

きつねさんでもわかるLLVM ~コンパイラを自作するためのガイドブック~(Amazon)
と、
LLVM/Clang実践活用ハンドブック(Amazon)
続きを読む →