構造預測分析表

預測分析表的作用，是為推導的進行指明方向——我們用當前下推棧棧頂和讀寫頭所指向的符號的組合（即當前的狀態(tài)），去查詢預測分析表，以確定推導的下一步該向著何種方向前進。

推導應該前進的方向，由 FIRST、FOLLOW 集合說明——這兩個集合能夠說明，我們可以通過怎樣的方式來一步步向著終結符靠近。

不懂也能用的構造步驟

預測分析表構造的步驟如下，建議按照例子實操一遍。實在想不通，背下來步驟應該也可以把表構造出來。

1. 看待填行的行首非終結符 A
2. 找到左部是上面看到的這個非終結符 A 的產(chǎn)生式，根據(jù)產(chǎn)生式右部的不同，按以下三種情況處理：
   1. 如果產(chǎn)生式是以非終結符 B 打頭的序列 α ，那么找到 FIRST(B)，將 FIRST(B) 集合中每個元素所在列、非終結符 A 所在行確定的位置填寫上序列 α
   2. 如果產(chǎn)生式是以終結符 a 打頭的序列 β ，那么直接去找終結符 a 所在列，并將 β 填入 A 行 a 列的位置中
   3. 如果產(chǎn)生式是 ε，則找到 FOLLOW(A) ，將 FOLLOW(A) 集合中每個元素所在列、非終結符 A 所在行確定的位置填寫上 ε

概括來說，就是：根據(jù)產(chǎn)生式左部的非終結符確定本次要構造的分析表行。根據(jù) FIRST、FOLLOW 集合，將產(chǎn)生式右部填入分析表，以此確定每行的內(nèi)容。比如對于產(chǎn)生式 L → E;L|ε，我們需要把產(chǎn)生出來的右部 E;L 和 ε 填入到分析表 L 行的某些位置中。

實例如下：

FIRST、FOLLOW 和分析表的原理？

FIRST、FOLLOW 集合都能夠說明一些東西，比如， FIRST(L) 集合告訴我們：

• 如果此時棧頂是 L ，而讀寫頭讀到了 id，那么我們應該用 E;L 來進行展開，因為這樣可以讓推導過程向著【把棧頂元素變?yōu)?code>id 】的方向前進。這是因為從 E 開始經(jīng)過數(shù)步推導后，E 能夠最終展開為 id 而完成匹配
  

• 如果此時棧頂是 L ，而讀寫頭讀到了 num ，那么我們應該用 E;L 來進行展開，因為這樣可以讓推導過程向著【把棧頂元素變?yōu)?num】的方向前進。這是因為從 E 開始經(jīng)過數(shù)步推導后，E 能夠最終展開為 num 而完成匹配

• 如果此時棧頂是 L ，而讀寫頭讀到了 ( ，那么我們應該用 E;L 來進行展開，因為這樣可以讓推導過程向著【把棧頂元素變?yōu)?(】的方向前進。這是因為從 E 開始經(jīng)過數(shù)步推導后，E 能夠最終展開為 ( 而完成匹配
  

而當產(chǎn)生式右部是 ε 時，根據(jù)該產(chǎn)生式左部的非終結符所對應的 FOLLOW 集合來確定這個 ε 該填到哪里——也就是說，僅當某個非終結符的產(chǎn)生式右部為 ε 時，我們才需要考慮 FOLLOW 集合

• 如果此時棧頂是 T'，而讀寫頭讀到了 + ，那么……嗯，T' 可沒有展開為 + 的產(chǎn)生式啊，但 T' 可以被穿透，其 FOLLOW 集合 FOLLOW(T') 是包含 + 的；
• 同理，如果此時棧頂是 T'，而讀寫頭讀到了 - ，也可以通過選擇將 T' 以 ε 展開而穿透的方式來向著推出 - 的方向前進。

LL(1) 文法

LL(1)，第一個 L ，代表從左到右掃描輸入序列，第二個 L 代表推導的過程是最左推導。1 則代表只有一個讀寫頭（也就是每次都只向前看一個終結符）

該文法的分析表的每個格子中只能有一個產(chǎn)生式的右部。該文法必須是非二義的，文法的產(chǎn)生式不能包含公共左因子和左遞歸。

LL(1) 文法使用范圍有限，實際主要使用 LR(1) 文法。LR(1) 文法是 LL(1) 文法的真超集