編譯原理前后文無關文法和語言

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

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

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

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

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

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

7、 名詞 謂語 3 the 形容詞 名詞 謂語 4 the big 名詞 謂語 5 the big elephant 謂語 6 the big elephant 動詞 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成立。 當然我們還可以推導出其它的句子，如the big peanut ate the elephant，在這里，我們只考慮句子的語法，而不考

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

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

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

11、5月20日，20點31分，星期二 基本概念和術語5。符號串集合的和與積設A，B為兩個符號串之集，定義和A+B（或A B） = w | w A，或 w B積AB（或 AB）= xy |x A, y B顯然， A+ = +A = A ； A = A = ；A = A = A6。符號串集的方冪與閉包第17頁，共51頁，2022年，5月20日，20點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點31分，星期二 基本概念和術語當我們把字母（符號）表視為由長度為1的符號串構(gòu)成的符號串集時，就可定義字母表上的連接、積、方冪等運算。例A=a,b,c第19頁，共51頁，2022年，5月20日，20點31分，星期二2.2.2 文法和語言的形式定義 我們從“產(chǎn)生語言”的角度出發(fā),討論文法和語言的形式定義。產(chǎn)生語言指制定出有限條規(guī)則，借助它們就能產(chǎn)生出

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

14、“:=” 右側(cè)的符號串取代其左側(cè)符號，直到所得的符號串中不再含有可被替換語法范疇。每次替換稱為一步（直接）推導，并用符號“”表示。 例如，我們首先用規(guī)則進行第一步推導(derivation)，就可得到 ，記為： 所得的符號串含有兩個語法范疇，可對其中任一個（例如對）進行新的推導（替換）： 重復上述過程，可得到一個推導序列（見下頁）。第21頁，共51頁，2022年，5月20日，20點31分，星期二用語法規(guī)則進行推導所得的推導序列推導步驟 所用規(guī)則所得的符號串 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點31分，星期二2.2.2 文法和語言的形式定義從前面的推導看，從出發(fā)，經(jīng)8步推導得到了一個英語句子。故前面的推導稱為長度為8的推導。若不關心推導的中間過程，可將從一符號串到另一符號串的推導用記號第23頁，共51頁，2022年，5月20日，20點31分，星期二規(guī)則的簡化表示在前面的語法規(guī)則定義中，有些語法范疇（如、）有若干條不同的規(guī)則來定義它，為簡明起見，我們可以將它們寫在同一個左部語法范疇下，將其定義值用符號“|”（讀作或）隔開。如、 、 的定義規(guī)則可簡記為:= monkey | banana:= ea

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

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

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

19、選式(Candidate)。 第30頁，共51頁，2022年，5月20日，20點31分，星期二例、 文法G =（VN ，VT ，P，S）， 其中： VN=S，VT =0，1， P=S 0S1，S 01。 開始符號是S S 0S1 00S11 0n-1S1n-1 0n1n 所以描述的語言為： L=0n1n|n1第31頁，共51頁，2022年，5月20日，20點31分，星期二例： 文法G =（VN ，VT，P，S）其中 ：VN =標識符，字母，數(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點31分，

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

21、 且、 (VNVT)*第34頁，共51頁，2022年，5月20日，20點31分，星期二例：GS: S 0S1, S 01 S 0S1 00S11 000S111 00001111 可有： A = 00S11 , =000S111 (相當A=S, = 0S1)第35頁，共51頁，2022年，5月20日，20點31分，星期二A =S， 0S1直接推導：S 0S1A=0S1， =00S11直接推導： 0S100S11例：A0S1，=0011直接推導：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點31分，星期二 若有 1 n ，或 1=n ,則記作1 n 例： 在例1中存在序列：10S1 00S11 000S111 00001111 n 記作： 0S1 00001111 0S1 00001111 +*一樣的 若存在直接推導的序列： 1 2 3 n (n1)則 稱1推導 n (或n規(guī)約到1 ) ，記 1 n +第37頁，共51頁，2022年，5月20日，20點31分，星期二（多步）推導012 n記為 0n n (恰用n步) 0+ n （至少一步） 0* n （若干步:零步或多步）第38頁，共51頁，2022年，5月20日，20點31分，星期二id+

23、id*id的不同推導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點31分，星期二例：算術表達式 GE: E E

24、+T | T T T*F | F F (E) | a 可推導出： E E+T T+TF+T a+T a+T*F a+F*Fa+a*F a+a*a 表示文法GE能推導出用符號a, +, *, (和)構(gòu)成的所有算術表達式第40頁，共51頁，2022年，5月20日，20點31分，星期二3、句型與句子句型：設GS是文法，若S x，且xV* , 則稱x是文法GS的句型 句子：設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點31分，星期二4、文法G產(chǎn)生的語言定義：L(G)= xSx， S為文法開始符號， xVT* L(G)是文法GS描述的語言，也是該文法能推導出所有句子的集合。 文法 EE+E|E*E|(E)|id可以派生出多少個句子？ 文法G的作用語言的有窮描述以有限的規(guī)則描述無限的語言現(xiàn)象有限: 產(chǎn)生式集合、終結(jié)符集合、非終結(jié)符集合無限： 可以導出無窮多個句子 （注：L也可是有窮）第42頁，共51頁，2022年，5月20日，20點31分，星期二例： GS: S 0S

26、1, S 01 L(G)0n1n n1因為S0S100S11 0n1n重復利用規(guī)則S0S1第43頁，共51頁，2022年，5月20日，20點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點31分，星期二例 考慮文法G: E (E)a 這個文法有1個非終結(jié)符E、3個終結(jié)符(,),a這個文法生成語言: L(G)=a ,(a),(a),(a),.， 即：串由零個或多個左括號、后接一個a ，以及后面是與左括號相同數(shù)量的右括號組成。作為這些串的一個推導示例，我們給出(a)的一個推導： E (E) (E) (a)第45頁，共51頁，2022年，5月20日，20點31分，星期二練習：文法GS：（1）SaSBE