編譯原理第2章文法和語言的基本知識課件

1、第2章文法和語言的基本知識本章是編譯原理課程的理論基礎，要求掌握形式語言的基本術(shù)語和概念,重點掌握短語、直接短語、句柄、素短語、規(guī)范推導、規(guī)范歸約。掌握文法和語言的定義，文法的二義性與遞歸性的判斷方法及句型的分析方法，文法分類。熟練使用文法定義程序設計語言的單詞和語法成分。對形式語言的理論有一個初步認識。教學目標Thursday, July 28, 20222.1 字母表和符號串的基本概念2.2 文法和語言的形式定義2.3 句型的分析2.4 文法和語言的分類教學內(nèi)容Thursday, July 28, 2022程序設計語言是一種形式語言，與自然語言既有相似的性質(zhì)又有本質(zhì)的不同。最主要的區(qū)別是：

2、形式語言的規(guī)則簡單、嚴格、無例外、無二義性。編譯程序的正確轉(zhuǎn)換建立在對程序設計語言的精確定義和描述基礎上。語法文法是描述語言語法的形式規(guī)則語義語言中各語句的含義語用從使用者的角度對語言的描述Thursday, July 28, 2022字母表：符號的非空有限集 例：=0，1 2.1字母表和符號串符號：字母表中的元素 例： 0，1符號串：由字母表中的符號組成的任何有窮序列 例：0,1, 01, 10, 011，.空符號串：無任何符號的符號串，用表示 C語言的字母表 Aa,b,0,1,9, +,_/, ( , ), = if, else,for.不對如=if,else,for,while符號就是字

3、符，對嗎？Thursday, July 28, 2022符號串的前綴和后綴: 從符號串s的尾部刪去若干個(包括0個)符號之后所余下的部分稱為s的前綴，0，01及011都是符號串011的前綴，1，11及011都是符號串011的后綴符號串集合：若集合A中的一切元素都是某字母表上的符號串，則稱A為該字母表上的符號串集合。例：=a，b，c A= a,aa,acThursday, July 28, 2022符號串的運算符號串x和y的連接:是把y的符號寫在x的符號之后得到的符號串xy 例如x=00，y=11，則xy=0011對于任意一個符號串s，有s= s=s 符號串的連接運算Thursday, July

4、 28, 2022符號串自身連接n次得到的符號串sn 定義為 ssss ，包括n個s，稱為符號串的冪運算 s0=，s1=s，s2=ss，設s=01，則s0=s1=01s2=0101 符號串的冪運算Thursday, July 28, 2022設A、B為符號串集合，則A和B的乘積定義為：AB xy |xA,yB例如，Aa,b，B=c,d則AB=符號串集合的乘積ac,ad,bc,bd Thursday, July 28, 2022有符號串集合A，定義A0 =, A1=A, A2=AA, A3=AAA, AnAn-1A=AAn-1 ，n0例如，A0,1，則A0=A1=A2=A3=符號串集合的冪運算0

5、,100,01,10,11000,001,010,011,100,101,110,111Thursday, July 28, 2022設A是符號串集合，定義 A A1 A2 A3 An 稱為集合A的正閉包。 A* A0 A稱為集合A的閉包。例：A=x,y A？ A* ？x,y, xx,xy,yx,yy , xxx,xxy,xyx,xyy, A1 A2 A3, x,y, xx,xy,yx,yy , xxx,xxy,xyx,xyy, A0 A1 A2 A3符號串集合的閉包運算Thursday, July 28, 2022的閉包*表示上的一切符號串（包括）組成的集合的正閉包+表示上的除外的所有符號串

6、組成的集合例：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, +=a,b,aa,ab,ba,bb,aaa,aab,Thursday, July 28, 2022若A為某語言的字母表 Aa,b,0,1,9, +,_/, ( , ), = if, else,for.B為單詞集 B =if, else,for, 則B A* 。語言的句子是定義在B上的符號串。若令C為句子集合，則C B * , 程序 C為什么對符號、符號串、符號串集合以及它們的運算感興趣？Thursday, July 28, 2022語言是由句子組成的集合，是由一組符號所構(gòu)成的集合字母表上的一個語言是上的一些符號串的

