編譯原理課件chapter

1、第四章 語(yǔ)法分析許暢南京大學(xué)計(jì)算機(jī)系2012年春季概要n 語(yǔ)法分析器n 上下文無(wú)關(guān)文法n 語(yǔ)法分析技術(shù)¡ 自頂向下¡ 自底向上n 語(yǔ)法分析器生成工具2程序設(shè)計(jì)語(yǔ)言構(gòu)造的描述n 程序設(shè)計(jì)語(yǔ)言構(gòu)造的語(yǔ)法可使用上下文無(wú)關(guān)文法 或BNF表示法來(lái)描述¡ 文法可給出精確易懂的語(yǔ)則¡ 可以自動(dòng)構(gòu)造出某些類(lèi)型的文法的語(yǔ)法分析器¡ 文法指出了語(yǔ)言的結(jié)構(gòu)，有助于進(jìn)一步的語(yǔ)義處理/代碼生成¡ 支持語(yǔ)言的演化和迭代3語(yǔ)法分析器的作用基本作用從詞法分析器獲得詞法單元的序列，確認(rèn)該序列是否 可以由語(yǔ)言的文法生成對(duì)于語(yǔ)法錯(cuò)誤的程序，報(bào)告錯(cuò)誤信息 對(duì)于語(yǔ)法正確的程序

2、，生成語(yǔ)法分析樹(shù)通常并不真的生產(chǎn)這棵語(yǔ)法分析樹(shù)4語(yǔ)法分析器的分類(lèi)通用語(yǔ)法分析器可以對(duì)任意文法進(jìn)行語(yǔ)法分析效率很低，不適合用于編譯器自頂向下語(yǔ)法分析器 (通常用于處理LL文法)從語(yǔ)法分析樹(shù)的根部開(kāi)始構(gòu)造語(yǔ)法分析樹(shù)自底向上語(yǔ)法分析器 (通常用于處理LR文法)從語(yǔ)法分析樹(shù)的葉子開(kāi)始構(gòu)造語(yǔ)法分析樹(shù)后兩種方法總是從左到右、逐個(gè)掃描詞法單元只能處理特定類(lèi)型的文法，但是這些文法足以用來(lái)描述程序設(shè)計(jì)語(yǔ)言5上下文無(wú)關(guān)文法定義：一個(gè)上下文無(wú)關(guān)文法 (CFG) 包含四個(gè)部分終結(jié)符號(hào)：組成串的基本符號(hào) (詞法單元名字)非終結(jié)符號(hào)：表示串的集合的語(yǔ)法變量給出了語(yǔ)言的層次結(jié)構(gòu)在程序設(shè)計(jì)語(yǔ)言中通常對(duì)應(yīng)于某個(gè)程序構(gòu)造，比如s

3、tmt (語(yǔ)句)開(kāi)始符號(hào)：某個(gè)被指定的非終結(jié)符號(hào)它對(duì)應(yīng)的串的集合就是文法的語(yǔ)言產(chǎn)生式集合：描述將終結(jié)符號(hào)和非終結(jié)符號(hào)組成串的方法產(chǎn)生式的形式：頭(左) 部à 體 (右) 部頭部是一個(gè)非終結(jié)符號(hào)，右部是一個(gè)符號(hào)串例子：expression à expression + term6上下文無(wú)關(guān)文法的例子簡(jiǎn)單算術(shù)表達(dá)式的文法終結(jié)符號(hào)：id, +, , *, /, (, )非終結(jié)符號(hào)：expression, term, factor開(kāi)始符號(hào)：expression 產(chǎn)生式集合expression à expression + term expression à ex

4、pression term expression à termterm à term * factor term à term / factor term à factorfactor à ( expression )factor à id7文法書(shū)寫(xiě)的約定n 終結(jié)符號(hào)：a b + 3 id n 非終結(jié)符號(hào): A B C S stmt n 文法符號(hào): X Y n 文法符號(hào)串: n 終結(jié)符號(hào)串: u v w n 開(kāi)始符號(hào): S8文法簡(jiǎn)單形式的例子E à E + T | E T | TT à T * F | T / F

5、| F F à ( E ) | idn 注意¡ | 是元符號(hào) (即文法描述中的符號(hào)，而不是文法符號(hào))¡ 這里的 ( 和) 不是元符號(hào)9推導(dǎo) (1)n 推導(dǎo)¡ 將待處理的串中的某個(gè)非終結(jié)符號(hào)替換為這個(gè)非終結(jié)符號(hào)的某個(gè)產(chǎn)生式的體¡ 從開(kāi)始符號(hào)出發(fā)，不斷進(jìn)行上面的替換，就可以得到文法的不同句型n 例子¡ 文法：E à E | E + E | E * E | ( E ) | id¡ 推導(dǎo)序列：E => E => ( E ) => ( id )10推導(dǎo) (2)推導(dǎo)的正式定義如果A à 是一個(gè)產(chǎn)生式

6、，那么A => 最左 (右) 推導(dǎo)：() 中不包含非終結(jié)符號(hào)符號(hào)：經(jīng)過(guò)零步或者多步推導(dǎo)出：對(duì)于任何串如果且 => ，那么經(jīng)過(guò)一步或者多步推導(dǎo)出：等價(jià)于且不等于11句型/句子/語(yǔ)言句型 (Sentential form)如果S，那么就是文法S的句型可能既包含非終結(jié)符號(hào)，又包含終結(jié)符號(hào)，也可以是空串句子 (Sentence)文法的句子就是不包含非終結(jié)符號(hào)的句型語(yǔ)言文法G的語(yǔ)言就是G的句子的集合，記為L(zhǎng)(G)w在L(G)中當(dāng)且僅當(dāng)w是G的句子，即Sw12語(yǔ)法分析樹(shù)推導(dǎo)的圖形表示形式根結(jié)點(diǎn)的標(biāo)號(hào)時(shí)文法的開(kāi)始符號(hào)每個(gè)葉子結(jié)點(diǎn)的標(biāo)號(hào)是非終結(jié)符號(hào)、終結(jié)符號(hào)或 每個(gè)內(nèi)部節(jié)點(diǎn)的標(biāo)號(hào)是非終結(jié)符號(hào)每個(gè)內(nèi)

