編譯原理課件chapter

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

2、不適合用于編譯器自頂向下語法分析器 (通常用于處理LL)從語法分析樹的根部開始構(gòu)造語法分析樹自底向上語法分析器 (通常用于處理LR)從語法分析樹的葉子開始構(gòu)造語法分析樹后兩種方法總是從左到右、逐個掃描詞法單元只能處理特定類型的述程序設(shè)計(jì)語言，但是這些足以用來描5上下文無關(guān)定義：一個上下文無關(guān)(CFG) 包含四個部分終結(jié)符號：組成串的基本符號 (詞法單元名字)非終結(jié)符號：表示串的集合的語法變量給出了語言的層次結(jié)構(gòu)在程序設(shè)計(jì)語言中通常對應(yīng)于某個程序構(gòu)造，比如stmt (語句)開始符號：某個被指定的非終結(jié)符號它對應(yīng)的串的集合就是的語言產(chǎn)生式集合：描述將終結(jié)符號和非終結(jié)符號組成串的方法產(chǎn)生式的形式：頭

3、 (左) 部 體 (右) 部頭部是一個非終結(jié)符號，右部是一個符號串例子：expression expression + term6上下文無關(guān)的例子簡單算術(shù)表的終結(jié)符號：id, +, , *, /, (, )非終結(jié)符號：expression, term, factor開始符號：expression 產(chǎn)生式集合expression expression + term expression expression term expression termterm term * factor term term / factor term factorfactor ( expression )facto

4、r id7書寫的約定n 終結(jié)符號：a b + 3 id n 非終結(jié)符號: A B C S stmt 符號: X Y n符號串: nn 終結(jié)符號串: u v w n 開始符號: S8簡單形式的例子E E + T | E T | TT T * F | T / F | F F ( E ) | idn 注意 | 是元符號 (即符號)描述中的符號，而不是 這里的 ( 和 ) 不是元符號9推導(dǎo) (1)n 推導(dǎo) 將待處理的串中的某個非終結(jié)符號替換為這個非終結(jié)符號的某個產(chǎn)生式的體 從開始符號出發(fā)，不斷進(jìn)行上面的替換，就可以得到的不同句型n 例子：E E | E + E | E * E | ( E ) | id

5、 推導(dǎo)序列：E = E = ( E ) = ( id )10推導(dǎo) (2)推導(dǎo)的正式定義如果A 是一個產(chǎn)生式，那么A = 最左 (右) 推導(dǎo)：() 中不包含非終結(jié)符號符號：經(jīng)過零步或者多步推導(dǎo)出：對于任何串如果且 = ，那么經(jīng)過一步或者多步推導(dǎo)出：等價于且不等于11句型/句子/語言句型 (Sentential form)如果S，那么就是S的句型可能既包含非終結(jié)符號，又包含終結(jié)符號，也可以是空串句子 (Sentence)的句子就是不包含非終結(jié)符號的句型語言G的語言就是G的句子的集合，記為L(G)w在L(G)中當(dāng)且僅當(dāng)w是G的句子，即Sw12語法分析樹推導(dǎo)的圖形表示形式根結(jié)點(diǎn)的標(biāo)號時的開始符號每個葉

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

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

8、是最左推導(dǎo)17二義性 (2)程序設(shè)計(jì)語言的通常都應(yīng)該是無二義性的否則就會導(dǎo)致一個程序有多種“正確”的解釋E E | E + E | E * E | ( E ) | id 的句子a + b * c如但有些二義性的情況可以方便的設(shè)計(jì)或語法分析器但是需要消二義性規(guī)則來剔除不要的語法分析樹比如：先乘除后加減18詞法分析和語法分析的比較19階段輸入輸出描述體系詞法分析源程序符號串詞法單元序列正則表語法分析詞法單元序列語法樹上下文無關(guān)(1)上下文無關(guān)和正則表上下文無關(guān)比正則表的能力更強(qiáng)描述所有的正則語言都可以使用但是一些用描述的語言不能用正則表描述證明首先S aSb | ab描述了語言anbn | n 0

