編譯原理第二章

1、第二章第二章 高級(jí)語言及其語法描述高級(jí)語言及其語法描述 n常用的高級(jí)語言常用的高級(jí)語言 FORTRANFORTRAN數(shù)值計(jì)算數(shù)值計(jì)算 COBOLCOBOL事務(wù)處理事務(wù)處理 PASCALPASCAL結(jié)構(gòu)程序設(shè)計(jì)結(jié)構(gòu)程序設(shè)計(jì) ADAADA大型程序、嵌入式實(shí)時(shí)系統(tǒng)大型程序、嵌入式實(shí)時(shí)系統(tǒng) PROLOGPROLOG邏輯程序設(shè)計(jì)邏輯程序設(shè)計(jì) ALGOLALGOL算法語言算法語言 C/C+C/C+系統(tǒng)程序設(shè)計(jì)系統(tǒng)程序設(shè)計(jì) JavaJavaInternetInternet程序設(shè)計(jì)程序設(shè)計(jì)n與機(jī)器語言或匯編語言比較與機(jī)器語言或匯編語言比較，高級(jí)語言高級(jí)語言的優(yōu)點(diǎn)：的優(yōu)點(diǎn)：較接近于數(shù)學(xué)語言和工程語言較接近于數(shù)學(xué)

2、語言和工程語言，比較直觀、比較直觀、自然和易于理解自然和易于理解; ;便于驗(yàn)證其正確性便于驗(yàn)證其正確性，易于改錯(cuò)易于改錯(cuò); ;編寫效率高編寫效率高; ;易于移植易于移植. .2.3 2.3 程序語言的語法描述程序語言的語法描述 n幾個(gè)概念幾個(gè)概念: :考慮一個(gè)考慮一個(gè)有窮有窮 字母表字母表 字符集字符集其中每一個(gè)元素稱為一個(gè)其中每一個(gè)元素稱為一個(gè)字符字符上的上的字字( (也叫也叫字符串字符串) ) 是指由是指由中的字符所構(gòu)中的字符所構(gòu)成的一個(gè)有窮序列成的一個(gè)有窮序列不包含任何字符的序列稱為不包含任何字符的序列稱為空字空字，記為，記為用用* *表示表示上的所有字的全體上的所有字的全體, ,包含空

3、字包含空字例如例如: : 設(shè)設(shè) =a=a， bb，則，則 * *=,a,b,aa,ab,ba,bb,aaa,.=,a,b,aa,ab,ba,bb,aaa,.n表示不含任何元素的空集。表示不含任何元素的空集。n、和和區(qū)別：區(qū)別： 是一個(gè)空字，是集合中的一個(gè)元素；是一個(gè)空字，是集合中的一個(gè)元素； 是一個(gè)空集合，即是一個(gè)空集合，即 ； 是一個(gè)有一個(gè)元素的集合。是一個(gè)有一個(gè)元素的集合。n*的子集的子集U和和V的的連接連接（積積）定義為）定義為UV | U & V n設(shè)：設(shè)：U a, aa V b, bb n那么：那么：UV= ab, abb, aab, aabb nV自身的自身的 n次積記為次

4、積記為Vn=VV Vn規(guī)定規(guī)定V0= ，令，令 V*=V0V1V2V3 稱稱V*是是V的的閉包閉包;n記記 V+VV* ，稱，稱V+是是V的正規(guī)閉包。的正規(guī)閉包。n設(shè)：設(shè)：U a, aa n那么：那么： U* = , a, aa, aaa, aaaa, U = a, aa, aaa, aaaa, 2.3.1 2.3.1 上下文無關(guān)文法上下文無關(guān)文法n文法文法： 描述語言的語法結(jié)構(gòu)的形式規(guī)則描述語言的語法結(jié)構(gòu)的形式規(guī)則nHe gave me a book. He He me me book book a a gave gave He me book a gave He He He gave He

