高級語言及其語法描述-有限自動機理論

1、1形式化的方法 用一整套帶有嚴格規(guī)定的符號體系來描述問題的方法。 Noan Chomsky 1956 形式語言理論 形式語言理論是編譯的理論基礎(chǔ) 編譯理論中用到的有關(guān)形式語言理論的最基本概念 字母表和符號串 文法和語言的形式定義 語法樹和文法的二義性 文法和語言的分類22.3 2.3 程序語言的語法描述程序語言的語法描述1. 1. 相關(guān)概念相關(guān)概念 考慮一個考慮一個有窮有窮 字母表字母表 字符集字符集 其中每一個元素稱為一個其中每一個元素稱為一個符號符號 上的上的符號串符號串 (也叫也叫字字) 是指由是指由中的中的符號符號所構(gòu)成所構(gòu)成的一個有窮序列的一個有窮序列空字，不包含任何符號的序列空字，

2、不包含任何符號的序列 * 上所有符號串的全體，包括上所有符號串的全體，包括例：若例：若 =a, b，則，則 *=, a, b, aa, ab, ba, bb, aaa, 3 ：空集，不包含任何元素的集合：空集，不包含任何元素的集合 * 的子集的子集U和和V的積定義為：的積定義為：(連接連接)UV= |U& V 注意，一般注意，一般UV VU, 但但(UV)W=U(VW) V自身的自身的n次次(連接連接)積積 Vn = VVVn V0 = 令令V* = V0V1 V2 V3 ，則令，則令V*是是V的閉包的閉包 V+ = VV* ，稱，稱V+是是V的正則閉包的正則閉包如如、分別表示符號串分

3、別表示符號串01和和110，則則表示符號串表示符號串01110，表示符表示符號串號串11001?？沾沁B接運算的恒等元素，空串是連接運算的恒等元素，s = s=s 4 例例 令令LA, B, , Z, a, b, , z，表示，表示L是由大、小寫是由大、小寫字母組成的字母表，字母組成的字母表，D0, 1, , 9，表示，表示D是由是由10個個數(shù)字組成的字母表。數(shù)字組成的字母表。L和和D可以分別看成是有窮的語言可以分別看成是有窮的語言集。用集合的運算作用于集。用集合的運算作用于L和和D所得到的所得到的6種新語言：種新語言： （1）LD是字母和數(shù)字的集合；是字母和數(shù)字的集合； （2）LD是所有一個

4、字母后隨一個數(shù)字的符號串的集合；是所有一個字母后隨一個數(shù)字的符號串的集合； （3）L6是由是由6個字母構(gòu)成的符號串的集合；個字母構(gòu)成的符號串的集合； （4）L*是所有字母串（包括是所有字母串（包括 ）的集合；）的集合； （5）L(LD )*是以字母開頭的所有字母數(shù)字串的集合；是以字母開頭的所有字母數(shù)字串的集合； （6）D+是不含空串的數(shù)字串的集合。是不含空串的數(shù)字串的集合。 從這個例子可以看出，從基本集合開始，利用集合上的從這個例子可以看出，從基本集合開始，利用集合上的運算，可以定義新的語言。運算，可以定義新的語言。52. 2. 上下文無關(guān)文法上下文無關(guān)文法文法：描述語言的語法結(jié)構(gòu)的文法：描述

5、語言的語法結(jié)構(gòu)的形式規(guī)則形式規(guī)則 (語法語法規(guī)則規(guī)則)。必須是必須是準確、易理解的，準確、易理解的，且應(yīng)且應(yīng)有強描述力有強描述力 應(yīng)應(yīng)有利于句子分析和翻有利于句子分析和翻譯譯 最好能夠最好能夠自動產(chǎn)生語法分析程序。自動產(chǎn)生語法分析程序。通常用符號通常用符號G表示表示(Grammar)。上下文無關(guān)文法：所定義的語法范疇是完全獨上下文無關(guān)文法：所定義的語法范疇是完全獨立于這種范疇可能出現(xiàn)的環(huán)境的，即是和立于這種范疇可能出現(xiàn)的環(huán)境的，即是和其上下文無關(guān)的，不同于自然語言。其上下文無關(guān)的，不同于自然語言。6例：英文例句分析例：英文例句分析 He gave me a book.設(shè)“” 為“由組成”或“定

