プログラミング言語処理

言語処理系とは

インタプリタとコンパイラ

言語処理系とは、プログラミング言語で記述されたプログラムを計算機上で実行するためのソフトウエアである。そのための構成として、大別して２つの構成方法がある。

インタープリター（interpreter,翻訳系）：言語の意味を解析しながら、その意味する動作を実行する。
コンパイラ（compiler,通訳系）：言語を他の言語に変換し、その言語のプログラムを計算機上で実行させるもの。狭い意味でコンパイラは、言語を機械語に変換し、実行するものであるが、他の言語、あるいは仮想機械コードに変換するものもコンパイラと呼ぶ。他の言語に変換するときには、特に translatorと呼ぶ場合もある。

元のプログラムをソースプログラム、翻訳の結果と得られるプログラムをオブジェクトプログラムと呼ぶ。機械語で直接、計算機上で実行できるプログラムを実行プログラムと呼ぶ。オブジェクトプログラムがアセンブリプログラムの場合には、アセンブラにより機械語に翻訳されて、実行プログラムを得る。他の言語の場合には、オブジェクトプログラムの言語のコンパイラでコンパイルすることにより、実行プログラムが得られる。仮想マシンコードの場合には、オブジェクトコードはその仮想マシンにより、インタプリトされて実行される。

言語処理系の基本構成

コンパイラにしてもインタプリターにしても、その構成は多くの共通部分を持つ。すなわち、ソースプログラムの言語の意味を解釈する部分は共通である。インタプリターは、解釈した意味の動作をその場で実行するのに対し、コンパイラではその意味の動作を行うコードを出力する。

言語処理系は、大きく分けて、次のような部分からなる。

字句解析(lexical analysis): 文字列を言語の要素（トークン、token）の列に分解する。
構文解析(syntax analysis): token列を意味を反映した構造に変換。この構造は、しばしば、木構造で表現されるので、抽象構文木（abstract syntax tree）と呼ばれる。ここまでの言語を認識する部分を言語のparserと呼ぶ。
意味解析(semantics analysis): 構文木の意味を解析する。インタプリターでは、ここで意味を解析し、それに対応した動作を行う。コンパイラでは、この段階で内部的なコード、中間コードに変換する。
最適化(code optimization): 中間コードを変形して、効率のよいプログラムに変換する。
コード生成(code generation): 内部コードをオブジェクトプログラムの言語に変換し、出力する。例えば、ここで、中間コードよりターゲットの計算機のアセンブリ言語に変換する。

コンパイラの性能とは、如何に効率のよいオブジェクトコードを出力できるかであり、最適化でどのような変換ができるかによる。インタープリタでは、プログラムを実行するたびに、字句解析、構文解析を行うために、実行速度はコンパイラの方が高速である。もちろん、機械語に翻訳するコンパイラの場合には直接機械語で実行されるために高速であるが、コンパイラでは中間コードでやるべき操作の全体を解析することができるため、高速化が可能である。

また、中間言語として、都合のよい中間コードを用いると、いろいろな言語から中間言語への変換プログラムを作ることで、それぞれの言語に対応したコンパイラを作ることができる。

例題：式の評価

さて、例として最も簡単な数式の評価について、インタプリターとコンパイラを作ってみることにする。目的は，

12 + 3 - 4

の式の入力に対し、この式を計算し、

と出力するプログラムを作ることである。これは、式という「プログラミング言語」を処理する言語処理系である。「式」という言語では、tokenとして、数字と"+"や"-"といった演算子がある。

まずは、字句解析ではこれらのトークンを認識する。例えば、上の例では、

１２の数字、＋の演算子、３の数字、−の演算子、４の数字、終わり

という列に変換する。

tokenは、tokenの種類と12の数字という場合の12の値の2つの組で表される。以下にtokenの種類を定義するexprParser.hを示す。

exprParser.h (一部) (ソースコードはこちらから)
#define EOL 0
#define NUM 1
#define PLUS_OP  2
#define MINUS_OP 3

extern int tokenVal;
extern int currentToken;

exprParser.h (一部) (ソースコードはこちらから)
#define EOL 0 #define NUM 1 #define PLUS_OP 2 #define MINUS_OP 3 extern int tokenVal; extern int currentToken;

字句解析を行う関数getTokenを示す。

