■

以下のフェーズを考える

1．正規表現の文法を考える
2. 1の文法が構文解析した時にあいまい（解析木が複数通りある）で無い事を確かめるため、LL(1)文法を満たしているかを考察する

まず1だけど、文法（構文規則）を考える。
正規表現の定義は前回与えた通りでさらに優先順位があり
R*が最も高く(=R+)次にRS、最後にR|Sとなる。
今回は"()"の表現も許すため(R)が最も優先順位が高くなる。

これからひとまず正規表現Rの再帰的下向き構文解析を以下のように置く

[文法R]
R = T or R | T
T = ET | 
E = F | F* | F+
F = CHARACTER | ( R )

※orは正規表現上"|"の事であるが、同じ記号を使うため便宜的に置き換えた。また、CHARACTERはアルファベットの事では空文字とする。


ここで、上記の文法がLL(1)である事を確かめるため、参考文献「コンパイラ 中田育男著」より以下の定義を引用する
【定義】記号列 と非終端記号について、First(\alpha)とFollow(A)を次のように定義する。
※とはそれぞれ非終端記号の集合と終端記号の集合を意味する


ただし、ならとする

※...とは任意の記号列を意味する

これはすなわち、はの先頭の終端記号になりうる集合であり、は文形式の中でAの直後の終端記号になりうるものの集合である。

また、を以下のように定義する

【定義】記号列 と非終端記号に対して、生成規則があるとき、を次のように定義する


※First, Follow, Directorを求めるアルゴリズムはめんどいんで掲載しない。

文法RのFirst, Follow, Directorを求めるとそれぞれ以下のようになる

■First
 First(F) = {CHARACTER, (}
 First(E) = {CHARACTER, (}
 First(T) = {CHARACTER, (, }
 First(R) = {CHARACTER, (, }
■Follow
 Follow(R) = {$, )}
 Follow(T) = {or, $, )}
 Follow(E) = {CHARACTER, (}
 Follow(F) = {CHARACTER, (, *, +}
■Director
 Director(R,TorR) = First(TorR) = {CHARACTER, (}
 Director(R,T) = First(T) or Follow(R) {CHARACTER, (, $, )}

ここでいきなり 
となってしまったので上記の正規表現文法RはLL(1)では無い。

というより、R = TorR|Tの時点で最初の文字がどちらの分岐に行くか定まるわけが無い。。
※

この文法Rって参考文献「Cプログラマのための　アルゴリズムとデータ構造」に出てた正規表現の構文規則とほぼ同じなんだけど（実際そこでも R = T|TorRという事をやっている）
、これはLL(1)である必要が無い？！
ってか良く考えたらこの構文規則をNFA,DFAと変換していくわけだけど、DFAってLL(1)を満たしてないか？！
という事はわざわざ最初の構文規則はLL(1)を満たして無くてもいい？
もしくはLL(1)が満たされていれば、実はその構文規則をNFAに変換する段階ですでにそれはDFAになっているかもしれない？

ここでDFAの定義を復習
DFAとは次の条件を満たす有限オートマトンである
(1) による遷移がない
(2) 1つの状態から同じ記号による異なった状態への遷移はない

これって確かにLL(1)っぽい。
なぜなら、の遷移が無いのでまずFollowを考える必要がない、次に、ある記号が与えられた場合遷移はかならず一意に定まる。

うーん。。
とりあえずLL(1)じゃないけど文法Rでコーディングしてみるかな。。