1、編譯原理電子教案第二章第二章高級語言及其語法描述高級語言及其語法描述上一頁下一頁2本章的主要內容本章的主要內容 高級語言的一般特性 語法、文法和語義 上下文無關的文法 分析樹與二義性 形式語言的概況及分類上一頁下一頁3本章要求本章要求 知識點：文法和語言的形式定義，分析樹和二義性，形式語言概觀。 深刻理解：上下文無關文法，推導，語言，最左推導，最右推導，分析樹和二義性。 熟練掌握：（1）已知上下文無關文法G和句型w，構造出w的推導，最左推導，最右推導，分析樹； （2）判定上下文無關文法G是二義性的。（3）已知上下文無關文法G，求出L，使得L=L（G）； 已知上下文無關語言 L，求出 G，使得

2、L（G）=L。上一頁下一頁4本章教學線索本章教學線索1 高級語言的一般特性高級語言的一般特性 1.1 程序語言的定義 1.2 程序語言的分類 1.3 數據類型與操作 1.4 高級語言常見的語句2 字符串字符串3 文法和語言文法和語言 4 語法分析樹與二義性問題語法分析樹與二義性問題 5 文法的分類（逐漸對產生式施加限制）文法的分類（逐漸對產生式施加限制）上一頁下一頁51.1 程序語言的定義程序語言的定義 高級程序語言都可看成是一個字符集上的字符串。程序語言主要是由語法和語義兩方面定義。 語言的語法是用來形成一個合法程序的一組規則，這些規則一部分稱為詞法規則，另一部分稱為語法規則。詞法規則定義了

3、單詞符號的形成規則，而語法規則定義了語法單位的形成規則。 語法單位：表達式、語句、函數、過程和程序等。 語義規則定義了語言的意義，語義規則定義語言的單詞符號和語法單位的意義。 程序語言的語法規則是用文法來描述的，目前的程序語言一般用上下文無關的文法來描述。上一頁下一頁61.2 程序語言的分類程序語言的分類（1）強制式語言（過程式語言）：命令驅動，面向語句，一個強制式語言程序由一系列語句組成，如：FORTRAN、C、PASCAL等；（2）應用式語言（函數式語言）：注重程序的表示功能，程序的開發過程就是從前面已有的函數出發構造更復雜的函數，如：LISP。（3）基于規則的語言（邏輯設計語言）：檢查一

4、定的條件，當它滿足值，則執行適當的操作，如：Prolog。（4）面向對象的語言：封裝性、繼承性、多態性，如：C+，Java，Smalltalk。上一頁下一頁71.3 數據類型與操作數據類型與操作 一個數據類型通常包括3種要素：（1）用于區別這種類型數據對象的屬性（2）這種類型的數據對象可以具有的值（3）可以作用于這種類型的數據對象的操作 常見的數據類型：（1）數值數據（2）邏輯數據（3）字符數據（4）指針類型（5）數組（6）記錄（7）字符串、棧、隊列（8）抽象數據類型（類）上一頁下一頁81.4 高級語言常見的語句高級語言常見的語句 說明語句 賦值語句 控制語句（無條件轉移語句、條件語句、循環語

5、句、過程調用語句、返回語句）上一頁下一頁9本章教學線索本章教學線索1 高級語言的一般特性高級語言的一般特性2 字符串字符串 2.1 字母表 2.2 符號串定義、術語及運算3 文法和語言文法和語言 4 語法分析樹與二義性問題語法分析樹與二義性問題5 文法的分類（逐漸對產生式施加限制）文法的分類（逐漸對產生式施加限制） 上一頁下一頁102.1 字母表字母表 字母表是符號的非空有窮集合。任何程序語言都有自己的字母表，一個程序語言只使用一個有限字符集作為字母表。用表示。例如:計算機語言：由符號“0”和“1”組成的字母表，=0，1 ASCII字符集；Pascal字母表為： = AZ, az, 09, +

6、, -, *, /, , :, , ; ，.， , (, ), , , , 上一頁下一頁112.2 符號串定義、術語及運算符號串定義、術語及運算 符號串的定義符號串的定義 設是一個有窮字母表，它的每個元素稱為一個符號。上的一個符號串是指由中的符號所構成的一個有窮序列。(1) 空字是上的一個符號串。空字是不包含任何符號的序列不包含任何符號的序列。(2) 若x是上的符號串，而a是的元素, 則xa是上的符號串。(3) y是上的符號串,當且僅當它由(1)和(2)導出。 由字母表中的符號所組成的任何有窮序列稱之為該字母表上的符號串,也稱作“字”。*(Kleene閉包)：表示上的所有字符串的全體，也在其中