7、部結(jié)點(diǎn)表示某個(gè)產(chǎn)生式的一次應(yīng)用內(nèi)部結(jié)點(diǎn)的標(biāo)號(hào)為產(chǎn)生式頭，結(jié)點(diǎn)的子結(jié)點(diǎn)從左到右是產(chǎn)生式的體樹(shù)的葉子組成的序列是根的文法符號(hào)的一個(gè)句型一棵語(yǔ)法分析樹(shù)可對(duì)應(yīng)多個(gè)推導(dǎo)序列，但每顆分析樹(shù)和唯一的最左推導(dǎo)及唯一的最右推導(dǎo)相關(guān)聯(lián)13語(yǔ)法分析樹(shù)的例子n 文法：E à E | E + E | E * E | ( E ) | idn 句子： ( id + id )14從推導(dǎo)序列構(gòu)造分析樹(shù)n 假設(shè)有推導(dǎo)序列¡ A = a1 => a2 => => ann 算法¡ 初始化：a1的分析樹(shù)是標(biāo)號(hào)為A的單個(gè)結(jié)點(diǎn)¡ 假設(shè)已經(jīng)構(gòu)造出ai-1 = X1X2Xk的分析樹(shù)，且

8、ai-1到ai的推導(dǎo)是將Xj替換為，那么在當(dāng)前分析樹(shù)中找出第j個(gè)非結(jié)點(diǎn)，向這個(gè)結(jié)點(diǎn)增加則增加一個(gè)標(biāo)號(hào)為的子結(jié)點(diǎn)的子結(jié)點(diǎn)；如果 = ，15構(gòu)造分析樹(shù)的例子n 推導(dǎo)序列¡ E => E => ( E ) => ( E + E ) => ( id + E )=> ( id + id )16二義性 (1)二義性 (Ambiguous)：一個(gè)文法可以為某個(gè)句子生成多棵語(yǔ)法分析樹(shù)，這個(gè)文法就是二義性的例子E => E + E => id + E => id + E * E => id + id * E=> id + id * idE =

9、> E * E => E + E * E => id + E * E => id + id * E=> id + id * id都是最左推導(dǎo)17二義性 (2)程序設(shè)計(jì)語(yǔ)言的文法通常都應(yīng)該是無(wú)二義性的否則就會(huì)導(dǎo)致一個(gè)程序有多種“正確”的解釋如文法 E à E | E + E | E * E | ( E ) | id 的句子a + b * c但有些二義性的情況可以方便文法或語(yǔ)法分析器的設(shè)計(jì)但是需要消二義性規(guī)則來(lái)剔除不要的語(yǔ)法分析樹(shù)比如：先乘除后加減18詞法分析和語(yǔ)法分析的比較19階段輸入輸出描述體系詞法分析源程序符號(hào)串詞法單元序列正則表達(dá)式語(yǔ)法分析詞法單元序

10、列語(yǔ)法樹(shù)上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法和正則表達(dá)式 (1)上下文無(wú)關(guān)文法比正則表達(dá)式的能力更強(qiáng)所有的正則語(yǔ)言都可以使用文法描述但是一些用文法描述的語(yǔ)言不能用正則表達(dá)式描述證明首先S à aSb | ab描述了語(yǔ)言anbn | n > 0，但是這個(gè)語(yǔ)言無(wú)法用DFA識(shí)別假設(shè)有DFA識(shí)別此語(yǔ)言L，且這個(gè)DFA有k個(gè)狀態(tài)。那么在識(shí)別ak+1的輸入串時(shí)，必然兩次到達(dá)同一個(gè)狀態(tài)。設(shè)自在第i個(gè)和第j個(gè)a時(shí)進(jìn)入同一個(gè)狀態(tài)，那么：因?yàn)镈FA識(shí)別L，ajbj必然到達(dá)接受狀態(tài)，因此aibj必然也到達(dá)接受狀態(tài)。直觀地講：有窮自不能計(jì)數(shù)20上下文無(wú)關(guān)文法和正則表達(dá)式 (2)證明 (續(xù))其次證明：任何正則語(yǔ)

11、言都可以表示為上下文無(wú)關(guān)文法的語(yǔ)言任何正則語(yǔ)言都必然有一個(gè)NFA；對(duì)于任意的NFA構(gòu)造如下的上下文無(wú)關(guān)文法對(duì)NFA的每個(gè)狀態(tài)i，創(chuàng)建非終結(jié)符號(hào)Ai如果有i在輸入a上到達(dá)j的轉(zhuǎn)換，增加產(chǎn)生式Ai à aAj如果i在輸入上到達(dá)j，那么增加產(chǎn)生式Ai à Aj如果i是一個(gè)接受狀態(tài)，增加產(chǎn)生式Ai à 如果i是開(kāi)始狀態(tài)，令A(yù)i為所得文法的開(kāi)始符號(hào)21NFA構(gòu)造文法的例子b(a|b)*abbA0 à aA0 | bA0 | aA1A1 à bA2 A2 à bA3 A3 à 考慮baabb的推導(dǎo)和接受過(guò)程可知：NFA接受一個(gè)句子的運(yùn)行

12、過(guò)程實(shí)際是文法推導(dǎo)出該句子的過(guò)程22文法及其生成的語(yǔ)言n 語(yǔ)言是由文法的開(kāi)始符號(hào)出發(fā)，能夠推導(dǎo)得到的 所有句子的集合¡ 文法G：S à a S | a | b，L(G) = ai(a|b), i >= 0¡ 文法G：S à a S b | ab，L(G) = anbn, n >= 1¡ 文法G：S à ( S ) S | ，L(G) = 所有具有對(duì)稱(chēng)括號(hào)對(duì)的串n 如何驗(yàn)證文法G所確定的語(yǔ)言L¡ 證明G生成的每個(gè)串都在L中¡ 證明L中的每個(gè)串都能被G生成23設(shè)計(jì)文法 (1)n 文法能夠描述程序設(shè)計(jì)語(yǔ)言的大

