編譯原理課程之文法基礎(chǔ)

1、形式語言基本知識形式語言基本知識第二章第二章 本章要求本章要求 主要內(nèi)容主要內(nèi)容：符號串，文法的概念及分：符號串，文法的概念及分類，語言的定義過程類，語言的定義過程 重點(diǎn)掌握重點(diǎn)掌握：上下文無關(guān)文法、推導(dǎo)、：上下文無關(guān)文法、推導(dǎo)、句型、句子、語言，語法樹、二義性句型、句子、語言，語法樹、二義性文法、文法的語言生成過程文法、文法的語言生成過程 問題：問題：1. 程序語言的定義主要包括哪兩個(gè)方面？2. 什么是語言的語法？3. 什么是語言的語法規(guī)則？一般程序語言的語法單位有哪些？4. 什么是語言的語義？5. 什么是名字的作用域？說明名字的作用域規(guī)則“最近嵌套原則”。6. 什么是名字的左值、右值？7.

2、 描述程序語言中表達(dá)式的形成規(guī)則。8. 什么是符號串的閉包、正則閉包？9. 什么是文法？什么是上下文無關(guān)文法？10. 什么是終結(jié)符號、非終結(jié)符號、開始符號、產(chǎn)生式？11. 描述上下文無關(guān)文法的形式定義。12. 和 兩個(gè)符號的含義及區(qū)別。13. 和 兩個(gè)符號的含義及區(qū)別。14. 什么是句型、句子、語言？15. 什么是句型的最左推導(dǎo)，最右推導(dǎo)？16. 什么是語法樹？17. 什么是二義性文法？18. 可否用算法確切地判定一個(gè)文法是二義性的？19. 描述程序設(shè)計(jì)語言時(shí)，對于上下文無關(guān)文法有哪些限制？20. 什么是左線性文法，右線性文法？2.1 程序語言定義的基本概念程序語言定義的基本概念高級程序語言的

3、基本功能和層次結(jié)構(gòu)高級程序語言的基本功能和層次結(jié)構(gòu) 程序語言的基本功能基本功能：描述數(shù)據(jù)和對數(shù)據(jù)的運(yùn)算。 所謂程序，本質(zhì)上說是描述一定數(shù)據(jù)的處理過程。程序的層次結(jié)構(gòu)程序的層次結(jié)構(gòu)程序程序| |子程序或分程序、過程、函數(shù)子程序或分程序、過程、函數(shù)| |語句語句| |表達(dá)式表達(dá)式| |數(shù)據(jù)引用數(shù)據(jù)引用 算符算符 函數(shù)調(diào)用函數(shù)調(diào)用程序語言每個(gè)組成成分的邏輯和實(shí)現(xiàn)意義程序語言每個(gè)組成成分的邏輯和實(shí)現(xiàn)意義 抽象的邏輯的意義抽象的邏輯的意義數(shù)學(xué)意義數(shù)學(xué)意義 計(jì)算機(jī)實(shí)現(xiàn)的意義計(jì)算機(jī)實(shí)現(xiàn)的意義具體實(shí)現(xiàn)具體實(shí)現(xiàn) 與機(jī)器語言或匯編語言比較，高級語言高級語言的優(yōu)點(diǎn)：的優(yōu)點(diǎn)：較接近于數(shù)學(xué)語言和工程語言，比較直觀、自然

4、和易于理解;便于驗(yàn)證其正確性，易于改錯(cuò);編寫效率高;易于移植.語語 法法 詞法規(guī)則詞法規(guī)則：單詞符號的形成規(guī)則：單詞符號的形成規(guī)則。單詞符號是語言中具有獨(dú)立意義的最基本結(jié)構(gòu)單詞符號是語言中具有獨(dú)立意義的最基本結(jié)構(gòu)。一般包括：常數(shù)、標(biāo)識符、基本字、算符、一般包括：常數(shù)、標(biāo)識符、基本字、算符、界符等。界符等。描述工具：有限自動(dòng)機(jī)描述工具：有限自動(dòng)機(jī) 語法規(guī)則語法規(guī)則：語法單位的形成規(guī)則：語法單位的形成規(guī)則。語法單位通常包括：表達(dá)式、語句、分程序、語法單位通常包括：表達(dá)式、語句、分程序、過程、函數(shù)、程序等過程、函數(shù)、程序等; ;描述工具：上下文無關(guān)文法描述工具：上下文無關(guān)文法程序語言的語法描述基礎(chǔ)程

