parsing - 左再帰文法で最初とフォローを見つける際の混乱

Question

最近、最初に見つけてフォローするという問題に直面しました

S->cAd
A->Ab|a

ここで、 A のプロダクションに左再帰があるため、どちらが正しい {a} 、 {empty,a} の最初の A と混同されています。A の最初に空の文字列を含めるかどうか混乱しています。--------------編集済み---------------

これの最初と次は何でしょう ,,これは私が今まで見た中でとても紛らわしい文法です

S->SA|A
A->a

解析テーブルを使用して、この文法が LL(1) にないことを証明する必要がありますが、1 つのセルに 2 つのエントリを取得できなかったため、証明できませんでした。

Answer 1

まず、につながる左再帰を削除する必要があります

S -> cAd
A -> aA'
A' -> bA' | epsilon

次に、計算できます

FIRST(A) = a         // as a is the only terminal nderived first from A.

EDIT :-

2 番目の質問については、

S -> AS'
S' -> AS' | epsilon
A -> a

FIRST(A) = a
FIRST(S) = a
FIRST(S') = {a,epsilon}.

を計算する前に左再帰を削除するという考え方は、FIRST()ここでFOLLOW()学ぶことができます。