9、，但是這個語言無法用DFA識別假設(shè)有DFA識別此語言L，且這個DFA有k個狀態(tài)。那么在識別ak+1的輸入串時，必然兩次到達(dá)同一個狀態(tài)。設(shè)自在第i個和第j個a時進(jìn)入同一個狀態(tài)，那么：因?yàn)镈FA識別L，ajbj必然到達(dá)接受狀態(tài)，因此aibj必然也到達(dá)接受狀態(tài)。直觀地講：有窮自不能計(jì)數(shù)20(2)上下文無關(guān)和正則表證明 (續(xù))其次證明：任何正則語言都可以表示為上下文無關(guān)文法的語言任何正則語言都必然有一個NFA；對于任意的NFA構(gòu)造如下的上下文無關(guān)對NFA的每個狀態(tài)i，創(chuàng)建非終結(jié)符號Ai如果有i在輸入a上到達(dá)j的轉(zhuǎn)換，增加產(chǎn)生式Ai aAj如果i在輸入上到達(dá)j，那么增加產(chǎn)生式Ai Aj如果i是一個接受狀

10、態(tài)，增加產(chǎn)生式Ai 如果i是開始狀態(tài)，令A(yù)i為所得的開始符號21NFA構(gòu)造的例子b(a|b)*abbA0 aA0 | bA0 | aA1A1 bA2 A2 bA3 A3 考慮baabb的推導(dǎo)和接受過程可知：NFA接受一個句子的運(yùn)行過程實(shí)際是推導(dǎo)出該句子的過程22及其生成的語言n 語言是由的開始符號出發(fā)，能夠推導(dǎo)得到的所有句子的集合G：S a S | a | b，L(G) = ai(a|b), i = 0G：S a S b | ab，L(G) = anbn, n = 1G：S ( S ) S | ，L(G) = 所有具有對稱括號對的串G所確定的語言Ln 如何驗(yàn)證 證明G生成的每個串都在L中 證明

11、L中的每個串都能被G生成23(1)設(shè)計(jì)能夠描述程序設(shè)計(jì)語言的大部分語法n 但不是全部，比如：標(biāo)識符的先后使用無法用上下文無關(guān)描述 因此語法分析器接受的語言是程序設(shè)計(jì)語言的超集；必須通過語義分析來剔除一些符合程序、但不合法的24(2)設(shè)計(jì)n 在進(jìn)行高效的語法分析之前，需要對處理 消除二義性做以下的二義性：可以為一個句子生成多顆不同的分析樹n 消除左遞歸中一個非終結(jié)符號A使得對某個串，左遞歸：推導(dǎo) A一個nA，則稱這個是左遞歸的 提取因子25二義性的消除 (1)一些二義性例子可以被改成等價的無二義性的stmtif expr then stmt| if expr then stmt else stm

12、t| otherif E1 then if E2then S1else S2的兩棵語法樹26二義性的消除 (2)為了保證“else和最近未匹配的then匹配”，我們要求在then分支的語句必須是匹配好的引入matched_stmt表示匹配好的語句，有如下 matched_stmt | open_stmt if expr then matched_stmt elsematched_stmt| otherstmtmatched_stmtopen_stmt if expr then stmt| if expr then matched_stmt else open_stmt二義性的消除方法沒有規(guī)律可

13、循27左遞歸的消除n 左遞歸的定義 如果一個中有非終結(jié)符號A使得AA，那么這個就是左遞歸的n 立即左遞歸 (規(guī)則左遞歸)中一個形如A A的產(chǎn)生式n 自頂向下的語法分析技術(shù)不能處理左遞歸的情況，因此需要消除左遞歸；但是自底向上的技術(shù)可以 處理左遞歸28立即左遞歸的消除假設(shè)非終結(jié)符號A立即左遞歸的情形，假設(shè)以A為左部的規(guī)則有：A A1 | A2 | | Am | 1| 2 | | n可以替換為A 1A | 2A | | nAA 1A | 2A | | mA | 由A生成的串總是以某個i開頭，然后跟上零個或者多個j的重復(fù) A A 29A A | A AA A | AA立即左遞歸消除示例30消除多步左