7、集合字母表上的每個語言是*的一個子集集合a,aa,aaa,或表示為w|w*且w=an,n1 為字母表上的一個語言 例如：字母表=a,b ,*=,a,b,aa,ab,ba,bb,aaa,aab,集合ab,aabb,aaabbb,anbn,或表示為w|w*且w=anbn,n1為字母表上的一個語言Thursday, July 28, 20222.2文法和語言的形式定義 文法是對語言結(jié)構(gòu)的定義與描述。（或稱為“語法”）。:=“=”:=“+” | “*”:=“(”“)” | | | Thursday, July 28, 2022文法的直觀概念：以漢語中的“我是大學生”為例。 采用BNF來表示漢語句子的構(gòu)

8、成規(guī)則為： 句子：=主語謂語 主語：=代詞|名詞 代詞：=我|你|他 名詞：=王明|大學生|工人|英語 謂語：=動詞直接賓語 動詞：=是|學習 直接賓語：=代詞|名詞 根據(jù)上述規(guī)則，“我是大學生”的構(gòu)成符合上述規(guī)則，而“我大學生是”不符合，我們說它不是句子。這些規(guī)則成為我們判別句子結(jié)構(gòu)合法與否的依據(jù)。換句話說，這些規(guī)則看成是一種元語言，用它描述漢語。這種的語言描述成為文法。 文法的四部分一組終結(jié)符號（語言的基本符號）一組非終結(jié)符號（語法單位）一個開始符號（一個特殊的非終結(jié)符號，最感興趣的語法單位）一組規(guī)則（也稱產(chǎn)生式或產(chǎn)生規(guī)則）Thursday, July 28, 2022文法的形式定義：P1

9、0的定義1.1例2-1，文法G=（ ， ，P，S）是描述標識符的文法，則其中： =標識符，字母，數(shù)字 =a,b,c.x,y,z,0,1,2,39 P = | a|b|c|.|z 0|1|2|.|9 S =Thursday, July 28, 2022賦值語句標識符表達式表達式表達式表達式標識符整數(shù)標識符表達式y(tǒng)=x+r*6y = x + r * 6Thursday, July 28, 2022 例：有一句子：“我是大學生” 。這是一個在語法、語義上都正確定句子，該句子的結(jié)構(gòu)（稱為語法結(jié)構(gòu)）是由它的語法決定的 。在本例中它為“主謂結(jié)構(gòu)”。如何定義句子的合法性？有窮語言：只需逐一列舉句子無窮語言：

10、使用文法定義句子的結(jié)構(gòu)，用適當條數(shù)的規(guī) 則把語言的全部句子描述出來。文法是以有窮的集 合刻劃無窮的集合的工具。文法的非形式定義Thursday, July 28, 2022 1.語法規(guī)則：我們通過建立一組規(guī)則，來描述句子的語法結(jié)構(gòu)。規(guī)定用“:=”表示“由組成”。:=:=| :=你|我|他:= 王民|大學生|工人|英語:=:=是|學習:=| 文法的BNF表示Thursday, July 28, 20222.由規(guī)則推導句子：有了一組規(guī)則之后，可以按照一定的方式用它們?nèi)ネ茖Щ虍a(chǎn)生句子。 推導方法：從一個要識別的符號開始推導，即用相應規(guī)則的右部來替代規(guī)則的左部，每次僅用一條規(guī)則去進行推導。 = = 這

11、種推導一直進行下去，直到所有帶的符號都由終結(jié)符號替代為止。Thursday, July 28, 2022 = = = 我 =我 =我是 =我是 =我是大學生:=:=| :=你|我|他:= 王民|大學生|工人|英語:=:=是|學習:=|推導方法：從一個要識別的符號開始推導，即用相應規(guī)則的右部來替代規(guī)則的左部，每次僅用一條規(guī)則去進行推導。Thursday, July 28, 2022例：有一英語句子：The big elephant ate the peanut.:=:= :=the:=big:=elephant:=:=ate:= :=peanutThursday, July 28, 2022 =

12、 = = the = the big = the big elephant = the big elephant = the big elephant ate = the big elephant ate = the big elephant ate the = the big elephant ate the peanut:=:= :=the:=big:=elephant | peanut:=:=ate:=Thursday, July 28, 2022上述推導可寫成 = the big elephant ate the peanut+說明： (1) 有若干語法成分同時存在時，我們總是從最左的

