編譯原理前后文無關(guān)文法和語言

1、編譯原理前后文無關(guān)文法和語言第1頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二本 章 內(nèi) 容2.1 語言的概述2.2 文法和語言的定義第2頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二2.1 語言的概述什么是語言自然語言(Natural Language)是人與人的通訊工具語義(Semantics):環(huán)境、背景知識(shí)、語氣、二義性難以形式化計(jì)算機(jī)語言(Computer Language)計(jì)算機(jī)系統(tǒng)間、人機(jī)間通訊工具嚴(yán)格的語法(Grammar)、語義(Semantics) 易于形式化：嚴(yán)格語言是用來交換信息的工具功能性描述第3頁，共51頁，2022年，5月20日，20點(diǎn)31

2、分，星期二2.1 語言概述語言的描述方法現(xiàn)狀自然語言：自然、方便-非形式化數(shù)學(xué)語言（符號(hào)）：嚴(yán)格、準(zhǔn)確-形式化形式化描述高度的抽象，嚴(yán)格的理論基礎(chǔ)和方便的計(jì)算機(jī)表示。第4頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二2.1 語言概述語言形式化的內(nèi)容提取單詞(Token)：滿足一定規(guī)則字符(Character)串句子(Sentence)：滿足一定規(guī)則單詞序列語言(Language)：滿足一定條件的句子集合語言是字和組合字的規(guī)則結(jié)構(gòu)性描述例：一譯開天第課今始編節(jié)上 今天開始上第一節(jié)編譯課第5頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二程序設(shè)計(jì)語言形式化的內(nèi)容提取程序設(shè)計(jì)語

3、言(Programming Language)：組成 程序的所有語句的集合程序(Program)：滿足語法規(guī)則的語句序列語句(Sentence) ：滿足語法規(guī)則的單詞序列單詞(Token) ：滿足詞法規(guī)則的字符串例變量=表達(dá)式if 條件 then 語句while條件 do 語句call 過程名(參數(shù)表)2.1 語言概述第6頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二語言描述形式文法語法語句語句的組成規(guī)則描述方法：BNF（巴科斯范式： Backus Normal Form ）范式、語法(描述)圖詞法單詞單詞的組成規(guī)則描述方法：BNF范式、正規(guī)式2.1 語言概述第7頁，共51頁，20

4、22年，5月20日，20點(diǎn)31分，星期二遺憾的是，對(duì)于自然語言來說，目前尚無能夠完全刻劃一語言全部句子的結(jié)構(gòu)的方法。然而，對(duì)大多數(shù)程序設(shè)計(jì)語言來說，此問題已被解決。1960年，P.Naur & J.Backus（巴科斯-瑙爾）首先用BNF（Backus-Naur-Formal（范式）對(duì)ALGOL語言進(jìn)行了描述。應(yīng)指出，BNF成功地解決了程序設(shè)計(jì)語言的語法描述問題，但描述其語義，還必須借助自然語言。復(fù)習(xí)：巴科斯范式 （BNF - Backus Normal Form）第8頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二通常，可用如下方式表示或定義一種語言：（1）若語言的句子有限時(shí)，可用