13、部分語(yǔ)法¡ 但不是全部，比如：標(biāo)識(shí)符的先下文無(wú)關(guān)文法描述后使用無(wú)法用上¡ 因此語(yǔ)法分析器接受的語(yǔ)言是程序設(shè)計(jì)語(yǔ)言的超集；必須通過(guò)語(yǔ)義分析來(lái)剔除一些符合文法、但不合法的程序24設(shè)計(jì)文法 (2)n 在進(jìn)行高效的語(yǔ)法分析之前，需要對(duì)文法做以下 處理¡ 消除二義性n 文法的二義性：文法可以為一個(gè)句子生成多顆不同的分析樹(shù)¡ 消除左遞歸n 左遞歸：文法中一個(gè)非終結(jié)符號(hào)A使得對(duì)某個(gè)串，存在一個(gè)推導(dǎo) AA，則稱(chēng)這個(gè)文法是左遞歸的¡ 提取左公因子25二義性的消除 (1)一些二義性文法可以被改成等價(jià)的無(wú)二義性的文法例子stmtàif expr then

14、stmt| if expr then stmt else stmt| otherif E1 then if E2then S1else S2的兩棵語(yǔ)法樹(shù)26二義性的消除 (2)為了保證“else和最近未匹配的then匹配”，我們要求在then分支的語(yǔ)句必須是匹配好的引入matched_stmt表示匹配好的語(yǔ)句，有如下文法à matched_stmt | open_stmtà if expr then matched_stmt elsematched_stmt| otherstmtmatched_stmtopen_stmt à if expr then stmt|

15、if expr then matched_stmt else open_stmt二義性的消除方法沒(méi)有規(guī)律可循27左遞歸的消除n 左遞歸的定義¡ 如果一個(gè)文法中有非終結(jié)符號(hào)A使得A 文法就是左遞歸的n 立即左遞歸 (規(guī)則左遞歸)¡ 文法中存在一個(gè)形如A à A的產(chǎn)生式A，那么這個(gè)n 自頂向下的語(yǔ)法分析技術(shù)不能處理左遞歸的情況，因此需要消除左遞歸；但是自底向上的技術(shù)可以 處理左遞歸28立即左遞歸的消除假設(shè)非終結(jié)符號(hào)A存在立即左遞歸 的情形，假設(shè)以A為左部的規(guī)則有：A à A1 | A2 | | Am | 1| 2 | | n可以替換為A à 1A

16、| 2A | | nAA à 1A | 2A | | mA | 由A生成的串總是以某個(gè)i開(kāi)頭，然后跟上零個(gè)或者多個(gè)j的重復(fù) A A 29A à A | A à AA à A | AA立即左遞歸消除示例30消除多步左遞歸n 消除立即左遞歸的方法并不能消除因?yàn)閮刹交蚨?步推導(dǎo)而產(chǎn)生的左遞歸¡ 文法：S à Aa | b，A à Ac | Sd | S => Aa => Sda¡n 如何消除？31通用的左遞歸消除方法輸入：沒(méi)有環(huán)和產(chǎn)生式的文法G輸出：等價(jià)的無(wú)左遞歸的文法步驟將文法的非終結(jié)符號(hào)任意排序?yàn)锳1,

17、A2, , Anfor i = 1 to n do for j = 1 to i1 do 將形如Ai à Aj的產(chǎn)生式替換為Ai à 1 | 2 | | k，其中Aj à 1 | 2 | | k是以Aj為左部的所有產(chǎn)生式消除Ai的立即左遞歸32通用左遞歸消除的例子S à Aa | bA à Ac | Sd | 步驟1：排列為S, Ai = 1時(shí)：內(nèi)層循環(huán)不運(yùn)行，S沒(méi)有立即左遞歸i = 2時(shí)：j = 1，處理規(guī)則A à Sd；替換得到A à Ac | Aad | bd | 消除A的立即左遞歸本例子中的產(chǎn)生式恰好沒(méi)有影響算法的正

18、確性S à Aa | bA à bdA | AA à cA | adA | 通用左遞歸消除的問(wèn)題在于很難找到新文法和舊文法的推導(dǎo)之間的對(duì)應(yīng)關(guān)系，因此很難依據(jù)新文法進(jìn)行語(yǔ)義處理33分析法簡(jiǎn)介試圖從開(kāi)始符號(hào)推導(dǎo)出輸入符號(hào)串以開(kāi)始符號(hào)作為初始的當(dāng)前句型每次為最左邊的非終結(jié)符號(hào)選擇適當(dāng)?shù)漠a(chǎn)生式通過(guò)查看下一個(gè)輸入符號(hào)來(lái)選擇這個(gè)產(chǎn)生式有多個(gè)可能的產(chǎn)生式時(shí)分析法為力比如文法：E à + E E | E E | id；輸入為+ id id id當(dāng)兩個(gè)產(chǎn)生式具有相同的前綴時(shí)無(wú)法文法：stmt à if expr then stmt else stmt | if

19、expr then stmt輸入：if a then 新文法：stmt à if expr then stmt elsePart elsePart à else stmt | 需要提取公因子34提取公因子的文法變換n 算法¡ 輸入：文法G¡ 輸出：等價(jià)的提取了左公因子的文法¡ 方法：對(duì)于每個(gè)非終結(jié)符號(hào)A，找出它的兩個(gè)或者多個(gè)可選產(chǎn)生式體之間的最長(zhǎng)公共前綴n A à 1 | 2 | | n | n A à A | ，A à 1 | 2 | | nn 其中是不以開(kāi)頭的產(chǎn)生式體35提取公因子的例子n 文法¡ S

20、 à i E t S | i E t S e S | a¡ E à bn 對(duì)于S而言，最長(zhǎng)的前綴是i E t S，因此¡ S à i E t S S | a¡ S à e S | ¡ E à b36自頂向下的語(yǔ)法分析為輸入串構(gòu)造語(yǔ)法分析樹(shù)從分析樹(shù)的根結(jié)點(diǎn)開(kāi)始，按照先根次序，深度優(yōu)先地 創(chuàng)建各個(gè)結(jié)點(diǎn)對(duì)應(yīng)于最左推導(dǎo)基本步驟確定對(duì)句型中最左邊的非終結(jié)符號(hào)應(yīng)用哪個(gè)產(chǎn)生式然后對(duì)句型中的非終結(jié)符號(hào)和輸入符號(hào)進(jìn)行匹配關(guān)鍵問(wèn)題確定對(duì)最左邊的非終結(jié)符號(hào)應(yīng)用哪個(gè)產(chǎn)生式37自頂向下分析的例子文法E à T EE &#