13、語法成 分進行推導，這稱之為最左推導，類似的有最右推導（一般推 導）。 (2) 從一組規(guī)則可推出不同的句子，如以上規(guī)則還可推出“大象吃象”、“大花生吃象”、“大花生吃花生”等句子，它們 在語法上都正確，但在語義上都不正確。 所謂文法是在形式上對句子結(jié)構(gòu)的定義與描述，而未涉及語義問題。Thursday, July 28, 2022例2-3，利用例2-2中的文法，推導出文法的句子012：最左推導：N =S =SD =SDD =DDD =0DD =01D =012最右推導：N =S =SD =S2 =SD2 =S12 =D12 =012在這里，N S為長度為1的推導， N SD為長度為2的推導N 0

14、12為長度為7的推導。其中，對于N S來說，S是N的直接推導，或N是S的直接歸約。一些規(guī)定： =推導 =規(guī)范推導 長度大于零的推導 長度可為零的推導 長度為n的推導 N SS SD|DD 0|1|2|9Thursday, July 28, 2022課堂作業(yè)：設有文法GS：Sa|（T）T T，S|S請給出句子（a,(a,a)的最左、最右推導。其最左推導為：S =（T）=（T，S）=（S，S）=（a，（T）=（a，（T，S）=（a，（S，S）=（a，（a，S）=（a，（a，a）其最右推導為：S =（T）=（T，S）=（T，（T）=（T，（T，S）=（T，（T，a）=（T，（S，a）=（T，（a，a

15、）=（S，（a，a）=（a，（a，a）=（a，S）Thursday, July 28, 2022文法GS=（VN，VT，P，S） VN ：非終結(jié)符號集 VT ：終結(jié)符號集 P： 產(chǎn)生式或規(guī)則的集合 S： 開始符號（識別符號） S VN ，S至少要在 一條規(guī)則中作為左部出現(xiàn)VVN VT稱為文法的字母表補: 規(guī)則的定義 : 或V+且至少有一個非終結(jié)符，而(VN VT)* 文法的形式定義Thursday, July 28, 2022G=(VT , VN, S, P)，其中:VN=表達式VT=+,*,(,),iS=表達式P=表達式表達式+表達式 表達式表達式*表達式 表達式(表達式) 表達式i 【例2

16、.1】程序語言中只含+、*運算的算術(shù)表達式，用i表示變量或常數(shù)，其文法可以表示為： 描述了表達式的語法規(guī)則 Thursday, July 28, 2022幾點說明：產(chǎn)生式左邊符號構(gòu)成集合VN ，且 S VN給定一個 文法，實際只需給出產(chǎn)生式集合，并指定識別符號G表達式:表達式表達式+表達式表達式表達式*表達式表達式(表達式)表達式iVN ：代表程序的語法成份，如“表達式”，它不會 出現(xiàn)在程序中VT ：會出現(xiàn)在程序中，如i+iThursday, July 28, 2022有些產(chǎn)生式具有相同的左部，可以和在一起GE：EE+E|E*E|(E)|i Thursday, July 28, 2022GS：

17、SL|SL|SDLa|b|zD0|1|9【例2.2】某種語言的標識符是以字母開頭的字母數(shù)字串，如果用L表示，D表示，用S表示字母數(shù)字串 描述了標識符的詞法規(guī)則 Thursday, July 28, 2022例：無符號整數(shù)的文法： G | 0 | 1 | 2 | 3 | | 9描述了無符號整數(shù)的詞法規(guī)則 Thursday, July 28, 2022說明：終結(jié)符集是輸入字符集，它是構(gòu)成單詞的最基本元素終結(jié)符集是經(jīng)詞法分析識別后的單詞集，如變量i,運算符+、*和分界符(、)，它們被視為語法分析中最基本元素 描述語法規(guī)則的文法GE：EE+E|E*E|(E)|i 描述詞法規(guī)則的文法GS：SL|SL|S