getToken.c (ソースコードはこちらから)
void getToken() { int c,n; again: c = getc(stdin); switch(c){ case '+': currentToken = PLUS_OP; return; case '-': currentToken = MINUS_OP; return; case '\n': currentToken = EOL; return; } if(isspace(c)) goto again; if(isdigit(c)){ n = 0; do { n = n*10 + c - '0'; c = getc(stdin); } while(isdigit(c)); ungetc(c,stdin); tokenVal = n; currentToken = NUM; return; } fprintf(stderr,"bad char '%c'\n",c); exit(1); }

void getToken()
{
    int c,n;
again:
    c = getc(stdin);
    switch(c){
    case '+': 
	currentToken = PLUS_OP;
	return;
    case '-': 
	currentToken = MINUS_OP;
	return;
    case '\n': 
	currentToken = EOL;
	return;
    }
    if(isspace(c)) goto again;
    if(isdigit(c)){
	n = 0;
	do {
	    n = n*10 + c - '0';
	    c = getc(stdin);
	} while(isdigit(c));
	ungetc(c,stdin);
	tokenVal = n;
	currentToken = NUM;
	return;
    }
    fprintf(stderr,"bad char '%c'\n",c);
    exit(1);
}

getToken.c (ソースコードはこちらから)

この関数は、字句を読み込み、currentTokenにtokenの種類、NUMの場合に tokenValに値を返す。

これを使うことにより、いわゆる構文解析しなくても、直接実行する（計算してしまう）インタプリターは簡単にできる。その動作は以下のような動作である。

現在の結果を変数resultに覚えておく。また、直前の演算子を変数opに覚えておく。
関数getTokenを呼んで、数字であれば、現在の結果と今の数字の値との計算を行う。但し、最初の数字（まだ、opがない）の場合には、現在の結果に入力された数字を格納する。
終わりがきたら、現在の数字を出力する。

これが、いわゆる電卓のアルゴリズムである。（この電卓の欠点を考えてみよ！）

cal.c
main() { int t; int op; int result; op = NUM; result = 0; while(1){ getToken() switch(currentToken){ case NUM: switch(op){ case NUM: result = tokenVal; break; case PLUS_OP: result = result + tokenVal; break; case MINUS_OP: result = result - tokenVal; break; } break; case PLUS_OP: case MINUS_OP: op = t; break; case EOL: printf("result = %d\n",result); exit(0); } } }

cal.c

main()
{
    int t;
    int op;
    int result;

    op = NUM;
    result = 0;
    while(1){
	getToken()
	switch(currentToken){
	case NUM:
	    switch(op){
	    case NUM: 
		result = tokenVal;
		break;
	    case PLUS_OP:
		result = result + tokenVal;
		break;
	    case MINUS_OP:
		result = result - tokenVal;
		break;
	    }
	    break;
	case PLUS_OP:
	case MINUS_OP:
	    op = t;
	    break;
	case EOL:
	    printf("result = %d\n",result);
	    exit(0);
	}
    }
}

ＢＮＦと構文木

では、この「式」というプログラミング言語の構文とはどのようなものであろうか。例えば、次のような規則が構文である。

　　足し算の式　:=  式　＋の演算子　式
　　引き算の式　:=  式　−の演算子　式
　　式　:= 数字　|  足し算の式 ｜　引き算の式

このような記述を、BNF (Backus Naur Form または Buckus Normal Form) という。

このような構造を反映するデータ構造を作るのが、構文解析である。図に示す。

構文解析のデータ構造は、以下のような構造体を作る。これをexprParser.hに定義しておく。

exprParser.h (一部) (ソースコードはこちらから)
typedef struct _AST {    
    int op;
    int val;
    struct _AST *left;
    struct _AST *right;
} AST;

AST *readExpr(void);

exprParser.h (一部) (ソースコードはこちらから)
typedef struct _AST { int op; int val; struct _AST left; struct _AST right; } AST; AST *readExpr(void);

この構文木を作るプログラムが、readExpr.cである。このプログラムでは、exprParser.hで定義されているASTを使って、構文木を作っている。このデータ構造は式の場合は、演算子とその左辺の式と右辺の式を持つ。数字の場合はこれらを使わずに値のみを格納する。tokenを読むたびに、データ構造を作っている。

readExpr.c (ソースコードはこちらから)
AST readExpr() { int t; AST e,ee; e = readNum(); while(currentToken == PLUS_OP \|\| currentToken == MINUS_OP){ ee = (AST )malloc(sizeof(AST)); ee->op = currentToken; getToken(); ee->left = e; ee->right = readNum(); e = ee; } return e; } AST readNum() { AST e; if(currentToken == NUM){ e = (AST *)malloc(sizeof(AST)); e->op = NUM; e->val = tokenVal; getToken(); return e; } else { fprintf(stderr,"bad expression: NUM expected\n"); exit(1); } }

