トップ言語処理入門 > ミニCインタプリタ

ミニCインタプリタ

1.言語処理教材

一般に形式言語はコンピュータではコンパイラかインタプリタによって実行される。

前に示した電卓プログラムはインタプリタに属する。

電卓プログラムも字句解析、構文解析、意味解析を備えているが、プログラミング言語とはほど遠い。 プログラム(C言語の例)とは下に示すように、変数や関数(サブルーチン)が使えたり、数式だけでなく、 if文や繰り返し処理を担うwhile文が使えたり、プログラムの途中経過や実行結果を printf関数などで自由に表示できるものを指す。

電卓プログラムは100行にも満たない。 しかし、下のようなプログラムを機械語に翻訳するコンパイラあるいは直接解釈実行するインタプリタは電卓プログラムより はるかに難しい。電卓プログラムで現れたのは簡単な字句解析と四則演算に対する構文解析と意味解析に過ぎない。 下のプログラムでは、変数の宣言と初期化、関数の定義と呼び出し、繰り返し制御文、プリント文などが登場している。

インタプリタには言語仕様がシンプルな場合、電卓プログラムのように、一文ずつ、解釈実行するものもあるが、 高度な言語仕様に対しては、中間語コード生成まではコンパイラと同じであり、 最終段階でコンパイラは中間語コードを機械語コードに変換するのに対して、 インタプリタはこの中間語コードを直接実行するところだけが異なる。

ただし、コンパイラの場合、最終的には機械語コードに翻訳するため、中間語はこの機械語と相性がよく、 効率のよい機械語に翻訳できるものとしておかなければならない。 インタプリタの場合、この制約は弱い。

具体的には、Windowsパソコンは通常インテルのx86系プロセッサが使用されるが、 これは演算などにレジスタをフルに活用するレジスタマシンである。 一方、インタプリタとしてはスタックマシンの方がプログラムがシンプルになる。 このため、制作演習でもスタックマシン用の中間語コードを生成する。 x86マシン用のコンパイラの場合、このスタックマシン用の中間語コードを効率の良い 機械語に翻訳するのは恐らく楽ではないだろう。

int add(int a, int b) {
    return (a+b);
}

void main() {
    int sum, n = 1;
    int wa;

    wa = add(12, 23);

    sum = 0;
    while (n <= 10) { 
        sum = sum + n;
        n = n + 1;
    }
    printf("add(12,23)=%d sum=%d", wa, sum);
}

コンパイラではターゲットマシンの機械語の理解や実行可能ファイルの作成が難しすぎるきらいがある。 演習では、部品の形で実行可能ファイル作成関数を与えることができるが、 できればブラックボックスがない方が望ましい。

そこで、演習ではまずインタプリタを作成する。 その後、インタプリタとコンパイラの違いを理解するために、コンパイラの制作演習を行う。 実行可能ファイル作成関数は部品として提供する。

インタプリタとしては中間言語に落とさず、直接、文毎に解釈実行する方法もあるが、 ここでは、スタックマシン用の中間語コードに落とし、これを解釈実行する方式とする。 コンパイラの説明がしやすく、また、コンピュータ・アーキテクチャの復習にもなる。

レジスタマシンを対象として作成したインタプリタよりも プログラム行数が1割程短くなった。 スタックマシンの方がレジスタマシンよりコード生成が分かりやすい。

2.言語仕様

制作演習の土台とするプログラムは現在500行弱である。 (もう少しリファインして、最終的には、400行程度にしたい。)

字句解析は50行余りで独立しているので、理解しやすいと思われる。

名前管理も50行程度であり、構文解析や意味解析・コード生成で使う部品のため、比較的理解しやすいと思われる。

構文解析〜コード生成が260行で全体の半分を占める。言語処理の中心である。

命令実行部が100行余り。中間語命令の設計がポイントとなる。

プログラムの難しさはプログラム行数のみに依存するわけではないが、一般的には大きくなるほど理解しにくくなる。 演習により、機能を追加するが、最終プログラムの行数は700行に抑えたい。 学習用といっても、実用技術を学ぶためのものであるから、非実用的なものであってはならない。 簡単なプログラムは問題なく解釈・実行できるようにする。そのため、これ以上小さく作ることは難しいであろう。

このプログラム ci0 では、このページの冒頭に示したプログラムが実行できる。 現在のインタプリタの構文規則は次の通りである。