18、DLa|b|zD0|1|9Thursday, July 28, 2022文法的表示方法3.語法圖2. EBNF： 擴充的BNF的元符號： , :=, |, , , , (, ) 字母 字母 數(shù)字 數(shù)字 標識符無符號整數(shù)1. BNF的元符號： , :=, |Thursday, July 28, 2022推導的形式定義如果是文法G=(VT，VN，S，P)的一個產(chǎn)生式，V*，有符號串x，y滿足x=，y=, x y則稱y是x的直接推導，也可以說，y直接歸約到x，記作x y。直接推導：用產(chǎn)生式的右部替換產(chǎn)生式的左部直接歸約：用產(chǎn)生式的左部替換產(chǎn)生式的右部的過程 例：x S SD LD aD a1=yGS

19、：SL|SL|SDLa|b|zD0|1|9Thursday, July 28, 2022S=SD, 使用規(guī)則SSD，其中=；SD=LD,使用規(guī)則SL，其中=,=D；LD=aD,使用規(guī)則La，其中=,=D；aD=a1, 使用規(guī)則D1，其中=a,=。 GS：SL|SL|SDLa|b|zD0|1|9根據(jù)文法和推導的定義，可推出終結(jié)符號串如果是文法G=(VT，VN，S，P)的一個產(chǎn)生式，V*，有符號串x，y滿足x=，y=, x y則稱y是x的直接推導，也可以說，y直接歸約到x，記作x y。Thursday, July 28, 2022 1 1 0(6)=(1)=(3)(5)=(2) 當符號串已沒有非終

20、結(jié)符號時，推導就必須終止。因為終結(jié)符不可能出現(xiàn)在規(guī)則左部，所以將在規(guī)則左部出現(xiàn)的符號稱為非終結(jié)符號。例如：G (1) (2) (3) (4) 0 | 1 | 2 | 3 | | 9Thursday, July 28, 2022如果存在直接推導序列：x y0 y1 y2yn=y則稱這個序列是一個從x至y的長度為n（n0）的推導，或稱y歸約到x，記作x y。若有x y，或x=y，則記作x y。 = = * = 例：x S SD LD aD a1=yGS：SL|SL|SDLa|b|zD0|1|9 = 記作x y或記作x y * = 例：x S SD LD aD a1=yGS：SL|SL|SDLa|b

21、|zD0|1|9 = 記作x y或記作x y * = Thursday, July 28, 2022文法GS （1）句型：x是句型 S ,且 V*；（2）句子：x是句子 S , 且, VT*；（3）語言：L（GS）= | VT*,S ；+文法GS所產(chǎn)生的所有句子的集合*句子是所有終結(jié)符號組成的句型語言的形式定義GE：EE+E|E*E|(E)|i 句型：E+EE+E*EE+E*iE+i*i句子： i+ii*ii+i*i(i+i)*i Thursday, July 28, 2022 形式語言理論可以證明以下兩點： （1）G L（G）； （2）L(G)G1，G2，Gn； 已知文法，求語言，通過推導；

22、 已知語言，構(gòu)造文法，無形式化方法，更多是憑經(jīng)驗Thursday, July 28, 2022例：GS S := aSb |ab求其所產(chǎn)生的語言。若S := aSb | ，如何？L(GS)=anbn|n1L(GS)=anbn|n0已知文法，求語言，通過推導課堂練習1：GS S := bA A := aA|aL(GS)=ban|n1課堂練習2：GS S := AB A := aA|a B := bB|bL(GS)=ambn|m,n1Thursday, July 28, 2022例：abna|n1,構(gòu)造其文法 定義. G和G是兩個不同的文法，若 L(G) = L(G) , 則G和G為等價文法。若n

23、0，如何？課堂練習3：anbnci |n1,i 0,構(gòu)造其文法 GS： S AB A aAb|ab BcB| G1S： SaBa, Bb|bBG2S： SaBa, Bb|BbG1S： SaBa, B |bBG2S： SaBa, B |BbThursday, July 28, 2022例：構(gòu)造一個文法，使其描述的語言是無符號整數(shù)。 GS：SSD|DD0|1|2|3|4|5|6|7|8|9G | 0 | 1 | 2 | 3 | | 9Thursday, July 28, 2022編譯感興趣的問題是:給定x, G, 求x L(G) ?x算法1算法2x L(G) ?Gyn出錯處理停機= = Thurs

