1、第二章第二章 高級語言及其語法描述高級語言及其語法描述引言：關于引言：關于形式語言形式語言2.1程序語言的定義程序語言的定義 1、詞法規則詞法規則、語法規則語法規則p12-132、語義語義P142.2高級語言的一般特性高級語言的一般特性P14-25(關于算符的優先順序關于算符的優先順序p23、名字的左值和右值名字的左值和右值p24）2.3 程序語言的語法描述程序語言的語法描述p252.3 程序語言的語法描述程序語言的語法描述一、符號和符號串一、符號和符號串字母表字母表：字母表：字母表是符號元素的是符號元素的非空非空集合。集合。符號符號：字母表中的元素。：字母表中的元素。 符號串符號串：字母表中

2、的符號所組成的任何：字母表中的符號所組成的任何有窮有窮序列。序列。 例如，若有字母表例如，若有字母表=a,b則則a，b是字母表是字母表中的元素中的元素(符號符號)；a，b，aa，ab，ba都是符號串。都是符號串。注意：符號串中注意：符號串中的符號與順序有的符號與順序有關，關，ab和和ba是不是不同的符號串同的符號串特別定義特別定義:空符號串空符號串不含任何符號的符號串，不含任何符號的符號串，用用 表示。表示。 設有字母表設有字母表=az, AZ,09, 各種運算符和其它特殊各種運算符和其它特殊符號，符號，則，由這些字母表中的元素則，由這些字母表中的元素(符號符號)可以組成不同可以組成不同的符號

3、串：的符號串：Program example;Var sum,I: integer;Begin Sum := 0;For I:=1 to 10 do sum:=sum+I;12345:=sum;End.Write(sum=,sum);A=符號串的運算符號串的運算：符號串的連接（聯結、乘積）符號串的連接（聯結、乘積）：符號串：符號串x和和y的連接是指的連接是指x和和y的符號按先后順序排列在一起組成一個新的符號串，的符號按先后順序排列在一起組成一個新的符號串，用用xy表示。表示。 例，若字母表例，若字母表=a,b，符號串符號串x=ab，y=ba則則xy=abba符號串的長度符號串的長度：符號串中符

4、號的個數為符號串的長度。：符號串中符號的個數為符號串的長度。 注意注意: (1)連接運算不滿足交換律，即連接運算不滿足交換律，即xyyx (2)任何符號串任何符號串x與空串與空串的連接都等于的連接都等于x，即即： x=x=x。 若若ab是符號串，則是符號串，則|ab|表示符號串的長度。表示符號串的長度。 |ab|=2同理：同理：|aabb|=4 注意：特別規定注意：特別規定 |=0。若有兩個符號串若有兩個符號串x=ab,y=cde那么，那么，|xy|=?5符號串的前綴與后綴符號串的前綴與后綴(頭和尾頭和尾)：若有符號串若有符號串 z=xy(x,y是符是符號串號串),我們稱我們稱x為為z的前綴的

5、前綴，y為為z的后綴。的后綴。例例z=abcd則：則：z的頭有，的頭有， , a , ab , abc , abcd z的尾有，的尾有， ,d , cd , bcd , abcd符號串的冪運算符號串的冪運算：設設X是一個符號串，則：是一個符號串，則： X0=，X1=X，X2=XX，Xn=XX=Xn例：若有符號串例：若有符號串x=ab，則：則：x0= ,x1= ab,x2= abab,x3= ababab顯然，若顯然，若n0,則則Xn=XXn-1 =Xn-1X。 即：符號串的冪運算服從結合律即：符號串的冪運算服從結合律 符號串符號串集合集合的運算的運算：符號串集合的乘積運算：符號串集合的乘積運算

6、：設設A、B為符號串集合（集合為符號串集合（集合中各元素都是字母表上的字符串），兩個字符串集合中各元素都是字母表上的字符串），兩個字符串集合的乘積定義為：的乘積定義為：AB=xy|xA , yB（笛卡兒乘積）笛卡兒乘積）設有字母表設有字母表=a,b,c,d，令令A=aa,bb，B=cc,dd則則AB=aacc,aadd,bbcc,bbdd， BA=ccaa,ccbb,ddaa,ddbb。顯然顯然 AB BA，即符號串集合乘積不滿足交換律即符號串集合乘積不滿足交換律。注意：因注意：因x = x=x故，故， A=AA=A=A =A 特別定義：空符號串集合：特別定義：空符號串集合： 空集合：空集合：

7、= A = A= 符號串集合的冪運算：符號串集合的冪運算：設設A為符號串集合，則集合的冪為符號串集合，則集合的冪運算定義如下運算定義如下:A0=A1=AA2=AAAn=AAAn個個=AAn-1=An-1A符號串集合的閉包：符號串集合的閉包：設設A為符號串集合，則集合的閉包為符號串集合，則集合的閉包定義如下定義如下:A的的正閉包正閉包： A+=A1A2A的的閉包：閉包： A*=A0A1A2設集合設集合A=a,b，則則 A+=a,b,aa,ab,ba,bb,aaa, A*=,a,b,aa,ab,ba,bb,aaa, 顯然：顯然： A*=A0A+ A+=AA*二、上下文無關二、上下文無關文法文法 (

8、p26)文法文法(Grammar):是描述語言的語法結構的形式是描述語言的語法結構的形式規則（即語法規則）。規則（即語法規則）。The big monkey ate a banana.規則規則：規則又叫：規則又叫產生式產生式(production rule)，它是，它是語法單位結構的一種表示，它引入了符號語法單位結構的一種表示，它引入了符號“:=:=”或或“”表示表示“由由組成組成”，上述句子的結構，上述句子的結構可以表示如下：可以表示如下： the big ate a monkey banana句子的推導句子的推導：用規則：用規則(產生式產生式)按一定方式去推導按一定方式去推導或產生句子的過

9、程。或產生句子的過程。 the big ate a monkey banana The The big The big monkey The big monkey The big monkey ate The big monkey ate The big monkey ate a The big monkey ate a banana The big monkey ate a banana語法樹語法樹(Parse Tree):句子結構的圖形表示方式句子結構的圖形表示方式monkeybigTheatebananaa歸納：什么是文法歸納：什么是文法 the big ate a monkey ban

10、ana三、文法和語言的形式定義三、文法和語言的形式定義定義定義2 文法文法是一個四元組：是一個四元組：GS=(VN, VT, P, S)其中：其中：VN為非終結符集合；為非終結符集合； VT為終結符集合；為終結符集合； VNVT =，一般令一般令 V= VNVT ，V中的符號稱為文法符號；中的符號稱為文法符號；(V字匯表）字匯表）P為產生式集合；為產生式集合； P中的每個產生式寫為：中的每個產生式寫為：或或 =。S為開始符號為開始符號(或稱根符號，識別符號或稱根符號，識別符號)。定義定義1 產生式產生式(或規則或規則)是一有序對是一有序對(A, )，通常寫為：，通常寫為： A 或或A = 其中

11、其中A是一個符號作為產生式左部，是一個符號作為產生式左部， 為有窮符號串作為產為有窮符號串作為產生式的右部，生式的右部，“ ”或或“ =”表示表示“定義為定義為”或或“由由組組成成”。另外：另外：GS也可簡寫為也可簡寫為G 在規則左部出現的在規則左部出現的符號稱為非終結符，符號稱為非終結符，它們的全體形成它們的全體形成VN在規則中只在右部在規則中只在右部出現的符號稱為終出現的符號稱為終結符，它們的全體結符，它們的全體形成形成VT例例 G1 =(N,0，1,N0N,N1N,N0,N1,N） 其中其中: 非終結符非終結符 VN =N終結符終結符VT =0，1V=N，0，1 P=N0N，N1N，N0

12、，N1開始符號開始符號S 為為N通常情況下，文法只用產生式集合表示：通常情況下，文法只用產生式集合表示：G1N: N0N N1N N0 N1定義定義3 符號串的符號串的推導與歸約推導與歸約：已給文法：已給文法G=(VN,VT,P,S)， V= VNVT，令令x,y,V* ，且且P，此時，由符號此時，由符號串串xy能夠直接產生出符號串能夠直接產生出符號串xy，我們稱：我們稱：符號串符號串xy是符號串是符號串xy的的直接推導直接推導；符號串符號串xy是符號串是符號串xy的的直接歸約直接歸約；記作記作: xy xy 對于上例中文法：對于上例中文法：G1N: N0N N1N N0 N1存在以下直接推導

13、：存在以下直接推導： N 1N 11xyxyx yx y若有若有1，2，nV* 且且1 2 ，n-1 n則稱則稱n是是1的推導的推導記作：記作： 1+n特別約定：若在推導關系特別約定：若在推導關系1n中允許中允許1=n，+則稱則稱n是是1 的廣義推導記作的廣義推導記作 1*nN +11N *N引用引用巴科斯范式巴科斯范式(BNF)表示文法：表示文法：對于具有相同左部的那些產生式，如：對于具有相同左部的那些產生式，如：Ux, Uy, Uz可以縮寫為：可以縮寫為：Ux|y|z (“|”可理解為可理解為“或或”)(1) (2) (3) (4) 0(5) 1(6) 2(7) 3(8) 4(9) 5(1

14、0) 6(11) 7(12) 8(13) 9(1) (2) |(3) 0 |1 |2 |3 |4 |5 |6 |7 |8 |9|用此文法和直接推導的定義可以用此文法和直接推導的定義可以推導出任一無符號整數推導出任一無符號整數(56) 5 56可表示為可表示為:+56 V*，則稱則稱為文法為文法G的句型的句型 VT*，則稱則稱為文法為文法G的句子的句子 文法文法G所對應的語言，記作所對應的語言，記作L(G)=|VT*，且且S+例例:前面提到的文法前面提到的文法G = VN，VT，P，無符號整數無符號整數其中，其中，VT =0，1，2，3，4，5，6，7，8，9 VN =無符號整數，數字串，數字無

15、符號整數，數字串，數字 P： 0123456789 5 56 試給出該文法的試給出該文法的句型、句子舉例，句型、句子舉例，并說明它所確定并說明它所確定的語言。的語言。由此我們可以看出，文法和語言是密切相關的，根據文由此我們可以看出，文法和語言是密切相關的，根據文法可以推導出任一句型和句子，而所有句子的集合則為法可以推導出任一句型和句子，而所有句子的集合則為該文法所對應的語言，即該文法所對應的語言，即語言是所有句子構成的集合，語言是所有句子構成的集合，它是所有終結符號串所組成的集合它是所有終結符號串所組成的集合VT*的子集的子集：L(G) VT*定義定義4 句型和句子句型和句子:設設G=(VN,

16、VT,P,S)是一文法，若是一文法，若 S *那么，句型和句子的那么，句型和句子的區別是什么區別是什么?定義定義5 規范推導規范推導(歸約歸約):對于直接推導對于直接推導xy xy，如果如果y只只包含終結符號包含終結符號或為空符號串，那么就把這種直接推導稱或為空符號串，那么就把這種直接推導稱為規范為規范(最右最右)推導，跟其對應的歸約稱為規范推導，跟其對應的歸約稱為規范(最左最左)歸約，歸約，且記作：且記作：xy rxy下面的推導是否規范推導下面的推導是否規范推導： 5 56 6 6 56若推導：若推導：1+n中的每一步直接推導都中的每一步直接推導都是規范的，那么我們就是規范的，那么我們就把推

17、導：把推導：1+n稱為是規范的，且記作：稱為是規范的，且記作：1n+r+r56每次對符號串最右非終結每次對符號串最右非終結符號進行替換符號進行替換例例 文法文法GE : EE+E | E*E | (E) | i 給出句子給出句子i*i+ i的最右及最左推導的最右及最左推導 。例例2.1 p30例例2.2例例2.3同樣，可給出最左推導的定義。同樣，可給出最左推導的定義。p30-31形式語言理論可以證明以下兩點：形式語言理論可以證明以下兩點：(1)給定一個文法給定一個文法G，就可以從結構上唯一地確定其語言：就可以從結構上唯一地確定其語言：GL(G)(2)給定一種語言給定一種語言L，能確定其文法，但

18、這種文法可能不能確定其文法，但這種文法可能不是唯一的：是唯一的：LG1或或G2例例1：有文法：有文法GZ: (1)ZaZb (2)Z ab它確定的語言是什么？它確定的語言是什么？用用BNF表示：表示： Z aZb|ab由產生式由產生式(2)知：知： zab 故故ab是文法的一個句子是文法的一個句子用產生式用產生式(1)(2)：zaZba2b2 故故a2b2是文法的一個句子是文法的一個句子反復使用產生式反復使用產生式(1)： zaZba2Zb2 an-1Zbn-1 anbn所以，文法所確定的語言為：所以，文法所確定的語言為：L(GZ)=anbn | n 1例例2：已知語言為：已知語言為 L(G)

19、=abna | n 1 試給出其文法。試給出其文法。G1Z: Z aBa B bB|bG2Z: Z aBa B Bb|b定義定義6 等價文法等價文法：如果：如果L(G1)=L(G2) ，那么稱那么稱G1和和G2為等價文法。為等價文法。定義定義7 遞歸產生式和遞歸文法遞歸產生式和遞歸文法：設給定文法：設給定文法G=(VN,VT,P,S) 若若x=且且y,則稱產生式則稱產生式A是是左遞歸產生式左遞歸產生式；若若x且且y=,則稱產生式則稱產生式A是是右遞歸產生式右遞歸產生式。B BbB bB(1)若存在產生式若存在產生式AP 且有且有 A xAy成立，則稱產成立，則稱產生式生式A是遞歸產生式；是遞歸

20、產生式； *若若具有具有xAy形式形式,則稱產生式則稱產生式A是是直接遞歸產生式直接遞歸產生式。(2)遞歸文法：遞歸文法： 若文法中至少存在一條直接遞歸產生式則稱該文法是若文法中至少存在一條直接遞歸產生式則稱該文法是直接遞歸的文法直接遞歸的文法；否則；否則 若有若有A +xAy ，或，或A +Ay ，或，或A +xA則稱文法為則稱文法為間接遞歸的文法間接遞歸的文法。可見，對于文法中任一非終結符號，若能建立一個推導可見，對于文法中任一非終結符號，若能建立一個推導過程，在推導所得的符號串中又出現了該非終結符號本過程，在推導所得的符號串中又出現了該非終結符號本身，則文法是遞歸的。身，則文法是遞歸的。

21、應當注意，一般的文法都是遞歸應當注意，一般的文法都是遞歸的的，文法，文法G只有遞歸定義，只有遞歸定義，L(G)中句子才是無窮的中句子才是無窮的 例：有文法例：有文法GS: S aB|bB B a|b是否是遞歸文法，確定什是否是遞歸文法，確定什么語言？么語言？非遞歸非遞歸文法，文法，L(GS)=aa,ab,ba,bb例：有文法例：有文法G(1) (2) |(3) 0 |1 |2 |3 |4 |5 |6 |7 |8 |9|該文法中有直接左遞歸產生式：該文法中有直接左遞歸產生式： 所以是遞歸文法。所以是遞歸文法。它是否為遞歸文法，確定的語言是什么？它是否為遞歸文法，確定的語言是什么？所確定的語言為：

22、所有無符號整數。所確定的語言為：所有無符號整數。L(G)=VT+若不用遞歸規則表示文法，就要用到無窮多條產生式：若不用遞歸規則表示文法，就要用到無窮多條產生式： | | |總之，總之，使用遞歸文法，可用有窮的產生式來描述無窮使用遞歸文法，可用有窮的產生式來描述無窮的語言的語言，反之，一個語言若是無窮的，則描述語言的，反之，一個語言若是無窮的，則描述語言的文法必定是遞歸的。文法必定是遞歸的。(程序設計語言一般是無窮的程序設計語言一般是無窮的)。 課堂練習課堂練習（見教案）（見教案）定義定義8 短語、簡單短語和句柄短語、簡單短語和句柄：設文法：設文法 G=(VN,VT,P,S) ， 且且 U VN

23、，x,y,u V*(1)若有若有SxUy*+xuy，則則u稱為句型稱為句型xuy的相對于的相對于U的的短語短語 ；(2)若有若有SxUy* xuy，則則u稱為句型稱為句型xuy的相對于的相對于U的的簡單簡單(直接直接)短語短語； 例例：有文法：有文法G(1) (2) |(3) 0 |1 |2 |3 |4 |5 |6 |7 |8 |9|因有：因有： *+6xyUyxuU= u= 6x,y= 6是句型是句型6相對于相對于的短語的短語(3)任一句型的任一句型的最左簡單短語最左簡單短語稱為該句型的稱為該句型的句柄句柄.因有：因有： *66是句型是句型6相對于相對于的短語，且為的短語，且為簡單短語簡單短

24、語xUyxyu說明：當句型有兩個以上的簡單短語同時存在時，說明：當句型有兩個以上的簡單短語同時存在時，我們把位于最左邊的那個簡單短語稱為我們把位于最左邊的那個簡單短語稱為“最左簡最左簡單短語單短語”，即該句型的句柄；若句型只有一個簡，即該句型的句柄；若句型只有一個簡單短語，那么，它就是最左簡單短語，即句柄。單短語，那么，它就是最左簡單短語，即句柄。例例1：在：在“6”中，中，6是句型是句型6中唯中唯一的一個簡單短語，所以它是句柄一的一個簡單短語，所以它是句柄.例例2：在：在“ 78”中，中， 、7和和8都是是句型簡單短語，所以位于左邊的都是是句型簡單短語，所以位于左邊的 是句是句柄柄.注意：可

25、從語法樹的角度理解短語和句柄。注意：可從語法樹的角度理解短語和句柄。p31例例：有文法：有文法G(1) (2) |(3) 0 |1 |2 |3 |4 |5 |6 |7 |8 |9|2.4語法樹和文法的二義性語法樹和文法的二義性語法樹語法樹: 設文法設文法G=(VN,VT,P,S) ，所謂語法樹是一張圖，這所謂語法樹是一張圖，這張圖表示一個句型的推導過程。語法樹結構是一棵倒立的張圖表示一個句型的推導過程。語法樹結構是一棵倒立的樹結構，其中，結點的名字樹結構，其中，結點的名字NV，根結點的名字根結點的名字S是文法是文法G的開始符號，樹中的中間結點是句型推導過程中使用的的開始符號，樹中的中間結點是句

26、型推導過程中使用的非終結符非終結符 ，樹的端末結點自左向右排列就是所給句型。，樹的端末結點自左向右排列就是所給句型。例例2.7 文法文法GE: EE+TT TT*FF FEi 句型句型E+F*i對應的語對應的語法樹如右圖所示：法樹如右圖所示： EE T+T *F F i可以看出，語法樹的生成過程直觀的給出了句型的推導過程。可以看出，語法樹的生成過程直觀的給出了句型的推導過程。子樹子樹：由語法樹的某個結點：由語法樹的某個結點(子樹的根子樹的根)連同它下面發出的連同它下面發出的部分組成語法樹的子樹。只含有單層分支的子樹為簡單子部分組成語法樹的子樹。只含有單層分支的子樹為簡單子樹。樹。EE T+T

27、*F F i子樹與短語子樹與短語：在句型所對：在句型所對應的語法樹中，若某些符應的語法樹中，若某些符號按從左到右的順序組成號按從左到右的順序組成某棵子樹的末端結點，那某棵子樹的末端結點，那么由這些末端結點所組成么由這些末端結點所組成的符號串是相對于子樹根的符號串是相對于子樹根結點的短語。結點的短語。例如：例如：F是句型相對于是句型相對于T的短語，且為簡單短語的短語，且為簡單短語; i是句型相對于是句型相對于F的短語，且為簡單短語的短語，且為簡單短語; F*i 是句型相對于是句型相對于T的短語的短語; E+F*i是句型相對于是句型相對于E的短語的短語.補充補充2個例子（教案個例子（教案P30-3

28、1）原則上語法樹有多原則上語法樹有多少棵子樹，就有多少棵子樹，就有多少個短語少個短語哪個是句柄？哪個是句柄？文法的二義性文法的二義性：若一個文法存在某個句子對應兩棵不同的：若一個文法存在某個句子對應兩棵不同的語法樹，則稱此文法是二義性文法，運用文法描述程序設語法樹，則稱此文法是二義性文法，運用文法描述程序設計語言的語句成份，一般希望所給文法是非二義文法，但計語言的語句成份，一般希望所給文法是非二義文法，但是，有時候采用二義性文法比非二義文法要簡單的多，所是，有時候采用二義性文法比非二義文法要簡單的多，所以，經常用二義性文法描述程序設計語言。以，經常用二義性文法描述程序設計語言。 例例1： 文法

29、文法GE : EE+E | E*E | (E) | i 試為符號串試為符號串E*E+i構造語法樹構造語法樹. EEE+EE*iEEE*EE+i先乘后加先乘后加先加后乘先加后乘所以文法是二義性的。在進行語法分析時通所以文法是二義性的。在進行語法分析時通過人工干預過人工干預(規定算符的優先級規定算符的優先級)，確定歸約，確定歸約(分析分析)順序順序 例例2：if 語句語句(1)(2)(3)2.5文法的分類文法的分類 按照文法中產生式的不同情況，按照文法中產生式的不同情況，Chomsky把文法分把文法分成四種類型，四種類型的文法對應著四種類型的語言。成四種類型，四種類型的文法對應著四種類型的語言。0

30、型文法型文法： 產生式形式為產生式形式為: u v 且且 u V+ v V* u中應至少含有一個非終結符號，這種文法又叫短語文中應至少含有一個非終結符號，這種文法又叫短語文法，它所確定的語言稱為法，它所確定的語言稱為0型語言。型語言。1型文法型文法: 產生式形式為產生式形式為 xUy xuy 且且 U VN u V+ x,y V* 則稱該文法為則稱該文法為1型文法，也稱為上下文敏感文法或上下文有型文法，也稱為上下文敏感文法或上下文有關文法。關文法。 即只有在即只有在U的左部為符號串的左部為符號串x而右部為符號串而右部為符號串y時，才允時，才允許把非終結符許把非終結符U用符號串用符號串u來代替，

31、即來代替，即U必須在上下文必須在上下文xy中中才行。這種文法所對應的語言為才行。這種文法所對應的語言為1型語言。型語言。2型文法型文法: 產生式形式為產生式形式為 U u 且且 U VN u V* 則稱該文法為則稱該文法為2型文法，也稱為上下文無關文法。型文法，也稱為上下文無關文法。2型型文法所確定的語言為文法所確定的語言為2型語言，大部分程序設計語言都是型語言，大部分程序設計語言都是2型語言。型語言。例例: 文法文法G =（S，a,b，SaSb, Sab，S）3型文法型文法: 產生式形式為產生式形式為 UxV|yxV|y 或或 U U Vx|yVx|y 且且 U,V VU,V VN N，x,yVx,yVT T+ + 則稱該文法為則稱該文法為3型文法，也稱線性文法、型文法，也稱線性文法、正則文法或正正則文法或正規文法規文法。這種文法所對應