PrimExpression ::= Identifier | "(" Expr ")" | Constant | FunctionCall
MulExpression ::= PrimaryExpression ( ("*" | "/" | "%") PrimaryExpression )*
AddExpression ::= MulExpression ( ("+" | "-") MulExpression )*
RelationalExpression ::= addExpr [("<" | ">" | "<=" | ">=") addExpr]
EqualityExpression ::= RelationalExpr [ ("==" | "!=") RelationalExpr ]
expression ::= [Identifier "="] addExpression

TypeSpecifier ::= "void" | "char*" | "int"
VarDeclarator ::= Identifier
VariableDeclaration ::= TypeSpecifier VarDeclarator ["=" Initializer] 
                             ("," VarDeclarator ["=" Initializer])* 
CompoundStatement ::= "{" (Statements)* "}"
IfStatement ::= "if" "(" Expression ")" Statement [ "else" Statement ]
WhileStatement ::= "while" "(" Expression ")" Statement
ReturnStatement ::= "return" [Expression] ";"
Statement ::= CompoundStmt | IfStmt | ReturnStmt| Expression ";" | ";"
FunctionDefinition ::= TypeSpecifier  VarDeclarator 
     "(" [ VarDeclaration ("," VarDeclaration)* ] ")" CompoundStatement

 Program ::= (FunctionDefinition | VariableDeclaration ";")*

構文規則に含まれない仕様の概要は次の通りである。

  1. 子ブロックでは親ブロックと重複する変数名は使用できない。 インタプリタ内部の名前管理表はグローバルとローカルの二つだけである。
  2. ネィテイブ関数はprintf関数のみサポートしている。引数の数は書式を含めて4個まで。個数の拡張は簡単。
  3. データ型は基本的には int 型のみである。 printf関数の書式が文字列のため、部分的に文字列型をサポートしている。
  4. コメントは // から行末までの一行コメントのみサポートしている。 複数行コメント /* 〜 */ は後で提供する。
  5. 文字列中のエスケープ文字には対応していない。getStr関数のエスケープ文字対応版を後で提供する。

演算子は一部しかサポートしていない。その他の演算子のサポートを演習課題とする。 制御文は if〜else文とwhile文をサポートしている。 break文かcontinue文は後で一方をサポートし、他方を演習課題とする。 これを参考にして、do〜while文、for文は演習課題、switch文はちょっとこみいっているので、 演習の後半で説明する程度でいいだろう。

配列、構造体は構文規則を示して基本演習がいいだろう。

実数演算は考え方を示して演習は発展課題といったところであろう。

Windowsプログラムは考え方を説明して、動くものを提供するのがいいだろう。


現在のプログラムは2、3のオプションを備えている。 -codeオプションでは、生成された中間語コードを出力してから、このコードを実行する。 上の例題プログラムでは次のようになる。(最後の1行がプログラムの出力)

いずれ、もう少しは見やすくしたい。 しかし、アセンブリ言語に慣れていない限り、理解しにくいであろうから、 行数がさほど増えない範囲で見直す。

C:\mh\mcc>ci0 test.c -code
0: func str add
1: label int 1
2: entry
3: addsp int 0
4: push stack-val 2
5: push stack-val 3
6: add
7: ret
8: func str main
9: label int 2
10: entry
11: addsp int -3
12: push stack-ref -2
13: push int 1
14: mov
15: push stack-ref -3
16: push int 23
17: push int 12
18: call int 1
19: addsp int 2
20: mov
21: push stack-ref -1
22: push int 0
23: mov
24: label int 3
25: push stack-val -2
26: push int 10
27: le
28: jz int 4
29: push stack-ref -1
30: push stack-val -1
31: push stack-val -2
32: add
33: mov
34: push stack-ref -2
35: push stack-val -2
36: push int 1
37: add
38: mov
39: jmp int 3
40: label int 4
41: push stack-val -1
42: push stack-val -3
43: push str "add(12,23)=%d sum=%d"
44: call str printf
45: addsp int 3
46: ret
add(12,23)=35 sum=55

3.課題

文字列は mem配列にコピーする予定であったが、現在は mem配列には文字列のアドレスのみを置いている。 文字列型をフルサポートするとき、 構造体や配列データの置き方と合せて検討したい。