readExpr.c (ソースコードはこちらから)

AST *readExpr()
{
    int t;
    AST *e,*ee;

    e = readNum();
    while(currentToken == PLUS_OP || currentToken == MINUS_OP){
	ee = (AST *)malloc(sizeof(AST));
	ee->op = currentToken;
	getToken();
	ee->left = e;
	ee->right = readNum();
	e = ee;
    }
    return e;
}

AST *readNum()
{
    AST *e;
    if(currentToken == NUM){
	e = (AST *)malloc(sizeof(AST));
	e->op = NUM;
	e->val = tokenVal;
	getToken();
	return e;
    } else {
	fprintf(stderr,"bad expression: NUM expected\n");
	exit(1);
    }
}

解釈実行：インタプリター

この構文木を解釈して実行する、すなわちインタプリターをつくってみることにする。その動作は、

式が数字であれば、その数字を返す。
式が演算子を持つ演算式であれば、左辺と右辺を解釈実行した結果を、演算子の演算を行い、その値を返す。

このプログラムがevalExpr.cである。 evalExpr.cは、構文木ASTを解釈して、解釈する。

数字のASTつまり、opがNUMであれば、その値を返す。
演算式であれば、左辺を評価した値と右辺を評価した値をopに格納されている演算子にしたがって、計算を行う。

これらは再帰的に呼び出しが行われていることに注意しよう。

evalExpr.c (ソースコードはこちらから)
int evalExpr(AST *e) { switch(e->op){ case NUM: return e->val; case PLUS_OP: return evalExpr(e->left)+evalExpr(e->right); case MINUS_OP: return evalExpr(e->left)-evalExpr(e->right); default: fprintf(stderr,"evalExpr: bad expression\n"); exit(1); } }

evalExpr.c (ソースコードはこちらから)

int evalExpr(AST *e)
{
    switch(e->op){
    case NUM: 
	return e->val;
    case PLUS_OP:
	return evalExpr(e->left)+evalExpr(e->right);
    case MINUS_OP:
	return evalExpr(e->left)-evalExpr(e->right);
    default:
	fprintf(stderr,"evalExpr: bad expression\n");
	exit(1);
    }
}

mainプログラムでは、関数readExprを呼び、構文木を作り、それを関数 evalExprで解釈実行して、その結果を出力する。これが、インタプリターである。先のプログラムと大きく違うのは、式の意味を表す構文木が内部に生成されていることである。この構文木の意味を解釈するのがインタプリターである。 (readExprでは１つだけ先読みが必要であるので、getTokenを呼び出している)

interpreter.c (ソースコードはこちらから)
int main() { AST *e; getToken(); e = readExpr(); if(currentToken != EOL){ printf("error: EOL expected\n"); exit(1); } printf("= %d\n",evalExpr(e)); exit(0); }

コンパイラとは

次にコンパイラをつくってみる。コンパイラとは、解釈実行する代わりに、実行すべきコード列に変換するプログラムである。実行すべきコード列は、通常、アセンブリ言語（機械語）であるが、そのほかのコードでもよい。中間コードとして、スタックマシンのコードを仮定することにする。スタックマシンは以下のコードを持つことにする。

PUSH n ：　数字nをスタックにpushする。
ADD ：　スタックの上２つの値をpopし、それらを加算した結果をpushする。
SUB : スタックの上２つの値をpopし、減算を行い、pushする。
PRINT: スタックの値をpopし、出力する。

コンパイラは、このスタックマシンのコードを使って、式を実行するコード列を作る。例えば、図で示した例の式12+3-4は下のようなコードになる。

  PUSH 12
  PUSH 3
  ADD
  PUSH 4
  SUB 
  PRINT

スタックマシンでの実行は以下のように行われる。

stackCode.hには、コードとその列を格納する領域を定義してある。

stackCode.h (ソースコードはこちらから)
#define PUSH 0 #define ADD 1 #define SUB 2 #define PRINT 3 #define MAX_CODE 100 typedef struct _code { int opcode; int operand; } Code; extern Code Codes[MAX_CODE]; extern int nCode;

コンパイルの手順は、以下のようになる。

式が数字であれば、その数字をpushするコードを出す。
式が演算であれば、左辺と右辺をコンパイルし、それぞれの結果をスタックにつむコードを出す。その後、演算子に対応したスタックマシンのコードを出す。
式のコンパイルしたら、PRINTのコードを出しておく。