6、義為”，則有語法規(guī)則： He me a gave book7推導(dǎo)He gave me a book 的語法的合法性。 He He He gave He gave He gave me He gave me He gave me a He gave me a book語法正確8得到語法分析樹: Hegavemeabook9 上下文無關(guān)文法的定義：上下文無關(guān)文法的定義： 一個上下文無關(guān)文法一個上下文無關(guān)文法G是一個四元式是一個四元式 G=(VT，VN，S，P)，其中，其中VT：終結(jié)符集合：終結(jié)符集合(非空非空)VN：非終結(jié)符集合：非終結(jié)符集合(非空非空)，且，且VT VN=S：文法的開始符號：文法

7、的開始符號，S VNP：產(chǎn)生式集合：產(chǎn)生式集合(有限有限)，每個產(chǎn)生式形式為每個產(chǎn)生式形式為P， P VN， (VT VN)*開始符開始符S至少必須在某個產(chǎn)生式的左部出現(xiàn)至少必須在某個產(chǎn)生式的左部出現(xiàn)一次。一次。10上下文無關(guān)文法上下文無關(guān)文法G包括四個組成部分：包括四個組成部分：一組一組終結(jié)符號終結(jié)符號：組成語言的基本符號，不可再：組成語言的基本符號，不可再分，如基本字、標識符、常數(shù)等。分，如基本字、標識符、常數(shù)等。一組一組非終結(jié)符號非終結(jié)符號：規(guī)則中用尖括號括起來的符：規(guī)則中用尖括號括起來的符號，表示一些語法成分，可以推導(dǎo)出其他號，表示一些語法成分，可以推導(dǎo)出其他的語法成分的語法成分,表示

8、一定符號串的集合表示一定符號串的集合11一個一個開始符號開始符號：特殊的非終結(jié)符，程序語言中，：特殊的非終結(jié)符，程序語言中，最終感興趣的是最終感興趣的是“程序程序”。一組一組產(chǎn)生式產(chǎn)生式：定義語法范疇的書寫規(guī)則，：定義語法范疇的書寫規(guī)則，A，A是一個非終結(jié)符，稱左部符號，是一個非終結(jié)符，稱左部符號， 稱為稱為產(chǎn)生式的右部，是由終結(jié)符號或產(chǎn)生式的右部，是由終結(jié)符號或|與非終結(jié)與非終結(jié)符號組成的一個符號串。產(chǎn)生式符號組成的一個符號串。產(chǎn)生式A稱為稱為關(guān)于關(guān)于A的一條產(chǎn)生規(guī)則。的一條產(chǎn)生規(guī)則。這種表示法稱這種表示法稱巴科斯范式巴科斯范式，簡稱，簡稱BNF范式范式。有的書用。有的書用“:=”代替代替“

9、”。12對于一個語法范疇，有時需幾個產(chǎn)生式，特對于一個語法范疇，有時需幾個產(chǎn)生式，特別需含遞歸的產(chǎn)生式。別需含遞歸的產(chǎn)生式。 例，定義只含+，*的算術(shù)表達式的文法 G=， 其中，P由下列產(chǎn)生式組成：E iE E+EE E*EE (E)13 幾點規(guī)定：幾點規(guī)定： P 1 P 2 可縮寫為可縮寫為 P 1| 2| n P n 其中，其中，“|”讀成讀成“或或”，稱為，稱為P的一個候選式。的一個候選式。 表示一個文法時，通常只給出開始符號和產(chǎn)生式，表示一個文法時，通常只給出開始符號和產(chǎn)生式，如上例，可表示為：如上例，可表示為：G(E)： E i | E+E | E*E | (E)合并：E i | E