5、序語言的語法描述基礎(chǔ) 幾個(gè)概念幾個(gè)概念: :考慮一個(gè)考慮一個(gè)有窮有窮 字母表字母表 上的字符集，上的字符集，其中每一個(gè)元素稱為一個(gè)其中每一個(gè)元素稱為一個(gè)字符，字符，上的上的字字( (也叫也叫字符串、符號串字符串、符號串) ) 是指由是指由中中的字符所構(gòu)成的一個(gè)有窮序列。的字符所構(gòu)成的一個(gè)有窮序列。不包含任何字符的序列稱為不包含任何字符的序列稱為空字空字，記為，記為用用* *表示表示上的所有字的全體上的所有字的全體, ,包含空字包含空字例如例如: : 設(shè)設(shè) =a=a， bb，則，則 * *=,a,b,aa,ab,ba,bb,aaa,.,a,b,aa,ab,ba,bb,aaa,. 符號串的長度符號

6、串的長度 : :符號串中符號的個(gè)數(shù)，例如: 某符號串中有m個(gè)符號,則稱其長度為m，表示為x=m，如001110的長度是6?？辗柎辗柎? 即不包含任何符號的符號串，用表示，其長度為0， 即=0。 *的子集的子集U和和V的的連接連接（積積）定義為）定義為UV | U & V 設(shè)：設(shè)：U a, aa V b, bb 那么：那么：UV= ab, abb, aab, aabb *的子集的子集U和和V的的連接連接（積積）定義為）定義為UV | U & V V自身的自身的 n次積記為次積記為Vn=VVV 規(guī)定規(guī)定V0= ，令，令 V*=V0V1V2V3 稱稱V*是是V的的閉包閉包; 記記 VVV* ，

7、稱，稱V+是是V的的正規(guī)閉包正規(guī)閉包。 設(shè)：設(shè)：U a, aa 那么：那么： U* = , a, aa, aaa, aaaa, U = a, aa, aaa, aaaa, 2.2 上下文無關(guān)文法及其語言上下文無關(guān)文法及其語言 文法文法是描述語言的語法結(jié)構(gòu)的形式規(guī)則。是描述語言的語法結(jié)構(gòu)的形式規(guī)則。 文法是一種工具，它可用于嚴(yán)格定義句子的結(jié)構(gòu)；用有窮的規(guī)則刻劃無窮的集合。 文法是被用來精確而無歧義地描述語言的句子的構(gòu)成方式。 文法描述語言的時(shí)候不考慮語言的含義。 He gave me a book. He He me me book book a a gave gave引引 例例 He me b

8、ook a gave He He He gave He gave He gave me He gave me He gave me a He gave me a book文法的形式定義文法的形式定義 由四部分組成：終結(jié)符號：是組成該語言的最基本的符號，是不可再分的基本符號,如保留字、標(biāo)識符等。非終結(jié)符號：規(guī)則中用尖括號括起來的符號，表示一些語法成分，可以推導(dǎo)出其他的語法成分,表示一定符號串的集合，是一個(gè)類，如表達(dá)式。開始符號：規(guī)則中的一個(gè)特殊的非終結(jié)符號，語言中的句子都從它開始推導(dǎo),如程序、句子產(chǎn)生式：定義語法成分的規(guī)則，其中： 一個(gè)文法G抽象地表示為四元組 G=（Vn,Vt,P,S） 其中V