この中間コードを生成するのが、compileExpr.cである。構文木を入力して、再帰的に上のアルゴリズムを実行する。コードはCodesという配列に格納しておく。

compileExpr.c (ソースコードはこちらから)
void compileExpr(AST *e) { switch(e->op){ case NUM: Codes[nCode].opcode = PUSH; Codes[nCode].operand = e->val; break; case PLUS_OP: compileExpr(e->left); compileExpr(e->right); Codes[nCode].opcode = ADD; break; case MINUS_OP: compileExpr(e->left); compileExpr(e->right); Codes[nCode].opcode = SUB; break; } ++nCode; }

compileExpr.c (ソースコードはこちらから)

void compileExpr(AST *e)
{
    switch(e->op){
    case NUM: 
	Codes[nCode].opcode = PUSH;
	Codes[nCode].operand = e->val;
	break;
    case PLUS_OP:
	compileExpr(e->left);
	compileExpr(e->right);
	Codes[nCode].opcode = ADD;
	break;
    case MINUS_OP:
	compileExpr(e->left);
	compileExpr(e->right);
	Codes[nCode].opcode = SUB;
	break;
    }
    ++nCode;
}

コード生成では、ここではスタックマシンのコードをCに直して出力することにしよう。Cで実行させるために、mainにいれておくことにする。このプログラムが、codeGen.cである。

codeGen.c (ソースコードはこちらから)
void codeGen() { int i; printf("int stack[100]; \nmain(){ int sp = 0; \n"); for(i = 0; i < nCode; i++){ switch(Codes[i].opcode){ case PUSH: printf("stack[sp++]=%d;\n",Codes[i].operand); break; case ADD: printf("sp--; stack[sp-1] += stack[sp];\n"); break; case SUB: printf("sp--; stack[sp-1] -= stack[sp];\n"); break; case PRINT: printf("printf(\"%%d\\n\",stack[--sp]);\n"); break; } } printf("}\n"); }

codeGen.c (ソースコードはこちらから)

void codeGen()
{
    int i;
    printf("int stack[100]; \nmain(){ int sp = 0; \n");
    for(i = 0; i < nCode; i++){
	switch(Codes[i].opcode){
	case PUSH:
	    printf("stack[sp++]=%d;\n",Codes[i].operand);
	    break;
	case ADD:
	    printf("sp--; stack[sp-1] += stack[sp];\n");
	    break;
	case SUB:
	    printf("sp--; stack[sp-1] -= stack[sp];\n");
	    break;
	case PRINT:
	    printf("printf(\"%%d\\n\",stack[--sp]);\n");
	    break;
	}
    }
    printf("}\n");
}

コンパイラのmainプログラムであるが、readExprまではインタープリタと同じである。標準出力に出力されるプログラムに適当に名前をつけ（たとえば、 output.c）これをCコンパイラでコンパイルして実行すればよい。（assembler のファイルの場合はasコマンドでコンパイルする。）

codeGen.c (ソースコードはこちらから)
int main() { AST *e; getToken(); e = readExpr(); if(currentToken != EOL){ printf("error: EOL expected\n"); exit(1); } nCode = 0; compileExpr(e); Codes[nCode++].opcode = PRINT; codeGen(); exit(0); }

電卓のプログラムに比べて、構文木を作るなど、ずいぶん遠周りをしたようであるが、その理由は演算の優先度や、括弧の式など、通常の数学で使われる式を正しく処理するためである。例えば、

　12*3 + 3*4

の場合には、掛け算を最初にして、それらを加算しなくてはならない。この処理を反映した構文木を作ることによって、正しく処理する「言語処理系」を作ることができるようになる。

ソースコード

式のインタプリター
- exprParser.h
- interpreter.c
- evalExpr.c
- getToken.c
- readExpr.c
- コンパイルの方法
```
 % cc -o interpreter interpreter.c evalExpr.c getToken.c readExpr.c 
```
- 実行の方法
  1. ファイル(input)に式を書いておく。
  2. それを標準入力にして実行
```
 % ./interpreter < input 
```
式のコンパイラ
- exprParser.h
- compiler.c
- compileExpr.c
- codeGen.c
- getToken.c
- readExpr.c
- コンパイルの方法
```
 % cc -o compile compile.c compileExpr.c codeGen.c getToken.c readExpr.c 
```
- 実行の方法
  1. ファイル(input)に式を書いておく。
  2. それを標準入力、標準出力としてoutput.cに出力
```
 % ./compile < input > output.c 
```
  3. output.cをコンパイル
```
 % cc output.c 
```
  4. 実行
```
 % a.out 
```
Makefile