第 11 回構文解析木

本日の内容

11-1. 構文解析
11-2. 括弧の処理
11-3. 数式の文法
11-4. コンパイラコンパイラ

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

11-1. 構文解析

バッカス・ナウア記法

文法の与え方にはさまざまな方法がありますが、ここではバッカス・ナウア記法を取り上げます。バッカス・ナウア記法では生成する文字列を作るアルファベットを終端記号と言います。終端記号の集合を $V_{T}$ で表します。一方、それに属さない記号を非終端記号と言います。非終端記号の集合を $V_{N}$ で表します。ルールは左辺に一つの非終端記号、右辺は非終端記号と終端記号の列で表します。通常は左辺と右辺は ::= や → という記号で結びます。そして最後に一つ非終端記号を開始記号として指定します。ルールの集合を P 、開始記号を S としたとき、文法の定義を $G = (V_{N}, V_{T}, P, S)$ と表します。

このように定義した文法において、つぎのような手順により記号列を生成します。

開始記号を左辺に含むルールを一つ選ぶ
開始記号をそのルールの右辺に置き換える
置き換えたものの中から非終端記号を一つ選ぶ
その非終端記号を左辺に含むルールを一つ選ぶ
その非終端記号を右辺に置き換える
すべてが終端記号なら終了、そうでなければ 3 に戻る

簡単のため、左辺が同じルールは、右辺を |(縦棒) で区切って列挙することで一つにまとめることにします。

文法の例

以下に簡単な文法の例を示します。

G=({文, 主語, 述語, 補語, 名詞句, 動詞, 代名詞, 冠詞, 名詞}, {This, is, a, pen}, P, 文)

P の定義

文 → 主語述語補語
主語 → 名詞句
述語 → 動詞
補語 → 名詞句
動詞 → is
名詞句 → 代名詞 | 冠詞名詞
代名詞 → This
冠詞 → a
名詞 → pen

このようなルールから、 This is a pen という記号列が導けます。

正規文法

バッカス・ナウア記法において、指定できるルールを「非終端記号→終端記号, 非終端記号 → 終端記号非終端記号」だけに制限した文法を正規文法といいます。

例11-1

a*: S→ε, S→aS
[abc]: S→a,S→b,S→c
(abc|asd): S→aA, A→bB, B→c, A→sC, C→d
.*(a|b): (アルファベットが { a, b, c } の時) S→aS, S→bS, S→cS, S→a, S→b

演習11-1

整数をこのルールにより表現しなさい。

構文解析木

一般のバッカス・ナウア記法による記号列の生成では、一つの非終端記号が複数の非終端、終端記号に対応します。そして、それに含まれる非終端記号がまた複数の非終端、終端記号に対応します。この導出の流れを図にすると、一つの非終端記号が複数の非終端、終端記号に対応するので、木の構造になります。

A→bCD というルールの場合
ルールの図示

根は開始記号になり、葉は終端記号、葉以外の頂点は非終端記号になります。与えられた記号列に対して、それの生成手順に対応した木を構文解析木と言います。例えば、上の This is a pen という記号列は次のような構文解析木を持ちます。

一つの記号列について、複数の構文解析木を持つ文法をあいまいであると言います。あいまいな文法はコンピュータで機械的に処理することができません。因みに英語はあいまいです。次の文章の解釈はなんと 4 通りあります。

Time flies like an arrow.

これは、動詞として Time, flies, like の三通りが考えられ、しかも Time が動詞の時は、 like an arrow の前が名詞になるので副詞句の他に形容詞句になる可能性があるからです。

動詞	like an arrow	訳
Time	副詞句	矢のように蝿の所要時間を計りなさい
Time	形容詞句	矢に似ている蝿の所要時間を計りなさい
flies	副詞句	時間は矢のように飛ぶ
like	副詞句	時間蝿は一本の矢が好きである

英語の場合、前後の文章や蝿、矢などに関する知識などを利用してふさわしい訳を選ぶ必要があります。

演習11-2

自然言語の構文解析はとても難しいです。次の日本語の構文解析木を書きなさい。

これはペンです
すもももももももものうち
きしゃのきしゃはきしゃできしゃした

演習11-3

次の日本語を、前後関係などで構文を意識して、英訳しなさい

わたしはうなぎです。

これは、料理屋で注文を確認された時に、発言した言葉です。
私の娘は男だった。

これは孫の誕生を話題にしている人同士の会話です。

11-2. 括弧の処理

正規文法では取り扱えなかった括弧も、このバッカスナウア記法では比較的簡単に扱えます。単純な括弧のみの言語は次のように書けます。

例11-2


S→ε
S→SS
S→(S)

演習11-4

上記の文法にさらに [](角括弧)も使えるようにしなさい

