DIRECTOR集合

トップダウン構文解析の解析木の非終端記号の展開時にどの生成規則を用いれば良いかを示す

$ \mathrm{DIRECTOR}(A,\alpha)は生成規則$ A\rightarrow \alphaの話をしている

各規則についてDIRECTORを求めればいい

条件の$ A\rightarrow \alphaって、$ Aは非終端記号で、$ \alphaは単に右辺

code:bnf

E -> TE'

E' -> +TE' | ε

みたいにあれば、$ \mathrm{DIRECOTR}(E, TE')や$ \mathrm{DIRECTOR}(E',+TE'), $ \mathrm{DIRECTOR}(E',\epsilon)を順々に求めていく

定義

生成規則$ A\rightarrow\alphaに対して$ \mathrm{DIRECTOR}(A,\alpha)は以下

$ \{a|a\in T,(a\in\mathrm{FIRST}(\alpha)-\{\epsilon\})または(\alpha\xRightarrow{\ast}\epsilonかつa\in\mathrm{FOLLOW}(A))\}

またはは、とりあえず右辺を試してみて、該当すればまたはのあとは試さなくていい？

記号の意味

$ \xRightarrow{\ast} は0回以上ステップの導出

生成規則に沿って解析木を展開する時に$ Aに当たりました

このときに$ Aをどう展開するかが問題になる

もし終端記号$ aが$ \mathrm{DIRECTOR}(A,\alpha)に入っていたら、$ A\rightarrow \alphaと展開して良い

しかし、もし$ aが$ \mathrm{DIRECTOR}(A,\alpha)にも$ \mathrm{DIRECTOR}(A,\beta)にも入っていたら、$ Aは$ \alpha,\betaのどちらに展開してよいかが決まらない

$ A\rightarrow\alpha,A\rightarrow\betaの2つの規則を考えたとき、

$ \mathrm{DIRECOTR}(A,\alpha)\cap\mathrm{DIRECTOR}(A,\beta)=\phiなら規則を選択できる

すべての生成規則に対してこの性質が成り立つ文法がLL(1)文法 ref LL法

DIRECOTR集合を求めるアルゴリズム

『(環境)5 プログラミング言語処理系』.icon p.156-参考

引数が複数文字のときの調べ方

$ \mathrm{DIRECTOR}(B,bC)

というよりわからないのは、$ \mathrm{FIRST}(bC)か

$ \mathrm{FIRST}(AB)=\mathrm{FIRST}(A)になるのか

一文字目

参考