アルゴリズムとデータ構造1

コンパイラ
2011年10月24日
酒居敬一＠Ａ４６８([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/COMP/2011/index.html
1
構文解析
前回の内容


下向き構文解析法


左再帰性の問題と、その除去
バックトラックの問題
今回の内容


ＬＬ(k)構文解析法。




LL(1)構文解析法

2
動機付けとして、下向き構文解析におけるバックトラックをなくしたい。
ＬＬは Left to right scan, Left most derivation より。
ｋ個の字句を先読みすることでバックトラックなし構文解析を実現する。
字句をひとつだけ先読みすることで、決定的に構文解析可能。
ＬＬ構文解析
下向き構文解析では、解析木を根から生成する。


根にある非終端記号（＝字句の列の先頭）がどの生成規則
に適合するか、それが初めにわかればバックトラック不要。
 A α|β
の例では、αとβのどちらかを一意に決めたい、ということ。
字句をひとつ読んだとき、それが生成規則を決める
手がかりであるかどうかがわかればよい？？？


入力記号aがαの先頭記号になりうるか？


入力記号aがＡの直後の終端記号になりうるか？



入力記号aがαの先頭記号でなければ、 A  α  ε の場合。
そこで、First集合、Follow集合というものを考えることにする。

3
そしてバックトラック不要にするために、 βの先頭記号ではないこと。
このようなaを含む集合をDirector集合という。
First集合
A α|β
αの先頭記号になりうる入力記号をFirst(α)とする。


同様にFirst(β)も考える。
First(α)∩First(β)＝φならば、入力記号により
αかβを一意に決定できる。




Firstα   a | a  T ,α  a 



ただし、 α  ε ならば ε  Firstα  とする。
ただし、εに展開してもいいかどうか一意に決定できないので、
そういうときは後述のFollow集合とともに決定する。


A  αε
4
First集合を求めるアルゴリズム
α，βを記号列、Ａ，Ｙを非終端記号、ａを終端記号とする。
1. αが空列記号（ε）のとき：First(α)にεを加える。
2. αが終端記号ａのとき： First(α)にａを加える。
3. αが非終端記号Ａのとき：Ａを左辺に持つすべての
生成規則Ａ→βについてFirst(β)を求め、その要素を
First(α)に加える。
4. αが長さ２以上の記号列（α＝Ｙβ）のとき
if   FirstY 
First  に FirstY  を加える。

else
5
First  に FirstY     と
First  を加える。
Follow集合

A  αε



という生成規則からはＡをεに展開してもよい。
このときは、   First  でもある。しかし、εは字句ではない。
入力からは、前ページのようには、一意に決定できない。
そこでFollow(A)という集合を考える。


これはＡの直後の終端記号に成りうる記号の集合。



FollowA   a | a  T ,S Aa


 a  First 
ならばαに展開できた。ところが、aがFirst集合に
含まれず   First  である場合でも a  FollowA であれば、
ここはαに展開できる。

つまり A  α  ε という生成規則に一意に決定できるということ。
6
Follow集合を求めるアルゴリズム
Ｓを開始記号、α，βを記号列、Ａ，Bを非終端記号、
ａを終端記号、＄を入力の最後を表す特殊な記号とする。
1. Ｓが開始記号のとき：Follow(Ｓ)に＄を加える。
2. A→αBβなる生成規則のとき：
Follow(B)にFirst(β)ー｛ε｝を加える。
3. A→αBβなる生成規則において、
First(β)にεが含まれているとき：
Follow(B)にFollow(A)を加える。

7
Director集合
First集合とFollow集合を合わせて、Ａをαに展開すべき
かどうかを決定するための集合をDirector集合として
定義する。

記号列 α  N  T 
*
と非終端記号A  N に対して、生成規則 A  α があるとき、
DirectorA, α  を次のように定義する
。

 

DirectorA, α   a | a  T ,a  Firstα  または  α  ε かつ a  FollowA 



ところで、同じ入力記
号 a が DirectorA, α  にも DirectorA,β  にも入っていたら、
α と β のどちらへ展開すべきかが決まらない。
そのようなものをなく
8
したものが、 LL1 文法である。
LL(1)文法
LL(1)文法の定義

与えられた文法Ｇに対する任意の生成規則
A  1 |  2 |  |  n
に対して
DirectorA, i   DirectorA, j    , where i  j
ならば、文法Ｇは
LL1 文法であるという。
先頭の字句をひとつ読めば展開すべき生成規則が
一意に決まるということを意味している。
そのような文法をLL(1)文法といっている。

9
再帰的下向き構文解析１

LL(1)文法であれば、バックトラックしない
再帰的下向き構文解析器が作成できる。
【文法Ｇ１】

（１）式
→
式＋項
（２）式
→
項
（３）項
→
項＊因子
（４）項
→
因子
（５）因子
→
（式）
（６）因子
→
ｉ
しかしながら、この文法Ｇ１では、左再帰性をもつため、
このままでは再帰的下向き構文解析ができない。
10
再帰的下向き構文解析２

左再帰性を除去した文法Ｇ２
【文法Ｇ２】

（１）式
→
項式端
（２）式端
→
＋項式端｜ε
（３）項
→
因子項端
（４）項端
→
＊因子項端｜ε
（５）因子
→
（式）｜ｉ
正規右辺文法もしくは拡張ＢＮＦによる文法Ｇ３
【文法Ｇ３】
11
（１）式
→
項｛＋項｝
（２）項
→
因子｛＊因子｝
（３）因子
→
（式）｜ｉ
形式言語による言語と文法の定義１

アルファベット

空でない有限集合。


文字・記号


アルファベットの要素を有限個並べたもの。
空語・空文字列・空記号列


アルファベットの要素。
語・文字列・記号列


ＡＢＣ…Ｚのような英語のアルファベットと混同しないように。
アルファベットの要素をひとつも含まないもの。εで表す。
語彙

12
生成規則に現れる記号（全部）の集合。
形式言語による言語と文法の定義２

四つ組Ｇ＝（Ｎ，Ｔ，Ｐ，Ｓ）を文法という。

Ｎ，Ｔ，Ｐは空ではない有限集合。



ＮとＴに共通部分はない。
Ｐの要素（生成規則）は「左辺→右辺」の形をとる。



Ｎ，Ｔ，Ｐの要素はそれぞれ非終端記号，終端記号，生成規則。
左辺と右辺は（Ｎ∪Ｔ）＊の要素とする。
開始記号ＳはＳ∈Ｎとする。
文法Ｇ上の言語Ｌ（Ｇ）とは、


開始記号Ｓから出発し、生成規則（Ｐの要素）を有限回適用して
得られた、終端記号列（文）の集合。


x  N  T  で S  x ならば x を文形式という。
x T
13


で S  x ならば
x を文という。




LG   x  T | S  x  である。


形式言語による言語と文法の定義３

句構造文法



タイプ０（制限なし）
タイプ１（文脈依存文法）


アセンブリ言語はこのタイプ。
タイプ2（文脈自由文法）



1950年代後半に言語学者チョムスキーによって考案された。
生成規則の左辺がひとつの非終端記号だけからなる。
Ｃ言語やJavaなど高級言語はたいていこのタイプ。
タイプ３（正規文法）
14
予習・復習

Ｃ言語では次のような宣言もしくは定義ができる。

複雑な宣言や定義をそのまま書くと複雑で読みにくいので、
通常はtypedefを使って段階的に宣言や定義する。
int *f();
int (*f)();
/* fはintへのポインタを返す関数 */
/* fはintを返す関数へのポインタ */
char **argv;
/* charへのポインタのポインタ */
int (*daytab)[13]; /* daytabはintを要素とする要素数13の配列へのポインタ */
int *daytab[13];
/* daytabはintへのポインタを要素とする要素数13の配列 */
char (*(*x())[])(); /* xはcharを返す関数へのポインタの配列へのポインタを返す関数 */
char (*(*x[3])())[5];/* xはcharを要素とする要素数5の配列へのポインタを返す関数
へのポインタを要素とする要素数3の配列 */
出典: "プログラミング言語Ｃ第２版", 共立出版, 149ページ, 2001年.

これらの文に対応する生成規則を考えてみよう！
15

Download Report