14、遞歸n 消除立即左遞歸的方法并不能消除因?yàn)閮刹交蚨嗖酵茖?dǎo)而產(chǎn)生的左遞歸：S Aa | b，A Ac | Sd | S = Aa = Sdan 如何消除？31通用的左遞歸消除方法輸入：沒有環(huán)和產(chǎn)生式的輸出：等價的無左遞歸的步驟G的非終結(jié)符號任意排序?yàn)锳1, A2, , An將for 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時：內(nèi)層循環(huán)不運(yùn)行

15、，S沒有立即左遞歸i = 2時：j = 1，處理規(guī)則A Sd；替換得到A Ac | Aad | bd | 消除A的立即左遞歸本例子中的產(chǎn)生式恰好沒有影響算法的正確性S Aa | bA bdA | AA cA | adA | 通用左遞歸消除的問題在于很難找到新和舊的推導(dǎo)之間的對應(yīng)關(guān)系，因此很難依據(jù)新進(jìn)行語義處理33分析法簡介試圖從開始符號推導(dǎo)出輸入符號串以開始符號作為初始的當(dāng)前句型每次為最左邊的非終結(jié)符號選擇適當(dāng)?shù)漠a(chǎn)生式通過查看下一個輸入符號來選擇這個產(chǎn)生式有多個可能的產(chǎn)生式時分析法為力：E + E E | E E | id；輸入為+ id id id比如當(dāng)兩個產(chǎn)生式具有相同的前綴時無法：stm

16、t if expr then stmt else stmt | if expr then stmt輸入：if a then 新：stmt if expr then stmt elsePartelsePart else stmt | 需要提取公因子34提取公因子的變換n 算法 輸入：G 輸出：等價的提取了因子的 方法：對于每個非終結(jié)符號A，找出它的兩個或者多個可選產(chǎn)生式體之間的最長公共前綴n A 1 | 2 | | n | n A A | ，A 1 | 2 | | nn 其中是不以開頭的產(chǎn)生式體35提取公因子的例子n S i E t S | i E t S e S | a E bn 對于S而言，

17、最長的前綴是i E t S，因此 S i E t S S | a S e S | E b36自頂向下的語法分析為輸入串構(gòu)造語法分析樹從分析樹的根結(jié)點(diǎn)開始，按照先根次序，深度優(yōu)先地創(chuàng)建各個結(jié)點(diǎn)對應(yīng)推導(dǎo)基本步驟確定對句型中最左邊的非終結(jié)符號應(yīng)用哪個產(chǎn)生式然后對句型中的非終結(jié)符號和輸入符號進(jìn)行匹配關(guān)鍵問題確定對最左邊的非終結(jié)符號應(yīng)用哪個產(chǎn)生式37自頂向下分析的例子E T EE + T E | T F TT * F T | F ( E ) | id輸入id + id * id分析樹序列見右38遞歸下降的語法分析遞歸下降語法分析一組過程組成每個非終結(jié)符號對應(yīng)于一個過程，該過程負(fù)責(zé)掃描此非終結(jié)符號對應(yīng)的結(jié)

18、構(gòu)程序執(zhí)行從開始符號對應(yīng)的過程開始當(dāng)掃描整個輸入串時宣布分析完成39遞歸下降分析技術(shù)的回溯如果沒有足夠的信息來唯一地確定可能的產(chǎn)生式，那么分析過程就產(chǎn)生回溯前面的算法報(bào)告錯誤 (第7行) 并不意味著輸入串不是句子，而可能是表示前面了產(chǎn)生式第1行上保存當(dāng)前的掃描指針；在第7行上應(yīng)該改成回退到保存的指針；GOTO 1) 并選擇下一個產(chǎn)生式如果沒有下一個產(chǎn)生式可選，報(bào)告錯誤回溯需要來回掃描，因而低效需要撤銷已經(jīng)完成的語義處理動作 (如果有)解決方法設(shè)法通過一些信息確定唯一可能的產(chǎn)生式40遞歸下降分析中回溯的例子：S cAd輸入串：cad步驟A ab | a調(diào)用函數(shù)SS選擇唯一產(chǎn)生式S cAd輸入中的

