問題を解く際、問題に何らかの構造がある場合がある。このような場合には、問題の持つ構造を木構造で表現し、木構造を探索しながら問題を解くことが有効である。
７．１ 数式の処理
○課題
数式の文法が与えられたとき、文法に従って数式の値を計算する
インタプリタとコンパイラを作成せよ。
|
○外部仕様
標準入力から入力された数式に対して、
・インタプリタの場合は数式の値
・コンパイラの場合はその数式を計算するアセンブラ命令
を標準出力へ出力する。
●数式
数式として四則演算式のみを考える。四則演算式は、
加算：数値+数値、減算：数値-数値、乗算：数値*数値、除算：数値/数値
とその組み合わせであり、乗算・除算は加算・減算より優先的に組み合わされる。
●アセンブラ命令
スタック計算機のアセンブラとして以下のものを考える。
push 値： スタックに値を入れる
add ： スタックの値を２つ取り出し、２つの値の和を入れる
sub ： 〃 差
mul ： 〃 積
div ： 〃 商
print ： スタックの値を取り出し、標準出力へ出力する
例題7.1.1 数式 2*3 をアセンブラ命令で記述せよ。
１と２をスタックに入れ、和を計算し、出力すればよい。
push 2 push 3 mul print
○概要設計
１．数式を標準入力から読み込み、木構造で表現する
２．インタプリタの場合は、木構造を辿って数式の値を得る
コンパイラの場合は、木構造を辿りながらアセンブラ命令を出力する
○詳細設計
●アクセス関数
ａ．木構造の生成
T=CREATE()：標準入力から数式を読み込み木構造 T を生成する
ｂ．数値の計算
V=CALC(T)：木構造 T の値を求める
ｃ．アセンブラ命令の出力
ASSEMBLE(T)：木構造 T を計算するためのアセンブラ命令を出力する
●データ構造
木構造として、情報部 info と、左部分木のノード情報 left および右部分木のノード情報 right を持つ２分木を考える。２分木を構成するセルは以下のようになる。
typedef struct node {
DATATYPE info; ○（info）
struct node *left;
struct node *right; ○ ○
} NodeRec, *Node; left right
（注）DATATYPE は、情報フィールドの型であり、利用する問題により設定する。
問 7.1.1 数式を木構造で表現する場合、NodeRec の info フィールドはどのようなデータ型を想定すればよいか。
問 7.1.2 数式 1+2*3+4 を木構造で表現せよ。
問 7.1.3 数式 1+2*3+4 をアセンブラ命令に変換するとどのようになるか。
７．２ 構文解析と形式文法
数式などの文法は、書き換え規則によって記述できる。一般に文法あるいは言語は、
（ＶＮ，ＶＴ，Ｐ，Ｓ）
の４つ組によって記述される。ただし、Ｐは書き換え規則（rewriting rule）の集合である生成規則（production）、ＶＮは書き換え規則の左辺に現れる非終端記号（nonterminal symbol）、ＶＴは書き換え規則の右辺のみに現れる終端記号（terminal symbol）、Ｓは生成規則の適用を開始する非終端記号の開始記号（start symbol）である。
文法は書き換え規則の形式により以下のように幾つかのクラスに分類される。
３型文法：正規文法（regular grammar, RG）
２型文法：文脈自由型文法（context free grammar, CFG）
１型文法：文脈依存型文法（context sensitive grammar, CSG）
０型文法：句構造文法（phrase structure grammar, PSG）
下位の文法によって記述できる文法は必ず上位の文法によって記述できる。したがって、３型文法は２型文法の部分集合、２型文法は１型文法の部分集合、１型文法は０型文法の部分集合という関係になる。
例題7.2.1 四則演算のための数式の文法を文脈自由型文法により記述せよ。
非終端記号を <> で囲み、書き換えの選択肢を | で表現すれば、言語は以下のように記述できる。
非終端記号の集合ＶＮ＝{<数式>, <加法式>, <乗法式>, <加法演算子>, <乗法演算子>}
終端記号の集合ＶＴ＝{+, -, *, /, 数値}
開始記号＝<数式>
生成規則＝{
<数式> → <加法式>
<加法式> → <乗法式> | <加法式> <加法演算子> <乗法式>
<乗法式> → 数値 | <乗法式> <乗法演算子> 数値
<加法演算子> → '+' | '-'
<乗法演算子> → '*' | '/'
}
●文の生成と解析
文法に従って数式などの文を生成する際には、開始記号に書き換え規則を適用し、書き換え規則の左辺の非終端記号を右辺の記号列で置き換える。逆に、文法に従って文を解析する際には、書き換え規則の右辺を左辺の非終端記号で置き換え、最終的に開始記号に書き換えることができることを確かめることになる。
文法に従って入力文を解析する際、２つの段階に分けて解析することが多い。
１．字句解析
入力文を最小単位に分割する処理であり、最小単位のことをトークン（token）と呼ぶ。
例えば、数式 1+2*3+4 を字句解析すれば、
数値(1) '+' 数値(2) '*' 数値(3) '+' 数値(4)
のように分解される。
２．構文解析
文法にしたがってトークンを組み合わせる処理であり、全てのトークンを組み合わせることができた場合には、文法的に正しいと判定する。通常文法的に正しいかどうかを判定するだけでなく、トークンを組み合わせる際に必要な情報を抽出するための処理を行う。
例えば、トークン 「数値 '*' 数値」 は、
乗法式 '*' 数値 → 乗法式 → 加法式 → 数式
と組み合わせることができるので、文法的に正しいと判定できる。
例題7.2.2 例題7.2.1 の数式の文法に従い、数式 1+2*3+4 の構文解析木を構成せよ。
数式
加法式
加法式 乗法式
加法式 乗法式 数値
乗法式 乗法式 数値
数値 数値
１ '＋' ２ '＊' ３ '＋' ４
この結果、数式は (1+(2*3))+4 と解析されたことになる。
問 7.2.1 例題7.2.1 の数式の文法により幾つかの数式を生成せよ。
問 7.2.2 例題7.2.1 の数式の文法により 1+2-3*4 を解析せよ。
問 7.2.3 数式の文法に ( ) 表現を含めよ。
問 7.2.4 数式の文法に代入文を含めよ。（ヒント）代入文の形式は、「変数名=数式」
７．３ 木構造の実現
２分木の木構造は、情報を保持するフィールドと左部分木の情報・右部分木の情報の位置を指すフィールドから構成されるセルが下図のように接続されたものである。
○a
○b ○c
○d ○e ○f
木に関する処理としては、節点の挿入・削除、節点の移動があるが、節点の挿入・削除については、線形リストと同様に行うことができる。節点の移動についても同様に考えることができるが、木を辿る順序によって幾つかの移動法がある。
１．先行順序訪問
最初に親を訪問し、次に左部分木、右部分木の順に訪問する
２．中間順序訪問
最初に左部分木を訪問し、次に親、右部分木の順に訪問する
３．後行順序訪問
最初に左部分木を訪問し、次に右部分木、親の順に訪問する
例題7.3.1 上図 a〜f までの節点を先行・中間・後行順序で訪問したときの様子を述べよ。
・先行順序訪問： a, b, d, e, c, f
・中間順序訪問： d, b, e, a, f, c
・後行順序訪問： d, e, b, f, c, a
●アクセス関数
ａ．節点の生成
N=NEW(info, left, right)：情報 info、左部分木 left、右部分木 right である新しい節点 N を生成する
ｂ．情報フィールド
info=INFO(node)：節点 node の情報フィールド info を返す
ｃ．左部分木への移動
left=LEFT(node)：節点 node の左部分木 left を返す
ｄ．右部分木への移動
right=RIGHT(node)：節点 node の右部分木 right を返す
○コーディング
【NEW操作】
Cell NEW(DATATYPE info, Node left, Node right)
{
Node new;
new=malloc(sizeof(NodeRec));
if(new!=NULL) {
new->info=info;
new->left=left;
new->right=right;
}
return(new);
}
【INFO操作】
DATATYPE INFO(Node node)
{
return(node->info);
}
【LEFT操作】
Node LEFT(Node node)
{
return(node->left);
}
【RIGHT操作】
Node RIGHT(Node node)
{
return(node->right);
}
例題7.3.2 アクセス関数を利用して、後行で訪問する関数 PostTrip を作成せよ。
PreTrip は、情報部、左部分木、右部分木の順に訪問すればよい。
void PreTrip(Node node)
{
if(node!=NULL) {
INFO(node) を出力;
PreTrip(LEFT(node));
PreTrip(RIGHT(node));
}
}
InTrip は、左部分木、情報部、右部分木の順に訪問すればよい。
void InTrip(Node node)
{
if(node!=NULL) {
InTrip(LEFT(node));
INFO(node) を出力;
InTrip(RIGHT(node));
}
}
PostTrip は、左部分木、右部分木、情報部の順に訪問すればよい。
void PostTrip(Node node)
{
if(node!=NULL) {
PostTrip(LEFT(node));
PostTrip(RIGHT(node));
INFO(node) を出力;
}
}
問 7.3.1 例題7.3.1 を参考にして、先行・中間順序で訪問する関数 PreTrip, InTrip を作成せよ。
問 7.3.2 親節点名、左節点名、右節点名が各行に記述されたファイルを読み込み、木を構成するためのアクセス関数を考えよ。
問 7.3.3 問 7.3.2 のアクセス関数により、例題7.3.1 の木を記述したファイルを読み込み、木を構成せよ。
問 7.3.4 問 7.3.3 で構成した木に対して、先行・中間・後行順序で訪問し、節点名を出力せよ。
７．４ 数式の字句解析と構文解析
数式の字句解析および構文解析を考える。字句解析を支援するツールとして lex、構文解析を支援するツールとして yacc がよく知られているが、ここでは全てＣ言語により実現する。
○字句解析
字句解析では、'+', '-', '*', '/' の演算子および数値（NUMBER）をトークンとして返す必要があるが、この他にファイルの終わり（END_FILE）、行の終わり（END_LINE）、エラー（ERROR）も返すことにする。
●アクセス関数
T=GetToken()：標準入力から読み込んだトークン T を返す
●データ構造
トークンは、'+', '-', '*', '/', NUMBER, END_FILE, END_LINE, ERROR という型を示す type フィールドと、型が NUMBER の場合にその数値を持つ value フィールドから構成する。
typedef struct {
int type, value;
} TokenRec, *Token;
【GetToken操作】
トークンの終わりを検出するために一文字先読みが必要な場合があるため、c に一文字先の文字を入れておく。ただし、先読みしていない場合は、c を EMPTY としている。
数値の場合には、一旦数字を token_text に入れ、型を NUMBER とし、token_text に入った文字列を atoi 関数で整数値に変換した結果を value フィールドの値としている。
#define END_FILE (-1)
#define END_LINE (-2)
#define NUMBER (-3)
#define ERROR (-4)
#define EMPTY (-5)
Token GetToken(void)
{
static int c=EMPTY;
static char token_text[TOKEN_SIZE];
static TokenRec token_rec;
int i;
if(c==EMPTY)
c=getchar(); /* 一文字先読みする */
while(isspace(c) && c!='\n')
c=getchar(); /* 空白を読み飛ばす */
switch(c) {
case '+': case '-': /* 加法演算子 */
case '*': case '/': /* 乗法演算子 */
token_rec.type=c;
break;
case '\n': /* 行末（改行コード） */
token_rec.type=END_LINE;
break;
case EOF: /* ファイルの終わり */
token_rec.type=END_FILE;
break;
default:
for(i=0; isdigit(c); ++i) { /* 数字の読込 */
token_text[i]=c;
c=getchar();
}
if(i==0) { /* エラー */
fprintf(stderr, "文字 %c は解釈できません\n", c);
token_rec.type=ERROR;
token_rec.value=c;
}
else { /* 数値 */
token_text[i]='\0';
token_rec.type=NUMBER;
token_rec.value=atoi(token_text);
return(&token_rec);
}
}
c=EMPTY; /* 先読み文字のクリア */
return(&token_rec);
}
○構文解析
構文解析を行う方法は様々であるが、ここでは直感的に理解しやすい再帰的下向き構文解析について簡単に説明する。例えば、
<AddExpression> → NUMBER '+' <AddExpression>
のような書き換え規則を、
AddExpression()
{
トークンを読み NUMBER であることを確認
トークンを読み '+' であることを確認
AddExpression();
}
のように実現するのである。ところが、
<AddExpression> → <AddExpression> '+' NUMBER
のような左再帰の書き換え規則では、
AddExpression()
{
AddExpression();
トークンを読み '+' であることを確認
トークンを読み NUMBER であることを確認
}
のようになり、無限ループに陥ってしまう。例題7.2.1 の文法では、このような左再帰の書き換え規則が含まれているため、左再帰を含まない形式に変換しておく必要がある。
Ａ → Ａα | β （βはＡでは始まらない）
という左再帰の書き換え規則は、
Ａ → βＡ'
Ａ' → αＡ' | ε （εは空を意味する）
というような左再帰を含まない形式に変換できる。したがって、例題7.2.1 の文法は、
<Expression>
→ <AddExpression>
<AddExpression>
→ <ProdExpression> <AddExpr_1>
<AddExpr_1>
→ {'+'|'-'} <ProdExpression> <AddExpr_1> | ε
<ProdExpression>→ NUMBER <ProdExpr_1>
<ProdExpr_1>
→ {'*'|'/'} NUMBER <ProdExpr_1> | ε
のように変換される。
●アクセス関数
ａ．数式
T=Expression()：トークンが１つ先読みされた状態で、標準入力から読み込んだ数式の木構造 T を返す
ｂ．加法式
T=AddExpression()：トークンが１つ先読みされた状態で、標準入力から読み込んだ加法式の木構造 T を返す
ｃ．乗法式
T=ProdExpression()：トークンが１つ先読みされた状態で、標準入力から読み込んだ乗法式の木構造 T を返す
ｄ．数値
T=Number()：トークンが１つ先読みされた状態で、標準入力から読み込んだ数値の木構造 T を返す
このアクセス関数により、数式 1+2*3+4 から以下のような木構造を生成する。
●データ構造
木構造のデータ型をトークンの型にする。トークンを先読みし、token に先読みしたトークンを設定しておくことにする。
○コーディング
【CREATE操作】
トークンを先読みし、改行およびエラーは読み飛ばし、ファイルの終わりでは NULL を返す。それ以外のトークンの場合には、Expression を呼び出す。
Node CREATE(void)
{
if(token==NULL)
token=GetToken(); /* トークンの先読み */
while(token->type==END_LINE || token->type==ERROR)
token=GetToken();
if(token->type==END_FILE)
return(NULL);
return(Expression());
}
【Expression操作】
<Expression> → <AddExpression> を実現する。
Node Expression(void)
{
return(AddExpression());
}
【AddExpression操作】
<AddExpression> → <ProdExpression> <AddExpr_1> を実現する。
【AddExpr_1関数】
<AddExpr_1> → {'+'|'-'} <ProdExpression> <AddExpr_1> | ε を実現する。
Node AddExpr_1(Node prod1)
{
Node prod2;
TokenRec t_rec;
switch(token->type) {
case '+': case '-':
t_rec=(*token);
token=GetToken();
prod2=ProdExpression();
return(AddExpr_1(NEW(t_rec, prod1, prod2)));
default:
return(prod1);
}
}
【ProdExpression操作】
<ProdExpression> → NUMBER <ProdExpr_1> を実現する。
【ProdExpr_1関数】
<ProdExpr_1> → {'*'|'/'} NUMBER <ProdExpr_1> | ε を実現する。
Node ProdExpr_1(Node number1)
{
Node number2;
TokenRec t_rec;
switch(token->type) {
case '*': case '/':
t_rec=(*token);
token=GetToken();
number2=Number();
return(ProdExpr_1(NEW(t_rec, number1, number2)));
default:
return(number1);
}
}
【Number操作】
トークンが数値ならば、木構造の節点を生成する。
Node Number(void)
{
Node number;
if(token->type!=NUMBER) {
fprintf(stderr, "数値が必要です\n");
number=NULL;
}
else number=NEW(*token, NULL, NULL);
token=GetToken();
return(number);
}
問 7.4.1 字句解析 GetToken 操作がトークン '(', ')' を返すようにせよ。
問 7.4.2 数式の文法に '(', ')' 表現を加え、構文解析を実現せよ。
問 7.4.3 数式の文法に代入文を含め、構文解析を実現せよ。
７．５ インタプリタ
構文解析の結果得られる木構造を参照して、数式の値を計算するインタプリタを実現する。
○コーディング
【CALC操作】
節点の情報部はトークンなので、トークンの type フィールドにより対応する演算を行う。演算はオペランドを計算した後で行うので、後行順序の訪問となる。
int CALC(Node node)
{
if(node!=NULL) {
switch(INFO(node).type) {
case NUMBER:
return(INFO(node).value);
case '+':
return(CALC(LEFT(node))+CALC(RIGHT(node)));
case '-':
return(CALC(LEFT(node))-CALC(RIGHT(node)));
case '*':
return(CALC(LEFT(node))*CALC(RIGHT(node)));
case '/':
return(CALC(LEFT(node))/CALC(RIGHT(node)));
}
}
return(0);
}
【main関数】
void main(void)
{
Node node;
while((node=CREATE())!=NULL)
printf("%d\n", CALC(node));
}
○数式と記法
数式の記法としては、
・中間置記法（infix notation）
<オペランド１><演算子><オペランド２>の順に記述する通常の形式
・前置記法（prefix notation）、ポーランド記法（polish notation）
<演算子><オペランド１><オペランド２>の順に記述する
・後置記法（postfix notation）、逆ポーランド記法（inverse polish notation）
<オペランド１><オペランド２><演算子>の順に記述する
という記法がある。特に、逆ポーランド記法は、スタックを利用することにより簡単に実行できるためインタプリタに採用されることも多い。
問 7.5.1 数式をポーランド記法に変換するためのコーディングを実現せよ。
問 7.5.2 数式を逆ポーランド記法に変換するためのコーディングを実現せよ。
７．６ コンパイラ
構文解析の結果得られる木構造を参照して、スタック用のアセンブラ命令を出力するコンパイラを実現する。
○コーディング
【ASSEMBLE操作】
数式の木構造を計算する命令を Instruction 関数により生成した後、print命令を生成する。
void ASSEMBLE(Node node)
{
Instruction(node);
printf("print\n");
}
【Instruction関数】
数値は「push 値」、和は「add」、差は「sub」、積は「mul」、商は「div」命令を生成する。
void Instruction(Node node)
{
if(node!=NULL) {
if(INFO(node).type==NUMBER)
printf("push %d\n", INFO(node).value);
else {
Instruction(LEFT(node));
Instruction(RIGHT(node));
switch(INFO(node).type) {
case '+':
printf("add\n"); break;
case '-':
printf("sub\n"); break;
case '*':
printf("mul\n"); break;
case '/':
printf("div\n"); break;
}
}
}
}
【main関数】
問 7.6.1 スタック用アセンブラ命令を解釈実行するスタック計算機を設計し、コーディングを行え。
問 7.6.2 アキュムレータとメモリから構成される計算機のアセンブラ命令を設計し、設計したアセンブラ用のコンパイラを作成せよ。
（注）アキュムレータとは、レジスタの一種であり、
load Ｍ Ａ＝Ｍ
store Ｍ Ｍ＝Ａ
add Ｍ Ａ＝Ａ＋Ｍ
sub Ｍ Ａ＝Ａ−Ｍ
mul Ｍ Ａ＝Ａ＊Ｍ
div Ｍ Ａ＝Ａ／Ｍ
print Ａの内容を標準出力に表示
などのように、演算はメモリＭとアキュムレータＡの間で行われる。
問 7.6.3 ２つのレジスタＲ１，Ｒ２とメモリから構成される計算機のアセンブラ命令を設計し、設計したアセンブラ用のコンパイラを作成せよ。
（注）算術演算がレジスタ間のみで行われるとすれば、
load Ｒ，Ｍ Ｒ＝Ｍ
store Ｒ，Ｍ Ｍ＝Ｒ
add Ｒ1＝Ｒ1＋Ｒ2
sub Ｒ1＝Ｒ1−Ｒ2
mul Ｒ1＝Ｒ1＊Ｒ2
div Ｒ1＝Ｒ1／Ｒ2
print Ｒ Ｒ1あるいはＲ2の内容を標準出力に表示
などのようになる。ただし、ＲはＲ1でもＲ2でもよいことを意味する。