5、枚舉法。 例如，只含兩個(gè)句子的語言： “I am a teacher”, “You are students”;（2）制定有限條規(guī)則，用于產(chǎn)生所要描述的語言的全部句子（可無限多），這些規(guī)則構(gòu)成了該語言的文法。（3）建立一種裝置（算法或過程），它以某字母表上的符號(hào)串為輸入，判別該符號(hào)串是否為所描述語言的句子。此裝置稱為自動(dòng)機(jī)。第9頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二巴科斯范式 （BNF ）例子：The big elephant ate the peanut.(大象吃花生）The little boy ran quickly.(小男孩跑得快）The man has a dog

6、.(這人有一條狗） 以上都是符合英語語法規(guī)則的句子，即它們是在英語語法規(guī)則中成立的句子。 如何描述一個(gè)給定的句子在給定規(guī)則下是否成立呢？第10頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二句子=主語謂語主語=冠詞形容詞名詞冠詞=the 形容詞= big謂語=動(dòng)詞賓語 動(dòng)詞=ate 賓語=冠詞名詞 名詞=elephant | peanut 我們把這種描述語法規(guī)則方法稱巴科斯范式，也稱巴科斯-瑙爾范式(Backus Normal Form)，簡(jiǎn)稱BNF。那么上面敘述的語法規(guī)則可寫為：第11頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二步驟 推導(dǎo) 所用規(guī)則1 謂語 2 形容詞

7、 名詞 謂語 3 the 形容詞 名詞 謂語 4 the big 名詞 謂語 5 the big elephant 謂語 6 the big elephant 動(dòng)詞 7 the big elephant ate 8 the big elephant ate 冠詞 9 the big elephant ate the 10 the big elephant ate the peanut 可見句子the big elephant ate the peanut成立。 當(dāng)然我們還可以推導(dǎo)出其它的句子，如the big peanut ate the elephant，在這里，我們只考慮句子的語法，而不考

8、慮句子的語義。 根據(jù)以上規(guī)則，可以推導(dǎo)出句子 The big elephant ate the peanut. 過程如下：第12頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二用巴科斯范式描述語言能給研究問題帶來很大方便。如下面9個(gè)句子都是正確的： We ran He ran I ran We ate He ate I ate We sat He sat I sat 如果我們用巴科斯范式來描述上面9個(gè)句子只要幾條規(guī)則就行了。 句子=主語謂語 主語=We | He | I 謂語=ran | ate | sat 可見，如果一個(gè)語言有無窮多個(gè)句子，那么用上述規(guī)則來描述更有實(shí)際意義.它用一組

9、規(guī)則來代替枚舉法，用有窮來描述無限。第13頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二2.2 文法和語言的定義本節(jié)主要內(nèi)容 基本概念和術(shù)語（字母表，符號(hào)串等）； 規(guī)則； 文法的定義； 推導(dǎo)； 句型與句子； 文法和語言的等價(jià)轉(zhuǎn)換等第14頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二2.2.1 基本概念和術(shù)語1。字母表（符號(hào)表、符號(hào)集） 由若干元素（符號(hào)、字母）組成的有限非空集合。2。符號(hào)串 用字母表中符號(hào)所組成的任何有限序列。 符號(hào)串的長(zhǎng)度 = 符號(hào)串中所含符號(hào)的個(gè)數(shù) 例：aba的長(zhǎng)度為3。記為：|aba|=3 空串 不含任何符號(hào)的符號(hào)串，記為 。顯然，| |= 0。本

10、課約定 用A、B、C、 等表示字母表或符號(hào)串集；用a,b,c,S,T,U 等表示符號(hào)；用s,t,u,x,y,z,等表示符號(hào)串。3。符號(hào)串的前（后）綴及子串 設(shè),，x是符號(hào)串，若x= ，則稱是x的子串；特別地，當(dāng)= （= ）時(shí)，稱 是x的前（后）綴。第15頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二 基本概念和術(shù)語4。符號(hào)串的連接和方冪 連接 設(shè)x,y是符號(hào)串，將y直接地拼接到x之后所得的新符號(hào)串稱為x與y的連接，記為xy 注意，一般說來，xy 不等于 yx；但 x = x = x 方冪 符號(hào)串x與其自身的 n-1次連接稱為 x 的 n 次方冪，記為第16頁，共51頁，2022年，

11、5月20日，20點(diǎn)31分，星期二 基本概念和術(shù)語5。符號(hào)串集合的和與積設(shè)A，B為兩個(gè)符號(hào)串之集，定義和A+B（或A B） = w | w A，或 w B積AB（或 AB）= xy |x A, y B顯然， A+ = +A = A ； A = A = ；A = A = A6。符號(hào)串集的方冪與閉包第17頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二例0,1+=0，1，00，01，11，000，001，010，011，100， a，b，c，d+ =a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，aaa，aab，aac，aad，aba，abb，abc 例0,1*=，0，1，

12、00，01，11，000，001，010，011，100， a，b，c，d*=，a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，aaa，aab，aac，aad，aba，abb，abc， 第18頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二 基本概念和術(shù)語當(dāng)我們把字母（符號(hào)）表視為由長(zhǎng)度為1的符號(hào)串構(gòu)成的符號(hào)串集時(shí)，就可定義字母表上的連接、積、方冪等運(yùn)算。例A=a,b,c第19頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二2.2.2 文法和語言的形式定義 我們從“產(chǎn)生語言”的角度出發(fā),討論文法和語言的形式定義。產(chǎn)生語言指制定出有限條規(guī)則，借助它們就能產(chǎn)生出

13、些語言的句子。我們以幾個(gè)英語句子構(gòu)成的語言為例進(jìn)行討論。并設(shè)每個(gè)句子都是“主-謂-賓”結(jié)構(gòu)。語法規(guī)則見右。其中，每個(gè)用括起來的部分是所要定義語言中的一個(gè)語法實(shí)體（稱為語法單位、語法結(jié)構(gòu)、語法范疇、語法變量等）?！?=”是用于定義語法結(jié)構(gòu)的符號(hào)，其含義（并讀作）“定義為”。 語法規(guī)則也稱為產(chǎn)生式(Production): := the :=:=:=monkey:=banana:=eat:=has:= the:= a第20頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二 現(xiàn)在，我們討論如何用上述規(guī)則推導(dǎo)出相應(yīng)語言的全部句子。推導(dǎo)：從語言最大的一個(gè)語法范疇（本例中是）開始，反復(fù)用語法規(guī)則中

14、“:=” 右側(cè)的符號(hào)串取代其左側(cè)符號(hào)，直到所得的符號(hào)串中不再含有可被替換語法范疇。每次替換稱為一步（直接）推導(dǎo)，并用符號(hào)“”表示。 例如，我們首先用規(guī)則進(jìn)行第一步推導(dǎo)(derivation)，就可得到 ，記為： 所得的符號(hào)串含有兩個(gè)語法范疇，可對(duì)其中任一個(gè)（例如對(duì)）進(jìn)行新的推導(dǎo)（替換）： 重復(fù)上述過程，可得到一個(gè)推導(dǎo)序列（見下頁）。第21頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二用語法規(guī)則進(jìn)行推導(dǎo)所得的推導(dǎo)序列推導(dǎo)步驟 所用規(guī)則所得的符號(hào)串 1 2 3 the 4 the 5 the monkey 6 the monkey eat 7 the monkey eat a 8 th

15、e monkey eat a banana第22頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二2.2.2 文法和語言的形式定義從前面的推導(dǎo)看，從出發(fā)，經(jīng)8步推導(dǎo)得到了一個(gè)英語句子。故前面的推導(dǎo)稱為長(zhǎng)度為8的推導(dǎo)。若不關(guān)心推導(dǎo)的中間過程，可將從一符號(hào)串到另一符號(hào)串的推導(dǎo)用記號(hào)第23頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二規(guī)則的簡(jiǎn)化表示在前面的語法規(guī)則定義中，有些語法范疇（如、）有若干條不同的規(guī)則來定義它，為簡(jiǎn)明起見，我們可以將它們寫在同一個(gè)左部語法范疇下，將其定義值用符號(hào)“|”（讀作或）隔開。如、 、 的定義規(guī)則可簡(jiǎn)記為:= monkey | banana:= ea

16、t | has:= the | a第24頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二語法規(guī)則及其產(chǎn)生的語言前面的語法規(guī)則可以產(chǎn)生16個(gè)不同的句子，由這16個(gè)句子組成的集合，就是該規(guī)則所定義（或所產(chǎn)生）的語言。應(yīng)指出，所產(chǎn)生的句子中，有些句子的含義是荒謬的（如 the banana eat a monkey和the banana eat the banana等）。然而，若不考慮語義，則我們就必須承認(rèn)它們是語法上合法的句子。第25頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二2.2.2 文法和語言的形式定義為得到文法的嚴(yán)格定義，我們對(duì)前面的規(guī)則進(jìn)行如下的概括：第26頁，共

17、51頁，2022年，5月20日，20點(diǎn)31分，星期二1、文法G 的形式定義1文法G為一個(gè)四元組: = (T，N，) T：終結(jié)符(Terminal)集 N：非終結(jié)符(Variable)集，TN= 語法范疇某個(gè)語言結(jié)構(gòu) ：開始符號(hào)(Start Symbol)，SN至少在產(chǎn)生式左側(cè)出現(xiàn)一次規(guī)定：（1）VN ，VT，P是有窮非空集合； （2）VNVT （不含公共元素）第27頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二：產(chǎn)生式(Product)集合 ，被稱為產(chǎn)生式（定義式），讀作：定義為。其中： (TN)+，且中至少有N中元素的一個(gè)出現(xiàn)。 (TN)*。 稱為產(chǎn)生式的左部(Left Part

18、)，稱為產(chǎn)生式的右部(Right Part)。 第28頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二例：算術(shù)表達(dá)式的文法P: EE + E EE - E EE * E EE/ E E( E ) Eid G =（id，+，-，*，/，(，)，E，P，E） 約定：只寫產(chǎn)生式?？珊?jiǎn)寫為： E E + E | E - E | E * E | E / E | ( E ) | id第29頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二產(chǎn)生式的簡(jiǎn)寫對(duì)一組有相同左部的產(chǎn)生式 1，2，n 可以簡(jiǎn)單地記為： 1|2|n 讀作：定義為或者1，或者2，或者n。并且稱它們?yōu)楫a(chǎn)生式。1，2，n稱為候

19、選式(Candidate)。 第30頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二例、 文法G =（VN ，VT ，P，S）， 其中： VN=S，VT =0，1， P=S 0S1，S 01。 開始符號(hào)是S S 0S1 00S11 0n-1S1n-1 0n1n 所以描述的語言為： L=0n1n|n1第31頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二例： 文法G =（VN ，VT，P，S）其中 ：VN =標(biāo)識(shí)符，字母，數(shù)字 VT= a,b ,c,x,y,z,0,1,9 S= P = | | a|b|z 0|1|9 第32頁，共51頁，2022年，5月20日，20點(diǎn)31分，

20、星期二1、文法的定義 文法的第二種表示法： 上例1改為： G: S 0S1 S 01 文法的第三種表示法： 上例1改為： GS: S 0S1 S 01一般約定，第一條產(chǎn)生式的左部是開始符號(hào)；用尖括號(hào)括起來的是非終結(jié)符號(hào)，不用尖括號(hào)括起來的是終結(jié)符號(hào)，或者用大寫字母表示非終結(jié)符號(hào)，小寫字母表示終結(jié)符號(hào)。 第33頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二2、直接推導(dǎo)的定義 如：有文法G: EE+E|E*E|(E)|i E (E) (E+E) (i+E) (i+i) （稱這樣一串替換序列是從E推出(i+i)的一個(gè)推導(dǎo))（1）定義： 稱 A直接推出 ，即： A 僅當(dāng) A 是一個(gè)產(chǎn)生式，