19、c和句型中的c匹配，繼續(xù)調(diào)用AA首先選擇產(chǎn)生式A ab，a和輸入的a匹配，b和輸入的d不匹配回溯并選擇下一個產(chǎn)生式A a；a和輸入的a相匹配；對A的調(diào)用返回；到S的調(diào)用S cAd中的d和下一個輸入d匹配對S的調(diào)用返回，已經(jīng)讀入所有輸入符號因此掃描結(jié)束，cad是S的句子41FIRST和FOLLOW在自頂向下的分析技術(shù)中，通常使用向前看幾個 符號來唯一地確定產(chǎn)生式 (通常只看一個符號)當(dāng)前句型是xA，而輸入是xa；那么選擇產(chǎn)生 式A 的必要條件是下列之一a，且以a開頭，即在某個句型中a跟在A之后如果按照這兩個條件選擇時能夠保證唯一性，那么我們就可以避免回溯因此，我們定義FIRST和FOLLOW42

20、FIRSTn FIRST() 可以從推導(dǎo)得到的串的首符號的集合 如果，那么也在FIRST()中n FIRST函數(shù)的意義 如果兩個A產(chǎn)生式 A | ，且FIRST()和FIRST() 不相交；下一個輸入符號是a，若a FIRST()，則選擇A ，若a FIRST()，則選擇A 43FIRST的計(jì)算方法計(jì)算FIRST(X)的方法如果X是終結(jié)符號，那么FIRST(X) = X如果X是非終結(jié)符號，且X Y1Y2Yk是產(chǎn)生式如果a在FIRST(Yi)中，且在FIRST(Y1), FIRST(Y2), ,FIRST(Yi-1)中，那么a也在FIRST(X)中如果在FIRST(Y1), FIRST(Y2),

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

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

23、 FIRST(F) = (, id FIRST(T) = FIRST(F) = (, id FIRST(E) = FIRST(T) = (, id FIRST(E) = +, FIRST(T) = *, n 由此可以推出各個產(chǎn)生式右部的FIRST集合 FIRST(TE) = FIRST(T) = (, idFIRST(+TE) = +47FIRST/FOLLOW的例子 (2)FOLLOW集合的計(jì)算過程 $在FOLLOW(E)中(E是開始符號) 由規(guī)則F (E)可知，)也在FOLLOW(E)中 由規(guī)則E TE可知FOLLOW(E)也包含了$和) 由規(guī)則E +TE，F(xiàn)IRST(E)中的+在FOLL

24、OW(T)中；且FIRST(E) 包含，因此FOLLOW(E)中的$和)也在FOLLOW(T)中 因?yàn)門只出現(xiàn)在T和T的產(chǎn)生式的末尾，可以得到FOLLOW(T) = FOLLOW(T) 由規(guī)則T FT，F(xiàn)IRST(T)中的*在FOLLOW(F)中；且FIRST(T)包含，因此FOLLOW(T)中的+, $, )也在FOLLOW(F)中因此nn FOLLOW(E) = $, )FOLLOW(E) = $, ) FOLLOW(T) = FOLLOW(T) = +, $, ) FOLLOW(F) = *, +, $, )48LL(1)(1)的任意兩個不同的產(chǎn)生式A | 定義：對終結(jié)符號a使得和都可以

25、推導(dǎo)出以a開頭的串不和最多只有一個可以推導(dǎo)出空串如果可以推導(dǎo)出空串，那么不能推導(dǎo)出以FOLLOW(A)中任何終結(jié)符號開頭的串等價于FIRST() FIRST() = (條件一、二)如果 FIRST()，那么FIRST() FOLLOW(A) = ； 反之亦然 (條件三)49LL(1)(2)對于LL(1)，可以在自頂向下分析過程中，根據(jù)當(dāng)前輸入符號來確定使用的產(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

26、stmt 得到句型if(exp) stmt else stmt然后發(fā)現(xiàn)要把句型中的第一個stmt展開，選擇產(chǎn)生式stmt while (exp) stmt，得到句型if (exp) while (exp) stmt else stmt再展開下個stmt，得到if (exp) while (exp) a else stmt 50分析表構(gòu)造算法G分析表Mn 輸入：n 輸出：n 方法 對于G的每個產(chǎn)生式A n 對于FIRST()中的每個終結(jié)符號a，將A 加入到MA, a中n 如果在FIRST()，那么對于FOLLOW(A)中的每個符號b，將A 加入到MA, b中 最后在所有的空白條目中填入error

27、51分析表的例子這個例子恰巧使得每個產(chǎn)生式的右部的第一個符號的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) = $, e使得S 也在MS, e中注意：LL(1)法是二義性的必然不是二義性的；而這個文53LL(1)的遞

