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

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

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

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

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

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

7、是將Xj替換為，那么在當前分析樹中找出第j個非結點，向這個結點增加則增加一個標號為的子結點的子結點；如果 = ，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 = E * E = E + E * E = id + E * E = id + id * E= id + id * id都

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

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

10、態，增加產生式Ai 如果i是開始狀態，令Ai為所得的開始符號21NFA構造的例子b(a|b)*abbA0 aA0 | bA0 | aA1A1 bA2 A2 bA3 A3 考慮baabb的推導和接受過程可知：NFA接受一個句子的運行過程實際是推導出該句子的過程22及其生成的語言n 語言是由的開始符號出發，能夠推導得到的所有句子的集合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 如何驗證 證明G生成的每個串都在L中 證明

11、L中的每個串都能被G生成23(1)設計能夠描述程序設計語言的大部分語法n 但不是全部，比如：標識符的先后使用無法用上下文無關描述 因此語法分析器接受的語言是程序設計語言的超集；必須通過語義分析來剔除一些符合程序、但不合法的24(2)設計n 在進行高效的語法分析之前，需要對處理 消除二義性做以下的二義性：可以為一個句子生成多顆不同的分析樹n 消除左遞歸中一個非終結符號A使得對某個串，左遞歸：推導 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二義性的消除方法沒有規律可

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

14、遞歸n 消除立即左遞歸的方法并不能消除因為兩步或多步推導而產生的左遞歸：S Aa | b，A Ac | Sd | S = Aa = Sdan 如何消除？31通用的左遞歸消除方法輸入：沒有環和產生式的輸出：等價的無左遞歸的步驟G的非終結符號任意排序為A1, A2, , An將for i = 1 to n do for j = 1 to i1 do 將形如Ai Aj的產生式替換為Ai 1 | 2 | | k，其中Aj 1 | 2 | | k是以Aj為左部的所有產生式消除Ai的立即左遞歸32通用左遞歸消除的例子S Aa | bA Ac | Sd | 步驟1：排列為S, Ai = 1時：內層循環不運行

15、，S沒有立即左遞歸i = 2時：j = 1，處理規則A Sd；替換得到A Ac | Aad | bd | 消除A的立即左遞歸本例子中的產生式恰好沒有影響算法的正確性S Aa | bA bdA | AA cA | adA | 通用左遞歸消除的問題在于很難找到新和舊的推導之間的對應關系，因此很難依據新進行語義處理33分析法簡介試圖從開始符號推導出輸入符號串以開始符號作為初始的當前句型每次為最左邊的非終結符號選擇適當的產生式通過查看下一個輸入符號來選擇這個產生式有多個可能的產生式時分析法為力：E + E E | E E | id；輸入為+ id id id比如當兩個產生式具有相同的前綴時無法：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 輸出：等價的提取了因子的 方法：對于每個非終結符號A，找出它的兩個或者多個可選產生式體之間的最長公共前綴n A 1 | 2 | | n | n A A | ，A 1 | 2 | | nn 其中是不以開頭的產生式體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自頂向下的語法分析為輸入串構造語法分析樹從分析樹的根結點開始，按照先根次序，深度優先地創建各個結點對應推導基本步驟確定對句型中最左邊的非終結符號應用哪個產生式然后對句型中的非終結符號和輸入符號進行匹配關鍵問題確定對最左邊的非終結符號應用哪個產生式37自頂向下分析的例子E T EE + T E | T F TT * F T | F ( E ) | id輸入id + id * id分析樹序列見右38遞歸下降的語法分析遞歸下降語法分析一組過程組成每個非終結符號對應于一個過程，該過程負責掃描此非終結符號對應的結

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

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

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

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

22、如果 = e， 則若當前輸入符號是b，可以選擇A ，因為A最終到達了e，而且后面跟著b45FOLLOW的計算方法算法將右端結束標記$放到FOLLOW(S)中按照下面的兩個規則不斷迭代，直到所有的FOLLOW集合都不再增長為止產生式A B，那么FIRST()中所有非的符號都在如果FOLLOW(B)中一個產生式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 由此可以推出各個產生式右部的FIRST集合 FIRST(TE) = FIRST(T) = (, idFIRST(+TE) = +47FIRST/FOLLOW的例子 (2)FOLLOW集合的計算過程 $在FOLLOW(E)中(E是開始符號) 由規則F (E)可知，)也在FOLLOW(E)中 由規則E TE可知FOLLOW(E)也包含了$和) 由規則E +TE，FIRST(E)中的+在FOLL

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

25、推導出以a開頭的串不和最多只有一個可以推導出空串如果可以推導出空串，那么不能推導出以FOLLOW(A)中任何終結符號開頭的串等價于FIRST() FIRST() = (條件一、二)如果 FIRST()，那么FIRST() FOLLOW(A) = ； 反之亦然 (條件三)49LL(1)(2)對于LL(1)，可以在自頂向下分析過程中，根據當前輸入符號來確定使用的產生式產生式：stmt if (exp) stmt else stmt |while (exp) stmt | a輸入：if (exp) while (exp) a else a首先選擇產生式stmt if (exp) stmt else

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

27、51分析表的例子這個例子恰巧使得每個產生式的右部的第一個符號的FIRST集合 就等于產生式右部的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、歸下降分析遞歸下降語法分析一組過程組成每個非終結符號對應于一個過程，該過程負責掃描非終結符號對應的結構可以使用當前的輸入符號來唯一地選擇產生式如果當前輸入符號為a，那么選擇MA, a中的產生式54分析 (1)非遞歸的n 在自頂向下分析的過程中，我們總是 匹配掉句型中左邊的所有終結符號 對 匹配邊的非終結符號，選擇適當的產生式展開的終結符號再被考慮，因此只需要記住句型的余下部分，以及尚未匹配的輸入終結符號串 由于展開的動作總是發生在余下部分的以用棧來存放這些符號，我們可55分析 (2)非遞歸的n 分析時的處理過程 初始化時，棧中僅包含開始符號S (和$) 如果棧頂元素是終結符號，那么進行匹配 如

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

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

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

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

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

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

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