9、n表示非終結(jié)符號Vt表示終結(jié)符號，VnVt=(字母表)，VnVt=S是開始符號，P是產(chǎn)生式，形如：(V+且至少含有一個(gè)非終結(jié)符號，V*) 產(chǎn)生式的形式為：A 左部符號，非終結(jié)符右部，可以含有非終結(jié)符和終結(jié)符產(chǎn)生式又稱為一條規(guī)則。有時(shí)一個(gè)產(chǎn)生式不足以描述該語法范疇，就用多個(gè)產(chǎn)生式，如算術(shù)表達(dá)式的描述為：(遞歸定義) E E + E | E * E|i E E + E E E * E E i相同左部的一個(gè)右部又稱一個(gè)候選式。形式語言與自動(dòng)機(jī)理論形式語言與自動(dòng)機(jī)理論（蔣宗禮等，（蔣宗禮等，清華大學(xué)出版社）對文法的定義：清華大學(xué)出版社）對文法的定義：上下文無關(guān)文法的定義上下文無關(guān)文法的定義一個(gè)上下文無

10、關(guān)文法G是一個(gè)四元式 G=(VT，VN，S，P)，其中VT：終結(jié)符集合(非空)VN：非終結(jié)符集合(非空)，且VT VN=S：文法的開始符號，SVNP：產(chǎn)生式集合(有限)，每個(gè)產(chǎn)生式形式為P， PVN， (VT VN)*開始符S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。上下文無關(guān)上下文無關(guān)文法所定義的語法成分獨(dú)立于它可能出現(xiàn)的環(huán)境，即不考慮上下文。算術(shù)表達(dá)式的文法定義算術(shù)表達(dá)式的文法定義 變量是表達(dá)式 表達(dá)式 + 表達(dá)式是表達(dá)式 表達(dá)式 * 表達(dá)式是表達(dá)式 (表達(dá)式) 是 表達(dá)式E E + E E E * E E ( E ) E i E E+E | E*E | (E) | i 上下文無關(guān)文法產(chǎn)生句子的

11、方法上下文無關(guān)文法產(chǎn)生句子的方法:從文法的開始符號出發(fā),反復(fù)連續(xù)使用產(chǎn)生式,對左邊的非終結(jié)符進(jìn)行替換和展開 例：表達(dá)式定義規(guī)則E E + E E E * E E ( E ) E i( i+i )E=( E ) =( E+E ) =( i+E ) =( i + i ) 例，定義只含例，定義只含+，*的算術(shù)表達(dá)式的文法的算術(shù)表達(dá)式的文法 G=， 其其中，中，P由下列產(chǎn)生式組成：由下列產(chǎn)生式組成：E iE E+EE E*EE (E) 幾點(diǎn)規(guī)定：幾點(diǎn)規(guī)定： “ ”也可以用也可以用“:=表示，表示， 這種表示稱為巴這種表示稱為巴科斯范式科斯范式(BNF) P 1 P 2 可縮寫為可縮寫為 P 1| 2|

12、 n P n 其中，其中，“|”讀成讀成“或或”，稱為，稱為P的一個(gè)候選式。的一個(gè)候選式。 表示一個(gè)文法時(shí)，通常只給出開始符號和產(chǎn)生式表示一個(gè)文法時(shí)，通常只給出開始符號和產(chǎn)生式，如上例，可表示為：，如上例，可表示為：G(E)： E i | E+E | E*E | (E)n例，定義只含例，定義只含+，*的算術(shù)表達(dá)式的文法的算術(shù)表達(dá)式的文法 G=， 其中，其中，P由下列產(chǎn)生式組成：由下列產(chǎn)生式組成：E iE E+EE E*EE (E) 定義：稱定義：稱 A 直接推出直接推出，即，即 A 僅當(dāng)僅當(dāng)A 是一個(gè)產(chǎn)生式，是一個(gè)產(chǎn)生式， 且且 ， (VT VN)* 。 如果如果 1 2 n，則我們稱這個(gè)序，