21、 且、 (VNVT)*第34頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二例：GS: S 0S1, S 01 S 0S1 00S11 000S111 00001111 可有： A = 00S11 , =000S111 (相當(dāng)A=S, = 0S1)第35頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二A =S， 0S1直接推導(dǎo)：S 0S1A=0S1， =00S11直接推導(dǎo)： 0S100S11例：A0S1，=0011直接推導(dǎo)：0S1 0011使用規(guī)則：S 010，1，AS， 01 規(guī)則： S 0S1 ， AS， 0S1 規(guī)則： S 0S1 0 ， 1AS， 0S1 第36頁，

22、共51頁，2022年，5月20日，20點(diǎn)31分，星期二 若有 1 n ，或 1=n ,則記作1 n 例： 在例1中存在序列：10S1 00S11 000S111 00001111 n 記作： 0S1 00001111 0S1 00001111 +*一樣的 若存在直接推導(dǎo)的序列： 1 2 3 n (n1)則 稱1推導(dǎo) n (或n規(guī)約到1 ) ，記 1 n +第37頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二（多步）推導(dǎo)012 n記為 0n n (恰用n步) 0+ n （至少一步） 0* n （若干步:零步或多步）第38頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二id+

23、id*id的不同推導(dǎo)EE+E|E*E|(E)|idE E+E id+E id+E*E id+id*E id+id*idE E+E E+E*E E+E*id E+id*id id+id*idE E*E E+E*E E+id*E id+id*E id+id*id不做限制句型 (sentential Form)（歸約）E * id+id*id施于最右變量右句型/規(guī)范句型 (canonical ) (最左/規(guī)范歸約)E + id+id*id施于最左變量左句型(left-) （最右歸約） E5 id+id*id第39頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二例：算術(shù)表達(dá)式 GE: E E