24、day, July 28, 20221.遞歸規(guī)則：規(guī)則右部有與左部相同的符號 左遞歸規(guī)則：AA 右遞歸規(guī)則：AA 自嵌入遞歸規(guī)則：AA遞歸文法2.遞歸文法：含有遞歸規(guī)則的文法，為直接遞歸文法ABaBAb GS：SL|SL|SDLa|b|zD0|1|9間接遞歸文法Thursday, July 28, 2022遞歸文法的優(yōu)點：可用有窮條規(guī)則，定義無窮語言 例：對于前面給出的無符號整數(shù)的文法是有遞歸文法，用12條規(guī)則就可以定義出所有的無符號整數(shù)。若不用遞歸文法，那將要用多少條規(guī)則呢？!GS：SSD|DD0|1|2|3|4|5|6|7|8|9Thursday, July 28, 2022左遞歸文法的缺

25、點：不能用自頂向下的方法來進行語法分析會造成死循環(huán)（后面將詳細論述）GE：Ei+i|i*i|(i+i)*i該文法所描述的語言為L(G)=i+i,i*i,(i+i)*i，無法表示無窮的表達式語言 Thursday, July 28, 20222.3句型的分析句型的分析： 是指識別輸入的符號串是否為某一文法的 句型(或句子)的過程 對于同一個句型或句子，可以通過不同的推導序列推導出來，這是因為在推導過程中所選擇的非終結(jié)符的次序不同 GE：EE+E|E*E|(E)|ii+i*i的推導序列有哪些？ Thursday, July 28, 2022最左(右)推導指對于一個推導序列中的每一直接推導，被替換的

26、總是當前符號串中的最左(右)非終結(jié)符號。最右推導也稱為規(guī)范推導。規(guī)范推導的逆過程，稱為最左歸約，也稱為規(guī)范歸約。用最左推導所推導出的句型稱為最左句型用最右推導所推導出的句型稱為最右句型，通常稱為規(guī)范句型規(guī)范推導與規(guī)范歸約Thursday, July 28, 2022賦值語句標識符表達式表達式表達式表達式標識符整數(shù)標識符表達式y(tǒng)=x+r*6語法分析的結(jié)果-語法樹語法樹與文法的二義性Thursday, July 28, 20221.語法樹：描述一個句子的語法結(jié)構(gòu)Thebigelephantatethepeanut語法成分（非終結(jié)符）單詞符號（終結(jié)符號)Thursday, July 28, 2022

27、語法樹：句子結(jié)構(gòu)的圖示表示法，它是一種有向圖，由結(jié)點和有向邊組成。 結(jié)點：符號 根結(jié)點：識別符號 中間結(jié)點：非終結(jié)符 葉結(jié)點：終結(jié)符或非終結(jié)符 有向邊：表示結(jié)點間的派生關系 SUVabcdThursday, July 28, 2022句型推導過程句型語法樹的生長過程 由推導構(gòu)造語法樹1從識別符號開始，逐步建立推導序列。由根結(jié)點開始，自上而下建立語法樹。Thursday, July 28, 2022例：G句型10= =0 0= 0=110=規(guī)范推導Thursday, July 28, 2022 由語法樹構(gòu)造推導2自下而上地修剪子樹的末端結(jié)點，直至把整棵樹剪掉（留根），每剪一次對應一次規(guī)約。從句型

28、開始，自右向左地逐步進行規(guī)約，建立推導序列。Thursday, July 28, 202201= = 0=10 0=規(guī)范規(guī)約與規(guī)范推導互為逆過程Thursday, July 28, 2022課堂練習：對于句子ii * i ，給出兩種不同的規(guī)范推導，并畫出語法樹定義:若一個文法的某句子存在兩個不同的最右(最左)推導，則該文法是二義性的，否則是無二義性的。2.文法的二義性GE：EE+E|E*E|(E)|i Thursday, July 28, 2022EEE+EE*iiiEEE*EE+iii這兩種不同的推導對應了兩種不同的語法樹(1) E=E+E=E+E*E =E+E*i =E+i*i = ii