21、224; + T E | T à F TT à * F T | F à ( E ) | id輸入id + id * id分析樹(shù)序列見(jiàn)右38遞歸下降的語(yǔ)法分析遞歸下降語(yǔ)法分析程序由一組過(guò)程組成每個(gè)非終結(jié)符號(hào)對(duì)應(yīng)于一個(gè)過(guò)程，該過(guò)程負(fù)責(zé)掃描此非終結(jié)符號(hào)對(duì)應(yīng)的結(jié)構(gòu)程序執(zhí)行從開(kāi)始符號(hào)對(duì)應(yīng)的過(guò)程開(kāi)始當(dāng)掃描整個(gè)輸入串時(shí)宣布分析完成39遞歸下降分析技術(shù)的回溯如果沒(méi)有足夠的信息來(lái)唯一地確定可能的產(chǎn)生式，那么分析過(guò)程就產(chǎn)生回溯前面的算法報(bào)告錯(cuò)誤 (第7行) 并不意味著輸入串不是句子，而可能是表示前面了產(chǎn)生式第1行上保存當(dāng)前的掃描指針；在第7行上應(yīng)該改成回退到保存的指針；GOTO 1)

22、 并選擇下一個(gè)產(chǎn)生式如果沒(méi)有下一個(gè)產(chǎn)生式可選，報(bào)告錯(cuò)誤回溯需要來(lái)回掃描，因而低效需要撤銷(xiāo)已經(jīng)完成的語(yǔ)義處理動(dòng)作 (如果有)解決方法設(shè)法通過(guò)一些信息確定唯一可能的產(chǎn)生式40遞歸下降分析中回溯的例子文法：S à cAd輸入串：cad步驟A à ab | a調(diào)用函數(shù)SS選擇唯一產(chǎn)生式S à cAd輸入中的c和句型中的c匹配，繼續(xù)調(diào)用AA首先選擇產(chǎn)生式A à ab，a和輸入的a匹配，b和輸入的d不匹配回溯并選擇下一個(gè)產(chǎn)生式A à a；a和輸入的a相匹配；對(duì)A的調(diào)用返回；到S的調(diào)用S à cAd中的d和下一個(gè)輸入d匹配對(duì)S的調(diào)用返回，已經(jīng)讀入所

23、有輸入符號(hào)因此掃描結(jié)束，cad是S的句子41FIRST和FOLLOW在自頂向下的分析技術(shù)中，通常使用向前看幾個(gè) 符號(hào)來(lái)唯一地確定產(chǎn)生式 (通常只看一個(gè)符號(hào))當(dāng)前句型是xA，而輸入是xa；那么選擇產(chǎn)生 式A à 的必要條件是下列之一a，且以a開(kāi)頭，即在某個(gè)句型中a跟在A之后如果按照這兩個(gè)條件選擇時(shí)能夠保證唯一性，那么我們就可以避免回溯因此，我們定義FIRST和FOLLOW42FIRSTn FIRST()¡ 可以從推導(dǎo)得到的串的首符號(hào)的集合¡ 如果，那么也在FIRST()中n FIRST函數(shù)的意義¡ 如果兩個(gè)A產(chǎn)生式 A à | ，且FIRST()

24、和FIRST() 不相交；下一個(gè)輸入符號(hào)是a，若a FIRST()，則選擇A à ，若a FIRST()，則選擇A à 43FIRST的計(jì)算方法計(jì)算FIRST(X)的方法如果X是終結(jié)符號(hào)，那么FIRST(X) = X如果X是非終結(jié)符號(hào)，且X à Y1Y2Yk是產(chǎn)生式如果a在FIRST(Yi)中，且在FIRST(Y1), FIRST(Y2), ,FIRST(Yi-1)中，那么a也在FIRST(X)中如果在FIRST(Y1), FIRST(Y2), , FIRST(Yk)中，那么在FIRST(X)中如果X是非終結(jié)符號(hào)且有X à ，那么在FIRST(X)中計(jì)算

25、FIRST(X1X2Xn)的方法向集合中加入FIRST(X1)中所有非的符號(hào)如果在FIRST(X1)中，再加入FIRST(X2)中的所有非 的符號(hào)；如果在所有FIRST(Xi)中，將加入FIRST(X1X2Xn)中44FOLLOWn FOLLOW(A)¡ 可能在某些句型中緊跟在A右邊的終結(jié)符號(hào)的集合¡ 例如：S à Aa，終結(jié)符號(hào)a FOLLOW(A)n FOLLOW函數(shù)的意義¡ 如果A à ，當(dāng) à e或 => e時(shí)，F(xiàn)OLLOW(A)可以幫助我們選擇恰當(dāng)?shù)漠a(chǎn)生式¡ 例如：A à ，而b屬于FOLLOW(A

26、)，如果 => e， 則若當(dāng)前輸入符號(hào)是b，可以選擇A à ，因?yàn)锳最終到達(dá)了e，而且后面跟著b45FOLLOW的計(jì)算方法算法將右端結(jié)束標(biāo)記$放到FOLLOW(S)中按照下面的兩個(gè)規(guī)則不斷迭代，直到所有的FOLLOW集合都不再增長(zhǎng)為止如果存在產(chǎn)生式A à B，那么FIRST()中所有非的符號(hào)都在FOLLOW(B)中如果存在一個(gè)產(chǎn)生式A à B，或者A à B且FIRST()包含，那么FOLLOW(A)中的所有符號(hào)都加入到FOLLOW(B)中請(qǐng)注意各個(gè)步驟中將符號(hào)加入到FOLLOW集合中的理由46FIRST/FOLLOW的例子 (1)文法¡