11-3. 数式の文法

足し算の文法

足し算だけの数式を解釈する文法を考えます。最初に次の文法を考えます。

文法 G₀

=({和},{数, +}, P₀, 和)

和 \to 数 + 数

この文法では、 1+1 のような式は解釈できますが、 1+2+3 は駄目です。そこで、足し算がいくつつながっていても解釈可能な文法を考えます。数式は、一般に左から右へ解釈します。したがって、 1+2+3 は 1+2 を解釈した後、その和に対して +3 を加えたものを新しい和とします。つまり、次のようなルールが必要になります。

和 \to 和 + 数

このルールがあれば、一番左の項以外はこれで解釈できます。一番左の項はそれだけで和とみなせば 1+2+3 を解釈できます。

文法 G₁

=({和},{数, +}, P₁, 和)

\begin{matrix} 和 \to 和 + 数 \\ 和 \to 数 \end{matrix}

なお、次のようにしてしまうと和の優先順序を指定できず、あいまいになります。

文法 G_1x

=({和},{数, +}, P_1x, 和)

\begin{matrix} 和 \to 和 + 和 \\ 和 \to 数 \end{matrix}

11-4. コンパイラコンパイラ

バッカス・ナウア記法を与えて、それを処理するプログラムを出力する処理系をコンパイラコンパイラと言います。 C 言語のプログラムを出力するものに yacc があります(bison という互換性のあるフリーソフトもあります)。 yacc は、数を取り出すなど構文解析の前段階である字句解析はしません。そのために lex という字句解析ソフトを使います(flex という互換性のあるフリーソフトもあります)。一方、 java 用のコンパイラコンパイラに JavaCCというクラスライブラリがあります。 JavaCC は構文解析も字句解析もできます。また、構文解析木を出力する JJTree というツールも付属してきます。

yacc

C 言語のソースを出力する yacc は lex と組み合わせて使います。非終端記号にあたるものだけ yacc で記述し、「数」や「単語」などのトークンは lex で解釈します。

yacc の定義ファイルは %% で区切り前半が定義部で、後半が規則部になります。定義部では lex に解釈させるトークンの名前の定義をします。一方規則部では、非終端記号を表す名前や、トークンの名前、さらに文字などを利用して文法をバッカスナウア記法で記述します。但し、矢印の代わりに :(コロン)を用い、左辺が共通の式は右辺を |(縦棒)で区切って記述します。そして、文法の式の後に lex と同様に {}で括った C 言語のプログラムを書くことができます。なお、その時、シンボル値という値を扱うことができます。これは、終端記号、非終端記号などのシンボルに値を割り当てて、規則にマッチした時に計算ができるようにしたものです。規則の右辺のシンボルの位置に対応して $1, $2, ... という記号で参照できます。そして、この規則の値として $$ という変数に代入できます。これが別の規則のシンボルに使われる場合、シンボル値が参照されます。また、終端記号には lex がグローバル変数として返してくる yyvalue という値が割り当てられます。

上記の G₁ を yacc で書くと次のようになります。


%{
#include <stdio.h>
yyerror(char *s){
  fprintf(stderr,"%s\n",s);
}
%}
%token KAZU EOL
%%
start:  
      | start wa EOL        { printf("=%d\n",$2); }
;

wa: wa '+' KAZU { $$ = $1 + $3;}
  | KAZU        { $$ = $1;}
;

%%
int main(void){
    yyparse();
    return 0;
  }

このように定義した yacc の定義ファイルに対して、 lex は次のように定義します。まず、lex のみの時は lex の定義ファイルのアクションに printf などを書きましたが、 yacc と連結する際は認識したら return でトークンの種類を返すようにします。また、yacc とトークンの定義やグローバル変数などを共有するため、定義部に y.tab.h ファイルの include と yyval 変数の外部宣言を行います。


%{
#include "y.tab.h"
extern int yylval;
%}
%%
[0-9]+ { yylval=atoi(yytext); return KAZU;}
[ \t] ;
\n     { return EOL; }
\d     { return 0; }
.      { return yytext[0]; }
%%

なおこれらのファイルに対する Makefile は次のようになります。


TARGET=wa
YACC=bison -y
$(TARGET).exe:	y.tab.o lex.yy.o
	$(CC) -o$@ $^ -lfl

y.tab.c: $(TARGET).y
	$(YACC) -d $<

y.tab.h: $(TARGET).y
	$(YACC) -d $<

lex.yy.c: $(TARGET).l
	$(LEX) $<

y.tab.o: y.tab.c y.tab.h
lex.yy.o: lex.yy.c

演習11-5

括弧を加えるにはどうしたら良いか考えなさい。

坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科

第 11 回 構文解析木