1. 自頂向下分析概述
? 從分析樹的根節(jié)點(diǎn)向葉節(jié)點(diǎn)方向構(gòu)造分析樹,可以看做是從文法開始符號(hào)推導(dǎo)出詞串的過程
(1). 最左推導(dǎo)
? 在最左推導(dǎo)中,總是選擇每個(gè)句型的最左側(cè)非終結(jié)符進(jìn)行替換.
(2). 遞歸向下分析
? 計(jì)算機(jī)程序?qū)崿F(xiàn)的自頂向下分析的通用形式.
? 每層遞歸對(duì)應(yīng)一個(gè)非終結(jié)符(相當(dāng)于遍歷一個(gè)樹的子節(jié)點(diǎn),非終結(jié)符對(duì)應(yīng)的是非葉子節(jié)點(diǎn))
? 搭配回溯使用
2. 文法轉(zhuǎn)換
(1). 消除直接左遞歸
? 當(dāng)同一個(gè)非終結(jié)符的多個(gè)候選式存在相同的前綴時(shí),會(huì)導(dǎo)致回溯(最終只會(huì)匹配其中一個(gè))
? 將含有 A->Aα 形式產(chǎn)生式的文法稱為是直接左遞歸的.使用最左推導(dǎo)的遞歸向下分析可能會(huì)無(wú)限遞歸.
A -> Aα | β ===> A -> βA' 其中 A' -> αA' | ε
? 因?yàn)槭亲筮f歸,所以都是A->βααααααα......這樣的,那么把第一個(gè)β抽取出來(lái),再新建立一個(gè)A'->αααααα....就可以替換左遞歸.其中后面新建立的這個(gè)式子是右遞歸的.
(2). 消除間接左遞歸
? S -> Aa | b
? A -> Ac | Sd | ε
? 這里的遞歸是間接存在于兩條文法中的.
? 將兩個(gè)式子代入,編程直接左遞歸,然后消除直接左遞歸
[圖片上傳失敗...(image-8e7d85-1582632405566)]
(3). 提取左公因式
[圖片上傳失敗...(image-6c6cf2-1582632405566)]
? 推遲決定,等待獲取到了足夠的信息在做出選擇.
3. LL1文法
(1). 預(yù)測(cè)分析法
? 在自頂向下的分析中,可能會(huì)遇到回溯.如果能夠預(yù)先讀取幾個(gè)字符,就可以避免很多回溯.
? LL1就是使用預(yù)先讀取一個(gè)字符的預(yù)測(cè)分析技術(shù)的文法.
1). 工作過程
? 從文法開始符號(hào)出發(fā),每一步根據(jù)當(dāng)前句型的最左非終結(jié)符和當(dāng)前輸入符號(hào),選擇正確的產(chǎn)生式,所選出的產(chǎn)生式必須是唯一的.
? 文法最好滿足的條件,即S_文法(簡(jiǎn)單的確定性文法):
- 每個(gè)產(chǎn)生式的右部都以終結(jié)符開始(每一次推導(dǎo)都能確定一個(gè)字符)
- 同一個(gè)非終結(jié)符的各個(gè)候選式的首終結(jié)符都不同.(每讀入一個(gè)字符都決定依次推導(dǎo),不會(huì)有回溯)
? 在推導(dǎo)過程中,如果當(dāng)前的文法不匹配,能否使用空產(chǎn)生式取決于當(dāng)前輸入的符號(hào)是否在使用空產(chǎn)生式后能夠被接收.(也就是跳過空產(chǎn)生式能否匹配)
4. FIRST集和FOLLOW集
(1). 非終結(jié)符的后繼符號(hào)集
? 非終結(jié)符A的后繼符號(hào)集就是指可能在某個(gè)句型中緊跟在A后面的終結(jié)符a的集合.記為==FOLLOW(A)==
(2). 產(chǎn)生式的可選集
? 產(chǎn)生式 A -> β的可選集是指可以選用該產(chǎn)生式==進(jìn)行推導(dǎo)時(shí)對(duì)應(yīng)的輸入符號(hào)==的概念.記為==SELECT(A->β)==
- SELECT(A->aβ) = {a} (這里就是明顯的可以接收字符a)
- SELECT(A->ε) = FOLLOW(A) (這里是非終結(jié)符A選擇推導(dǎo)為空產(chǎn)生式的條件就是遇到了可以接收的終結(jié)符)
q_文法:
- 每個(gè)產(chǎn)生式的右部要么是ε,要么以終結(jié)符開始
- 相同左部的產(chǎn)生式有不想交的可選集
(3). 串首終結(jié)符集
? 作為串首的第一個(gè)符號(hào),并且是終結(jié)符.
? 給定一個(gè)文法符號(hào)串α,α的串首終結(jié)符集==FIRST(α)==被定義為可以從α推導(dǎo)出的所有串首終結(jié)符構(gòu)成的集合.
? (α等價(jià)的所有串的首字符)
? 如果α能推出空串,那么空串也在FIRST集中.
? 那么,是不是意味著,如果FIRST(α)中不包含空串,那么SELECT(A->α) = FIRST(α).(如果該串A通過一個(gè)文法一定能推出來(lái)一個(gè)串,那么使用該文法記性推導(dǎo)時(shí)索要輸入的字符一定是α的等價(jià)串的首字符.....好像廢話了)
? 如果FIRST(α)中包含空串,那么SELECT(A->α) = ( FIRST(α)-{ε} ) ∪ FOLLOW(A)(如果這個(gè)串A通過一個(gè)文法可能會(huì)推出空串,那么需要讀入一個(gè)α等價(jià)串首字符-空字符 和 A后面可以接受的任意一個(gè)字符,也就是直接將A推導(dǎo)為空串)
? 總結(jié):有文法A->α, 如果α可以推出空串,那么本次推導(dǎo)可以輸入α等價(jià)串的首字符(除去空串)和A的任意后繼終結(jié)符(直接將A推導(dǎo)為空串).如果不能推出空串,那么只能輸入α等價(jià)串的首字符.
(4). LL1文法
? 文法G是LL(1)的,當(dāng)且僅當(dāng)G的任意兩個(gè)擁有任意左部的產(chǎn)生式A -> α | β滿足以下條件:
- 如果α和β都不能推導(dǎo)出空串,那么FIRST(α)∩FIRST(β) = ?(不相交)
- α和β至多有一個(gè)能推出空串(FOLLOW(A)部分會(huì)相交)
- 如果α能推出空串,那么FIRST(β)∩FOLLOW(A) = ?(原因同上)
(5). 預(yù)測(cè)分析表
1). 求FIRST集
? 根據(jù)定義,求出等價(jià)串的所有首字符即可.
2). 求FOLLOW集
? 根據(jù)定義求出所有跟隨的字符,這里如果作為產(chǎn)生式的最右側(cè)出現(xiàn),要添加結(jié)束符$.
? 適當(dāng)?shù)膮⒖糉IRST集
3). 求SELECT集
? 右部的FIRST集,如果右部能推出空串,還要加上左部的FOLLOW集.
4). 預(yù)測(cè)分析表
[圖片上傳失敗...(image-aec080-1582632405566)]
? SELECT集的含義是非終結(jié)符能通過讀取那個(gè)字符通過產(chǎn)生式進(jìn)行推導(dǎo),這里裝換為非終結(jié)符通過那個(gè)產(chǎn)生式讀取某個(gè)符號(hào).
5. 遞歸的預(yù)測(cè)分析法
6. 非遞歸的預(yù)測(cè)分析法
7. 預(yù)測(cè)分析法中的錯(cuò)誤處理
8. 自底向上的分析概述
? 從分析樹的底部葉節(jié)點(diǎn)向頂部根節(jié)點(diǎn)方向構(gòu)造分析樹.
? 可以看做是將輸入串歸約為開始符號(hào)的過程.
(1). 移入-歸約分析
? 最右歸約.
? 使用棧,將出入串輸入到棧中,每次入棧后判斷棧頂?shù)膎個(gè)元素是否是某個(gè)產(chǎn)生式的右部,如果是,進(jìn)行歸約.直到棧中包含開始符號(hào)且輸入緩沖區(qū)為空.
? 所選棧頂?shù)淖址M可能長(zhǎng),保證推導(dǎo)的唯一性.
9. LR分析法概述
? LR文法是最大的,可以構(gòu)造出移入-歸約語(yǔ)法分析器的文法類.
? LR(k)分析是指需要提前查看k個(gè)符號(hào),一般k=0或者1是有實(shí)踐意義的.
(1). 基本原理
[圖片上傳失敗...(image-b9e62f-1582632405566)]
? 當(dāng)輸入棧中沒有字符時(shí),為移進(jìn)狀態(tài).
? 當(dāng)輸入棧中的字符不能進(jìn)行歸約,需要繼續(xù)輸入字符時(shí),為待約狀態(tài).
? 當(dāng)輸入棧中的字符符合某個(gè)產(chǎn)生式的右部時(shí),為歸約狀態(tài).
