コンパイラの基礎原理 II

コンパイラの基本原理 II
–bison を用いた構文解析ルーチンの作成–
目的
1
前回の実験では，flex を用いて字句解析器を作成し，プログラムを字句に分解した．その後，分割された字句
が，プログラミング言語の文法に正しく対応しているか検査する構文解析に移行する．今回の実験では，bison を
用いて構文解析器を作成し，解構文解析の概念と仮想マシンのアーキテクチャおよびそのアセンブリ言語につい
て理解する．
原理
2
2.1
形式文法
形式言語理論における文法とは，非終端記号の集合 VN ，終端記号の集合 VT ，生成規則の集合 P ，開始記号 S
の 4 つ要素によって構成される 4 つ組 G = (VN , VT , P, S) である．
非終端記号
非終端記号とは生成規則を記述するために用いられる変数のことで，生成規則の左辺に現れる記号
のことである．
終端記号
終端記号は正規表現のアルファベットの要素からなる記号列の集合で，生成規則の右辺にのみ現れる．
生成規則
生成規則とは，非終端記号と終端記号を用いて表された書き換え規則のことである．例えば，加算と
乗算からのみなる数式を生成できる生成規則 P は
P = {E → T | E + T,
T → F | T ∗ F,
F → N U M | (E)}
のようになる．ここで，VN = {E, T, F } は非終端記号， VT = {+, ∗, (, ), N U M } は終端記号である．ただし，
N U M は r([1 − 9][0 − 9]∗) のような正規表現で表される数に対応しているものとし，| は「または」を意味する．
開始記号
開始記号は，文の生成をどの生成規則から始めるかを指定する．上記，加算と乗算のみからなる数式
の場合，E が開始記号である．開始記号から始めて，次々に生成規則を適用していけば，その文法に属する様々
な文が生成できる．
予習問題
正規文法および文脈自由文法について調べ，オートマトンならびにコンパイラとの関連についてまとめよ．
2.2
構文解析
構文解析とは，字句解析で切り出されたトークンが，どのような文法からから生成されるのかを解析すること
である．構文解析を行うプログラムを構文解析器と呼ぶ．そして，その解析過程を利用して簡単な数式を仮想マ
シンのアセンブリ言語に変換する．
1
構文解析器作成ツール Bison
2.2.1
本実験では，文法定義から構文解析器を生成するツール Bison（yacc 互換）を用いる．Bison の記述形式につ
いて簡単に解説する．
%{
C 言語で記述したヘッダファイルやマクロの定義
..........【 1 】
%}
非終端記号や演算子の優先順位などの宣言
..........【 2 】
%%
文法の定義
..........【 3 】
%%
C 言語のコード
..........【 4 】
【 1 】では，
【 3 】や【 4 】に現れる C 言語のコードが用いるヘッダファイルの参照やマクロの定義などを記
述する．
【 2 】では，終端記号や非終端記号の宣言および対応する値のデータ型，演算子の優先順位などを宣言す
る．
【 3 】では，生成規則を記述し規則を認識したときの処理（意味処理）を設計する．
【 4 】では，プログラム中
で使用する関数など，C 言語のコードを記述する．
宣言の記述
【 2 】のブロックでは，生成規則の記述に使用する
• 終端記号
• 属性値の型
• 開始記号
などを宣言する．
終端記号は，
%token
終端記号列
なる書式で宣言する．例えば，符号なし整数（名前を N U M とする）を宣言するなら
%token
NUM
と記述する．終端記号として宣言された「名前」は，bison により生成される C 言語のプログラムの中でマクロ
として定義され，一意な値が与えられる．このマクロは，字句解析器とのインターフェイスでトークンの種別の値
として用いられる．なお，1 文字の終端記号であれば宣言する必要はなく，後に説明する「生成規則の記述」で，
「’+’」のような文字定数の形式で記述できる．このときの種別の値は，その文字の ASCII コードが用いられる．
属性値の型は，
%union {
型フィールド名;
.....
}
なる書式で宣言する．そして，属性値を参照される各記号に対してもその型を指定する必要がある．非終端記号
の場合は
2
%type <フィールド名> 記号列
で，終端記号を %token で宣言する場合は
%token <フィールド名> 終端記号列
で属性値を宣言できる．
開始記号は，
%start 非終端記号
で宣言する．
生成規則の記述
【 3 】のブロックには，生成規則の左辺の非終端記号，記号 “:”，右辺の非終端記号および終
端記号からなる記号列の順に記述する．そして，C 言語で記述した意味処理を，中括弧 “{
}” で囲む．左辺の
非終端記号が同一の生成規則が複数存在するときは，“|” で区切って書くこともできる．
例えば，生成規則が
E →T | E+T
で，意味処理として対応する演算を行う場合，
E : T
| E ’+’ T
{ $$ = $1; }
{ $$ = $1 + $3; }
<----- (*)
;
と書く．各記号と意味処理には，属性と呼ばれる値が対応している．意味処理における “$$” は，
「生成規則の左辺
の非終端記号の属性（値）」を，“$n” は，
「生成規則の右辺の n 番目の記号の属性（値）」を意味する．なお，終端
記号もひとつの記号である．したがって，(*) の意味処理は，
「右辺の E の属性値（$1）と T の属性値（$3）の和
を，左辺の E の属性値とする」ことを表す．
予習問題
加算と乗算からのみなる数式を生成できる生成規則 P として
P = {E → E + E | E ∗ E | (E) | N U M }
を用いたときの問題点と，その問題を Bison ではいかに回避しているかを論ぜよ．
ヒント：「曖昧な文法，演算子の優先順位，結合規則」について調査し，“1 + 2 + 3” および “1 + 2 * 3” と
いった具体例を挙げながら説明すること．
bison の使い方についての詳細は，以下を参照すること．
http://ipr20.cs.ehime-u.ac.jp/~kinoshita/exp3
2.2.2
還元による構文解析
生成規則の矢印（→）を逆にたどることを還元と呼ぶ．開始記号から出発して，生成規則をくり返し適用して
生成された文であれば，還元を繰り返すことで，いずれは開始記号にたどり着くはずである．この場合，その文
はその文法から生成される，あるいは受理されると言う．この還元の過程を利用して構文解析木などを作る構文
解析法があり， Bison ではこの方法を用いている．
例えば，1 ∗ 2 + 3 の 1 ∗ 2 の部分は
T → F → 1 (N U M )
F → 2 (N U M )
3
により，1, 2 がそれぞれ T, F に還元され T ∗ F + 3 となる．すると，T ∗ F が生成規則 T → T ∗ F の右辺とマッ
チするので，T + 3 に還元される．次に，
E→T
T → F → 3 (N U M )
により，T, 3 がそれぞれ E, T に還元され， T + 3 は E + T となる．すると， E → E + T の右辺とマッチする
ので，E に還元される．これは開始記号であり，この文法で 1 ∗ 2 + 3 が生成でき受理できることを意味する．以
上の還元の過程を表 1 に示す．
文
2.3
表 1: 還元の過程
適用する規則
1∗2+3
F ∗2+3
F → 1 (N U M )
T →F
T ∗2+3
T ∗F +3
F → 2 (N U M )
T →T ∗F
T +3
E→T
E+3
E+F
F → 3 (N U M )
T →F
E+T
E
E →E+T
アセンブリ言語
コンピュータが直接実行できるコードのことを機械語と言う．これは，通常バイナリコードであるため，テキス
トとして読むことはできない．これを，言語の論理的な構造を保存したまま，その表現形式をテキストとして判
読できるようにしたものがアセンブリ言語である．アセンブリ言語は，ニーモニックと呼ばれる単純な命令群に
よって記述される．これらは通常，その環境の最小命令単位と対応している．
加算と乗算からなる数式を，以下の仮定のもと，表 2 に示すアセンブリ言語を用いて翻訳する．
• 汎用レジスタが少なくとも 10 個ある．各レジスタは R0, R1,. . . のように表記する．
• 各汎用レジスタは，加算・乗算に用いることができる．
• 汎用レジスタには，数 n を代入することができる．
• PRINT 命令で指定したレジスタの内容を表示することができる．
処理内容
加算
乗算
レジスタへの値設定
レジスタの内容表示
表 2: 各種ニーモニック
ニーモニック数式
ADD Rx, Ry
MUL Rx, Ry
Rx ← Rx + Ry
Rx ← Rx × Ry
SET Rx, n
PRINT Rx
Rx ← n
備考
計算結果は Rx に代入
計算結果は Rx に代入
以上の取り決めのもと，“1 * 2 + 3” を計算するためのアセンブリ言語は以下のようになる．
4
3
SET
SET
R0,
R1,
1
2
MUL
SET
R0,
R1,
R1
3
ADD
PRINT
R0,
R0
R1
実験
1. Bison を用いて，整数の加算と乗算のみからなる数式をアセンブリ言語に翻訳するコンパイラ eucom を以下
の手順で生成せよ．サンプルソース (eucom.l, eucom.y) を付録に示す．
%flex eucom.l
%bison eucom.y
%gcc eucom.tab.c -ll -o eucom
次のように数式を入力しその結果を記録せよ．また，正しい計算をするアセンブリ言語が出力されているか
検証せよ．
%echo "1*2+3" | ./eucom
%echo "1+2+3" | ./eucom
2. 実数の四則演算をアセンブリコードに翻訳できるコンパイラを生成し，いくつか簡単な数式を入力し，生成
されるアセンブリ言語を記録せよ．また，それが正しいか検証せよ．なお，仮想マシンのニーモニックが足
りない場合は，自分で適切な機能を追加してもよい．例えば，NEG Rx（Rx の符号を反転する）や，SIN
Rx （Rx の sin を求め，Rx に代入する）など．
※ 表や解析木を用いるなどして，Bison がいかにしてアセンブリ言語を生成したか， “順を追って” 説明する
こと．
5
サンプルプログラム
A
[eucom.l]
/*****************************************************************************/
%{
#include <string.h>
/*
strdup を用いるために必要
strdup の書式は
char *strdup(const char *s);
で，その動作は，文字列 s の複製である新しい文字列へのポインタを返す．
新しい文字列のためのメモリは malloc で得て，free で解放することができる．
詳細は man strdup を参照すること．
*/
%}
/*****************************************************************************/
num
"0"|[1-9][0-9]*
operator
"+"|"-"|"*"
parentheses "("|")"
/*****************************************************************************/
%%
{num}
{ yylval.str = strdup(yytext); return NUM; }
/*** 数を yylval.str に保存し，種別 NUM を返す ***/
{operator}
{ return yytext[0]; }
{parentheses} { return yytext[0]; }
/*** 各オペレータまたは括弧自身を種別として使う ***/
"\n"
[" ""\t"]+
.
{ return 0; }
{ printf("error: ’%c’\n", yytext[0]); exit(1); }
%%
/*****************************************************************************/
6
[eucom.y]
/*****************************************************************************
* C 言語インターフェイス宣言部
*****************************************************************************/
%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef enum { R0, R1, R2, R3, R4, R5, R6, R7, R8, R9 } reg_id;
/*** アセンブリコード生成関数のプロトタイプ宣言 ***/
void
asm_PRINT(reg_id Rx);
reg_id asm_SET(char *n);
reg_id asm_ADD(reg_id Rx, reg_id Ry);
reg_id asm_MUL(reg_id Rx, reg_id Ry);
/*** [追加ニーモニック] 例えば，このように追加する ***/
reg_id asm_NEG(reg_id Rx);
%}
/*****************************************************************************
* 非終端記号 (E,T,F) とその型および終端記号 (NUM,’+’,’*’,’(’,’)’),
* 開始記号 (S) の定義
*****************************************************************************/
%union { char *str; reg_id reg; } /* 構文解析の戻り値として文字列型とレジスタ ID 型を扱う */
%type <reg> E T F
%token <str> NUM
%token
’+’ ’*’ ’(’ ’)’
%start
S
/*****************************************************************************
* 生成規則の定義
*****************************************************************************/
%%
S: E
{ asm_PRINT($1); };
E: T
E: E ’+’ T
{ $$ = $1; };
{ $$ = asm_ADD($1, $3); }; /* ’+’ は左結合 */
T: F
T: T ’*’ F
{ $$ = $1; };
{ $$ = asm_MUL($1, $3); }; /* ’*’ は左結合 */
F: NUM
F: ’(’ E ’)’
{ $$ = asm_SET($1); };
{ $$ = $2; };
%%
/*****************************************************************************
* メインルーチンおよびサブルーチンの実装部分
*****************************************************************************/
#include "lex.yy.c"
int yyerror(const char *s) { printf("%s\n", s); exit(1); }
7
int main() { return yyparse(); }
/*****************************************************************************/
reg_id reg_stack[] = { R0, R1, R2, R3, R4, R5, R6, R7, R8, R9 }; /* レジスタスタック */
int reg_sp = 0; /* レジスタスタックポインタ */
/*** レジスタスタックから利用可能なレジスタを確保する関数 ***/
reg_id reg_alloc(void)
{
return reg_stack[reg_sp++];
}
/*** レジスタスタックに使い終わったレジスタを戻す関数 ***/
void reg_free(reg_id r)
{
reg_stack[--reg_sp] = r;
}
/*** PRINT ニーモニックを出力する ***/
void asm_PRINT(reg_id Rx)
{
printf("PRINT R%d\n", Rx);
reg_free(Rx);
}
/*** SET ニーモニックを出力する ***/
reg_id asm_SET(char *n)
{
reg_id Rx = reg_alloc();
printf("SET R%d,%s\n", Rx, n);
free(n); /* 字句解析で strdup した領域の解放 */
return Rx;
}
/*** ADD ニーモニックを出力する ***/
reg_id asm_ADD(reg_id Rx, reg_id Ry)
{
printf("ADD R%d,R%d\n", Rx, Ry);
reg_free(Ry);
return Rx;
}
/*** MUL ニーモニックを出力する ***/
reg_id asm_MUL(reg_id Rx, reg_id Ry)
{
printf("MUL R%d,R%d\n", Rx, Ry);
reg_free(Ry);
return Rx;
}
/*** [追加ニーモニック] NEG ニーモニックを出力する ***/
reg_id asm_NEG(reg_id Rx)
{
printf("NEG R%d\n", Rx);
return Rx;
}
8

Download Report