自頂向下語(yǔ)法分析方法
-
什么叫確定：
兩個(gè)確定：①確定對(duì)最左的非終結(jié)符進(jìn)行替換（最左推導(dǎo)）②對(duì)于同一個(gè)非終結(jié)符，確定一個(gè)產(chǎn)生式進(jìn)行推導(dǎo)（SELECT集，無(wú)回溯）哄芜。
-
一個(gè)上下文無(wú)關(guān)文法是LL(1)文法的充分必要條件：
關(guān)于一個(gè)非終結(jié)符的各個(gè)產(chǎn)生式的可選集互不相交。
-
LL(1)文法的判定過(guò)程：
-
檢查產(chǎn)生式中是否有含有左遞歸或左公因子：
含有左遞歸或左公因子的文法一定不是LL(1)文法帘皿；
不含有左遞歸或左公因子的文法也不能確定是否為L(zhǎng)L(1)文法稠腊；
-
標(biāo)記能推導(dǎo)出ε的非終結(jié)符：
先找出能直接推出ε的非終結(jié)符躁染，然后再查看其他產(chǎn)生式的右部，通過(guò)這些非終結(jié)符檢查還有沒(méi)有其他非終結(jié)符也可推出ε架忌，直到?jīng)]有發(fā)現(xiàn)為止吞彤。
-
計(jì)算每個(gè)產(chǎn)生式的FIRST集：
①如果這個(gè)產(chǎn)生式右部第一個(gè)字符是終結(jié)符，那么這個(gè)終結(jié)符就屬于它的FIRST集叹放。
②如果這個(gè)產(chǎn)生式右部第一個(gè)字符是非終結(jié)符饰恕，那么這個(gè)非終結(jié)符的FIRST集就屬于它的FIRST集。
如果這個(gè)非終結(jié)符的FIRST集中含ε井仰，那么后面的字符如果是終結(jié)符......
③如果這個(gè)產(chǎn)生式右部可以推出ε埋嵌，那么ε也屬于它的FIRST集。
-
計(jì)算每個(gè)非終結(jié)符的FOLLOW集：
首先向開(kāi)始符號(hào)的FOLLOW集中添加
#俱恶，然后對(duì)于所有非終結(jié)符雹嗦，不斷的找含有它的產(chǎn)生式右部：①該非終結(jié)符后面的字符若是終結(jié)符，那么這個(gè)終結(jié)符就屬于它的FOLLOW集合是；
②該非終結(jié)符后面的字符若是非終結(jié)符了罪，那么這個(gè)非終結(jié)符的FIRST()集中的所有元素就屬于它的FOLLOW集；
如果這個(gè)非終結(jié)符的FIRST()集中含ε聪全，將ε刪去泊藕，同時(shí)將這個(gè)產(chǎn)生式左部FOLLOW集中的所有元素添加至它的FOLLOW集中；
注意：不需要考慮后面的字符了荔烧，因?yàn)橐呀?jīng)包含在FIRST()集中了吱七。
-
計(jì)算每個(gè)產(chǎn)生式的SELECT集：
①如果這個(gè)產(chǎn)生式可以推出ε，那么它的SELECT集是
{FIRST(該產(chǎn)生式右部)-ε}∪FOLLOW(該產(chǎn)生式左部的非終結(jié)符)鹤竭。②如果這個(gè)產(chǎn)生式不能推出ε踊餐，那么它的SELECT集是
{FIRST(該產(chǎn)生式右部)}。 -
檢查相同左部產(chǎn)生式的SELECT集的交集：
檢查相同左部產(chǎn)生式的SELECT集的交集臀稚，如果全為空集說(shuō)明該文法是LL(1)文法吝岭，反之則不是。
-
-
消除左公因式：
有顯式的左公因式和隱式的左公因式吧寺，對(duì)于隱式的左公因式要先化成顯式窜管；
例：
顯式：
A→aB|aC
隱式：
A→ad|Bc
B→ae
解決方法：類(lèi)似合并同類(lèi)項(xiàng)，將左公因式提出稚机，不同的部分用或連接幕帆，并用一個(gè)新的非終結(jié)符指向它。
注意：某些特殊的含左公因式的文法可能會(huì)出現(xiàn)循環(huán)替換的情況赖条，此時(shí)無(wú)法解決左公因式問(wèn)題失乾。
-
消除左遞歸：
有直接左遞歸和間接左遞歸和一般左遞歸常熙，對(duì)于間接左遞歸要先化成直接；
例子：
Ⅰ直接（模板）：
P → P α | β
可改寫(xiě)為：
P → βQ（因?yàn)镻一定是β開(kāi)頭）
Q → αQ | ε（Q就是α+）
其中Q為新增的非終結(jié)符Ⅱ間接：
S → PQ | a
P → QS | bⅢ一般：
S → PQ | a
P → QS | b
Q → SP | c
做以下變換：
①S → PQ | a
P → SPS|cS|b②S → SPSQ|cSQ|bQ|a
③按照直接左遞歸方法消除后：
S → cSQR|bQR|aR
R → PSQR | ε④結(jié)果：
S → cSQR|bQR|aR
P → SPS|cS|b
Q → SP | c
R → PSQR | ε -
遞歸下降分析法：
通過(guò)計(jì)算的SELECT集判斷編寫(xiě)子程序：
例子：
遞歸下降分析法ParseE'函數(shù)表示進(jìn)入E'的產(chǎn)生式碱茁，通過(guò)switch函數(shù)分離相同左部的產(chǎn)生式裸卫，然后依次檢查產(chǎn)生式右部字符，如果是終結(jié)符纽竣，則通過(guò)MatchToken函數(shù)判斷符合墓贿，不符合則出錯(cuò)；如果是非終結(jié)符蜓氨，則繼續(xù)遞歸跳轉(zhuǎn)至它所對(duì)應(yīng)的Parse函數(shù)聋袋。
遞歸下降分析法對(duì)應(yīng)的是最左推導(dǎo)過(guò)程
優(yōu)點(diǎn)：程序結(jié)構(gòu)和層次清晰明了，易于手工實(shí)現(xiàn)语盈；
對(duì)于語(yǔ)義加工舱馅，這種方法十分靈活；
缺點(diǎn)：遞歸調(diào)用可能帶來(lái)效率問(wèn)題刀荒。 -
表驅(qū)動(dòng)LL(1)分析方法（預(yù)測(cè)分析法 ）
例子：
預(yù)測(cè)分析法首先根據(jù)計(jì)算出的SELECT集繪制出預(yù)測(cè)分析表
預(yù)測(cè)分析表然后新建一個(gè)分析棧，向空棧中依次壓入
#和文法的開(kāi)始符號(hào)E棘钞，然后比較剩余輸入串的首字符和分析棧頂元素缠借，如果不同，則先將分析棧頂元素出棧宜猜，然后將對(duì)應(yīng)預(yù)測(cè)分析表中的產(chǎn)生式右部<u>從后向前</u>依次入棧泼返；如果相同，則先將分析棧頂元素出棧姨拥，并將剩余輸入串的首字符刪去绅喉；然后重復(fù)以上過(guò)程直到棧為#，剩余輸入串也為#叫乌，則表示語(yǔ)法匹配成功柴罐。分析過(guò)程
-
LL(1)分析中的一種錯(cuò)誤處理辦法 ：
發(fā)現(xiàn)錯(cuò)誤的情況：
(1) 棧頂?shù)慕K結(jié)符與當(dāng)前輸入符不匹配;
(2) 非終結(jié)符A于棧頂，面臨的輸入符為a憨奸，但分析表M的M[A,a]為空 （FIRST(A)中沒(méi)有a）;應(yīng)急”恢復(fù)策略:
對(duì)于錯(cuò)誤(1) 跳過(guò)輸入串中的一些符號(hào)直至遇到和棧頂?shù)慕K結(jié)符相同的字符為止革屠。對(duì)于錯(cuò)誤((2) 跳過(guò)輸入串中的一些符號(hào)直至遇到“同步符號(hào)”為止 。
同步符號(hào)的選擇
(1) 把FOLLOW(A)中的所有符號(hào)作為A的同步符號(hào)排宰。跳過(guò)輸入串中的一些符號(hào)直至遇到這些“同步符號(hào)”似芝，把A從棧中彈出，可使分析繼續(xù)板甘。（跳過(guò)A）
(2) 把FIRST(A)中的符號(hào)加到A的同步符號(hào)集党瓮，當(dāng)FIRST(A)中的符號(hào)在輸入中出現(xiàn)時(shí)，可根據(jù)A恢復(fù)分析盐类。 （不跳過(guò)A）