13、則我們稱這個(gè)序列是從列是從 1到到 n的一個(gè)的一個(gè)推導(dǎo)推導(dǎo)。若存在一個(gè)從。若存在一個(gè)從 1到到 n的推導(dǎo)，則稱的推導(dǎo)，則稱 1可以可以推導(dǎo)推導(dǎo)出出 n 。 對文法對文法G(E)： E i | E+E | E*E | (E)E (E) (E+E) (i+E) (i+i)n通常，用通常，用 表示：從表示：從 1 1出發(fā)，經(jīng)過出發(fā)，經(jīng)過一步或若干步，可以推出一步或若干步，可以推出 n n。n1n*1 用用 表示：從表示：從 1 1出發(fā)，經(jīng)過出發(fā)，經(jīng)過0 0步或步或若干步，可以推出若干步，可以推出 n n。* 所以所以 ： 即即 或或*S ,|)(*TV SGLq定義：假定定義：假定G G是一個(gè)文法，

14、是一個(gè)文法，S S 是它的開始符號。是它的開始符號。如果如果 ，則，則 稱是一個(gè)稱是一個(gè)句型句型。僅含終結(jié)符。僅含終結(jié)符號的句型是一個(gè)號的句型是一個(gè)句子句子。文法。文法G G所產(chǎn)生的句子的全所產(chǎn)生的句子的全體是一個(gè)體是一個(gè)語言語言，將它記為，將它記為 L(G)L(G)。 文法文法G所產(chǎn)生的語言所產(chǎn)生的語言定義為： L(G)=x|S=x,其中S為文法的開始符號，xVt* 。即: 一個(gè)文法G可以推導(dǎo)出的所有句子構(gòu)成的一個(gè)集合, 就確定了一個(gè)語言。* 例2.1 (P30) 考慮文法G1: 它定義了什么語言。S bAA aA|a推導(dǎo)過程 ：S=bA =ba S=bA =baA=baa . S=bA =

15、baA= =baa歸納得： L(G1) = ban | n1 例2.2(P30) 考慮文法G2: 它定義的語言是：S ABA aA|aB bB|bL(G2) = ambn |m,n1 練習(xí)：文法(A,B,S,a,b,c,P,S) S Ac|aB A ab B bc寫出(G)的全部元素 L(G) = abc 例：例： (i*i+i)是文法是文法G(E)： E i | E+E | E*E | (E)的一個(gè)句子。的一個(gè)句子。 證明：證明： E (E) (E+E) (E*E+E) (i*E+E) (i*i+E) (i*i+i) E，(E)，(E*E+E)，(i*i+i)是句型。是句型。q例：文法例：文

16、法G1(A)：A c|AbG1(A)的語言的語言?L(G1)=c，cb，cbb，以以c開頭，后繼若干個(gè)開頭，后繼若干個(gè)b 例：文法例：文法G2(S)：S ABA aA|aB bB|bG2(S)的語言的語言?L(G2)=ambn|m，n0q例：給出產(chǎn)生語言為例：給出產(chǎn)生語言為anbn|n 1的文法。的文法。 G3(S)： S aSb S abq例：給出產(chǎn)生語言為例：給出產(chǎn)生語言為ambn|1 n m 2n的的文法。文法。 G4(S)： S aSb | aaSb S ab | aab 思考：構(gòu)造一個(gè)文法G3使得：L(G3) = anbn |n1 S aSbS ab a,b的個(gè)數(shù)相同,則文法G3為：

17、 文法等價(jià)：文法等價(jià)： 若文法G1和文法G2所產(chǎn)生的語言相同，即L(G1) = L(G2)，則稱文法G1和文法G2等價(jià)等價(jià)。例：有如下兩個(gè)文法，判斷它們是否等價(jià)？ G1=（S，0，S，S0S，S0） G2=（S，0，S，SS0，S0）S0S0S00S0S 00S 0000 L(G1) = 0n | n1 對于對于G2： 對于對于G1 ：SS0 S00 0000 L(G2) = 0n | n1 G1G2，但L(G1) = L(G2)，文法G1和G2等價(jià) 例3 : G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i 表達(dá)式 (

18、i+i)*i的推導(dǎo)過程： (1) E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i (2) E E*E E*i (E)* i (E + E)*i (E+ i)*i (i + i)*il 得到一個(gè)語言，是通過利用所有的產(chǎn)生式推導(dǎo)出所有可能的句子，構(gòu)成一個(gè)集合。l 但是一個(gè)句型到另一個(gè)句型(句子)的推導(dǎo)過程不是唯一的。 從一個(gè)句型到另一個(gè)句型的推導(dǎo)往往不唯從一個(gè)句型到另一個(gè)句型的推導(dǎo)往往不唯一。一。 E+Ei+Ei+i E+EE+ii+i 最左推導(dǎo)最左推導(dǎo)：任何一步：任何一步 都是對都是對 中的最中的最左非終結(jié)符進(jìn)行替換。左非終結(jié)符進(jìn)行替換。

19、最右推導(dǎo)最右推導(dǎo)：任何一步：任何一步 都是對都是對 中的最中的最右非終結(jié)符進(jìn)行替換。右非終結(jié)符進(jìn)行替換。 最左推導(dǎo)最左推導(dǎo): 在整個(gè)推導(dǎo)過程中,任何一步推導(dǎo)=都是對中最左邊的非終結(jié)符進(jìn)行替換。 最右推導(dǎo)最右推導(dǎo): 在推導(dǎo)之前確定推導(dǎo)的順序，是對句子進(jìn)行確定性分析所必須的例3： G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i (i+i)*i的最左推導(dǎo)過程： E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i最右推導(dǎo)過程： E E*E E*i (E + E)*i (E+

20、i)*i (i + i)*i2.3 語法樹和文法的二義性語法樹和文法的二義性語法樹語法樹 語法樹語法樹：推導(dǎo)的形式化表示推導(dǎo)的形式化表示，有助于理解句子語法結(jié)構(gòu)的層次 每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，該標(biāo)記屬字母集中的一個(gè)符號，根由開始符號標(biāo)記。 當(dāng)某個(gè)非終結(jié)符被它的某個(gè)候選式所替換時(shí)，就產(chǎn)生相應(yīng)的下一層的結(jié)點(diǎn)，候選式中自左至右的每個(gè)符號對應(yīng)一個(gè)新的結(jié)點(diǎn)，并標(biāo)記它，畫出其與父結(jié)點(diǎn)之間的連線。例：對文法G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i 句子(i+i)*i 的語法樹： 在語法樹的推導(dǎo)過程中的任何時(shí)刻，沒有后代的端末結(jié)點(diǎn)

21、自左至右排列起來就是一個(gè)句型。 一棵語法樹表示了一個(gè)句型很多可能的不同推導(dǎo)過程。(包括最左推導(dǎo)和最右推導(dǎo))。例3： G = (E, i, +, *, (, ) , P , E) P： E E + E | E * E | ( E ) | i 句子 ( i * i + i)的語法樹： (1) E (E) (E + E) (E * E + E) (i * E + E) (i *i + i) (2) E (E) (E * E) (i*E) (i * E + E) (i * i + E) (i *i + i)并不是任何情況下一個(gè)句型就唯一地對應(yīng)一棵語法樹。文法的二義性文法的二義性 定義定義：如果一個(gè)文法

22、存在某個(gè)句子對應(yīng)兩棵不同的語法樹，則說這個(gè)文法是二二義義的 。 對二義文法中的某個(gè)句子的分析不是唯一的，因此總是希望文法是無二義的。 但是二義文法有時(shí)也是有用的。2.4 文法的分類文法的分類 Chomsky于于1956年建立形式語言體系，他把文年建立形式語言體系，他把文法分成四種類型：法分成四種類型：0，1，2，3型。型。 與上下文無關(guān)文法一樣，它們都由四部分組成，與上下文無關(guān)文法一樣，它們都由四部分組成，但對產(chǎn)生式的限制有所不同。但對產(chǎn)生式的限制有所不同。0型型(短語文法，圖靈機(jī)短語文法，圖靈機(jī))： 產(chǎn)生式形如：產(chǎn)生式形如： 其中：其中： (VT VN)*且至少含有一個(gè)非終結(jié)且至少含有一個(gè)非

23、終結(jié)符；符； (VT VN)*1型型(上下文有關(guān)文法，線性界限自動(dòng)機(jī)上下文有關(guān)文法，線性界限自動(dòng)機(jī))： 產(chǎn)生式形如：產(chǎn)生式形如： 其中：其中：| | | |，僅，僅 S 例外。例外。2型型(上下文無關(guān)文法，非確定下推自動(dòng)機(jī)上下文無關(guān)文法，非確定下推自動(dòng)機(jī))： 產(chǎn)生式形如：產(chǎn)生式形如： A 其中：其中：A VN； (VT VN)*。3型型(正規(guī)文法，有限自動(dòng)機(jī)正規(guī)文法，有限自動(dòng)機(jī))： 產(chǎn)生式形如：產(chǎn)生式形如： A B 或或 A 其中：其中： VT*；A，B VN 產(chǎn)生式形如：產(chǎn)生式形如： A B 或或 A 其中：其中： VT*；A，B VN（注意：線性文法中，產(chǎn)生式的右部只有一（注意：線性文法中

24、，產(chǎn)生式的右部只有一個(gè)非終結(jié)符。）個(gè)非終結(jié)符。）右線性文法右線性文法左線性文法左線性文法四種類型描述能力比較四種類型描述能力比較0型1型2型3型語言的層次語言的層次 這四種語言可被4種自動(dòng)機(jī)識別： 0型圖靈機(jī) 1型線性界限自動(dòng)機(jī) 2型下推自動(dòng)機(jī) 3型有窮自動(dòng)機(jī) 從外到內(nèi)，四種文法對產(chǎn)生式的限制越來越多，語言的描述能力越來越弱 正規(guī)文法的描述能力比上下文無關(guān)文法的描述能力弱。 正規(guī)文法只能用于描述單詞的構(gòu)成。 上下文無關(guān)文法有足夠的能力描述現(xiàn)今大多數(shù)程序設(shè)計(jì)語言的語法結(jié)構(gòu)。 2.5 類類Pascal語言語言Sample的文法描述的文法描述 類PASCAL語言Sample，是PASCAL語言的裁減

25、版本，具有一般高級語言的共同特征： 它的字符集包括所有的大小寫字母、數(shù)字和一些界符； 有多種數(shù)據(jù)類型：整型、實(shí)型、字符型等； 有變量說明和常量說明； 包括順序、條件和循環(huán)三種語句結(jié)構(gòu)。詳細(xì)地說，Sample語言包括如下一些語法成分：1數(shù)據(jù)類型：數(shù)據(jù)類型：整型、布爾型、實(shí)型和字符類型2表達(dá)式：表達(dá)式：可進(jìn)行算術(shù)、邏輯表達(dá)式的運(yùn)算3說明語句：說明語句：常量說明、變量說明4賦值語句賦值語句5控制語句控制語句：If語句、while語句、repeat語句和for循環(huán)語句6begin end復(fù)合語句復(fù)合語句7程序語句（程序語句（program）與結(jié)束語句）與結(jié)束語句(end.)2.5.1 Sample語言

26、字符集的定義語言字符集的定義 (1) := | (2) := a|b|c|z|A|B|C|Z (3) := 0|1|2|3|9 (4) := +|-|*|/|=|(|)|:|;|,|_|.2.5.2、 Sample語言詞法定義語言詞法定義 (1) := | (2) := and|begin|bool|char|const|do|else|end|false |for|if|input|integer|not|or|output|program |read|real|repeat|then|to|true|until|var|while|write (3) := /*|*/|=|:= (4) := | Sample語言詞法定義（續(xù)）語言詞法定義（續(xù)） (5) := | (6) := | (7) :=