編譯原理課件chapter

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

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

3、tmt (語句)開始符號：某個被指定的非終結(jié)符號它對應的串的集合就是文法的語言產(chǎn)生式集合：描述將終結(jié)符號和非終結(jié)符號組成串的方法產(chǎn)生式的形式：頭(左) 部à 體 (右) 部頭部是一個非終結(jié)符號，右部是一個符號串例子：expression à expression + term6上下文無關文法的例子簡單算術表達式的文法終結(jié)符號：id, +, , *, /, (, )非終結(jié)符號：expression, term, factor開始符號：expression 產(chǎn)生式集合expression à expression + term expression à ex

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

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

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

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

8、ai-1到ai的推導是將Xj替換為，那么在當前分析樹中找出第j個非結(jié)點，向這個結(jié)點增加則增加一個標號為的子結(jié)點的子結(jié)點；如果 = ，15構造分析樹的例子n 推導序列¡ 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 =

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

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

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

12、過程實際是文法推導出該句子的過程22文法及其生成的語言n 語言是由文法的開始符號出發(fā)，能夠推導得到的 所有句子的集合¡ 文法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) = 所有具有對稱括號對的串n 如何驗證文法G所確定的語言L¡ 證明G生成的每個串都在L中¡ 證明L中的每個串都能被G生成23設計文法 (1)n 文法能夠描述程序設計語言的大

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

14、stmt| if expr then stmt else stmt| 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|

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

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

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時：內(nèi)層循環(huán)不運行，S沒有立即左遞歸i = 2時：j = 1，處理規(guī)則A à Sd；替換得到A à Ac | Aad | bd | 消除A的立即左遞歸本例子中的產(chǎn)生式恰好沒有影響算法的正

18、確性S à Aa | bA à bdA | AA à cA | adA | 通用左遞歸消除的問題在于很難找到新文法和舊文法的推導之間的對應關系，因此很難依據(jù)新文法進行語義處理33分析法簡介試圖從開始符號推導出輸入符號串以開始符號作為初始的當前句型每次為最左邊的非終結(jié)符號選擇適當?shù)漠a(chǎn)生式通過查看下一個輸入符號來選擇這個產(chǎn)生式有多個可能的產(chǎn)生式時分析法為力比如文法：E à + E E | E E | id；輸入為+ id id id當兩個產(chǎn)生式具有相同的前綴時無法文法：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é)符號A，找出它的兩個或者多個可選產(chǎn)生式體之間的最長公共前綴n A à 1 | 2 | | n | n A à A | ，A à 1 | 2 | | nn 其中是不以開頭的產(chǎn)生式體35提取公因子的例子n 文法¡ S

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

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

22、 并選擇下一個產(chǎn)生式如果沒有下一個產(chǎn)生式可選，報告錯誤回溯需要來回掃描，因而低效需要撤銷已經(jīng)完成的語義處理動作 (如果有)解決方法設法通過一些信息確定唯一可能的產(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不匹配回溯并選擇下一個產(chǎn)生式A à a；a和輸入的a相匹配；對A的調(diào)用返回；到S的調(diào)用S à cAd中的d和下一個輸入d匹配對S的調(diào)用返回，已經(jīng)讀入所

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

24、和FIRST() 不相交；下一個輸入符號是a，若a FIRST()，則選擇A à ，若a FIRST()，則選擇A à 43FIRST的計算方法計算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), , FIRST(Yk)中，那么在FIRST(X)中如果X是非終結(jié)符號且有X à ，那么在FIRST(X)中計算

25、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 à ，當 à e或 => e時，F(xiàn)OLLOW(A)可以幫助我們選擇恰當?shù)漠a(chǎn)生式¡ 例如：A à ，而b屬于FOLLOW(A

26、)，如果 => e， 則若當前輸入符號是b，可以選擇A à ，因為A最終到達了e，而且后面跟著b45FOLLOW的計算方法算法將右端結(jié)束標記$放到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)文法¡

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) = *, 由此可以推出各個產(chǎn)生式右部的FIRST集合n¡ FIRST(TE) = FIRST(T) = (, idFIRST(+TE) = +47FIRST/FOLLOW的例子

28、 (2)FOLLOW集合的計算過程¡ $在FOLLOW(E)中(E是開始符號)¡ 由規(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)中¡ 因為T只出現(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)定義：對文法的任意兩個不同的產(chǎn)生式A à | 不存在終結(jié)符號a使得和都可以推導出以a開頭的串和最多只有一個可以推導出空串如果可以推導出空串，那么不能推導出以FOLLOW(A)中任何終結(jié)符號開頭的串等價于FIRST() Ç FIRST() =

30、 (條件一、二)如果 FIRST()，那么FIRST() Ç FOLLOW(A) = ； 反之亦然(條件三)49LL(1)文法 (2)對于LL(1)文法，可以在自頂向下分析過程中，根據(jù)當前輸入符號來確定使用的產(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)要把句型中的第一個stmt展開，選擇產(chǎn)生式s

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

32、恰巧使得每個產(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) =

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

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

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

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

37、體相匹配的特定子串被替換為該產(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歸約為F，而不是將T歸約為E？：T歸約為E之后，E * id不再是句型問題：如何確定這一點？63句柄n 對輸入從左到右掃描，并進行自底向上語法分析， 實際上可以反向構造出一個最右推導n 句柄¡ 最右句型中和某個產(chǎn)生式體匹

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

53、94SLR分析表構造的例子n 項集I0E à ×ET à ×T*FE à ×E+T T à ×FE à ×T F à ×(E)F à ×id¡ ACTION0, ( = s4¡ GOTO0, E = 1 GOTO0, F = 3n 項集I1：E à Eס ACTION1, + = s6n 項集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 對于I2¡ 第一個項使ACTION2, = = s6¡ 第二個項使ACTION2, = = 歸約R à L96SLR的原理：可行前綴 (1)n LR(0)自刻畫了可能出現(xiàn)在移入-歸約語法分析棧中的文法符號串