28、歸下降分析遞歸下降語法分析一組過程組成每個非終結(jié)符號對應(yīng)于一個過程，該過程負(fù)責(zé)掃描非終結(jié)符號對應(yīng)的結(jié)構(gòu)可以使用當(dāng)前的輸入符號來唯一地選擇產(chǎn)生式如果當(dāng)前輸入符號為a，那么選擇MA, a中的產(chǎn)生式54分析 (1)非遞歸的n 在自頂向下分析的過程中，我們總是 匹配掉句型中左邊的所有終結(jié)符號 對 匹配邊的非終結(jié)符號，選擇適當(dāng)?shù)漠a(chǎn)生式展開的終結(jié)符號再被考慮，因此只需要記住句型的余下部分，以及尚未匹配的輸入終結(jié)符號串 由于展開的動作總是發(fā)生在余下部分的以用棧來存放這些符號，我們可55分析 (2)非遞歸的n 分析時的處理過程 初始化時，棧中僅包含開始符號S (和$) 如果棧頂元素是終結(jié)符號，那么進(jìn)行匹配 如

29、果棧頂元素是非終結(jié)符號n 使用分析表來選擇適當(dāng)?shù)漠a(chǎn)生式n 在棧頂用產(chǎn)生式右部替換產(chǎn)生式左部n 對所有的分析都可以用同樣的驅(qū)動程序56分析表驅(qū)動的分析器如果棧中的符號序列為，w是已經(jīng)被讀入的部分輸入，w是尚未處理的輸入；那么wS推導(dǎo)出w我們試圖從推導(dǎo)出余下的輸入終結(jié)符號串w分析程序使用awMX, a來擴(kuò)展X，將此產(chǎn)生式的右部按倒序壓入棧中57w分析算法輸入：串w，分析表M輸出：如果w是句子，輸出w的最左推導(dǎo)；否則報(bào)錯(1)(2)初始化：輸入緩沖區(qū)中為w$，棧中為S$；ip指向w的第一個符號令X = 棧頂符號，ip指向輸入符號aif (X = a) X出棧，ip向前移動 /* 和終結(jié)符號的匹配 *

30、/ else if (X是終結(jié)符號) error() /* 失配 */else if (MX, a是報(bào)錯條目) error() /* 無適當(dāng)?shù)漠a(chǎn)生式 */ else if (MX, a = X Y1Y2Yk) 輸出產(chǎn)生式X Y1Y2Yk彈出棧頂符號X；將Yk, Yk-1, , Y1壓入棧中不斷執(zhí)行第二步，直到要么報(bào)錯，要么棧中為空(3)58分析表驅(qū)動分析的例子輸入：id + id * id59注意：已經(jīng)匹配部分加上棧中符號必然是一個最左句型自底向上的語法分析n 為一個輸入串構(gòu)造語法分析樹的過程n 從葉子 (輸入串中的終結(jié)符號，將位于分析樹的底端) 開始，向上到達(dá)根結(jié)點(diǎn) 在實(shí)際的語法分析過程中并

31、真的構(gòu)造出相應(yīng)的分析樹，但是分析樹概念可以方便理解n 重要的自底向上語法分析的通用框架 移入-歸約 (shift-reduce)n 簡單LR技術(shù) (SLR)、LR技術(shù) (LR)60分析過程示例61歸約w“歸約”為n 自底向上語法分析過程看開始符號S的過程n 歸約步驟 一個與某產(chǎn)生式體相匹配的特定子串被替換為該產(chǎn)生式頭部的非終結(jié)符號n 問題 何時歸約 (歸約哪些符號串) ？ 歸約到哪個非終結(jié)符號？62歸約的例子id * id的歸約過程id * id，F(xiàn) * id，T * id，T * F，T，E對于句型T * id，有兩個子串和某產(chǎn)生式右部匹配T是E T的右部id是F id的右部為什么選擇將id

