【導(dǎo)讀】推出，反之必然出錯(cuò)。符號表示經(jīng)過0步或若干步的推導(dǎo)。有文法G[S]，若Sx，且x∈VT*，則稱x是文法G[S]的句子。說明00001111是G[S]的句子。個(gè)推導(dǎo)的構(gòu)造過程。是對α中的最左（右）非終結(jié)符進(jìn)行替換。由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。當(dāng)前串中尋找一個(gè)子串，看它是否能歸約到文法的某個(gè)非終結(jié)符號，該子串稱為“可歸約串”。即每個(gè)產(chǎn)生式的右部的開始終結(jié)符不同。的開始終結(jié)符號集合中，則選擇S→Ap往下進(jìn)行推導(dǎo)。為此，我們定義一。若SμAβ,且βε,則#∈FOLLOW。于非終結(jié)符A的替換仍可唯一地確定候選。由以上例子可以看出，例～例。的自頂向下分析,可用帶回溯的自頂向下分析。

　　

【正文】 （見附錄） 遞歸子程序要求文法必須是 LL(1)文法。 預(yù)測分析方法 預(yù)測分析方法是自頂向下分析的另一種方法，一個(gè)預(yù)測分析器是由三個(gè)部分組成。 預(yù)測分析程序 (總控程序 ) 先進(jìn)后出棧 (stack) 預(yù)測分析表 表驅(qū)動予測分析程序模型 Input 總控程序 預(yù)測分析表 stack 其中只有預(yù)測分析表與文法有關(guān)，而分析表又可用 一個(gè)矩陣 M(或稱二維數(shù)組 )表示。矩陣的元素 M[A， a]中的下標(biāo) A表示非終結(jié)符， a為終結(jié)符或 句子括號 “ ”，矩陣元素 M[A,a]中的內(nèi)容為存放著 一條關(guān)于 A的產(chǎn)生式， 表明當(dāng)用非終結(jié)符 A向下推 導(dǎo)時(shí)，面臨輸入符 a時(shí)，所應(yīng)采取的候選產(chǎn)生式， 當(dāng)元素內(nèi)容無產(chǎn)生式時(shí)，則表明用 A為左部向下推 導(dǎo)時(shí)遇到了不該出現(xiàn)的符號，因此元素內(nèi)容為轉(zhuǎn)向 出錯(cuò)處理的信息 A a A → α A遇到輸入符 a，選用哪個(gè)產(chǎn)生式，如果 A → α， α ε， a ∈ Frist(α) 。如果 A → α， α → ε a ∈ Follow(A),即如果 a ∈ select(A → α)則把 A → α加入到 M(A, a)中。 解： (1) 判斷它是否是 LL（ 1）文法因?yàn)樵撐姆ê凶筮f歸，所以不是 LL（ 1）文法，必須改寫成 LL(1)文法： G’[ E]: (1) E – TE’ (2) E’ – +TE’ (3) E’ – ? (4) T – FT’ (5) T’ – *FT’ (6) T’ – ? (7) F – (E) (8) F – a 例：為文法 G (E): E – E+T|T T – T*F|F F – a|(E) 構(gòu)造預(yù)測分析表。 Select(E – TE’)=First(T)=First(F)={a,(} Select(E’ – +TE’)={+} Select(E’ – ?)=Follow(E’)=Follow(E)=(,)} Select(T – FT’)=First(F)={(,a} Select(T’ – *FT’)={*} Select(T’ – ?)=Follow(T’)=Follow(T) =(First（ E’){?}) ∪ Follow(E’) = (First（ E’){?})∪ Follow(E)={+,)} Select(F – (E))={(} Select(F – a )={a} G’[ E]: (1) E – TE’ (2) E’ – +TE’ (3) E’ – ? (4) T – FT’ (5) T’ – *FT’ (6) T’ – ? (7) F – (E) (8) F – a a + * ( ) E E – TE’ E – TE’ E’ – +TE’ – ? – ? T – FT’ – FT’ T’ – ? – *FT’ – ? – ? F – a – (E) G’[ E]: (1) E – TE’ (2) E’ – +TE’ (3) E’ – ? (4) T – FT’ (5) T’ – *FT’ (6) T’ – ? (7) F – (E) (8) F – a 分析輸入串 a+a 棧內(nèi)容 棧頂符號 當(dāng)前輸入 余留串 M[X,b ] 1 E E a +a E – TE’ 2 E’T T a +a T – FT’ 3 E’T’F F a +a F – a 4 E’T’a a a +a 匹配 a 5 E’T’ T’ + a T’ – ? 6 E’ E’ + a E’ – +TE’ 7 E’T+ + + a 匹配 + 8 E’T T a T – FT’ 9 E’T’F F a F – a 10 E’T’a a a 匹配 a 11 E’T’ T’ T’ – ? 12 E’ E’ E ’ – ? 13 預(yù)測分析程序的框圖 分析算法 BEGIN 首先把 ’ ‘然后把文法開始符號推入棧；把第一個(gè)輸入符號讀進(jìn) a。 FLAG： =TRUE； WHILE FLAG DO BEGIN 把棧頂符號上托出去并放在Ｘ 中； IF X ? Vt THEN IF X=a THEN 把下一 個(gè)輸入符號讀進(jìn) a ELSE ERROR ELSE IF X=‘’ THEN IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE IF ?[X,b]={X – X1X2..XK} THEN 把 XK， X K1,..,X1一一推進(jìn)棧 ELSE ERROR END OF WHILE。 STOP/*分析成功，過程完畢 *／ END LL(1)文法的性質(zhì) ： LL(1)文法是無二義的 LL(1)文法不含左遞歸 非 LL(1)文法的改造 消除左遞歸 提左公因子 將產(chǎn)生式Ａ ? ?β |?? 變換為： Ａ ? ?B B ? β |?