5、 gave He gave me He gave me He gave me a He gave me a bookn一個(gè)上下文無關(guān)文法一個(gè)上下文無關(guān)文法G包括四個(gè)部分包括四個(gè)部分n一組終結(jié)符號(hào)：組成語言的基本符號(hào)一組終結(jié)符號(hào)：組成語言的基本符號(hào)n一組非終結(jié)符號(hào)：代表語法范疇一組非終結(jié)符號(hào)：代表語法范疇n一個(gè)開始符號(hào)：特殊的非終結(jié)符號(hào)一個(gè)開始符號(hào)：特殊的非終結(jié)符號(hào)n一組產(chǎn)生式：語法范疇的一種書寫規(guī)則一組產(chǎn)生式：語法范疇的一種書寫規(guī)則 如：如： An上下文無關(guān)文法的定義：上下文無關(guān)文法的定義： 一個(gè)上下文無關(guān)文法一個(gè)上下文無關(guān)文法G G是一個(gè)四元式是一個(gè)四元式 G=(VG=(VT T，V VN

6、N，S S，P)P)，其中，其中V VT T：終結(jié)符集合：終結(jié)符集合( (非空非空) )V VN N：非終結(jié)符集合：非終結(jié)符集合( (非空非空) )，且，且V VT T V VN N= =S S：文法的開始符號(hào)，：文法的開始符號(hào)，S S V VN NP P：產(chǎn)生式集合：產(chǎn)生式集合( (有限有限) )，每個(gè)產(chǎn)生式形式為，每個(gè)產(chǎn)生式形式為P P， P P V VN N， ( (V VT T V VN N) )* *開始符開始符S S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。一次。n例，變量例，變量E E是一個(gè)算術(shù)表達(dá)式；若是一個(gè)算術(shù)表達(dá)式；若E E1 1和和E E2 2是算

7、術(shù)表達(dá)式，則是算術(shù)表達(dá)式，則E E1 1+E+E2 2、E E1 1* *E E2 2和（和（E E）也是算術(shù)表達(dá)式。也是算術(shù)表達(dá)式。 定義只含定義只含+ +，* *的算術(shù)表達(dá)式的文法的算術(shù)表達(dá)式的文法 G=iG=P， 其中，其中，P P由下列產(chǎn)生式組成：由下列產(chǎn)生式組成：E E i iE E E+E E+EE E E E* *E EE E (E) (E)n幾點(diǎn)規(guī)定：幾點(diǎn)規(guī)定：“ “ ” ”也可以用也可以用“:=:=表示，表示， 這種表示稱為這種表示稱為巴科斯范式巴科斯范式(BNF)(BNF) P P1 1 P P2 2 可縮寫為可縮寫為 P P1 1| | 2 2| | | n n P Pn

8、 n 其中，其中，“|”|”讀成讀成“或或”，稱為，稱為P P的一個(gè)候選式。的一個(gè)候選式。表示一個(gè)文法時(shí)，通常只給出開始符號(hào)和產(chǎn)生式，表示一個(gè)文法時(shí)，通常只給出開始符號(hào)和產(chǎn)生式，如上例，可表示為：如上例，可表示為：G(E)G(E)： E E i | E+E | E i | E+E | E* *E | (E)E | (E)n例，例，G=iG=P，E E i iE E E+E E+EE E E E* *E EE E (E) (E)n定義：稱定義：稱 A A 直接推出直接推出，即，即 A A 僅當(dāng)僅當(dāng)A A 是一個(gè)產(chǎn)生式，是一個(gè)產(chǎn)生式， 且且 ， ( (V VT T V VN N) )* * 。n如

9、果如果 1 1 2 2 n n，則我們稱這個(gè)，則我們稱這個(gè)序列是從序列是從 1 1到到 n n的一個(gè)的一個(gè)推導(dǎo)推導(dǎo)。若存在一個(gè)。若存在一個(gè)從從 1 1到到 n n的推導(dǎo)，則稱的推導(dǎo)，則稱 1 1可以可以推導(dǎo)推導(dǎo)出出 n n 。n例，對(duì)文法例，對(duì)文法G(E)G(E)：E Ei | E+E | Ei | E+E | E* *E |(E)E |(E)E E (E)(E)( (E+EE+E) )(i(i+E+E) )(i(i+i+i) )n通常，用通常，用 表示：從表示：從 1 1出發(fā)，經(jīng)過出發(fā)，經(jīng)過一步或若干步，可以推出一步或若干步，可以推出 n n。1n 用用 表示：從表示：從 1 1出發(fā)，經(jīng)過出

10、發(fā)，經(jīng)過0 0步或步或若干步，可以推出若干步，可以推出 n n。 所以所以 ： 即即 或或+ +1n* * *+ +S*()|&TL GSVq定義：假定定義：假定G G是一個(gè)文法，是一個(gè)文法，S S 是它的開始符號(hào)。是它的開始符號(hào)。如果如果 ，則，則 稱是一個(gè)稱是一個(gè)句型句型。 僅含終結(jié)符號(hào)的句型是一個(gè)僅含終結(jié)符號(hào)的句型是一個(gè)句子句子。文法。文法G G所所產(chǎn)生的句子的全體是一個(gè)產(chǎn)生的句子的全體是一個(gè)語言語言，將它記為，將它記為 L(G)L(G)。* *+ +n例：證明例：證明 (i(i* *i+i)i+i)是文法是文法G(E)G(E)： E E i | E+E | E i | E+E