10、AE | (E)A +|14 上下文無關(guān)文法如何定義語言上下文無關(guān)文法如何定義語言: :從文法的開始符從文法的開始符號出發(fā)號出發(fā), ,反復(fù)連續(xù)使用產(chǎn)生式反復(fù)連續(xù)使用產(chǎn)生式, ,對左邊的非終結(jié)對左邊的非終結(jié)符進行替換和展開符進行替換和展開 直接推導(dǎo)直接推導(dǎo)：又稱一步推導(dǎo)：又稱一步推導(dǎo)( (用用 符號符號=表示表示),),就是就是用某條規(guī)則的右部去替換該規(guī)則的左部用某條規(guī)則的右部去替換該規(guī)則的左部 連續(xù)使用某個產(chǎn)生式右部去替換左部某個非終連續(xù)使用某個產(chǎn)生式右部去替換左部某個非終結(jié)符的過程結(jié)符的過程, ,得到的連續(xù)序列稱為推導(dǎo)得到的連續(xù)序列稱為推導(dǎo), ,從從 到我是大學(xué)生是一個到我是大學(xué)生是一個推導(dǎo)

11、推導(dǎo). .15約約 定定大寫字母大寫字母A, B, C, 或漢語詞組代表非終結(jié)符號；或漢語詞組代表非終結(jié)符號；小寫字母小寫字母a, b, c, 代表終結(jié)符；代表終結(jié)符； , , 等代表由終結(jié)符和非終結(jié)符組成的符號串。等代表由終結(jié)符和非終結(jié)符組成的符號串。16 定義：稱定義：稱 A 直接推出直接推出，即，即 A 僅當僅當A 是一個產(chǎn)生式，是一個產(chǎn)生式， 且且 ， (VT VN)* 。例：例：S-01, 0S-01, 0S S0=00=001010(0(直接推導(dǎo)直接推導(dǎo) , , ) ) v v直接推導(dǎo)直接推導(dǎo)出出w,w,也稱也稱w w直接歸約直接歸約到到v,v, 記作記作 v v w w 。直接推

12、導(dǎo)直接推導(dǎo)就是用產(chǎn)生式的右部替換產(chǎn)生式的左部就是用產(chǎn)生式的右部替換產(chǎn)生式的左部的過程的過程直接歸約直接歸約就是用產(chǎn)生式的左部替換產(chǎn)生式的右部就是用產(chǎn)生式的左部替換產(chǎn)生式的右部的過程的過程17 如果如果 1 2 n，則我們稱這個序列，則我們稱這個序列是從是從 1到到 n的一個的一個推導(dǎo)推導(dǎo)。若存在一個從。若存在一個從 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)18 1n，從，從 1出發(fā)，經(jīng)一步或若干步，可出發(fā)，經(jīng)一步或若干步，可推導(dǎo)出推導(dǎo)出 n， 1+

13、 1n，從，從 1出發(fā)，經(jīng)出發(fā)，經(jīng)0步或若干步，可推步或若干步，可推導(dǎo)出導(dǎo)出 n ， 0 故故 1n，相當于，相當于 = 或或 +19三種推導(dǎo)的比較 直接推導(dǎo)（直接推導(dǎo)（）的長度為）的長度為1 直接推導(dǎo)序列（直接推導(dǎo)序列（ +）的長度）的長度n1 廣義推導(dǎo)（廣義推導(dǎo)（ *）的長度）的長度020 例例 : G = (E, i, +, *, (, ) , P , E) (1.1) P： E E + E | E * E | ( E ) | i 表達式表達式(i)和和(i+i)*i的推導(dǎo)：的推導(dǎo)：E (E) (i)E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i

14、 + i)*i E E 0步推導(dǎo)步推導(dǎo) E (i + i)*i 6步推導(dǎo)步推導(dǎo) E (i + i)*i 6步推導(dǎo)步推導(dǎo) E (E) 直接推導(dǎo)直接推導(dǎo)*21句型、句子、語言的定義q句型和句子句型和句子設(shè)有文法設(shè)有文法GSGS，若符號串，若符號串是從開始符推導(dǎo)是從開始符推導(dǎo)出來的出來的, ,即即 S S =* * ，則稱，則稱是文法是文法G G的的句型句型。 若若僅由終結(jié)符組成僅由終結(jié)符組成, ,即即 S S =* * ，且，且VVT T* *，則稱則稱是文法是文法G G的的句子句子。例例 文法文法GSGS： S0S1S0S1， S01S01因為因為S S 0 0S S1 1 00 00S S11

