トップダウン解析 - 最初とフォロー

Question

私は最初にやる方法を学びたいと思っている次の文法を持っています。私は正しいと思う。しかし、FOLLOWはここに起因非終端C.

に混乱して文法は次のとおりです。FIRSTについては

S --> ABC 
A --> a | Cb |ε 
B --> C | dA | ε 
C --> e | f 

：FOLLOWについては

First(S) = First(A)-{ε} + First(C) = { a,f, e, ε} 
First(B) = First(C) = {d,e,f,ε} 

：

Follow(S) = {ε} 
Follow(A) = First(B)-{ε} + First(C) = {a,e,f} 
Follow(B) = Follow(C) = Follow(S) = { $} 
Follow(C) = Follow(B) = Follow(S) = {b, $} 

プロダクションAとBに2つのCがあるので、私は問題がありますか？ これに近いですか？

Answer 1

私は最初にすでに間違っていると思います。

AとBは任意であり、Cは、非空の最初を有するように：

まず

First(S) = First(A) + First(B) + First(C) - {ε} 
First(A) = {a} + First(C) + {ε} 
First(B) = First(C) + {d, ε} 
First(C) = {e, f} 

=>

First(A) = {a, e, f, ε} 
First(B) = {d, e, f, ε} 

=>

First(S) = {a, d, e, f} 

---

出現にはnt、 が続きます最後のルール

Follow(S) = {$} 
Follow(A) = First(B) - {ε} + Follow(B) = {d, e, f} 
Follow(B) = First(C) = {e, f} 
Follow(C) = Follow(S) + Follow(B) + {b} = {b, e, f, $} 

（私はこの権利を得たいと考えています。）詳しくは

---

：

Follow(S) = {$}   [Start rule] 

Follow(A) = First(B) - {ε} [S --> A.BC] 
      + First(C)  [S --> AB.C as B or First(B) contains ε] 
      + Follow(B)  [B. --> C | dA. | ε] 

Follow(B) = First(C)  [S --> AB.C as C does not contain ε stops] 

Follow(C) = Follow(S)  [S. --> ABC.] 
      + {b}   [A --> a | C.b |ε] 
      + Follow(B)  [B. --> C. | dA | ε] 

X.などのLHS上のドット - > ... Follow（S）の結果。

RHS上のドット... - > ... .X ... First（X） - {ε}の結果 Xのε-productionがある間、続行：... - > ... X. ...

これは「私の」ルールであり、あなたの本は多少異なる代数を使用するかもしれません。

Answer 2

私は文法について次のように答えています。最初のものは既に正しく答えられているので。

follow(S) = {$}; 
follow(A) = {$,d,e,f}; 
follow(B) = {$,e,f}; 
follow(C) = {$,b,e,f}; 

A、B、Cの後に '$'を含める理由は以下のとおりです。文法にA ---> ABCというプロダクションがある場合、Cがヌル可能な場合、フォロー（A）のすべてが（B）のフォローになります。