7、。表示不含任何元素的空集。例如：若=a，b，則*=，a，b ，aa，ab，ba，bb，aaa， 上一頁下一頁12 符號串的術語符號串的術語設s是符號串前綴：移走s的尾部的零個或多于零個符號后綴：刪去s的頭部的零個或多于零個符號子串：從s中刪去一個前綴和一個后綴子序列：從s中刪去零個或多于零個符號(這些符號不要求是連續的）逆轉：將S中的符號按相反次序寫出而得到的符號串。長度：是該符號串中的符號的數目。例如|aab|=3,|=0。真前綴，真后綴，真子串: xsx 例子：符號串s=banana前綴：,b,ba,ban,bana,banan,banana后綴：banana,anana,nana,ana

8、,na,a, 子串：banana,anana,banan,anan, 子序列: baa(這些符號不要求是連續的）逆轉（用SR表示）：ananab長度：banana=6上一頁下一頁13 符號串的運算符號串的運算（1）連接：設x和y是符號串，它們的連接 xy是把y的符號寫在x的符號之后得到的符號串。例如：x = ba，y = nana，xy = banana。（2）方冪：x0 = ；x1 = x；x2 = xx ；xn=xn-1x ； 例如： x = ba，x1= ba， x2=baba，x3=bababa，上一頁下一頁14 符號串集合符號串集合(語言）的運算語言）的運算設*的子集U和V是兩個符號

9、串集合，則合并：UV |U orV（或表示為：U+V）連接：UV |U and V方冪： V0=， V1V，V2VV，VnVn-1V 語言V的閉包，記作V*： V*Vi（i=0） = V0V1V2V3 語言V的正則閉包，記作V+（V+V V*） V+Vi（i =1） = V1V2V3 上一頁下一頁15本章教學線索本章教學線索1 高級語言的一般特性高級語言的一般特性2 字符串字符串3 文法和語言文法和語言 3.1 文法的定義（上下文無關的文法） 3.2 直接推導和推導的定義 3.3 最左推導與最右推導 3.4 語言的定義4 語法分析樹與二義性問題語法分析樹與二義性問題 5 文法的分類（逐漸對產生

10、式施加限制）文法的分類（逐漸對產生式施加限制）上一頁下一頁163 文法和語言文法和語言 例子：He gave me a book Hegavemebooka語法樹語法樹上一頁下一頁17語法規則語法規則 He me a gave book上一頁下一頁18 注意：其中He,me,book,gave,a等稱為終結符；、等稱為非終結符號；這種書寫形式稱為產生式。 產生式（規則，重寫規則或生成式）： Uu （或U:=u） 且UV+，uV* ，U是符號,稱為規則左部，u是有窮非空符號串，為規則右部。 非終結符號：需要進一步定義的符號，不會出現在程序中。 終結符號：不需要再定義，會出現在程序中。上一頁下一頁

11、193.1 文法的定義（上下文無關的文法）文法的定義（上下文無關的文法）一個上下文無關的文法G可以表示成一個四元式(VT，VN，S，P)，其中： VT是一個非空有限集，它的每個元素稱為終結符； VN是一個非空有限集，它的每個元素稱為非終結符，且有VTVN= S是一個非終結符，稱為開始符號； P是一個產生式集合（有限），每個產生式的形式是A，其中AVN，（VTVN）*。S至少必須在某個產生式的左部出現一次。可以將左部相同的產生式縮寫成：A1|2|3|n 上一頁下一頁20（注意：終結符號是組成語言的基本符號，比如關鍵字、標志符、常數、算符和界符等；非終結符用來代表語法范疇，比如算術表達式、賦值語句

12、、程序等；開始符號是一個特殊的非終結符，代表了我們最終有用的語法范疇。） 例2.1：一個簡單的算術表達式的文法：G = ( i，+，*，(，)，P )P： * （） i可以簡單表示為：E E+TTT T*F FF ( E ) i 上一頁下一頁21巴科斯范式（BNF：Backus-Naur Form）： “”：表示定義為，“ ”：表示或另一種表示法： := i := + * 將非終結符用括起來表示，用“:=”表示“定義為”，用“ ”表示“或”，這種方法不夠簡潔。 上一頁下一頁22令G=（VT，VN，S，P），若AP，且，（VTVN）*，則稱A直接推出，表示成A ，我們稱：A直接推出 ，反之稱直接

13、歸約到A； 如果存在一個直接推導序列： 1 2 3 n（n0），我們稱這個序列是從 1到n 的一個推導。 1 n：表示從1經過一步或若干步可以推導出n。 1 n：表示從1經過0步或若干步可以推導出n。（ 意味著=，或者 ）。3.2 直接推導和推導的定義直接推導和推導的定義+*上一頁下一頁23例：E E+T T+T F+Ti+T i+F i+i A產生式E E+TE E+T E+T T+TE T+TT+T F+TT F+TF+Ti+TF i+Ti+Ti+FT Fi+i+Fi+iF ii+上一頁下一頁243.3 最左推導與最右推導最左推導與最右推導 對于推導，如果每一步都是對中的最左非終結符最左非

14、終結符進行替換的，則我們稱這種推導為最左推導，如果每一步都是對中的最最右非終結符右非終結符進行替換的，則我們稱這種替換為最右推導。 例2-2：對于文法：EE+ E|E*E|(E)|i 我們看對于（i*i+i）的推導最左推導：E （E） （E+E） （E*E+E） （i*E+E） (i*i+E) (i*i+i)最右推導：E （E） （E+E） （E+i） （E*E+i） (E*i+i) (i*i+i) 上一頁下一頁25 例2-3:文法GS: SAB AA0|1B B0|S1 請給出句子101001的最左和最右推導。 最左推導： S AB 1B B10B 10S1 10AB1 101BB1 101

15、0B1 101001 最右推導： S AB AS1AAB1 AA01 A1B01 A1001 1B1001 101001 上一頁下一頁26 假定G是一個文法，S是它的開始符號。如果S ，則稱是一個句型。僅含終結符的句型是一個句子。文法G所產生句子的全體是一個語言，將它記為：L（G）， 則L（G）=|S & VT* 例2-4：考慮文法 G(a,b,S,S，P）其中P：SaSb abSaSb aaSbb a3Sb3 an-1Sbn-1 anbn這里文法可以表示為：L(G) = anbn|n1注意：1)句型與句子的區別和聯系 2)文法和語言之間并不存在一一對應關系，對于一給定的文法，唯一地確

16、定它所產生的語言；但對于一個給定的語言往往可用若干個不同的文法來產生。3.4 語言的定義語言的定義+*上一頁下一頁27本章教學線索本章教學線索1 高級語言的一般特性高級語言的一般特性2 字符串字符串3 文法和語言文法和語言4 語法分析樹與二義性問題語法分析樹與二義性問題 4.1 語法分析樹的定義 4.2 文法的二義性問題 4.3 壓縮過的文法（化簡了的文法）5 文法的分類（逐漸對產生式施加限制）文法的分類（逐漸對產生式施加限制）上一頁下一頁284.1 語法分析樹的定義語法分析樹的定義設G=（VT，VN，S，P），G的一棵分析樹滿足如下條件： 每一結點有一標記，此標記是VTVN中的符號。 根的標

17、記是S。 如果一個結點是內部結點，且標記A，那么A必在VN中。 如果編號為n的結點有標記A，結點n1，n2，nk是點n的從左到右的兒子，并分別有標記X1，X2，Xk，則AX1X2Xk必須是P中的產生式。 若結點n有標記，那么結點n是葉子，且是它父親唯一的兒子。 上一頁下一頁29畫語法樹的兩種方法：自頂向下：根據推導序列，對每步推導畫相應分枝自底向上：根據歸約序列，對每步歸約畫相應分枝 有關分析樹要注意的幾點： 一個句型推導或分析用一棵樹結構圖示出來，它反應了一個句子的語法結構層次。 對于一個句子的多種推導（若文法是無二義性的），采用各種推導過程，畫出的分析樹是一樣的。分析樹并未描述推導過程。

18、在書中，用畫分析樹的過程解釋語法分析過程，用分析樹圖解語法結構。分析樹是推導的圖形表示。上一頁下一頁30E（樹根）（E）E+EE*Eiii12345E（E）（E+E）（E*E+E）（i*E+E）（i*i+E）（i*i+i）對于（i*i+i）的語法分析樹上一頁下一頁314.2 文法的二義性問題文法的二義性問題 描述一個句子的文法不是唯一的； 對于一個句子的分析應是唯一的。 考慮文法：EE+ E|E*E|（E）|i， 句子 （i*i+i）推導一：E (E) (E+E) (E*E+E) (i*E+E) (i*i+E) (i*i+i)推導二：E (E) (E*E) (i*E) (i*E+E) (i*i

19、+E) (i*i+i)上一頁下一頁32推導一對應的語法樹推導二對應的語法樹E（樹根）（E）E*EE+Eiii12345E（樹根）（E）E+EE*Eiii12345上一頁下一頁33 如果一個文法的句子存在兩棵不同的分析樹，那么該句子是二義性的。如果一個文法包含二義性的句子，則稱這個文法是二義性的；否則，該文法是無二義性的。 上一頁下一頁34幾點說明：1）一般來說，程序語言要求無二義性文法，對于條件語句，經常使用二義性文法描述它：S if 條件 then 語句 if 條件 then 語句 else 語句 其它語句二義性的句子：if e1 then if e2 then s1 else s2 2）在

20、能駕馭的情況下，使用二義性文法。3）對于任意一個上下文無關文法，不存在一個算法，能夠在有限的步驟內判定它是無二義性的；但能給出一組充分條件，滿足這組充分條件的文法是無二義性的。上一頁下一頁354.3 壓縮過的文法（化簡了的文法）壓縮過的文法（化簡了的文法）1）文法中不含有任何形如 PP的產生式；2）每個非終結符號P必須都有用處。即： S P 且P ，VT* （兩層含義：一方面意味著，必須存在含P的句型，另一方面方面意味著對于P不存在永不終結的回路）*+上一頁下一頁36本章教學線索本章教學線索1 高級語言的一般特性高級語言的一般特性2 字符串字符串3 文法和語言文法和語言4 語法分析樹與二義性問

21、題語法分析樹與二義性問題 5 文法的分類（逐漸對產生式施加限制）文法的分類（逐漸對產生式施加限制） 5.1 喬姆斯基文法（Chomsky） 5.2 上下文有關的語法結構 5.3 自嵌套的文法 5.4 文法的遞歸性 5.5 文法與語言的典型題目上一頁下一頁375.1 喬姆斯基文法（Chomsky）喬姆斯基文法（Chomsky）：四種類型：0型，1型，2型，3型0型：G =（VT，VN，S，P） 規則形式： ， (VTVN)*， 推導： 例如：GS = （S，A，B，C，D，E，a，P，S），其中P由如下產生式組成：SACaB CaaaC CBDB CBE aDDa ADAC aEEa AE 上一

22、頁下一頁381型（上下文有關）：對于產生式均滿足，僅僅S除外，但S不得出現在任何產生式的右部。例如：GS = （S，A，B，C，A ，a，b，c，P，S） 其中P： SaSBA SabB BABA BA AA AA AB bAbb bBbc cBcc L（G）=aibici|i1 上一頁下一頁392型（上下文無關）：G的任何產生式為A A VN， (VN VT)* 例如：GS = （S，a，b，SaSb，Sab，S） L（G）= aibi|i13型（右線性）：G的任何產生式為A B或A ， VT*，A、BVN （左線性）：G的任何產生式為A B或A ， VT*，A、BVN3型文法等價于正規式，

23、因此又稱為正規文法。上一頁下一頁40四種文法之間的關系 由于四種文法是按照將產生式做進一步限制而定義的，所以它們之間是逐級“包含”的關系，由四種文法產生的語言也是逐級“包含”的關系。 即： 3型語言類 2型語言類 1型語言類 0型語言類注：0型語言除外，從其中刪去或往其中添加一個空串并不改變其語言類。語言層正規語言3上下文無關語言2上下文有關語言1遞歸可枚舉語言0圖靈機TM線性界限自動機LBA下推自動機PDA有窮自動機FA上一頁下一頁415.2 上下文有關的語法結構上下文有關的語法結構 現在使用的程序語言中,有些語言結構并不是總能用上下文無關文法描述的。 例例2.9 L1=wcw|wa,b+。例如,aabcaab就是L1的一個句子。這個語言是檢查程序中標識符的聲明應先于引用的抽象。 例例2.10 L2=anbmcndm|n,m0，它是檢查過程聲明的形參個數和過程引用的參數個數一致問題的抽象。 語言中過程定義