Compiler Construction Lecture No.6
Menu Menu
yaccによる構文解析
今までは、再帰下降法(Recursive Decent)という構文解析方法を使ってきた。この方法は十分に高速だし、十分に一般的である。また、プログラマにとって、コンパイラの処理状況が直接的に見えるという利点もある。しかし再帰下降法では、文法規則そのものを、そのままプログラムの構造とすることが必ずできるわけではない。例えば、左再帰は、while などを使わなくてはいけなかった。文法規則は、一般的に以下のような形で表される。
aexpr : aexpr '-' mexpr
| aexpr '+' mexpr ;
このように、: の左が一つの非終端シンボル(non-terminal symbolという)しかない文法は、Conext Free Grammar(CFG, 文脈自由文法)と呼ばれる。これは構文解析のアルゴリズムがあることが知られている。左のシンボルが複数あるようなものは、Contex Dependent Grammar(文脈依存文法) と呼ばれる。Context Dependent
Grammarを一般的に構文解析することは決定不能(undecidable)であることもわかっている。もし、文脈自由文法で、再帰呼び出しが再後尾にしかないのならば、それはFinite State(有限状態遷移) であり、その場でただちに構文解析される。高度な文法を使用したから、構文が読みやすくなるわけでもないが、有限状態遷移で表現されるような文法では、例えば、「()の対応」などを記述することはできない。これは若干不便だといわれても仕方がない。
したがって、ここで扱うコンパイラは基本的には、CFG(のsubset)を対象とすることになる。CFGのsubsetを自動的に構文解析するプログラムを生成することは可能であり、Unixのyacc、GNU projectのbisonなどが知られている。yacc では、shift-reduce によるLR grammarの構文解析プログラムを生成することができる。
yaccによる構文解析では、以下のことに注目する。
文法規則一つについて、一つの木が返される この手続きからreturnする場合と、他の手続きを呼び出す場合があるこの手続きからreturnする場合は、文法要素が確定した時であり還元(reduce)と呼ばれる。他の手続きを呼び出す場合は、遷移(shift)と呼ばれる。
reduece 文法要素が確定し、スタックが減る
shift 新しい文法要素を試す。スタックが増す。
CFGのあるsubsetでは、このshift, reduce の組を状態遷移で表すことができる。すると、構文解析プログラムは、その状態遷移を行う機械となる。そして、reduce をおこなう部分に木を返す手続きを記述すれば良い。これが、yacc の原理である。例えば、この構文解析をyacc で記述すると以下のようになる。
aexpr : aexpr '+' mexpr { $$ = new_node('+',0,$1,$3); }
| aexpr '-' mexpr { $$ = new_node('-',0,$1,$3); }
| mexpr {$$ = $1; }
;
$$ が返す木を表し、$1,$2,$3... などが文法規則中に現われた要素の木を表す。返す木の型(ここではnode *)は、YYSTYPEを#defineすることによって定義できる。実際には、木以外のものでも構わない。C の union などを使ってより自由度をあげることもできる。構文解析部分以外は、 s-tree-compile.c
と、まったく同じものを使うことができる。例えば、 s-yacc.y
のように記述することができる。yacc に -v option を付けてコンパイルすることにより、生成された状態遷移を見ることができる。
曖昧な文法
それでは、これで yacc を使えば、構文解析はすべてOkなのだろうか? 実際のコンパイラでは、さまざまな問題がある。例えば、
statement : if ( expr ) statement
| if ( expr ) statement else statement
| a | b | c
;
という文法を考えて見よう。if (x==y) if (z==w) a else b は、どのように解釈されるべきだろうか?
if (x==y) { if (z==w) a else b }
if (x==y) { if (z==w) a } else b
の2種類の解釈が可能である。(これは、間違いやすい部分でもある。僕だったら、{}は省略しない。) これは、曖昧な文法と呼ばれる。CFGは、曖昧さを許す文法であり、実は人間は曖昧な文法の方が読みやすいし書きやすいと感じるようである。
if.y if.y は、yacc if.y ; gcc if.tab.c -ly ; ./a.out で動かす。
または、
bison if.y ; clang if.tab.c -ly
問題6.1
前の二通りの解釈が出てくる時の文法の適用順序を図を用いて示せ。
あいまいな文法の解決
実際には、このような文は、適当な規則により適当な解釈に固定される。逆にいえば、yacc がこのような曖昧な文法にであった時には、それを解決しなければならない。(状態遷移には曖昧さは許されない)このような曖昧さに出会った時に yacc は、shift reduce conflict とか、reduce reduce conflict という文句をいう。yacc では、この場合は先に書いてある文法規則が優先される。つまり、二つ目の解釈になる。しかし、それが常に望ましいとは限らない。このためのいろいろなオプションがyaccには用意されている。
例えば、演算子の順位を指定することにより曖昧さを解決することもできる。例えば、四則演算だったら、
%left '+' '-'
%left '*' '/'
expr : expr '+' expr { $$ = new_node('+',0,$1,$3); }
| expr '-' expr { $$ = new_node('-',0,$1,$3); }
| expr '*' expr { $$ = new_node('-',0,$1,$3); }
| expr '/' expr { $$ = new_node('-',0,$1,$3); }
| term /* $$=$1 は省略可能 */
;
と記述することもできる。%leftが、左再帰を表し、その出現順序が演算子の優先順位を表している。
ここでは、yaccの実現や他の機能にはあまり深入りしないことにしよう。ただ、yacc の conflict はエラーではなく、曖昧な文法を表していて、yacc が勝手にそれを解決しているということは覚えておこう。conflict は文法の間違いを表していることも多いが、特に直す必要がない場合も多い。
構造体定義を考える
ここで出て来る例題は、(Yaccによる構文の例題のディレクトリ) にあります。( /usr/open/classes/kono/compiler/yacc/ )Cの構造体定義の文法を定義し、それを構文解析するプログラムをyacc で記述してみよう。ただし、簡単にするために変数名やタグ名は、以下のものに限るとする。
var, var1, var2, tag1, tag2, tag3 , name, name1, name2また、データ型もint, char, struct, union, * のみに限ることにしよう。
例えば、以下のような構文が正しく構文解析される必要がある。(構文の例題)
struct name1 {
int tag;
char tag1;
} var;
union name2 {
int tag;
struct name1 *tag1;
} var1;
struct name2 {
int tag;
union {
int tag;
char tag1;
} tag2;
} var2;
残念ながら yacc の非終端記号には、int や char のCの予約語は使えない。これはバグだが、字句解析部分を自分で書くことによって避けることができる。ここでは lex を使おう。
lex
lex (lexical analysis programs ) は、正規表現とアクション(action)の組み合わせを入力とし、C の字句解析プログラムを出力する。アクションはCの文である。例えば、
var|var1|var2 return VAR;
struct return STRUCT;
[a-z_A-Z][a-z_A-Z0-9]* return NAME;
\{ return '{';
ここで戻り値は、#define で定義する。
# define NAME 1
# define VAR 2
# define STRUCT 3
などのようにする。これらは実際には yacc で生成される y.tab.h を使う。
ついでに行番号も数えさて、空白なども読み飛ばそう。
\n lineno++;
[ \t]*
lineno は外部変数なので extern 宣言が必要だし、y.tab.h は lex が生成するCのコードでinclude させる必要がある。それには、このようにする。(small.l)
%{
#include "y.tab.h"
extern int lineno;
%}
%%
var|var1|var2 return VAR;
struct return STRUCT;
[a-z_A-Z][a-z_A-Z0-9]* return NAME;
\; return ';';
\n lineno++;
[ \t]* ;
. return yytext[0];
%%
この字句解析部をテストするためには、以下のようなテストプログラムを使う。
#include <stdio.h>
extern int yylex();
int lineno;
main() {
int token;
while(token=yylex()) {
printf("%d %d\n",lineno,token);
}
}
これをテストするためのMakefileも作ろう。
lextest: small.l lextest.c y.tab.h
lex small.l
cc $(CFLAGS) -o lextest lextest.c lex.yy.c -ll
lex はdefaultで lex.yy.c を生成する。-ll は標準入力を使う時に使うライブラリである。
問題6.2
このプログラムの動作をチェックし、例題を字句解析するのに必要な
残りの部分を書きたせ。
文法解析部分
yacc では、まず、lex が返すべき値を終端記号として教える必要がある。
%token NAME VAR TAG CHAR INT STRUCT UNION
文法の一部は例えば、以下のようになる。
declares : declare ';' | declares declare ';';
declare : type objects
type : CHAR | INT | struct;
struct : STRUCT NAME;
objects : VAR | objects ',' VAR;
これらにyaccを動かして前のlexと接続するために必要な簡単なmainルーチンをつける。(small.y)
%{
#include <stdio.h>
int lineno;
int yydebug;
%}
%token NAME VAR STRUCT
%%
declares : declare ';' | declares declare ';';
declare : type objects
type : struct;
struct : STRUCT NAME;
objects : VAR | objects ',' VAR;
%%
main() {
yydebug = 0;
yyparse();
}
yyerror() {
printf("error on line %d\n",lineno);
}
この例題を動かすMakefileは以下のようになる。
yacctest: lextest small.y
yacc -d $(YYDEBUG) small.y
cc $(CFLAGS) -o yacctest y.tab.c lex.yy.c -ll
問題6.3
最初の 例題 が通るまで文法を拡張し、lex と yacc に実装して、例題が通ることを確認せよ。
yacc に -t フラグをつけて、yydebug=1 とすると、より細かい情報が出力される。その意味を考えて文法のデバッグをしよう。
問題6.4
Yacc による Shell の機能を拡張せよ。