15、 11 000 000S S111 111 0000111100001111所以所以S,S,0S1 ,00S11 ,000S111,000011110S1 ,00S11 ,000S111,00001111都是都是G G的句型的句型0000111100001111是是G G的句子的句子22q語言的定義語言的定義由文法由文法G G生成的語言記為生成的語言記為L(G),L(G),它是文法它是文法G G的一切句的一切句子的集合子的集合, ,即即 L(G)=x|S L(G)=x|S =+ +x x，且，且 xVxVT T* * 例例 文法文法G G： S0S1S0S1， S01S01S0S1 00S11

16、 03S13 0n-1S1n-1 0n1nL(G)=0L(G)=0n n1 1n n|n1|n1q文法和語言的關(guān)系：文法和語言的關(guān)系：文法文法G G生成的每個串都在生成的每個串都在L(G)L(G)中中L(G)L(G)中的每個串確實能被中的每個串確實能被G G生成生成23根據(jù)文法，可以通過推導(dǎo)得到該文法相應(yīng)的語言；根據(jù)文法，可以通過推導(dǎo)得到該文法相應(yīng)的語言；例：例：GE E：EE+T|TEE+T|TTTTTF|FF|F F(E)|aF(E)|aE E E+T T+T F+T a+T a+TF a+FF a+aF a+aa表示一切能用符號表示一切能用符號a，+，(，)構(gòu)成的算術(shù)表達式構(gòu)成的算術(shù)表達

17、式有了語言的要求，也可以為該語言設(shè)計文法有了語言的要求，也可以為該語言設(shè)計文法例：若語言由例：若語言由0、1符號串組成，串中符號串組成，串中0和和1的個數(shù)相同，的個數(shù)相同，構(gòu)造其文法為：構(gòu)造其文法為：A 0B|1CB 1|1A|0BBC 0|0A|1CC24 例：文法例：文法(A,B,S,a,b,c,P,S) S-Ac|aB A-ab B-bc寫出寫出(G)的全部元素的全部元素 L(G) = abc25例例1：考慮文法：考慮文法G1：SbA AaA|a定義了一個什么語言定義了一個什么語言分析：分析：SbAbaSbAbaAbaaSbAbaA.baa.所以：所以：L(G1)=ban | n1l得到

18、一個語言，是通過利用所有的侯選式推導(dǎo)出所得到一個語言，是通過利用所有的侯選式推導(dǎo)出所有句子，構(gòu)成一個集合。有句子，構(gòu)成一個集合。L(G1) = 以以b開頭后跟一個或多個開頭后跟一個或多個a的串的串26推導(dǎo)例題2e.g. 文法產(chǎn)生的語言文法產(chǎn)生的語言L(G2)=ambn|m,n 1L(G3) = anbn|n 1G2: S A B A a A | a B b B | bG3: S a S b | ab27e.g. 文法產(chǎn)生的語言文法文法G2對句子對句子aaabb的推導(dǎo)：的推導(dǎo)：S = A B A B S A B = a A B a A B A a A = a a A B a a A B A a

19、A = a a a B a a a B A a = a a a b B a a a b B B b B = a a a b b a a a b b B bA= aB = abA= Ab = ab S A B A a A | a B b B | b28e.g. 文法產(chǎn)生的語言文法文法G3對句子對句子aaaabbbb的推導(dǎo)：的推導(dǎo)：S = a S b a S b S a S b = a a S b b a a S b b S a S b = a a a S b b b a a a S b b b S a S b = a a a a b b b b a a a a b b b b S a bS a

20、S b | ab29例例4：文法：文法G3(A)：A c|AbG3(A)的語言的語言?L(G3)=c，cb，cbb，以以c開頭，后繼若干個開頭，后繼若干個b30 從一個句型到另一個句型的推導(dǎo)往往不唯從一個句型到另一個句型的推導(dǎo)往往不唯一。一。 E+Ei+Ei+i E+EE+ii+i 最左推導(dǎo)最左推導(dǎo)：任何一步：任何一步 都是對都是對 中的最中的最左非終結(jié)符進行替換。左非終結(jié)符進行替換。 最右推導(dǎo)最右推導(dǎo)：任何一步：任何一步 都是對都是對 中的最中的最右非終結(jié)符進行替換。右非終結(jié)符進行替換。31舉例 例例: 文法文法GS: SAB AA0|1B B0|S1 請給出句子請給出句子101001的最左