11、| E* *E | (E)E | (E)的一個(gè)句子。的一個(gè)句子。 證明：證明：E E (E)(E)( (E+EE+E) )( (E E* *E+EE+E) ) (i(i* *E+EE+E) )(i(i* *i+Ei+E) ) (i(i* *i+ii+i) )q例：文法例：文法G G1 1(A)(A)：A A c|Ab c|Ab 定義定義的語言的語言? ?A A c cA A Ab Ab cbcbA A Ab Ab Abb Abb cbbcbbA A Ab Ab Abb Abb Abbb Abbb cbbbcbbb所以所以 L(G L(G1 1)=c)=c，cbcb，cbbcbb，cbbbcbb

12、b， 以以c c開頭，后繼若干個(gè)開頭，后繼若干個(gè)b bn例：文法例：文法G G2 2(S)(S)：S S AB ABA A aA|a aA|aB B bB|b bB|bG G2 2(S)(S)的語言的語言? ?L(GL(G2 2)=a)=am mb bn n|m|m，n0n0q例：給出產(chǎn)生語言為例：給出產(chǎn)生語言為aan nb bn n|n|n 1 1 的文法。的文法。 G G3 3(S)(S)： S S aSb aSb S S ab abn從一個(gè)句型到另一個(gè)句型的推導(dǎo)往往不從一個(gè)句型到另一個(gè)句型的推導(dǎo)往往不唯一。唯一。 E+E E+E i+E i+E i i+i +i E+E E+E E+i

13、E+i i i+i+in最左推導(dǎo)最左推導(dǎo)：任何一步：任何一步 都是對(duì)都是對(duì) 中的中的最左非終結(jié)符進(jìn)行替換。最左非終結(jié)符進(jìn)行替換。例，例，G(E)G(E)：E E i | E+E | E i | E+E | E* *E |(E)E |(E)的一個(gè)句子的一個(gè)句子(i(i* *i+ii+i) ) 。E E (E)(E) ( (E+EE+E) ) ( (E E* *E+EE+E) ) (i(i* *E+EE+E) ) (i(i* *i+Ei+E) ) (i(i* *i+ii+i) )n最右推導(dǎo)最右推導(dǎo)：任何一步：任何一步 都是對(duì)都是對(duì) 中中的最右非終結(jié)符進(jìn)行替換。的最右非終結(jié)符進(jìn)行替換。例，例，G(E

14、)G(E)：E E i | E+E | E i | E+E | E* *E |(E)E |(E)的一個(gè)句子的一個(gè)句子(i(i* *i+ii+i) ) 。E E (E)(E) ( (E+EE+E) ) ( (E+iE+i) ) (E(E* *E+iE+i) ) (E(E* *i+ii+i) ) (i(i* *i+ii+i) )2.3.2 2.3.2 語法樹與二義性語法樹與二義性n用一張圖表示一個(gè)句型的推導(dǎo)用一張圖表示一個(gè)句型的推導(dǎo), ,稱為語法樹。稱為語法樹。 E i + * ( ) E i i E E E E （ E E ）E EE E (E)(E) ( (E+EE+E) ) ( (E E*

15、*E+EE+E) ) (i(i* *E+EE+E) ) (i(i* *i+Ei+E) ) (i(i* *i+ii+i) )E E + + E EE E * * E Ei ii ii in如果使用最左如果使用最左( (右右) )推導(dǎo)，則一個(gè)最左推導(dǎo)，則一個(gè)最左( (右右) )推導(dǎo)與語法樹一一對(duì)應(yīng)的。推導(dǎo)與語法樹一一對(duì)應(yīng)的。（ E E ）E EE E (E)(E) ( (E+EE+E) ) ( (E E* *E+EE+E) ) (i(i* *E+EE+E) ) (i(i* *i+Ei+E) ) (i(i* *i+ii+i) )E E + + E EE E * * E Ei ii ii iE E (

16、E)(E) ( (E+EE+E) ) ( (E+iE+i) ) (E(E* *E+iE+i) ) (E(E* *i+ii+i) ) (i(i* *i+ii+i) )n如果使用最左如果使用最左( (右右) )推導(dǎo)，則一個(gè)最左推導(dǎo)，則一個(gè)最左( (右右) )推導(dǎo)與語法樹一一對(duì)應(yīng)的。推導(dǎo)與語法樹一一對(duì)應(yīng)的。 一棵語法樹是不同推導(dǎo)過程的共性抽象。一棵語法樹是不同推導(dǎo)過程的共性抽象。n一個(gè)句型是否只對(duì)應(yīng)唯一一棵語法樹？一個(gè)句型是否只對(duì)應(yīng)唯一一棵語法樹？（ E E ）E EE E (E)(E) ( (E E* *E E) ) ( (i i* *E E) ) (i(i* *E+EE+E) ) (i(i* *

17、i+Ei+E) ) (i(i* *i+ii+i) )E E * * E EE E + + E Ei ii ii in一個(gè)句型是否只對(duì)應(yīng)唯一一棵語法樹？一個(gè)句型是否只對(duì)應(yīng)唯一一棵語法樹？ 最左推導(dǎo)最左推導(dǎo) 最左推導(dǎo)最左推導(dǎo)（ E E ）E EE E + + E EE E * * E Ei ii ii i（ E E ）E EE E * * E EE E + + E Ei ii ii in一個(gè)句型是否只對(duì)應(yīng)唯一最左一個(gè)句型是否只對(duì)應(yīng)唯一最左( (右右) )推導(dǎo)？推導(dǎo)？ 最左推導(dǎo)最左推導(dǎo) 最左推導(dǎo)最左推導(dǎo)E E (E)(E) ( (E+EE+E) ) ( (E E* *E+EE+E) ) (i(i*

18、*E+EE+E) ) (i(i* *i+Ei+E) ) (i(i* *i+ii+i) )E E (E)(E) ( (E E* *E E) ) ( (i i* *E E) ) (i(i* *E+EE+E) ) (i(i* *i+Ei+E) ) (i(i* *i+ii+i) )n定義定義：如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹棵不同的語法樹，或者有兩個(gè)不同的最左或者有兩個(gè)不同的最左（右）推導(dǎo)，則稱這個(gè)（右）推導(dǎo)，則稱這個(gè)文法是二義的文法是二義的。G(E)G(E)： E E i|E+E|E i|E+E|E* *E|(E) E|(E) 是二義文法。是二義文法。n語言