29、* i(2) E= E*E = E*i = E+E*i = E+i*i = ii * iThursday, July 28, 2022若文法是二義性的，則在編譯時就會產(chǎn)生不確定性文法的二義性是不可判定的，即不可能構(gòu)造出一個算法，通過有限步驟來判定任一文法是否有二義性?？梢圆捎脙煞N途徑來解決文法的二義性問題 1不改變文法中原有的規(guī)則，僅加進一些語法的非形式規(guī)定。規(guī)定“*”運算優(yōu)先級高于“+”運算，且服從左結(jié)合 改寫文法，把排除二義性的規(guī)則合并到原有文法中2Thursday, July 28, 2022EiET+TF*iFTFi例:算術(shù)表達式的文法 E:= E+T | TT := T*F | FF

30、 := (E) | iGE：EE+E|E*E|(E)|i Thursday, July 28, 2022短語與句柄 P18定義：設G是一個文法，并設w=xuy 是該文法的一個句型。若*xy且+u，則稱u為句型w=xuy對非終結(jié)符的一個短語。若*xy且u，則稱u為句型w=xuy相對于非終結(jié)符的一個簡單(直接）短語。任何一個句型的最左簡單短語稱為柄短語（句柄）。含有終結(jié)符的短語，并且不存在也具有這種性質(zhì)真子串的短語稱為素短語。P72Thursday, July 28, 2022例：表達式文法G ： +| *| ()|i對句型i*()的推導為： * * i* i*() Thursday, July

31、28, 2022對應的推導樹為：表達式文法G ： +| *| ()|iThursday, July 28, 2022語法樹與短語使用推導樹計算句型（句子）的短語簡單、明了推導 *xy +u等價于：等價于： xy uThursday, July 28, 2022因此稱u是句型xuy(對)的一個短語等價于： xy u以 為子樹根的葉結(jié)點的全體Thursday, July 28, 2022若子樹高度為1，則u還是直接 短語，最左直接短語為句柄。若u是含有終結(jié)符的最小的短語，則為素短語，句型最左邊的素短語稱為最左素短語（P72）。例：上例的文法G 和句型i*()容易從推導樹中看出：短語：i, i*()

32、, ()直接短語：i，()句柄（左直接短語）：i素短語：i，()最左素短語：iThursday, July 28, 2022例，找出針對左邊文法的句型T+T*F+a的所有短語、簡單短語(直接短語)、素短語和句柄。此句型對應的分析樹為：EE+TE+TTT*FFa短語： 直接短語：句柄： E E + TE TT T * FT FF （E）F aTT*FT+T*FT+T*F+aaTT*FaT素短語：T*F a最左素短語：T*F Thursday, July 28, 2022課堂練習設有文法GE如下：EE+T|E-T|TTT*F|T/F|FF（E）|id 請給出句型（F+id)-T*(E-T)的所有短

33、語、簡單短語和句柄。EE-TTF（E）E+TTFFidT*F（E）E-T短語有：FidF+id(F+id)E-T（E-T）T*（E-T）（F+id)-T*(E-T)直接短語有：F,id, E-T句柄有：F素短語：id E-T 最左素短語：idThursday, July 28, 20222.4文法和語言的分類 形式語言(喬姆斯基)：通過抽象，對語言進行形式化描述用一組數(shù)學符號和規(guī)則來描述的語言稱為形式語言 *的任何子集稱作上的形式語言L（GS）= | VT*,S +由文法定義語言 文法和語言分類：0型、1型、2型、3型 這幾類文法的差別在于對產(chǎn)生式施加不同的限制。Thursday, July

34、28, 2022 0型語言：L0 0型文法稱為無約束短語結(jié)構(gòu)文法。規(guī)則的左部和右部都可以是符號串，一個短語可以產(chǎn)生另一個短語。 0型： P： := 其中V*且至少含有一個非終結(jié)符，V* Thursday, July 28, 20220型文法GS:SABS|ABABBAA0B1L(GS)=x|x是由n個01或10組成的二進制數(shù)字串，n1該文法產(chǎn)生的語言為Thursday, July 28, 2022SACaBCaaaCCBDBaBBaCBE aDDaADACaEEaAE例：0型文法GS：Thursday, July 28, 2022 1型文法 ： P： A := 其中 AVN， V*， V 注意

