コンパイラ 2011年10月24日 酒居敬一＠Ａ４６８(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/COMP/2011/index.html

構文解析 前回の内容 今回の内容 下向き構文解析法 ＬＬ(k)構文解析法。 LL(1)構文解析法 左再帰性の問題と、その除去 バックトラックの問題 今回の内容 ＬＬ(k)構文解析法。 動機付けとして、下向き構文解析におけるバックトラックをなくしたい。 ＬＬは Left to right scan, Left most derivation より。 ｋ個の字句を先読みすることでバックトラックなし構文解析を実現する。 LL(1)構文解析法 字句をひとつだけ先読みすることで、決定的に構文解析可能。

ＬＬ構文解析 下向き構文解析では、解析木を根から生成する。 根にある非終端記号（＝字句の列の先頭）がどの生成規則 に適合するか、それが初めにわかればバックトラック不要。 　　　　　　の例では、αとβのどちらかを一意に決めたい、ということ。 字句をひとつ読んだとき、それが生成規則を決める 手がかりであるかどうかがわかればよい？？？ 入力記号aがαの先頭記号になりうるか？ そしてバックトラック不要にするために、 βの先頭記号ではないこと。 入力記号aがＡの直後の終端記号になりうるか？ 入力記号aがαの先頭記号でなければ、 の場合。 そこで、First集合、Follow集合というものを考えることにする。 このようなaを含む集合をDirector集合という。

First集合 αの先頭記号になりうる入力記号をFirst(α)とする。 ただし、εに展開してもいいかどうか一意に決定できないので、 そういうときは後述のFollow集合とともに決定する。 入力記号をひとつ読んだ場合を議論しているのに、入力記号を一切読まなくてもいいと生成規則が言ってる場合には議論の前提がずれてることになる。もちろんこれ単独で答えが出ないということ。

First集合を求めるアルゴリズム α，βを記号列、Ａ，Ｙを非終端記号、ａを終端記号とする。 αが非終端記号Ａのとき：Ａを左辺に持つすべての 生成規則Ａ→βについてFirst(β)を求め、その要素を First(α)に加える。 αが長さ２以上の記号列（α＝Ｙβ）のとき

Follow集合 という生成規則からはＡをεに展開してもよい。 そこでFollow(A)という集合を考える。 　　　　　　　　という生成規則からはＡをεに展開してもよい。 このときは、　　　　　　　　でもある。しかし、εは字句ではない。 入力からは、前ページのようには、一意に決定できない。 そこでFollow(A)という集合を考える。 これはＡの直後の終端記号に成りうる記号の集合。 　　　　　　　ならばαに展開できた。ところが、aがFirst集合に 含まれず　　　　　　　　である場合でも　　　　　　　　　であれば、 ここはαに展開できる。 つまり　　　　　　　という生成規則に一意に決定できるということ。

Follow集合を求めるアルゴリズム Ｓを開始記号、α，βを記号列、Ａ，Bを非終端記号、 ａを終端記号、＄を入力の最後を表す特殊な記号とする。 Ｓが開始記号のとき：Follow(Ｓ)に＄を加える。 A→αBβなる生成規則のとき： Follow(B)にFirst(β)ー｛ε｝を加える。 A→αBβなる生成規則において、 First(β)にεが含まれているとき： Follow(B)にFollow(A)を加える。

Director集合 First集合とFollow集合を合わせて、Ａをαに展開すべき かどうかを決定するための集合をDirector集合として 定義する。

LL(1)文法 LL(1)文法の定義 先頭の字句をひとつ読めば展開すべき生成規則が 一意に決まるということを意味している。 そのような文法をLL(1)文法といっている。

再帰的下向き構文解析１ LL(1)文法であれば、バックトラックしない 再帰的下向き構文解析器が作成できる。 しかしながら、この文法Ｇ１では、左再帰性をもつため、 このままでは再帰的下向き構文解析ができない。 【文法Ｇ１】 （１）式 → 式＋項 （２）式 項 （３）項 項＊因子 （４）項 因子 （５）因子 （式） （６）因子 ｉ

再帰的下向き構文解析２ 左再帰性を除去した文法Ｇ２ 正規右辺文法もしくは拡張ＢＮＦによる文法Ｇ３ 【文法Ｇ２】 （１）式 → 項 式端 項　式端 （２）式端 ＋項　式端｜ε （３）項 因子　項端 （４）項端 ＊因子　項端｜ε （５）因子 （式）｜ｉ 【文法Ｇ３】 （１）式 → 項　｛＋項｝ （２）項 因子　｛＊因子｝ （３）因子 （式）｜ｉ

形式言語による言語と文法の定義１ アルファベット 文字・記号 語・文字列・記号列 空語・空文字列・空記号列 語彙 空でない有限集合。 ＡＢＣ…Ｚのような英語のアルファベットと混同しないように。 文字・記号 アルファベットの要素。 語・文字列・記号列 アルファベットの要素を有限個並べたもの。 空語・空文字列・空記号列 アルファベットの要素をひとつも含まないもの。εで表す。 語彙 生成規則に現れる記号（全部）の集合。

形式言語による言語と文法の定義２ 四つ組Ｇ＝（Ｎ，Ｔ，Ｐ，Ｓ）を文法という。 文法Ｇ上の言語Ｌ（Ｇ）とは、 Ｎ，Ｔ，Ｐは空ではない有限集合。 Ｎ，Ｔ，Ｐ の要素はそれぞれ非終端記号，終端記号，生成規則。 ＮとＴに共通部分はない。 Ｐの要素（生成規則）は「左辺→右辺」の形をとる。 左辺と右辺は（Ｎ∪Ｔ）＊の要素とする。 開始記号ＳはＳ∈Ｎとする。 文法Ｇ上の言語Ｌ（Ｇ）とは、 開始記号Ｓから出発し、生成規則（Ｐの要素）を有限回適用して 得られた、終端記号列（文）の集合。

形式言語による言語と文法の定義３ 句構造文法 タイプ０（制限なし） タイプ１（文脈依存文法） タイプ2（文脈自由文法） タイプ３（正規文法） 1950年代後半に言語学者チョムスキーによって考案された。 タイプ０（制限なし） タイプ１（文脈依存文法） アセンブリ言語はこのタイプ。 タイプ2（文脈自由文法） 生成規則の左辺がひとつの非終端記号だけからなる。 Ｃ言語やJavaなど高級言語はたいていこのタイプ。 タイプ３（正規文法）

予習・復習 Ｃ言語では次のような宣言もしくは定義ができる。 これらの文に対応する生成規則を考えてみよう！ 複雑な宣言や定義をそのまま書くと複雑で読みにくいので、 通常はtypedefを使って段階的に宣言や定義する。 これらの文に対応する生成規則を考えてみよう！ int *f(); /* fはintへのポインタを返す関数 */ int (*f)(); /* 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年.