《西安電子科技大學《編譯原理》.ppt》由會員分享，可在線閱讀，更多相關《西安電子科技大學《編譯原理》.ppt（32頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、1,第三章 語法分析,詞法分析：元素是字母表，組成字符串，線性結構，單詞的集合 語法分析：元素是終結符，組成句子，樹結構， 句子的集合 語法的雙重含意： 語法規(guī)則：上下文無關文法（子集LL文法或LR文法） 語法分析：下推自動機（LL或LR分析器），自上而下和自下而上分析,本章主要內容： 與語法分析有關的基本概念和相關問題 上下文無關文法 自上而下分析 自下而上分析 上機作業(yè)第二部分：函數(shù)繪圖語言的語法分析器,2,3.1 語法分析的若干問題 3.1.1 語法分析器的作用,語法分析器是編譯器前端的重要組成部分，許多編譯器，特別是由自動生成工具構造的編譯器，往往其前端的中心部件就是語法分析器。語
2、法分析器在編譯器中的位置和作用下：,它的主要作用有兩點： 根據(jù)詞法分析器提供的記號流，為語法正確的輸入構造分析樹（或語法樹），這是本章的重點，在以后各節(jié)中詳細討論； 檢查輸入中的語法（可能包括詞法）錯誤，并調用出錯處理器進行適當處理，下邊簡單介紹語法錯誤處理的基本原則，而在以后的討論中忽略此問題。,3,3.1.2 語法錯誤的處理原則, 源程序中可能出現(xiàn)的錯誤 兩類：語法錯誤和語義錯誤。 詞法錯誤如非法字符或拼寫錯關鍵字、標識符等； intege20times 語法錯誤是指語法結構出錯，如少分號、begin/end不配對等。 beginx:=a+by:=x; 靜態(tài)語義錯誤：如類型不一致、參數(shù)
3、不匹配等； a,b:integer;x:array1..10 of integer; x:=a+b; 動態(tài)語義錯誤（邏輯錯誤）：如無窮遞歸、變量為零時作除數(shù)等。 while (t) ...;a:=a/b;,大多數(shù)錯誤的診斷和恢復集中在語法分析階段。一個原因是大多數(shù)錯誤是語法錯誤，另一個原因是語法分析方法的準確性，它們能以非常有效的方法診斷語法錯誤。 在編譯的時侯，想要準確診斷語義或邏輯錯誤有時是很困難的。,4,3.1.2 語法錯誤的處理原則（續(xù)1）, 語法錯誤處理的目標 對語法錯誤的處理，一般希望達到以下基本目標： 清楚而準確地報告錯誤的出現(xiàn)，地點正確、不漏報、不錯報也不多報； 迅速地從每
4、個錯誤中恢復過來（以便分析繼續(xù)進行）； 不應使對語法正確源程序的分析速度降低太多。,5,3.1.2 語法錯誤的處理原則（續(xù)2）, 語法錯誤的基本恢復策略 緊急方式恢復：拋棄若干輸入，直到遇到同步記號。 短語級恢復：采用串替換的方式對剩余輸入進行局部糾正（拋棄插入）。 出錯產(chǎn)生式：用出錯產(chǎn)生式捕捉錯誤（預測錯誤）。預置型的短語級恢復方式。 全局糾正：對錯誤輸入序列x，找相近序列y，使得x變換成y所需的修改、插入、刪除次數(shù)最少。,例3.1 下述兩條是有語法錯誤的語句，其中第一條賦值句結束時忘記加分號，采用緊急恢復方式和短語級恢復方式的可能結果分別如下所示。 x := a + b y :=
5、c + d; 緊急方式： x := a + b + d; -- 丟棄b之后的若干記號，直到遇到同步記號+為止。 短語級恢復：x := a + b; -- 加入分號，使之成為一個賦值句 y := c + d;,6,3.2 上下文無關文法(Context Free Grammar, CFG)3.2.1 CFG的定義與表示,定義3.1 CFG是一個四元組G =（N，T，P，S），其中 （1） N是非終結符（Nonterminals）的有限集合； （2） T是終結符（Terminals）的有限集合，且NT=； （3） P是產(chǎn)生式（Productions）的有限集合， A，其中AN（左部），(N
6、T)*（右部）， 若=，則稱A為空產(chǎn)生式（也可以記為A ）； （4） S是非終結符，稱為文法的開始符號（Start symbol）。,例3.2 簡單算術表達式的上下文無關文法可表示如下： N=E T=+，*，(，)，-，id S=E P: E E + E （1） E E * E （2） E （E） （3） (G3.1) E -E （4） E id （5）,7, 由產(chǎn)生式集表示CFG 3.2.1 CFG的定義與表示（續(xù)1）,前提：若文法正確，第一個產(chǎn)生式的左部是文法開始符號S 則： N是僅出現(xiàn)在產(chǎn)生式左邊符號的集合， T是所有不出現(xiàn)在產(chǎn)生式左邊符號的集合（
7、記號）,P: E E + E （1） E E * E （2） E （E） （3） E -E （4） E id （5）, 產(chǎn)生式的一般讀法 可以將產(chǎn)生式中的記號讀作“定義為”或者“可導出”。 更一般的，“E E + E”可用自然語言表述為“算術表達式定義為兩個算術表達式相加”， 或者“一個算術表達式加上另一個算術表達式，仍然是一個算術表達式”。, 終結符與非終結符書寫上的區(qū)分 (a) 用大小寫區(qū)分： E id (b) 用“”區(qū)分： E id E E + E (c) 用區(qū)分： + 約定：大寫英文字母A、B、C表示非終結符； 小寫英文字母a、b、c表示終結符；
8、 小寫希臘字母、、表示任意文法符號序列。,S=E N=E T=+，*，(， )，-，id,8, 產(chǎn)生式的縮寫形式 3.2.1 CFG的定義與表示（續(xù)2）,當若干個產(chǎn)生式具有相同的左部非終結符時，可以將它們合并為一個產(chǎn)生式。 該產(chǎn)生式的左部是此非終結符， 右部是所有原來右部的或運算（并集合）， 產(chǎn)生式也以非終結符命名。,例3.3 G3.1可以重寫為如下形式： E E + E （1） | E * E （2） |（E） （3） (G3.2) | -E （4） | id （5）,P: E E + E （1） E E * E （2） E （E） （3） E -
9、E （4） E id （5）,我們可以稱它為E產(chǎn)生式。 用“|”連接的每個右部稱為一個候選項，它們具有平等的權利。 即id是一個表達式，-E也是一個表達式。,9,3.2.2 CFG產(chǎn)生語言的基本方法推導,CFG（產(chǎn)生式）通過推導的方法產(chǎn)生語言。 通俗地講，產(chǎn)生式產(chǎn)生語言的過程是從開始符號S開始， 對產(chǎn)生式左部的非終結符反復地使用產(chǎn)生式： 將產(chǎn)生式左部的非終結符替換為右部的文法符號序列（展開產(chǎn)生式，用標記=表示），直到得到一個終結符序列。,例3.4 用(G3.2)產(chǎn)生終結符序列-(id+id)可如下： E = -E by(4) = -(E) by(3) = -(E+E)
10、 by(1) = -(id+E) by(5) = -(id+id) by(5),E E + E （1） | E * E （2） |（E） （3） (G3.2) | -E （4） | id （5）,10,3.2.2 CFG產(chǎn)生語言的基本方法推導（續(xù)1）,定義3.2 利用產(chǎn)生式產(chǎn)生句子的過程中，將產(chǎn)生式A的右部代替文法符號序列A中的A得到的過程，稱為A直接推導出，記作：A=。 若對于任意文法符號序列1，2，...n，均有1=2=...=n，則稱此過程為零步或多步推導，記為： 1=*n，其中1=n的情況為零步推導。 若1n，即推導過程中至少使用一次產(chǎn)生式，則稱此過程為至少一步推導，
11、記為：1=+n。 ,定義3.2強調了兩點： ，有=*，即推導具有自反性； 若=*，=*，則=*，即推導具有傳遞性。,定義3.3 由CFG G所產(chǎn)生的語言L(G)被定義為: L(G) = S=+ and T* ， L(G)稱為上下文無關語言（Context Free Language, CFL），稱為句子。若S=*，(NT)*，則稱為G的一個句型。 ,11,3.2.2 CFG產(chǎn)生語言的基本方法推導（續(xù)2）,定義3.4 在推導過程中，若每次直接推導均替換句型中最左邊的非終結符，則稱為最左推導，由最左推導產(chǎn)生的句型被稱為左句型。 ,類似的可以定義最右推導與右句型，最右推導也被稱為規(guī)范推導。,再
12、考察-(id+id)的推導過程（這是一個最左推導）： E = -E = -(E) = -(E+E) = -(id+E) = -(id+id) 1 2 3 4 5 6 其中，1是文法開始符號，6是句子，其他i(i=2、3、4、5)均是句型。句型是一個相當廣泛的概念，根據(jù)定義3.3可知，1和6同樣也是句型。,12,3.2.3 推導、分析樹與語法樹,對于推導：E = -E = -(E) = -(E+E) = -(id+E) = -(id+id) 它產(chǎn)生句子的方式很不直觀，看起來十分困難。 分析樹是推導的圖形表示，它的表示很直觀，并且同時反映語言結構的實質和推導過程。,定義3.5 對CFG
13、 G的句型，分析樹被定義為具有下述性質的一棵樹。 （1） 根由開始符號所標記； （2） 每個葉子由一個終結符、非終結符、或標記； （3） 每個內部結點由一個非終結符標記； （4） 若A是某內部節(jié)點的標記，且X1，X2，...，Xn是該節(jié)點從左到右所有孩子的標記，則AX1X2...Xn是一個產(chǎn)生式。若A，則標記為A的結點可以僅有一個標記為的孩子。 ,分析樹與語言和文法的關系： 每一直接推導（每個產(chǎn)生式），對應一棵僅有父子關系的子樹，即產(chǎn)生式左部非終結符“長出”右部的孩子； 分析樹的葉子，從左到右構成G的一個句型。若葉子僅由終結符標記，則構成一個句子。,13,3.2.3 推導、分析樹與語法樹（續(xù)1
14、）,例3.5 再考察-(id+id)的推導過程。 E = -E = -(E) = -(E+E) = -(id+E) = -(id+id) 用分析樹的方式如下：,E -E,E ( E ),E E + E,E id,最左推導和最右推導的中間過程對應的分析樹可能不同，因為句型不同： -(id+E) 或 -(E+id) 但是最終的分析樹相同，因為最終是同一個句子： -(id+id),分析樹既反映了產(chǎn)生句型的推導過程，又反映了句型的結構。,14,3.2.3 推導、分析樹與語法樹（續(xù)2）,更多的情況下，僅關注句型結構，而忽略推導過程。,定義3.6 對CFG G的句型，表達式的語法樹被定義為具有下述性質的一
15、棵樹: （1） 根與內部節(jié)點由表達式中的操作符標記； （2） 葉子由表達式中的操作數(shù)標記； （3）用于改變運算優(yōu)先級和結合性的括弧，被隱含在語法樹的結構中。 ,15,3.2.3 推導、分析樹與語法樹（續(xù)3）,例3.6 句子-(id+id)和句型if C then s1 else s2 ：,S if C then S1 else S2,分析樹：左部非終結符“產(chǎn)生”右部文法符號序列； 語法樹：操作符（運算）“作用于”操作數(shù)（運算對象）； 習慣上：分析樹和語法樹被分別稱為具體語法樹和抽象語法樹。,16,3.2.4 二義性與二義性的消除3.2.4.1 二義性（歧義，Ambiguity）,問題：一個句子
16、可能對應多于一棵分析樹 例3.7 句子id+id*id和id+id+id可能的分析樹：,G3.2： E E + E （1） | E * E （2） |（E） （3） | -E （4） | id （5）,定義3.7 若G對同一句子產(chǎn)生不止一棵分析樹，則稱G是二義的。 原因：在產(chǎn)生句子的過程中某些直接推導有多于一種選擇,一個句子有多于一棵分析樹，僅與文法和句子有關，與采用的推導方法無關； 文法中缺少對文法符號優(yōu)先級和結合性的規(guī)定。,17,“懸空（dangling）else”問題 3.2.4.1 二義性（續(xù)1）,S if C then S (1) | if C then S el
17、se S (2) | id := E (3)(G3.3) C E = E | E E (4)...(6) E E + E | - E | id | n (7)...(10),例3.8 條件語句 if x0 then x:=5 else x:=-5,if x0 then x:=5 else x:=-5,if x0 then x:=5 else x:=-5,18,3.2.4.2 二義性的消除,文法二義不能說明程序設計語言是二義。程序設計語言不能二義。 消除語言二義的兩種方法： 改寫二義文法為非二義文法； 規(guī)定二義文法中符號的優(yōu)先級和結合性，使僅產(chǎn)生一棵分析樹。 改寫二義文法為非二義文法,再分
18、析id+id*id和id+id+id：,例3.9 與G3.2等價的非二義文法: E E + T | T T T * F | F (G3.4) F （E） | -F | id,問題：如何將二義文法改寫為非二義文法？,19,可以看出： 改寫二義文法為非二義文法（續(xù)1）, 新引入的非終結符，限制了每一步直接推導均有唯一選擇； 最終分析樹的形狀，僅與文法有關，而與推導方法無關； 非終結符的引入，增加了推導步驟（分析樹增高）； 越接近S的文法符號的優(yōu)先級越低。（如EE+T）。 對于AA，若A在終結符左邊出現(xiàn)（即終結符在中），則A產(chǎn)生式具有左結合性質。,改寫二義文法的關鍵步驟： (a)
19、引入一個新的非終結符，增加一個子結構并提高一級優(yōu)先級； (b) 遞歸非終結符在終結符左邊，運算具有左結合性，否則具有右結合性。,例3.10 改寫二義文法G3.2為G3.4 ：,E E + E （1） | E * E （2） |（E） （3） | -E （4） | id （5）,E E + T | T T T * F | F F (E) | -F | id,20,再討論“懸空else”問題 改寫二義文法為非二義文法（續(xù)2）,if-then-else和if-then：在一個復合if語句中，可能then多于else，使得else不知與哪個then結合。 一般原則是右結合，即else與
20、其左邊最靠近的then結合。 改寫文法的根據(jù)是將S分為完全匹配（MS）和不完全匹配（UMS）兩類，且在UMS中規(guī)定else右結合。,S if C then S | if C then S else S | id := E C E = E | E E E E + E | - E | id | n,S MS (1) | UMS(2) MS if C then MS else MS (3) | id := E(4) UMS if C then S(5) | if C then MS else UMS(6)(G3.5) C E = E | E E(7)...(9) E E + T | T(1
21、0)...(11) T T * F | F(12)...(13) F （E） | -F | id | n(14)...(17),21, 改寫二義文法為非二義文法（續(xù)3）,if x0 then x:=5 else x:=-5,if x0 then x:=5 else x:=-5,S MS (1) | UMS(2) MS if C then MS else MS (3) | id := E(4) UMS if C then S(5) | if C then MS else UMS(6) C E = E | E E(7)...(9) E E + T | T(10)...(11)(G3.5) T
22、 T * F | F(12)...(13) F （E） | -F | id | n(14)...(17),22, 為文法符號規(guī)定優(yōu)先級和結合性,二義文法的優(yōu)點： 比非二義文法容易理解； 分析效率高（分析樹低，直接推導步驟少）。 對于：id+id*id,為二義文法規(guī)定優(yōu)先級和結合性（YACC的方法）： %left + %left * %right - E : E + E | E * E | - E | ( E ) | id,E E + E | E * E | - E | ( E ) | id,EE+T|T TT*F|F F(E)|-F|id,23, 修改語言的語法（表現(xiàn)形式被改變）, A
23、da中用end if結束條件語句，于是有： if x0 then if x0 then x:=5; then x:=5; end if;else x:=-5; else x:=-5;end if; end if;end if;, 給表達式加括號，如Pascal中邏輯和算術運算： (a+b)(c*d),24,3.3 語言與文法簡介,文法的重要作用： 給出精確、易于理解的語言結構說明； 以文法為基礎的語言，便于加入新的、或修改、刪除舊的語言結構； 有些類別的文法，可以自動生成高效的分析器。,本節(jié)從理論的角度對文法進行簡單地討論。討論建立在形式語言與自動機的理論之上，且僅引用結論而忽略數(shù)學的證
24、明，有興趣的同學可以參閱相關文獻。 希望通過本節(jié)的討論，對文法的分類和它們在編譯器構造中的作用有一定的了解。 （證明技術.ppt：語言與問題、證明技術等簡單介紹）,25,3.3.1 正規(guī)式與上下文無關文法 正規(guī)式到CFG的轉換,推論3.1 正規(guī)式所描述的語言結構均可用CFG描述，反之不一定。 ,從正規(guī)式到CFG的對應關系：, 構造正規(guī)式的NFA； 若0為初態(tài)，則A0為開始符號； 對于move(i,a)=j，引入產(chǎn)生式AiaAj； 對于move(i,)=j，引入產(chǎn)生式 AiAj； 若i是終態(tài)，則引入產(chǎn)生式Ai 。,例3.11 從正規(guī)式r=(a|b)*abb的NFA構造CFG：,A0 aA0|
25、bA0|aA1 A1 bA2 A2 bA3 A3 ,經(jīng)驗的方法： A HT H | Ha | Hb T abb 分別產(chǎn)生abb的分析樹：,26, 為什么用正規(guī)式而不用CFG描述詞法, 詞法規(guī)則簡單，用正規(guī)式描述已足夠； 正規(guī)式的表示比CFG更直觀、簡潔、易于理解； 有限自動機的構造比下推自動機簡單，且分析效率高； 區(qū)分詞法和語法，為編譯器前端的模塊劃分提供方便。,貫穿詞法分析和語法分析始終的思想： 語言的描述和語言的識別是表示一個語言的兩個不同側面，二者缺一不可；（語言、文法、自動機） 用正規(guī)式和CFG描述的語言，對應的識別方法（自動機）不同； 一般情況下，正規(guī)式適合描述線性結構，
26、如標識符、關鍵字、注釋等； CFG適合描述具有嵌套（層次）性質的非線性結構，如不同結構的句子if-then-else、while-do等。,27,3.3.2 上下文有關語言（Context Sensitive Language, CSL）,程序設計語言中除了CFG可以描述的結構之外，還有一些是CFG無法描述的所謂上下文有關的結構。 典型的這類語言結構包括：變量的聲明與引用、過程調用時形參與實參的一致性檢查等。 描述它們的文法被稱為上下文有關文法（Context Sensitive Grammar, CSG）。,例3.12 不能用CFG描述的語言： L1=c|(a|b)*（ 標識符聲明與引
27、用一致性的抽象） L2=anbmcndm|n1和m1（形參與實參一致性的抽象） L3=anbncn|n1 （計數(shù)問題的抽象）,相近的CFL： L1=cr|(a|b)* （SaSa|bSb|c） L2=anbmcmdn|n1, m1 （SaSd|aAd AbAc|bc） L2=anbncmdm|n1, m1 （SAB AaAb|abBcBd|cd） L3=ambmcn|m, n1 （AAC AaAb|ab CcC|c）,28,計數(shù)問題,L3=anbncn|n1 CSL L3=ambmcn|m,n1 CFL（AAC AaAb|ab CcC|c）,命題：L3不是正規(guī)集，因為構造不出可以識別L3的DF
28、A。 證明：（反證） 假設L3是正規(guī)集，則可構造n個狀態(tài)的DFA D，它接受L3； 考察D讀完，a，aa，...，an，分別到達S0，S1，...，Sn，共有n+1個狀態(tài)。 根據(jù)鴿巢原理，序列中至少有兩個狀態(tài)相同，設Si=Sj（ji）， 因為aibick L3 所以存在路徑aibick。,但是D中也有路徑ajbick，矛盾。故L3不是正規(guī)集。 ,L3=akbmcn|k，m，n1 （a+b+c+ ）,29,3.3.3 形式語言與自動機簡介,定義3.8 若文法G=(N，T，P，S)的每個產(chǎn)生式中，均有(NT)*，且至少含有一個非終結符，(NT)*，則稱G為0型文法。 對0型文法施加以下第i條限
29、制，即得到i型文法。 1. G的任何產(chǎn)生式（S除外）滿足||||； 2. G的任何產(chǎn)生式形如A，其中AN，(NT)*； 3. G的任何產(chǎn)生式形如Aa或者AaB(或者ABa)，其中A，BN，aT。 ,文法、語言與自動機,30,再考察L3： 3.3.3 形式語言與自動機簡介（續(xù)）,L3=anbncn|n1 L3=ambmcn|m,n1 （AAC AaAb|ab CcC|c） L3=akbmcn|k，m，n1 （a+b+c+ ）,例3.15 L3可以用下述CSG描述： SaSBC (1) SaBC (2) CBBC (3) aBab (4) bBbb(5) bCbc(6) cCcc(7),
30、句子akbkck 的推導： S =...= ak-1S(BC)k-1 (1) = ak(BC)k (2) =...= akBkCk (3) = akbBk-1Ck (4) =...= akbkCk (5) = akbkcCk-1 (6) =...= akbkck (7),結論：CSG、CFG、正規(guī)式能力遞減（看教材） 但是：能力越強的文法，其文法的設計和自動機的構造越困難 因此：語法分析僅用到CFG（除特別指出，文法即指CFG ）,31,結 束,32,改寫二義文法：,(a) 引入一個新的非終結符，增加一個子結構并提高一級優(yōu)先級； (b) 遞歸非終結符在終結符左邊，運算具有左結合性，否則具有右結合性。,E E + E （1） | E * E （2） |（E） （3） | -E （4） | id （5）,1. 優(yōu)先級：+*( ), -, id 2. 結合性：左結合+, * 右結合- 無結合id 3. 非終結符與運算： E:+（E產(chǎn)生式，左遞歸） T:*，（T產(chǎn)生式，左遞歸） F:-,( ), id（F產(chǎn)生式，右遞歸）,E E + T | T T T * F | F F (E) | -F | id,問題： 如何看待( )？ 返回,
西安電子科技大學《編譯原理》.ppt