32、歸約為F，而不是將T歸約為E？：T歸約為E之后，E * id不再是句型問題：如何確定這一點(diǎn)？63句柄n 對輸入從左到右掃描，并進(jìn)行自底向上語法分析， 實(shí)際上可以反向構(gòu)造出一個最右推導(dǎo)n 句柄 最右句型中和某個產(chǎn)生式體匹配的子串，對它的歸約代表了該最右句型的最右推導(dǎo)的最后一步 正式定義：如果S是A 的一個句柄Aww，那么緊跟之后的n 在一個最右句型中，句柄右邊只有終結(jié)符號n 如果是無二義性的，那么每個句型都有且只有一個句柄64句柄的例子n 輸入：id * id65移入-歸約分析技術(shù)使用一個棧來保存歸約/掃描移入的符號棧中符號 (從底向上) 和待掃描的符號組成了一個最右句型開始時刻：棧中只包含$，

33、而輸入為w$ 結(jié)束時刻：棧中$S，而輸入$在分析過程中，不斷地移入符號，并在識別到句柄時進(jìn)行歸約句柄被識別時總是出現(xiàn)在棧的頂部66主要分析動作n 移入：將下一個輸入符號移動到棧頂n 歸約：將句柄歸約為相應(yīng)的非終結(jié)符號 句柄總是在棧頂 具體操作時彈出句柄，壓入被歸約到的非終結(jié)符號n 接受：宣布分析過程完成n 報(bào)錯：發(fā)現(xiàn)語法錯誤，調(diào)用錯誤恢復(fù)子程序67歸約分析過程的例子68為什么句柄總是在棧頂？n 為什么每次歸約得到的新句型的句柄仍在棧頂(不在棧的中間) ？n 考慮最右推導(dǎo)的兩個連續(xù)步驟的兩種情況 情況(1)：A被替換為By，然后產(chǎn)生式體中的最右非終結(jié)符號B被替換為 (歸約之后句柄為By) 情況(

34、2)：A首先被展開，產(chǎn)生式體中只包含終結(jié)符號； 下一個最右非終結(jié)符號B位于y左側(cè)移入-歸約分析中的對于有些不能使用移入-歸約分析的，不管用什么樣的移入-歸約分析器都會到達(dá)這樣的格局即使知道了棧中所有內(nèi)容、以及下面k個輸入符號，人們?nèi)匀粺o法知道是否該進(jìn)行歸約 (移入-歸約者不知道按照什么產(chǎn)生式進(jìn)行歸約 (歸約-歸約)，或)例如：設(shè)棧中符號串是，接下來的k個符號是x，產(chǎn)生移入/歸約的是y和y使得axy是最右句型且是句柄 (需歸約)，而axy也是最右句型，但是句柄還在右邊 (需移入)70移入-歸約的例子71歸約-歸約的例子n 輸入為id ( id , id )時的格局 棧： id ( idn輸入：,

35、 id ) 72LR語法分析技術(shù)LR(k)的語法分析概念L表示最左掃描，R表示反向構(gòu)造出最右推導(dǎo)k表示最多向前看k個符號當(dāng)k增大時，相應(yīng)的語法分析器的規(guī)模急劇增大k = 2時，程序語言的語法分析器的規(guī)模通常非常龐大當(dāng)k = 0, 1時，已經(jīng)可以解決很多語法分析問題，因此具有實(shí)踐意義因此，我們只考慮k 12w，那么我們說項(xiàng)A 12是可行前綴1的有效項(xiàng)97SLR的原理：可行前綴 (2)如果我們知道項(xiàng)A 12對1有效 當(dāng)2不等于空，表示句柄尚未出現(xiàn)在棧中，應(yīng)該移入 如果2等于空，表示句柄已出現(xiàn)在棧中，應(yīng)該歸約n如果某個時刻兩個有效項(xiàng)要求執(zhí)行不同的動n作，那么就應(yīng)該設(shè)法解決實(shí)際上表示可行前綴可能是兩個最右句型的前綴， 第一個包含了句柄，而另一個尚未包含句柄 也可能都認(rèn)為包含句柄，但