21、和最右推導(dǎo)。的最左和最右推導(dǎo)。 最左推導(dǎo)：最左推導(dǎo)： S AB 1B B10B 10S1 10AB1 101BB1 1010B1 101001 最右推導(dǎo)：最右推導(dǎo)： S AB AS1AAB1 AA01 A1B01 A1001 1B1001 101001323. 3. 語法分析樹與二義性語法分析樹與二義性語法樹語法樹(推導(dǎo)樹推導(dǎo)樹Parse Tree)作用作用:直觀地描述上下文無關(guān)文法的句型直觀地描述上下文無關(guān)文法的句型推導(dǎo)過程。給定文法推導(dǎo)過程。給定文法G=(VN,VT,P,S)，對，對于于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹樹33語法樹的相關(guān)概念 結(jié)點：每個樹

22、的結(jié)點對應(yīng)于一個符號。結(jié)點的名字就結(jié)點：每個樹的結(jié)點對應(yīng)于一個符號。結(jié)點的名字就是該符號。是該符號。 邊：兩個結(jié)點之間的連線。邊：兩個結(jié)點之間的連線。 根結(jié)點：沒有邊進入的結(jié)點。根結(jié)點：沒有邊進入的結(jié)點。 分支：某個結(jié)點向下射出的邊和其結(jié)點稱為分支。分支：某個結(jié)點向下射出的邊和其結(jié)點稱為分支。（父子結(jié)點，兄弟結(jié)點）（父子結(jié)點，兄弟結(jié)點） 子樹：語法樹的某個結(jié)點和它向下射出的部分子樹：語法樹的某個結(jié)點和它向下射出的部分 末端結(jié)點：沒有向下射出的邊的結(jié)點成為末端結(jié)點。末端結(jié)點：沒有向下射出的邊的結(jié)點成為末端結(jié)點。在相對于句型的語法樹中，末端結(jié)點可能是非終結(jié)符在相對于句型的語法樹中，末端結(jié)點可能是非

23、終結(jié)符號。號。34語法樹的概念 定義：語法樹的結(jié)點由符號組成。根結(jié)點對定義：語法樹的結(jié)點由符號組成。根結(jié)點對應(yīng)于識別符號。只有非終結(jié)符號對應(yīng)的結(jié)點應(yīng)于識別符號。只有非終結(jié)符號對應(yīng)的結(jié)點有子結(jié)點。并且，一個結(jié)點和它的子結(jié)點分有子結(jié)點。并且，一個結(jié)點和它的子結(jié)點分別對應(yīng)于文法中的一個規(guī)則的左部和右部。別對應(yīng)于文法中的一個規(guī)則的左部和右部。 引入語法樹的意義：作為識別句子的輔助工引入語法樹的意義：作為識別句子的輔助工具，語法樹可以表示句子的結(jié)構(gòu)。這一點對具，語法樹可以表示句子的結(jié)構(gòu)。這一點對于其后的語義分析有非常重要的意義。于其后的語義分析有非常重要的意義。35語法樹的特征 給定文法給定文法G，G=

24、(VN,VT,P,S)，對于，對于G的任何句型都能構(gòu)造與之關(guān)的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹（推導(dǎo)樹）。這棵樹具有下列特征：聯(lián)的語法樹（推導(dǎo)樹）。這棵樹具有下列特征：1、根結(jié)點的標記是、根結(jié)點的標記是開始符號開始符號S；2、每個結(jié)點的標記都是、每個結(jié)點的標記都是V中的一個符號；中的一個符號；3、若一棵子樹的根結(jié)點為、若一棵子樹的根結(jié)點為A，且其所有直接子孫的標記從左向，且其所有直接子孫的標記從左向右的排列次序為右的排列次序為A1A2AR，那么，那么 A A1A2.AR一定是一定是P中的一中的一條規(guī)則；條規(guī)則；4、若一標記為、若一標記為A的結(jié)點至少有一個除它以外的子孫，則的結(jié)點至少有一個除它以