27、 E à TE¡ T à FTFIRST集合nE à +TE | T à *FT | F à (E) | idn¡ FIRST(F) = (, id¡ FIRST(T) = FIRST(F) = (, id¡ FIRST(E) = FIRST(T) = (, id¡ FIRST(E) = +, FIRST(T) = *, 由此可以推出各個(gè)產(chǎn)生式右部的FIRST集合n¡ FIRST(TE) = FIRST(T) = (, idFIRST(+TE) = +47FIRST/FOLLOW的例子

28、 (2)FOLLOW集合的計(jì)算過(guò)程¡ $在FOLLOW(E)中(E是開(kāi)始符號(hào))¡ 由規(guī)則F à (E)可知，)也在FOLLOW(E)中¡ 由規(guī)則E à TE可知FOLLOW(E)也包含了$和)¡ 由規(guī)則E à +TE，F(xiàn)IRST(E)中的+在FOLLOW(T)中；且FIRST(E) 包含，因此FOLLOW(E)中的$和)也在FOLLOW(T)中¡ 因?yàn)門(mén)只出現(xiàn)在T和T的產(chǎn)生式的末尾，可以得到FOLLOW(T) = FOLLOW(T)¡ 由規(guī)則T à FT，F(xiàn)IRST(T)中的*在FOLLOW(F

29、)中；且FIRST(T)包含，因此FOLLOW(T)中的+, $, )也在FOLLOW(F)中因此nn¡ FOLLOW(E) = $, )FOLLOW(E) = $, )¡ FOLLOW(T) = FOLLOW(T) = +, $, )¡ FOLLOW(F) = *, +, $, )48LL(1)文法 (1)定義：對(duì)文法的任意兩個(gè)不同的產(chǎn)生式A à | 不存在終結(jié)符號(hào)a使得和都可以推導(dǎo)出以a開(kāi)頭的串和最多只有一個(gè)可以推導(dǎo)出空串如果可以推導(dǎo)出空串，那么不能推導(dǎo)出以FOLLOW(A)中任何終結(jié)符號(hào)開(kāi)頭的串等價(jià)于FIRST() Ç FIRST() =

30、 (條件一、二)如果 FIRST()，那么FIRST() Ç FOLLOW(A) = ； 反之亦然(條件三)49LL(1)文法 (2)對(duì)于LL(1)文法，可以在自頂向下分析過(guò)程中，根據(jù)當(dāng)前輸入符號(hào)來(lái)確定使用的產(chǎn)生式產(chǎn)生式：stmt à if (exp) stmt else stmt |while (exp) stmt | a輸入：if (exp) while (exp) a else a首先選擇產(chǎn)生式stmt à if (exp) stmt else stmt 得到句型if(exp) stmt else stmt然后發(fā)現(xiàn)要把句型中的第一個(gè)stmt展開(kāi)，選擇產(chǎn)生式s

31、tmt à while (exp) stmt，得到句型if (exp) while (exp) stmt else stmt再展開(kāi)下個(gè)stmt，得到if (exp) while (exp) a else stmt 50分析表構(gòu)造算法n 輸入：文法G分析表Mn 輸出：n 方法¡ 對(duì)于文法G的每個(gè)產(chǎn)生式A à n 對(duì)于FIRST()中的每個(gè)終結(jié)符號(hào)a，將A à 加入到MA, a中n 如果在FIRST()，那么對(duì)于FOLLOW(A)中的每個(gè)符號(hào)b，將Aà 加入到MA, b中¡ 最后在所有的空白條目中填入error51分析表的例子文法這個(gè)例子

32、恰巧使得每個(gè)產(chǎn)生式的右部的第一個(gè)符號(hào)的FIRST集合 就等于產(chǎn)生式右部的FIRST集合； 但是在一般情況下不總是這樣的E à TE T à FTF à (E) | idE à +TE | T à *FT | FIRST集F：(, idE, T：(, idE：+, T：*, FOLLOW集E, E：$, )T, T：+, $, )F：*, +, $, )分析表的例子文法：S à iEtSS | a；S à eS | ；E à bFIRST(eS) = e，使得S à eS在MS, e中FOLLOW(S) =

33、 $, e使得S à 也在MS, e中注意：LL(1)文法必然不是二義性的；而這個(gè)文法是二義性的53LL(1)文法的遞歸下降分析遞歸下降語(yǔ)法分析程序由一組過(guò)程組成每個(gè)非終結(jié)符號(hào)對(duì)應(yīng)于一個(gè)過(guò)程，該過(guò)程負(fù)責(zé)掃描非終結(jié)符號(hào)對(duì)應(yīng)的結(jié)構(gòu)可以使用當(dāng)前的輸入符號(hào)來(lái)唯一地選擇產(chǎn)生式如果當(dāng)前輸入符號(hào)為a，那么選擇MA, a中的產(chǎn)生式54分析 (1)非遞歸的n 在自頂向下分析的過(guò)程中，我們總是¡ 匹配掉句型中左邊的所有終結(jié)符號(hào)¡ 對(duì)于最左邊的非終結(jié)符號(hào)，選擇適當(dāng)?shù)漠a(chǎn)生式展開(kāi)¡ 匹配的終結(jié)符號(hào)再被考慮，因此只需要記住句型的余下部分，以及尚未匹配的輸入終結(jié)符號(hào)串¡ 由

34、于展開(kāi)的動(dòng)作總是發(fā)生在余下部分的左端，我們可以用棧來(lái)存放這些符號(hào)55分析 (2)非遞歸的n 分析時(shí)的處理過(guò)程¡ 初始化時(shí)，棧中僅包含開(kāi)始符號(hào)S (和$)¡ 如果棧頂元素是終結(jié)符號(hào)，那么進(jìn)行匹配¡ 如果棧頂元素是非終結(jié)符號(hào)n 使用分析表來(lái)選擇適當(dāng)?shù)漠a(chǎn)生式n 在棧頂用產(chǎn)生式右部替換產(chǎn)生式左部n 對(duì)所有文法的分析都可以用同樣的驅(qū)動(dòng)程序56分析表驅(qū)動(dòng)的分析器如果棧中的符號(hào)序列為，w是已經(jīng)被讀入的部分輸入，w是尚未處理的輸入；那么w'S推導(dǎo)出w我們?cè)噲D從推導(dǎo)出余下的輸入終結(jié)符號(hào)串w分析程序使用awMX, a來(lái)擴(kuò)展X，將此產(chǎn)生式的右部按倒序壓入棧中57w分析算法輸入：