24、+T | T T T*F | F F (E) | a 可推導(dǎo)出： E E+T T+TF+T a+T a+T*F a+F*Fa+a*F a+a*a 表示文法GE能推導(dǎo)出用符號(hào)a, +, *, (和)構(gòu)成的所有算術(shù)表達(dá)式第40頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二3、句型與句子句型：設(shè)GS是文法，若S x，且xV* , 則稱x是文法GS的句型 句子：設(shè)GS是文法，若S x，且xVT* , 則稱x是文法GS的句子（句子是句型的特殊）結(jié)論句子一定是句型，句型不一定是句子。 例：GS: S 0S1, S 01 S 0S1 00S11 000S111 00001111 S, 0S1 ,

25、 00S11 , 000S111 , 00001111都是句型，只有00001111是G的句子*第41頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二4、文法G產(chǎn)生的語言定義：L(G)= xSx， S為文法開始符號(hào)， xVT* L(G)是文法GS描述的語言，也是該文法能推導(dǎo)出所有句子的集合。 文法 EE+E|E*E|(E)|id可以派生出多少個(gè)句子？ 文法G的作用語言的有窮描述以有限的規(guī)則描述無限的語言現(xiàn)象有限: 產(chǎn)生式集合、終結(jié)符集合、非終結(jié)符集合無限： 可以導(dǎo)出無窮多個(gè)句子 （注：L也可是有窮）第42頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二例： GS: S 0S

26、1, S 01 L(G)0n1n n1因?yàn)镾0S100S11 0n1n重復(fù)利用規(guī)則S0S1第43頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二例：文法G: S bA A aA|a 考慮該文法定義的語言。 S bA S bA baA baa S bA baA baaA baaa S bA baA baa 所以： L(G)=ban| n1第44頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二例 考慮文法G: E (E)a 這個(gè)文法有1個(gè)非終結(jié)符E、3個(gè)終結(jié)符(,),a這個(gè)文法生成語言: L(G)=a ,(a),(a),(a),.， 即：串由零個(gè)或多個(gè)左括號(hào)、后接一個(gè)a ，以及后面是與左括號(hào)相同數(shù)量的右括號(hào)組成。作為這些串的一個(gè)推導(dǎo)示例，我們給出(a)的一個(gè)推導(dǎo)： E (E) (E) (a)第45頁，共51頁，2022年，5月20日，20點(diǎn)31分，星期二練習(xí)：文法GS：（1）SaSBE