35、：規(guī)則的左邊的字符串長度右邊字符串長度 1型語言：L1稱為上下文敏感或上下文有關。也即只有在 、 這樣的上下文中才能把A改寫為Thursday, July 28, 2022SaSBESaBEBEbEaBab bBbb bEbeeEee例：1型（上下文有關）文法GS：SACaBCaaaCCBDBaBBaCBE aDDaADACaEEaAE例：0型文法GS：Thursday, July 28, 2022 2型： P： A:= 其中 A VN ， V* 2型語言：L2 稱為上下文無關文法。也即把A改寫為時，不必考慮上下文。Thursday, July 28, 2022例：2型（上下文無關）文法 文法

36、GS：SABABS|0BSA|1 SThursday, July 28, 20222型（上下文無關）文法 文法GS：S0A|1BA1S|1B0S|0該文法產(chǎn)生的語言為：L(GS)=anbn|n1Thursday, July 28, 2022（右線性） P： A:=a 或 A:=aB 其中 A、B VN a VT3型語言：L3 又稱正則語言. 3型文法稱為正則文法。它是對2型文法進行進一步限制。 左線性 和右線性文法是相互等價的 注意：每個產(chǎn)生式右邊至少有一個終結(jié)符出現(xiàn)（左線性） P： A:=a 或 A:=Ba 其中 A、B VN a VT 3型文法：Thursday, July 28, 202

37、2GS： S0A|1B|0 A0A|1B|0S B1B|1|0GI：I lTI lT lTT dTT lT d例：3型文法Thursday, July 28, 20223型文法(正則文法) GS： S0A|1B|0 A0A|1B|0S B1B|1|02型（上下文無關）文法GS：SBA A1S|1 B0S|01型（上下文有關）文法GS：SaSBESaBEBEbEaBab bBbb bEbeeEee0型文法GS： SACaB CBE CaaaC aDDa CBDB ADAC aBBa aEEaThursday, July 28, 2022有關文法的實用限制1、 若文法中有如U:=U的規(guī)則，則這就是

38、有害規(guī)則，它會引起二義性，而無任何用處。 例如存在U:=U， U:= a | b,則有兩棵語法樹：UaUUa文法中不能含有有害規(guī)則和多余規(guī)則Thursday, July 28, 2022 2、 多余規(guī)則：（1）某條規(guī)則U:=u的左部非終結(jié)符U（U不是識別符號），不在任何其他規(guī)則右部出現(xiàn)，即所有的推導始終不會用到此規(guī)則。（2）在推導句子的過程中，一旦使用了該規(guī)則，將推不出任何終結(jié)符號串。即該規(guī)則中含有推不出任何終結(jié)符號串的非終結(jié)符。 例如給定GS，若其中關于U的規(guī)則只有如下一條： U:=xUy 該規(guī)則是多余規(guī)則。若還有U:=a，則此規(guī)則并非多余若某文法中無有害規(guī)則或多余規(guī)則，則稱該文法是壓縮過的

39、。Thursday, July 28, 2022根據(jù)上述討論，L0 L1 L2 L30型文法可以產(chǎn)生L0、L1、L2、L3，但2型文法只能產(chǎn)生L2，不能產(chǎn)生L1。2型文法1型文法0型文法3型文法四種文法之間的逐級“包含”關系Thursday, July 28, 20222型文法（不確定的下推自動機）1型文法（不確定的界限自動機）0型文法（圖靈機）3型文法（有限自動機）形式語言與自動機Thursday, July 28, 2022圖靈機Thursday, July 28, 20222.5PL/0編譯程序概述PL/0編譯程序pcode解釋程序PL/0源程序pcode代碼PASCAL語言的子集，功能簡單，結(jié)構(gòu)清晰，可讀性強，具備了一般高級語言的必備部分Thursday, July 28, 2022PL/0語言的功能（1）賦值語句；（2）語句串，即beginend語句；（3）條件語句，即if語句；（4）循環(huán)語句，即while語句；（5）過程調(diào)用語句，即call語句；（6）輸入語句，即read語句；（7）輸出語句，即write語句。語句類型Thursday, July 28, 2022（1）常量說明（全局）（2）變量說明；（3）過程說明。說明類型數(shù)據(jù)類型整型Thursday, July 28, 2022標識符（