35、串w，分析表M輸出：如果w是句子，輸出w的最左推導(dǎo)；否則報(bào)錯(cuò)(1)(2)初始化：輸入緩沖區(qū)中為w$，棧中為S$；ip指向w的第一個(gè)符號(hào)令X = 棧頂符號(hào)，ip指向輸入符號(hào)aif (X = a) X出棧，ip向前移動(dòng) /* 和終結(jié)符號(hào)的匹配 */ else if (X是終結(jié)符號(hào)) error() /* 失配 */else if (MX, a是報(bào)錯(cuò)條目) error() /* 無(wú)適當(dāng)?shù)漠a(chǎn)生式 */ else if (MX, a = X à Y1Y2Yk) 輸出產(chǎn)生式X à Y1Y2Yk彈出棧頂符號(hào)X；將Yk, Yk-1, , Y1壓入棧中不斷執(zhí)行第二步，直到要么報(bào)錯(cuò)，要么棧中為

36、空(3)58分析表驅(qū)動(dòng)分析的例子輸入：id + id * id59注意：已經(jīng)匹配部分加上棧中符號(hào)必然是一個(gè)最左句型自底向上的語(yǔ)法分析n 為一個(gè)輸入串構(gòu)造語(yǔ)法分析樹(shù)的過(guò)程n 從葉子 (輸入串中的終結(jié)符號(hào)，將位于分析樹(shù)的底端) 開(kāi)始，向上到達(dá)根結(jié)點(diǎn)¡ 在實(shí)際的語(yǔ)法分析過(guò)程中并真的構(gòu)造出相應(yīng)的分析樹(shù)，但是分析樹(shù)概念可以方便理解n 重要的自底向上語(yǔ)法分析的通用框架¡ 移入-歸約 (shift-reduce)n 簡(jiǎn)單LR技術(shù) (SLR)、LR技術(shù) (LR)60分析過(guò)程示例61歸約n 自底向上語(yǔ)法分析過(guò)程看成從串w“歸約”為文法 開(kāi)始符號(hào)S的過(guò)程n 歸約步驟¡ 一個(gè)與某產(chǎn)生式

37、體相匹配的特定子串被替換為該產(chǎn)生式頭部的非終結(jié)符號(hào)n 問(wèn)題¡ 何時(shí)歸約 (歸約哪些符號(hào)串) ？¡ 歸約到哪個(gè)非終結(jié)符號(hào)？62歸約的例子id * id的歸約過(guò)程id * id，F(xiàn) * id，T * id，T * F，T，E對(duì)于句型T * id，有兩個(gè)子串和某產(chǎn)生式右部匹配T是E à T的右部id是F à id的右部為什么選擇將id歸約為F，而不是將T歸約為E？：T歸約為E之后，E * id不再是句型問(wèn)題：如何確定這一點(diǎn)？63句柄n 對(duì)輸入從左到右掃描，并進(jìn)行自底向上語(yǔ)法分析， 實(shí)際上可以反向構(gòu)造出一個(gè)最右推導(dǎo)n 句柄¡ 最右句型中和某個(gè)產(chǎn)生式體匹

38、配的子串，對(duì)它的歸約代表了該最右句型的最右推導(dǎo)的最后一步¡ 正式定義：如果S是A à 的一個(gè)句柄Aww，那么緊跟之后的n 在一個(gè)最右句型中，句柄右邊只有終結(jié)符號(hào)n 如果文法是無(wú)二義性的，那么每個(gè)句型都有且只 有一個(gè)句柄64句柄的例子n 輸入：id * id65移入-歸約分析技術(shù)使用一個(gè)棧來(lái)保存歸約/掃描移入的文法符號(hào)棧中符號(hào) (從底向上) 和待掃描的符號(hào)組成了一個(gè)最右句型開(kāi)始時(shí)刻：棧中只包含$，而輸入為w$ 結(jié)束時(shí)刻：棧中$S，而輸入$在分析過(guò)程中，不斷地移入符號(hào)，并在識(shí)別到句柄時(shí)進(jìn)行歸約句柄被識(shí)別時(shí)總是出現(xiàn)在棧的頂部66主要分析動(dòng)作n 移入：將下一個(gè)輸入符號(hào)移動(dòng)到棧頂n

39、歸約：將句柄歸約為相應(yīng)的非終結(jié)符號(hào)¡ 句柄總是在棧頂¡ 具體操作時(shí)彈出句柄，壓入被歸約到的非終結(jié)符號(hào)n 接受：宣布分析過(guò)程完成n 報(bào)錯(cuò)：發(fā)現(xiàn)語(yǔ)法錯(cuò)誤，調(diào)用錯(cuò)誤恢復(fù)子程序67歸約分析過(guò)程的例子68為什么句柄總是在棧頂？n 為什么每次歸約得到的新句型的句柄仍在棧頂(不在棧的中間) ？n 考慮最右推導(dǎo)的兩個(gè)連續(xù)步驟的兩種情況¡ 情況(1)：A被替換為By，然后產(chǎn)生式體中的最右非終結(jié)符號(hào)B被替換為 (歸約之后句柄為By)¡ 情況(2)：A首先被展開(kāi)，產(chǎn)生式體中只包含終結(jié)符號(hào)； 下一個(gè)最右非終結(jié)符號(hào)B位于y左側(cè)移入-歸約分析中的對(duì)于有些不能使用移入-歸約分析的文法

40、，不管用什么樣的移入-歸約分析器都會(huì)到達(dá)這樣的格局即使知道了棧中所有內(nèi)容、以及下面k個(gè)輸入符號(hào)，人們?nèi)匀粺o(wú)法知道是否該進(jìn)行歸約 (移入-歸約者不知道按照什么產(chǎn)生式進(jìn)行歸約 (歸約-歸約)，或)例如：設(shè)棧中符號(hào)串是，接下來(lái)的k個(gè)符號(hào)是x，產(chǎn)生移入/歸約的是存在y和y使得axy是最右句型且是句柄 (需歸約)，而axy也是最右句型，但是句柄還在右邊 (需移入)70移入-歸約的例子71歸約-歸約的例子n 輸入為id ( id , id )時(shí)的格局¡ 棧： id ( idn輸入：, id ) 72LR語(yǔ)法分析技術(shù)LR(k)的語(yǔ)法分析概念L表示最左掃描，R表示反向構(gòu)造出最右推導(dǎo)k表示最多向前看k