19、的二義性：一個(gè)語言的二義性：一個(gè)語言是二義性的語言是二義性的，如，如果對(duì)它不存在無二義性的文法。果對(duì)它不存在無二義性的文法?？赡艽嬖诳赡艽嬖贕和和G，一個(gè)為二義的，一個(gè)為無二，一個(gè)為二義的，一個(gè)為無二義的。但義的。但L(G)=L(G)n二義性問題是不可判定問題，即不存在一二義性問題是不可判定問題，即不存在一個(gè)算法，它能在有限步驟內(nèi)，確切地判定個(gè)算法，它能在有限步驟內(nèi)，確切地判定一個(gè)文法是否是二義的。一個(gè)文法是否是二義的。n可以找到一組無二義文法的充分條件。可以找到一組無二義文法的充分條件。二義文法：二義文法：G(E)G(E)： E E i|E+E|E i|E+E|E* *E|(E)E|(E)表

20、達(dá)式表達(dá)式 項(xiàng)項(xiàng)|表達(dá)式表達(dá)式+項(xiàng)項(xiàng)項(xiàng)項(xiàng) 因子因子 | 項(xiàng)項(xiàng)*因子因子因子因子 (表達(dá)式表達(dá)式) | i無二義文法：無二義文法： G(E)G(E)：E E T | E+T T | E+T T T F | T F | T* *F F F F (E) | i (E) | iE ET TF F) )( (E EE ET T+ +T TF Fi iF FT T* *F Fi ii iE E T T F F (E)(E) ( (E+TE+T) ) ( (T+TT+T) ) (T(T* *F F+T+T) ) (F(F* *F+TF+T) ) (i(i* *F+TF+T) ) (i(i* *i+T)i+T) (i(i* *i+F) i+F) (i(i* *i+i)i+i)考慮句子考慮句子(i(i* *i+i)i+i)n描述程序設(shè)計(jì)語言時(shí)，對(duì)于上下文無關(guān)文描述程序設(shè)計(jì)語言時(shí)，對(duì)于上下文無關(guān)文法的限制法的限制 ：1 1 不