25、外的子孫，則AVN5、若樹的所有葉結(jié)點上的標記從左到右排列為字符串、若樹的所有葉結(jié)點上的標記從左到右排列為字符串w，則，則w是是文法文法G的的句型句型；若；若w中僅含中僅含終結(jié)符號終結(jié)符號，則，則w為文法為文法G所產(chǎn)生的所產(chǎn)生的句句子子。36從推導(dǎo)構(gòu)造語法樹 方法：把識別符號做方法：把識別符號做為根結(jié)點，對每一個為根結(jié)點，對每一個直接推導(dǎo)畫一個分支，直接推導(dǎo)畫一個分支，分支的名字是直接推分支的名字是直接推導(dǎo)中被替換的非終結(jié)導(dǎo)中被替換的非終結(jié)符號，直到再無分支符號，直到再無分支可畫結(jié)束?？僧嫿Y(jié)束。 例如：推導(dǎo)S AB AcBd Accdd abccddSBBdbaAcdc37語法樹的構(gòu)造過程S

26、AB AcBd Accdd abccddSSBASBB dAcSBB dAcdcSBB dbaAcdc（1）（2）（3）（5）（4）38從語法樹構(gòu)造推導(dǎo) 方法：從分支建立直接推導(dǎo)，然后從語法方法：從分支建立直接推導(dǎo)，然后從語法樹中剪去之這個分支，直到無分支可剪。樹中剪去之這個分支，直到無分支可剪。 語法樹表明了在推導(dǎo)過程中使用了哪條規(guī)語法樹表明了在推導(dǎo)過程中使用了哪條規(guī)則和使用在哪個非終結(jié)符號上，但它并沒則和使用在哪個非終結(jié)符號上，但它并沒有表明使用規(guī)則的順序。有表明使用規(guī)則的順序。 一棵語法樹可能對應(yīng)不止一種推導(dǎo)。一棵語法樹可能對應(yīng)不止一種推導(dǎo)。一棵語法樹是不同推導(dǎo)過程的共性抽象。一棵語法樹

27、是不同推導(dǎo)過程的共性抽象。39從語法樹構(gòu)造推導(dǎo)的過程 例如文法GS： S AB A aAb|ab B cBd|cd 存在下面的推導(dǎo)可能： S AB AcBd (4) (3) Accdd abccdd (2) (1) S AB abB abcBd abccdd（從后往前看）SBBdbaAcdc(1)(2)(3)(4)40文法G：EE+E|EE|（E）|i句子 ii+i 對應(yīng)的語法樹兩個不同的最左推導(dǎo)：兩個不同的最左推導(dǎo)：推導(dǎo)推導(dǎo)1：E E+E EE+E iE+E ii+E ii+i推導(dǎo)推導(dǎo)2：E EE iE iE+E ii+E ii+iiEE+EEEiiEEEiEE+ii文法的二義性文法的二義性

28、(Ambiguity)41定義定義 如果一個文法存在如果一個文法存在某個句子某個句子對應(yīng)兩棵不對應(yīng)兩棵不同的語法樹，則說這個文法是二義的。同的語法樹，則說這個文法是二義的。 二義性文法存在某個句子二義性文法存在某個句子, ,它它有兩個不有兩個不同的最左（右）推導(dǎo)同的最左（右）推導(dǎo)42 例例 設(shè)設(shè)if語句語句S的文法的文法G=(E，A，S，if，then，else，S，P)，其中，其中P為：為： Sif E then S （1） S if E then S else S （2） SA （3） 證明該文法是二義的。證明該文法是二義的。 由文法有推導(dǎo)：由文法有推導(dǎo)：S if E then S if