41、個(gè)符號(hào)當(dāng)k增大時(shí)，相應(yīng)的語(yǔ)法分析器的規(guī)模急劇增大k = 2時(shí)，程序語(yǔ)言的語(yǔ)法分析器的規(guī)模通常非常龐大當(dāng)k = 0, 1時(shí)，已經(jīng)可以解決很多語(yǔ)法分析問(wèn)題，因此具有實(shí)踐意義因此，我們只考慮k <= 1的情況73LR語(yǔ)法分析器的優(yōu)點(diǎn)由表格驅(qū)動(dòng)；雖然手工構(gòu)造表格工作量大，但表 格可以自動(dòng)生成對(duì)于幾乎所有的程序設(shè)計(jì)語(yǔ)言，只要寫(xiě)出上下文無(wú)關(guān)文法，就能夠構(gòu)造出識(shí)別該構(gòu)造的LR語(yǔ)法分 析器最通用的無(wú)回溯移入-歸約分析技術(shù)，且和其它技 術(shù)一樣高效可以盡早檢測(cè)到錯(cuò)誤能分析的文法比LL(k)文法74LR(0)項(xiàng)文法的一個(gè)產(chǎn)生式加上在其中某處的一個(gè)點(diǎn)A à ×XYZ，A à X&#

42、215;YZ，A à XY×Z，A à XYZ×注意：A à 只對(duì)應(yīng)一個(gè)項(xiàng)A à ×直觀含義項(xiàng)A à ×表示已經(jīng)掃描/歸約到了，并期望接下來(lái)的輸入中經(jīng)過(guò)掃描/歸約得到，然后把歸約到A如果為空，表示我們可以把歸約為A 項(xiàng)也可以用一對(duì)整數(shù)表示：(i, j)表示第i條產(chǎn)生式，點(diǎn)位于右部第j個(gè)位置75LR(0)項(xiàng)集規(guī)范族的構(gòu)造三個(gè)相關(guān)定義增廣文法項(xiàng)集閉包CLOSURE GOTO函數(shù)增廣文法G的增廣文法G是在G中增加新開(kāi)始符號(hào)S，并加入產(chǎn)生式S à S而得到的顯然G和G接受相同的語(yǔ)言，且按照S à

43、; S進(jìn)行歸約實(shí)際上就表示已經(jīng)將輸入符號(hào)串歸約成為開(kāi)始符號(hào)76項(xiàng)集閉包CLOSUREn 項(xiàng)集的閉包CLOSURE：如果I是文法G的一個(gè)項(xiàng)集，那么CLOSURE(I)就是根據(jù)下列兩條規(guī)則從I 構(gòu)造得到的項(xiàng)集¡ 將I中的各個(gè)項(xiàng)加入到CLOSURE(I)中¡ 如果A à ×B在CLOSURE(I)中，B à 是一個(gè)產(chǎn)生式，并且項(xiàng)B à ×不在CLOSURE(I)中，就將該項(xiàng)加入其中；不斷應(yīng)用這條規(guī)則，直到?jīng)]有新項(xiàng)可被加入n 意義： A à ×B，表示接下來(lái)希望看到由B推導(dǎo)出的串，那首先要看到由B推導(dǎo)得到的子串，

44、因此加上B的各個(gè)產(chǎn)生式對(duì)應(yīng)的項(xiàng)77CLOSURE(I)的構(gòu)造算法78項(xiàng)集閉包構(gòu)造的例子n 增廣文法¡ E à E¡ F à (E) | idE à E+T | TT à T*F | Fn 項(xiàng)集E à ×E的閉包¡ E à ×E在閉包中¡ E à ×E+T, E à ×T在閉包中¡ T à ×T*F, T à ×F在閉包中¡ F à ×(E), F à

45、; ×id在閉包中79GOTO函數(shù)GOTO函數(shù)I是一個(gè)項(xiàng)集，X是一個(gè)文法符號(hào)，GOTO(I, X)定義為I 中所有形如的項(xiàng)A à ×X所對(duì)應(yīng)的項(xiàng)A à X×的集合的閉包例如I = E à E×, E à E×+TGOTO(I, +)計(jì)算如下I中只有一個(gè)項(xiàng)的點(diǎn)后面跟著+，對(duì)應(yīng)的項(xiàng)為E à E+×T CLOSURE(E à E+×T) = E à E+×T, T à ×T*F, T à ×F,F à

46、×(E), F à ×id80求LR(0)項(xiàng)集規(guī)范族的算法從初始項(xiàng)集開(kāi)始，不斷計(jì)算各種可能的后繼，直到生成所有的項(xiàng)集81項(xiàng)集規(guī)范族構(gòu)造示例82LR(0)自的構(gòu)造n 構(gòu)造方法¡ 基于規(guī)范LR(0)項(xiàng)集族可以構(gòu)造LR(0)自¡ 規(guī)范LR(0)項(xiàng)集族中的每個(gè)項(xiàng)集對(duì)應(yīng)于LR(0)自一個(gè)狀態(tài)的¡ 狀態(tài)轉(zhuǎn)換：如果GOTO(I, X) = J，則從I到J有一個(gè)標(biāo)號(hào)為X的轉(zhuǎn)換¡ 初始狀態(tài)為CLOSURE(S à ×S)對(duì)應(yīng)的項(xiàng)集83LR(0)自的作用 (1)假設(shè)文法符號(hào)串使LR(0)自到狀態(tài) (項(xiàng)集) j如果j中有一個(gè)形

47、如A à ×的項(xiàng)，那么從開(kāi)始狀態(tài)運(yùn)行在之后添加一些終結(jié)符號(hào)可以得到一個(gè)最右句型是的后綴，且是這個(gè)句型的句柄 (對(duì)應(yīng)產(chǎn)生式A à )表示可能找到了當(dāng)前最右句型的句柄如果j中存在一個(gè)項(xiàng)B à ×X，那么在之后添加X(jué)和一些終結(jié)符號(hào)可得到一個(gè)最右句型這個(gè)句型中B à X是句柄，但還沒(méi)找到，還需移入84LR(0)自的作用 (2)LR(0)自的使用移入-歸約時(shí)，LR(0)自被用于識(shí)別句型已得到的文法符號(hào)序列對(duì)應(yīng)于LR(0)自的一條路徑不需要每次用該文法符號(hào)序列來(lái)運(yùn)行LR(0)自路徑被放到棧中，且文法符號(hào)可以省略，由LR(0)狀態(tài) 可以確定相應(yīng)文法