29、E then if E then S else S 同樣也有推導(dǎo)：同樣也有推導(dǎo)：S if E then S else S if E then if E then S else S 對于同一個句型對于同一個句型if E then if E then S else S，由于應(yīng)用規(guī)則的順序不同，得到了兩個不同的推由于應(yīng)用規(guī)則的順序不同，得到了兩個不同的推導(dǎo)，所以該文法是二義文法。導(dǎo)，所以該文法是二義文法。43為什么要避免文法產(chǎn)生二義性？ 二義性的文法將給編譯程序的執(zhí)行帶來問二義性的文法將給編譯程序的執(zhí)行帶來問題。當編譯程序?qū)Χx性文法生成的句子題。當編譯程序?qū)Χx性文法生成的句子結(jié)構(gòu)進行語法分析時，

30、就會產(chǎn)生兩種甚至結(jié)構(gòu)進行語法分析時，就會產(chǎn)生兩種甚至更多種不同的理解。語法結(jié)構(gòu)上的不確定更多種不同的理解。語法結(jié)構(gòu)上的不確定性，必將導(dǎo)致語義處理上的不確定性。因性，必將導(dǎo)致語義處理上的不確定性。因此，希望描述語言的文法是無二義性的。此，希望描述語言的文法是無二義性的。44如何消除文法的二義性？(1) 方法一：不改變文法中原有的語法規(guī)則，僅加進一方法一：不改變文法中原有的語法規(guī)則，僅加進一些語法的非形式規(guī)定。些語法的非形式規(guī)定。 如如1：對于文法對于文法 GE: E i E E+E E E*E E (E) 規(guī)定運算符優(yōu)先順序和結(jié)合律，即規(guī)定運算符優(yōu)先順序和結(jié)合律，即*優(yōu)先于優(yōu)先于+，+、*服從左

31、結(jié)合。服從左結(jié)合。 如如2：Pascal中二義性的消除是通過約定，如在符中二義性的消除是通過約定，如在符合合if 語句中，語句中，else子句總是屬于最近的尚無子句總是屬于最近的尚無else子句子句的那個的那個if語句。語句。45如何消除文法的二義性？(2) 方法二：構(gòu)造一個等價的無二義性的文法，方法二：構(gòu)造一個等價的無二義性的文法，即把排除二義性的規(guī)則合并到原有文法中，即把排除二義性的規(guī)則合并到原有文法中，改寫原有的文法。改寫原有的文法。 如文法如文法 G(E)： E i|E+E|E*E|(E) 將運算符的優(yōu)先順序和結(jié)合規(guī)則加到原有文將運算符的優(yōu)先順序和結(jié)合規(guī)則加到原有文法中，則可構(gòu)造無二義