48、符號(hào)在移入后，根據(jù)原來(lái)的棧頂狀態(tài)即可知道新的狀態(tài)在歸約時(shí)，根據(jù)歸約產(chǎn)生式的右部長(zhǎng)度彈出相應(yīng)狀態(tài)， 仍然可以根據(jù)此時(shí)的棧頂狀態(tài)計(jì)算得到新?tīng)顟B(tài)85LR(0)的作用演示：分析id * id棧中只保留了狀態(tài)，文法符號(hào)可以從相應(yīng)的狀態(tài)中獲取86LR語(yǔ)法分析器的結(jié)構(gòu)所有的分析器都使用相同的驅(qū)動(dòng)程序分析表隨文法以及LR分析技術(shù)的不同而不同棧中存放的是狀態(tài)序列；可以由狀態(tài)序列求出符號(hào)序列分析程序根據(jù)棧頂狀態(tài)、當(dāng)前輸入， 通過(guò)分析表確定語(yǔ)法分析動(dòng)作87LR語(yǔ)法分析表的結(jié)構(gòu)n 兩個(gè)部分：動(dòng)作ACTION，轉(zhuǎn)換GOTOn ACTION表項(xiàng)有兩個(gè)參數(shù)：狀態(tài)i，終結(jié)符號(hào)a¡ 移入j：j是一個(gè)狀態(tài)，把j壓入棧

49、(同時(shí)移入a)¡ 歸約A à ：把棧頂?shù)臍w約為A (并根據(jù)GOTO表項(xiàng)壓入新?tīng)顟B(tài))¡ 接受：接受輸入，完成分析¡ 報(bào)錯(cuò)：在輸入中發(fā)現(xiàn)語(yǔ)法錯(cuò)誤n GOTO表項(xiàng)¡ 如果GOTOIi, A = Ij，那么GOTOi, A = j88LR語(yǔ)法分析器的格局LR語(yǔ)法分析器的格局包含了棧中內(nèi)容和余下輸入(s0s1sm, aiai+1an$)第一個(gè)分量是棧中的內(nèi)容 (右側(cè)是棧頂)第二個(gè)分量是余下輸入LR語(yǔ)法分析器的每一個(gè)狀態(tài)都對(duì)應(yīng)一個(gè)文法符號(hào)(s0除外)如果進(jìn)入狀態(tài)s的邊的標(biāo)號(hào)為符號(hào)X，那么s就對(duì)應(yīng)于X令Xi為si對(duì)應(yīng)的符號(hào)，那么X1X2Xm aiai+1an

50、對(duì)應(yīng)于一個(gè)最右句型89LR語(yǔ)法分析器的行為n 對(duì)于格局(s0s1sm, aiai+1an$)，LR語(yǔ)法分析器查詢(xún)條目ACTIONsm, ai確定相應(yīng)的動(dòng)作¡ 移入s：執(zhí)行移入動(dòng)作，將狀態(tài)s (對(duì)應(yīng)輸入ai) 移入棧中，得到新格局(s0s1sms，ai+1an$)¡ 歸約A à ：將棧頂?shù)臍w約為A，壓入狀態(tài)s，得到新格局(s0s1sm-rs，aiai+1an$)，其中r是的長(zhǎng)度，狀態(tài)s = GOTOsm-r, A¡ 接受：語(yǔ)法分析過(guò)程完成¡ 報(bào)錯(cuò)：發(fā)現(xiàn)語(yǔ)法錯(cuò)誤，調(diào)用錯(cuò)誤恢復(fù)例程90LR語(yǔ)法分析算法n 輸入：文法G的LR語(yǔ)法分析表，輸入串wn 輸出

51、：如果w在L(G)中，則輸出自底向上語(yǔ)法分析 過(guò)程中的歸約步驟，否則輸出錯(cuò)誤指示n 算法如下：LR分析表的例子(1) E à E+T(3) T à T*F(5) F à (E)(2) E à T(4) T à F(6) F à idn 文法：92LR分析過(guò)程的例子n 輸入：id * id + id93SLR語(yǔ)法分析表的構(gòu)造n SLR語(yǔ)法分析表以LR(0)自為基礎(chǔ)n 增廣文法G的SLR語(yǔ)法分析表構(gòu)造算法¡ 構(gòu)造G的LR(0)項(xiàng)集規(guī)范族I0, I1, , In¡ 狀態(tài)i對(duì)應(yīng)于項(xiàng)集Ii，相關(guān)的ACTION/GOTO表?xiàng)l目

52、如下n A à ×a在Ii中，且GOTO(Ii, a) = Ij，那么ACTIONi, a = sjn A à ×在Ii中，那么對(duì)FOLLOW(A)中所有a，ACTIONi, a = 按Aà 歸約n 如果S à S×在Ii中，那么將ACTIONi, $設(shè)置為“接受”n 如果GOTO(Ii, A) = Ij，那么GOTO表中，GOTOi, A = j¡ 空白的條目設(shè)置為errorn 如果SLR分析表中沒(méi)有，這個(gè)文法就是SLR的SLR的基本思想是：要把a(bǔ)歸約成為A，后面必須是FOLLOW(A)中的終結(jié)符號(hào)；否則只能移入

53、94SLR分析表構(gòu)造的例子n 項(xiàng)集I0E à ×ET à ×T*FE à ×E+T T à ×FE à ×T F à ×(E)F à ×id¡ ACTION0, ( = s4¡ GOTO0, E = 1 GOTO0, F = 3n 項(xiàng)集I1：E à Eס ACTION1, + = s6n 項(xiàng)集I2：E à Tס ACTION2, * = s7ACTION0, id = s5GOTO0, T = 2E à E×+TACTION1, $ = 接受T à T×*FACTION2, +/)/$ = 歸約E à T95非SLR(1)文法的例子n S à L = R | Rn L à *R | idn R à Ln 對(duì)于I2¡ 第一個(gè)項(xiàng)使ACTION2, = = s6¡ 第二個(gè)項(xiàng)使ACTION2, = = 歸約R à L96SLR的原理：可行前綴 (1)n LR(0)自刻畫(huà)了可能出現(xiàn)在移入-歸約語(yǔ)法分析棧中的文法符號(hào)串