32、性的文法法中，則可構(gòu)造無二義性的文法 46二義文法：G(E)： E i|E+E|E*E|(E)表達式表達式 項項|表達式表達式+項項項項 因子因子 | 項項*因子因子因子因子 (表達式表達式) | i無二義文法：無二義文法： G(E)：E T | E+T T F | T*F F (E) | i47)EEEFFTTTTi+*(EFiiE T F (E) (E+T) (T+T) (T*F+T) (F*F+T) (i*F+T) (i*i+T) (i*i+F) (i*i+i)考慮句子考慮句子(i*i+i)48上下文無關(guān)文法限制：上下文無關(guān)文法限制：(化簡后化簡后) 不存在任何形如不存在任何形如PP的產(chǎn)

33、生式的產(chǎn)生式(多余多余) 每個非終結(jié)符每個非終結(jié)符P必須都有用處必須都有用處b. 必須存在終結(jié)符串必須存在終結(jié)符串 ，使，使P，即，即P不不存在永不終結(jié)的回路。存在永不終結(jié)的回路。*TVa. 從從S出發(fā)，存在出發(fā)，存在SP *+49 文法G（S）: S Bd A Ad|d B Cd |Ae C Ce D e 文法G（S）: S Bd A Ad|d B Ae504.4.形式語言概述形式語言概述喬姆斯基將其分為四類，喬姆斯基將其分為四類，0, 1, 2, 3，與上下文無關(guān)，與上下文無關(guān)文法一樣，它們都由四部分組成，差別在于對產(chǎn)生式施文法一樣，它們都由四部分組成，差別在于對產(chǎn)生式施加不同的限制。加不

34、同的限制。v0型文法（型文法（PSG） 0型語言或短語結(jié)構(gòu)語言型語言或短語結(jié)構(gòu)語言v1型文法（型文法（CSG） 1型語言或上下文有關(guān)語言型語言或上下文有關(guān)語言v2型文法（型文法（CFG） 2型語言或上下文無關(guān)語言型語言或上下文無關(guān)語言v3型文法（型文法（RG）3型語言或正則（正規(guī)）語言型語言或正則（正規(guī)）語言510型文法型文法(短語文法，圖靈機短語文法，圖靈機) ：對文法對文法G，如果它的，如果它的每個產(chǎn)生式每個產(chǎn)生式 是這樣的一種結(jié)構(gòu)：是這樣的一種結(jié)構(gòu)：(VNVT)* 且至少含有一個非終結(jié)符且至少含有一個非終結(jié)符(VN VT)*0型文法相應(yīng)的語言為型文法相應(yīng)的語言為0型語言，或稱遞歸可枚舉型

35、語言，或稱遞歸可枚舉集，它的識別系統(tǒng)是圖靈（集，它的識別系統(tǒng)是圖靈（Turing）機。）機。如文法如文法G，其中，其中VN=A,B,S VT=0,1 P= S0AB 1B0 BSA|01 A1SB1 A0S0B 52q1型文法型文法(上下文有關(guān)上下文有關(guān))：它是它是0型文法的特例，對型文法的特例，對P中的任一產(chǎn)生式中的任一產(chǎn)生式，都，都|， 僅僅僅僅 S除除外外,但但S不得出現(xiàn)在任何產(chǎn)生式的右部。不得出現(xiàn)在任何產(chǎn)生式的右部。q1型文法相應(yīng)的語言稱為型文法相應(yīng)的語言稱為1型語言或上下文有關(guān)型語言或上下文有關(guān)語言，它的識別系統(tǒng)是線性有界自動機。語言，它的識別系統(tǒng)是線性有界自動機。q例例 文法文法G

36、SGS： SaSBE SaSBE SaBESaBEEBBEEBBEaBab aBab bBbb bBbb bEbe bEbe eEeeeEee53 文法文法G的每一個產(chǎn)生式均為下列形式：的每一個產(chǎn)生式均為下列形式：A其中其中，V*，A Vn, V+ 它表示當它表示當A的上文為的上文為 且下文為且下文為時可把時可把A替替換成換成 ，因此稱，因此稱1型文法為上下文有關(guān)文法。型文法為上下文有關(guān)文法。 滿足前頁定義的長度限制，但它更明確地表滿足前頁定義的長度限制，但它更明確地表達了上下文有關(guān)的特性，即達了上下文有關(guān)的特性，即A必須在的上下必須在的上下文環(huán)境中才能被替換。文環(huán)境中才能被替換。54q2型文

37、法（上下文無關(guān)文法）型文法（上下文無關(guān)文法） ：它是：它是1型文法的特型文法的特例，對任一產(chǎn)生式例，對任一產(chǎn)生式，都有，都有VN N ， (VN NVT T)*q2型文法相應(yīng)的語言稱為型文法相應(yīng)的語言稱為2型語言或上下文無關(guān)語言。型語言或上下文無關(guān)語言。它的識別系統(tǒng)是下推自動機。它的識別系統(tǒng)是下推自動機。q例例 文法文法GS： SAB ABS|0 BSA|12型文法產(chǎn)生式的一般形式是型文法產(chǎn)生式的一般形式是: A ，它表示不管，它表示不管A的上下文如何都可把的上下文如何都可把A替換成替換成 ，因此被稱為上，因此被稱為上下文無關(guān)文法。下文無關(guān)文法。通常程序設(shè)計語言的文法，可用通常程序設(shè)計語言的文法，可用2型文法來描述，型文法來描述，因此我們重點研究因此我們重點研究2型文法。如型文法。如C，Pascal 55q3型文法型文法(正規(guī)文法正規(guī)文法)：它是它是2型文法的特例，型文法的特例，任一產(chǎn)生任一產(chǎn)生式式的形式都為的形式都為 AaB或或Aa，其中，其中A ，BVN N ，aVT Tq這種形式的這種形式的3型文法也叫型文法也叫右線性文法右線性文法。3型文法還有一種型文法還有一種形式，限定形式，限定P