1、第第2章章 文法和語言的基本知識文法和語言的基本知識 形式語言理論是編譯的重要理論形式語言理論是編譯的重要理論基礎基礎。 本章主要介紹編譯理論中用到的本章主要介紹編譯理論中用到的形式語言理論的最基本概念形式語言理論的最基本概念 重點介紹如何采用形式化的方法重點介紹如何采用形式化的方法描述程序設計語言。描述程序設計語言。第第2章章 文法和語言的基本知識文法和語言的基本知識q字母表和符號串字母表和符號串q文法和語言的形式定義文法和語言的形式定義q短語、直接短語和句柄短語、直接短語和句柄q語法樹和文法的二義性語法樹和文法的二義性q文法和語言的分類文法和語言的分類2.1 概概 述述 對程序設計語言的描

2、述是從語對程序設計語言的描述是從語法、語義和語用三個因素來考慮。法、語義和語用三個因素來考慮。語法語法是對語言結構的定義。是對語言結構的定義。 語用語用則是從使用的角度去描述則是從使用的角度去描述語言。語言。語義語義是描述了語言的含義。是描述了語言的含義。2.1 概概 述述例如例如 賦值語句賦值語句s s2 2* *3.14163.1416* *r r* *(r+h)(r+h)的的 非形式化的描述為：非形式化的描述為：語法：語法：賦值語句由一個變量，后隨一個賦賦值語句由一個變量，后隨一個賦 值號值號“”，其后面再跟一個表達式構成。，其后面再跟一個表達式構成。語義：語義：首先計算語句右部表達式的

3、值，然首先計算語句右部表達式的值，然后把所得結果送給左部變量中。后把所得結果送給左部變量中。語用：語用：賦值語句可用來計算和保存表達式賦值語句可用來計算和保存表達式的值。的值。2.1 概 述 這種非形式化描述這種非形式化描述, ,不夠清晰和不夠清晰和準確。準確。 為了精確定義和描述程序設計語為了精確定義和描述程序設計語言言, ,需采用形式化的方法。需采用形式化的方法。 形式化方法形式化方法, ,是用一整套帶有嚴是用一整套帶有嚴格規定的符號體系來描述問題的方法。格規定的符號體系來描述問題的方法。 2.2 字母表和符號串的基本概念字母表和符號串的基本概念內容主要包括：內容主要包括：1.字母表和符號

4、串的定義字母表和符號串的定義2.符號串的運算符號串的運算2.2.1 字母表和符號串字母表和符號串元素的非空有窮集合。元素的非空有窮集合。例如，例如，= a, b, c 1. 字母表字母表 根據字母表的定義，根據字母表的定義，是是字母表，字母表，它由它由a a、b b、c c三個三個元素元素組成。組成。不同的語言有不同的字母表不同的語言有不同的字母表任何語言的字母表指出該語言中允任何語言的字母表指出該語言中允許出現的一切符號許出現的一切符號2.2.1 字母表和符號串字母表和符號串 是一個字母表，由是一個字母表，由0 0、1 1兩個元素兩個元素組成。組成。注意注意:例如，例如， =0, 1 (2)

5、 字母表中的元素字母表中的元素, 可以是字母、可以是字母、數字或其他符號數字或其他符號。(1) 字母表中至少包含一個元素字母表中至少包含一個元素。2.2.1 字母表和符號串字母表和符號串 字母表中的元素稱為符號或稱為字母表中的元素稱為符號或稱為字符。字符。例如，前述例子中例如，前述例子中2. 符號（字符）符號（字符）a、b、c 是字母表是字母表中的符號；中的符號；0、1 是字母表是字母表中的符號。中的符號。2.2.1字母表和符號串字母表和符號串 例如，設有字母表例如，設有字母表= a, b, c 符號的有窮序列稱為符號串。符號的有窮序列稱為符號串。 符號串總是建立在某個特定字符號串總是建立在某

6、個特定字母表上的且只母表上的且只由字母表上的有窮多由字母表上的有窮多個符號組成。個符號組成。 則有則有: 符號串符號串 a a，b b，abab，baba， cbacba， abcabc 3. 符號串（字）符號串（字）2.2.1 字母表和符號串字母表和符號串說明說明: :不包含任何符號的符號串不包含任何符號的符號串, , 稱為稱為空空符號串符號串，用，用表示。表示。符號串中符號的符號串中符號的順序順序是很重要的。是很重要的。abab和和baba是字母表是字母表上的上的兩個兩個不同的不同的符號串。符號串。空符號串由空符號串由0 0個符號組成，個符號組成，其長度其長度| |=0|=0 x x x2

7、.2 .2 符號串的運算符號串的運算 設設x和和y是符號串，則串是符號串，則串xy稱為它稱為它們的們的連接連接。則則xy_ yx _ 注意注意：對任意一個符號串：對任意一個符號串x，1. 符號串的連接符號串的連接(結結)例如例如，設，設xabc，y102.2.2 符號串的運算符號串的運算2.(符號串的符號串的)集合的乘積集合的乘積 設設A和和B是符號串的集合是符號串的集合, 則則A和和B的乘積定義為：的乘積定義為： 集合的乘積是滿足于集合的乘積是滿足于 xA, yB的的所有符號串所有符號串 xy 所構成的集合。所構成的集合。AB=xy | xA, yB A A A2.2.2 符號串的運算符號串

8、的運算例如：例如：設設A= a, b , B= c, d 則則AB= ac, ad, bc, bd 由于對任意的符號串由于對任意的符號串x，總有總有 x=x =x所以所以, 對任意集合對任意集合A, 我們有我們有:2.2.2 符號串的運算符號串的運算 特別指出特別指出:是符號串是符號串, 不是集合不是集合 表示由空串表示由空串 組成的集合組成的集合, 這樣的這樣的集合不是空集集合不是空集= 2.2.2 符號串的運算符號串的運算 3. 符號串的冪運算符號串的冪運算 設設x是符號串是符號串, 則則x的冪運算定義為：的冪運算定義為： x0= x1= x x2= xx x3= xxx xn= xx x

9、=x xn-1(n0)n注意：注意：x0 12.2.2 符號串的運算符號串的運算例如例如, 設設 xabc 則則x0= _x1= _x2=xx= _ 2.2.2 符號串的運算符號串的運算 4.(符號串的符號串的)集合的冪運算集合的冪運算 設設A是符號串的集合，則集合是符號串的集合，則集合A的的冪運算定義為：冪運算定義為：A0= A1=AA2=AA An= AA A=AAn-1(n0)n2.2.2 符號串的運算符號串的運算例如，設例如，設A= a, b ，則則A0= _A1=A= a, b A2=AA= _ A3=AAA=A2A= aaa, aab, aba, abb, baa, bab, bb

10、a, bbb 2.2.2 符號串的運算符號串的運算5. 集合集合A的正閉包的正閉包A與閉包與閉包A* 設設A是符號串的集合，則是符號串的集合，則A的正閉的正閉包包A和和A的閉包的閉包A*的定義為的定義為:A+=A1A2 An A*= A0 A1A2 An =A+n 例如例如: 假設假設A a，n A 0 n A 1 an A 2 aan則則A + a，aa，aaa，aaaa， nA*= A0A+ = ， a，aa，aaa，2.2.2 符號串的運算符號串的運算A+表示表示A中中元素元素a, ,b構成的構成的所有符號所有符號串串的集合的集合A*比比A+多含一個空符號串多含一個空符號串 。例如，設例

11、如，設A= a, b , 則：則：A+= a, b, aa, ab, ba, bb, aaa, aab, A*= , a, b, aa, ab, ba, bb, aaa, aab, 2.3 2.3 文法和語言的形式定義文法和語言的形式定義 每個形式語言都是某個字母表上每個形式語言都是某個字母表上按按某種規則某種規則構成的構成的所有符號串的集合所有符號串的集合。 任何一個字母表上符號串的集合任何一個字母表上符號串的集合均可定義為一個形式語言均可定義為一個形式語言。2.3.1形式語言形式語言2.32.3.1.1 形式語言形式語言 對每個具體語言對每個具體語言, ,都有語法和語都有語法和語義兩個方面

12、，義兩個方面，形式語言形式語言不考慮語言不考慮語言的具體意義，即的具體意義，即不考慮語義不考慮語義。C C語言是其字母表上的符合要求的語言是其字母表上的符合要求的符號串的集合，每個符號串的集合，每個C C語言程序是語言程序是一個符號串。一個符號串。 2.3.1 2.3.1 形式語言形式語言形式語言的描述形式語言的描述 對形式語言的描述有兩種方法：對形式語言的描述有兩種方法： 當語言為當語言為有窮集合有窮集合時，用時，用枚舉法枚舉法來表來表示語言。示語言。 當語言為當語言為無窮集合無窮集合時，用時，用文法文法來描述來描述語言。語言。 2.3.1 2.3.1 形式語言形式語言 均表示字母表均表示字

13、母表A上的一個形式語言。上的一個形式語言。由于由于這三個語言均是有限符號串的集合，因此，這三個語言均是有限符號串的集合，因此，可枚舉出其全部句子來表示該語言。可枚舉出其全部句子來表示該語言。 例如，設有字母表例如，設有字母表A= a, b, c ，則則L L1 1= a, b, c L L2 2= a, aa, ab, ac L L3 3= c, cc 2.3.1 2.3.1 形式語言形式語言例如，設字母表例如，設字母表= 0, 1 , 則則+ +=1 12 23 3= = 0, 1, 00, 10, 11, 01, 000, 100, 當語言為當語言為無窮集合無窮集合時，用時，用文法文法來描

14、述來描述語言。語言。 2.3.1 2.3.1 形式語言形式語言用用A表示表示+，用式子，用式子A0表示符號串表示符號串0A或或A生成符號串生成符號串0 讀作讀作生成生成或或由由組組成成。集合。集合A可表示成：可表示成： A0A1AA0AA1+ +=1 12 23 3= = 0, 1, 00, 10, 11, 01, 000, 100, 2.3.2.3.2 2 文法的形式定義文法的形式定義 規則是一個符號與一個符號串的規則是一個符號與一個符號串的有序對有序對（A,），通常寫作：通常寫作： A（或（或A ) 1.1. 規則規則 也稱產生式也稱產生式 規則的作用是告訴我們如何用規則的作用是告訴我們如

15、何用規規則中的符號串生成語言中的序列則中的符號串生成語言中的序列。2.3.2.3.2 2 文法的形式定義文法的形式定義 例如，前述例中一組規則例如，前述例中一組規則 描述的語言序列只可能是由描述的語言序列只可能是由0和和1組成的符號串。組成的符號串。A0A1AA0AA12.3.2.3.2 2 文法的形式定義文法的形式定義 規則中出現的符號分為兩類規則中出現的符號分為兩類 終結符號終結符號 非終結符號非終結符號 終結符號終結符號是是組成語言的基本符號組成語言的基本符號，是一個語是一個語言的不可再分的基本符號言的不可再分的基本符號，通常用小寫字母，通常用小寫字母表示。表示。 例如，上例中的例如，上

16、例中的0和和1。 2.3.2.3.2 2 文法的形式定義文法的形式定義 非終結符號非終結符號是出現在規則是出現在規則左部左部能派能派生出符號或符號串的那些符號。生出符號或符號串的那些符號。每個非終結符號表示一定符號串的每個非終結符號表示一定符號串的集合。集合。用大寫字母表示或用尖括號把非終用大寫字母表示或用尖括號把非終結符號括起來。例如，上例中的結符號括起來。例如，上例中的A。2.3.2.3.2 2 文法的形式定義文法的形式定義 規則的非空有窮集合，規則的非空有窮集合，通常表示通常表示成四元組成四元組VN是規則中非終結符號的集合。是規則中非終結符號的集合。VT是規則中終結符號的集合。是規則中終

17、結符號的集合。P 是文法規則的集合。是文法規則的集合。 2. 文法文法G=(VN,VT, P, S )S 是文法的開始符號是文法的開始符號 SVN 2.3.2.3.2 2 文法的形式定義文法的形式定義 文法的開始符號也稱文法的識文法的開始符號也稱文法的識別符號別符號，它至少要在一條規則中作，它至少要在一條規則中作為左部出現。代表我們為左部出現。代表我們所定義的語所定義的語言言。 由文法定義可知，文法是對語言由文法定義可知，文法是對語言結構的定義和描述，四大要素結構的定義和描述，四大要素關鍵是關鍵是規則的集合規則的集合。 2.3.2.3.2 2 文法的形式定義文法的形式定義 將它們縮寫為：將它們

18、縮寫為：A 1 | 2 | | nA 1A 2A n 其中每個其中每個 i有時也稱為有時也稱為A的一個的一個候選式候選式。 為了書寫方便，對于若干個左為了書寫方便，對于若干個左部相同的規則部相同的規則，如，如2.3.2.3.2 2 文法的形式定義文法的形式定義 我們我們約定約定： 第一條規則的左部是第一條規則的左部是開始開始( (識別識別) )符號符號。 對文法對文法G不用四元組顯示表示不用四元組顯示表示，僅只，僅只 將將規則寫出規則寫出。 2.3.1 2.3.1 文法的形式定義文法的形式定義 G=(VN，VT，P，S )VN=AVT=0，1P: A 0 | 1 | A0 | A1S=A前例中

19、描述前例中描述+ +的文法是的文法是: :2.3.2.3.2 2 文法的形式定義文法的形式定義 例例1 設字母表設字母表=a, b，試設計一個試設計一個文法，描述語言文法，描述語言 L= a2n, b2n | n1 分析分析 關鍵是設計一組規則生成語言關鍵是設計一組規則生成語言中的符號串。中的符號串。 分析語言中串的結構特征分析語言中串的結構特征： 2.3.2.3.2 2 文法的形式定義文法的形式定義 當當n1 L=_ L=aa, bb, aaaa, bbbb, aaaaaa, bbbbbb, 即即語言語言L是由是由偶數個偶數個a，偶數個偶數個b這樣這樣的符號串組成的集合的符號串組成的集合。

20、L=a2n, b2n | n1當當n2 L=_當當n3 L=aaaaaa, bbbbbb2.3.2.3.2 2 文法的形式定義文法的形式定義 因此，定義語言因此，定義語言L的文法的文法 G=( VN，VT，P，S )其中：其中： VN=A, B, DVT=a, bP= Aaa S=ABaa Dbb | bbD | bb | bbD注意注意:VTaa,bb | aaB| aaB2.3.2.3.2 2 文法的形式定義文法的形式定義 提出問題提出問題: 描述該語言的文法描述該語言的文法是否唯一呢？是否唯一呢？對于一個給定的語言，對于一個給定的語言，描述該語言描述該語言的文法是不唯一的的文法是不唯一的

21、。 P : AB | DBaa | aBaDbb | bDb 若若G和和G是兩個不同的文法，如是兩個不同的文法，如果它們描述的語言相同，那么，稱果它們描述的語言相同，那么，稱G和和G 為為等價文法等價文法。2.3.2.3.2 2 文法的形式定義文法的形式定義 描述該語言的文法是否描述該語言的文法是否G也可以也可以？2.3.2.3.2 2 文法的形式定義文法的形式定義 對此例，對此例，我們提出下面這樣一個問題：我們提出下面這樣一個問題： G=( A, a, b, P, A ) 其中其中P= Aaa | bb | Aaa | Abb 對于文法對于文法G來說，它所產生的來說，它所產生的有些符號串，如

22、有些符號串，如aabb，bbaa， 不屬于語言不屬于語言L，即即設計的文法超出了設計的文法超出了所定義語言的范圍所定義語言的范圍。 2.3.2.3.2 2 文法的形式定義文法的形式定義 P= Aaa | bb | Aaa | Abb 2.3.2.3.2 2 文法的形式定義文法的形式定義 例例2 試設計一個表示所有試設計一個表示所有標識符標識符的文法的文法 分析分析 為為確定確定P中規則。應搞清楚中規則。應搞清楚集合中串的結構特征。集合中串的結構特征。 2.3.2.3.2 2 文法的形式定義文法的形式定義 用用I代表標識符；代表標識符；L代表字母；代表字母；D代表數字代表數字; 則定義標識符的文

23、法則定義標識符的文法為：為： 字母字母 字母或數字串字母或數字串標識符的結構可用下圖表示標識符的結構可用下圖表示:2.3.2.3.2 2 文法的形式定義文法的形式定義 G=(VN，VT，P，S)其中：其中： VN=I, L, DVT=a,b,c, x,y,z,0,1,2,x,y,z,0,1,2, ,9,9P= IL S=ILa | b | c | | x | y | zD0 | 1 | 2 | 3 | | 9 | I L| I D2.3.2.3.2 2 文法的形式定義文法的形式定義 若將定義標識符的文法設計成：若將定義標識符的文法設計成： 其中其中 VN，VT ，S 同上同上 G=(VN，VT

24、，P，S )P= IL | I DLa | b | c | |x|y|z|x|y|zD0 | 1 | 2 | 3 | |9 |9 2.3.2.3.2 2 文法的形式定義文法的形式定義 該文法不能定義該文法不能定義ab，abc 僅由字母串組成的標識符，僅由字母串組成的標識符，縮小縮小了所定義語言的范圍了所定義語言的范圍。 P= IL | I DLa | b | c | |x|y|z|x|y|zD0 | 1 | 2 | 3 | |9 |9 2.3.2.3.2 2 文法的形式定義文法的形式定義 用用I代表標識符；代表標識符；L代表字母；代表字母；D代表數字；代表數字；T代表字母數字串；代表字母數字串

25、；則則定義標識符的文法還可寫為：定義標識符的文法還可寫為： 字母字母 字母或數字串字母或數字串2.3.2.3.2 2 文法的形式定義文法的形式定義 P: IL | LT TL | D | LT | DT La | b | c | |x|y|z|x|y|z D0 | 1 | 2 | 3 | | 9 字母字母 字母或數字串字母或數字串2.3.2.3.2 2 文法的形式定義文法的形式定義 例例3 用文法定義一個含、用文法定義一個含、* *的算術表達式，定義用下述自然語的算術表達式，定義用下述自然語言描述：言描述： 變量是一個表達式；變量是一個表達式； 若若 E1和和 E2是算術表達式是算術表達式,

26、則則 E1E2、E1* *E2、(E1) 也是算術表也是算術表達式。達式。 2.3.2.3.2 2 文法的形式定義文法的形式定義 分析分析 定義用自然語言描述是非定義用自然語言描述是非形式定義，形式定義，用用文法來定義文法來定義即是即是用形用形式化式化的的方法定義表達式。定義算術方法定義表達式。定義算術表達式的文法為：表達式的文法為： G=(E, i, +, * *, (, ) , P, E )其中其中P為：為：Ei | E+E | E* *E | (E)2.3.2.3.2 2 文法的形式定義文法的形式定義 P為：為：Ei | E+E | E* *E | (E) i, i+i, i* *i,

27、i+i* *i, (i+i), 注意：是符號注意：是符號串的集合串的集合2.3.2.3.2 2 文法的形式定義文法的形式定義 例例4 設字母表設字母表 = a, b , 試設計一試設計一個文法，描述語言個文法，描述語言 L= abna | n0 分析分析 該該語言中串的結構特征語言中串的結構特征是是 當當n1 L= aba L= aa, aba, abba, 當當n2 L= abba 當當n0 L= aa (b0=)2.3.2.3.2 2 文法的形式定義文法的形式定義 所以所以定義語言的文法為：定義語言的文法為： G=( A, B, a, b, P, A )P= AaBa BBb | L= a

28、a, aba, abba, 2.3.2.3.2 2 文法的形式定義文法的形式定義 例例5 設字母表設字母表= (, ) ,試設計試設計一個文法描述語言一個文法描述語言 L= (n )n | n0分析分析 該該語言中串的結構特征語言中串的結構特征是是 當當n=0 L= 注注: (0 )0= 當當n=1 L= ( ) 當當n=2 L= ( ) L= , ( ), ( ), ( ), 2.3.2.3.2 2 文法的形式定義文法的形式定義 S | ( S )所以定義語言的文法為： L= (n )n | n02.3.2.3.3 3 語言的形式定義語言的形式定義 1. 直接推導 令令G是一文法，我們稱是一

29、文法，我們稱 xAy直接直接推導出推導出 xy ，即即 xAyxy 僅僅 A 是是 G 的一條規則的一條規則, 且且 x, y (VNVT)*。也就是說從符號也就是說從符號串串 xAy 直接推導出直接推導出 xy 僅使用一次僅使用一次規則規則。 2.3.2.3.3 3 語言的形式定義語言的形式定義例如，設有文法例如，設有文法GS: S01 使用規則使用規則 S01 此時此時 x ， y P為：為：S 0 1 | 0 S 1 有如下直接推導：有如下直接推導：S0S1 使用規則使用規則 S0S1 此時此時 x ， y 2.3.2.3.3 3 語言的形式定義語言的形式定義 0S10011 使用規則使

30、用規則 S01 此時此時 x0， y1 00S11000S111 使用規則使用規則 S0S1 此時此時 x00 , y11 000S11100001111 使用規則使用規則 S01 此時此時 x000 y111S 0 1 | 0 S 12.3.32.3.3 語言的形式定義語言的形式定義 (1) 形式上形式上的區別，推導用的區別，推導用“”表示，規則用表示，規則用“”表示表示 。 (2) 對文法對文法G中任何規則中任何規則A，我我們們有有A，即即推導的依據是規則推導的依據是規則。 注意推導和規則的區別：注意推導和規則的區別：即表示從即表示從 0 出發，經出發，經 一步或若干步一步或若干步 或或者

31、說者說 使用若干次規則使用若干次規則可推導出可推導出 n。 2.3.32.3.3 語言的形式定義語言的形式定義 如果存在一個直接推導序列：如果存在一個直接推導序列： 則我們稱這個序列是一個從則我們稱這個序列是一個從 0至至 n的的長度為長度為n的推導，記為的推導，記為 2推導推導0 1 2 n+0 n2.3.32.3.3 語言的形式定義語言的形式定義 例如例如 設有文法設有文法GE=(E,T,F,i,+,* *,(,),P,E)對對 i+ +i* *i 有如下直接推導序列有如下直接推導序列: : 我們可記為我們可記為 其中其中P為：為：EE+T | TTT* *F | FF(E) | iEE+

32、TT+TF+Ti+Ti+T* *Fi+F* *Fi+i* *Fi+i* *iEi+i* *i+2.3.32.3.3 語言的形式定義語言的形式定義 3廣義推導廣義推導 有：有： 0 n表示從表示從 0出發，經出發，經0步或若干步，步或若干步， 可推導出可推導出 n。* * 0 n意味著意味著 0 n或者或者 0= n。* *+ +EE* *Ei+i* *i* *對上例對上例 EE+T | T TT* *F | F F(E) | i2.3.32.3.3 語言的形式定義語言的形式定義 區別：區別： 直接推導的直接推導的長度為長度為1 推導的推導的長度大于等于長度大于等于1 廣義推導的廣義推導的長度大

33、于等于長度大于等于0句型和句子句型和句子 4. 句型和句子句型和句子 設有文法設有文法GS（S是文法是文法G的開始符號）的開始符號） 如果如果S x, xx, x (VNVT)* 則稱符號串則稱符號串x x 為文法為文法GS的的句型句型。* * 如果如果S x, xx, x VT* 則稱符號串則稱符號串x x為文法為文法 GS的的句子句子。* *2.3.32.3.3 語言的形式定義語言的形式定義 例例1 設有文法設有文法GS： 我們有我們有: 01、0S1、00S11和和000111 都是都是G的句型，的句型，01和和000111還是文法還是文法GS的句子的句子 S01 | 0S1S 0101

34、*S 0S10S1*S 00S1100S11*S 000111000111*2.3.32.3.3 語言的形式定義語言的形式定義 例例2 設有文法設有文法GE： 試證明符號串試證明符號串 (i* *i+i) 是文法是文法GE的一的一個句子。個句子。 分析分析 只要證明符號串只要證明符號串 (i* *i+i) 對文法對文法 G存在一個推導，就可證明符號串存在一個推導，就可證明符號串 (i* *i+i) 是文法是文法GE的一個句子的一個句子。 EE+E | E* *E | (E) | i2.3.32.3.3 語言的形式定義語言的形式定義 EE+E | E* *E | (E) | iE(E)(E+E)

35、(E* *E+ +E)(i* *E+ +E)(i* *i+E)(i* *i+i) 即有即有 E(i* *i+i), 所以符號串所以符號串(i+i* *i)是文法是文法 GE的一個句子。的一個句子。 * *（2）L(G)是是VT* 的子集。即屬于的子集。即屬于VT* 的符的符 號串號串 x 不一定屬于不一定屬于L(G)。2.3.32.3.3 語言的形式定義語言的形式定義 5語言語言 文法文法GS產生的所有句子的集合稱為文產生的所有句子的集合稱為文 法法G所定義的語言所定義的語言,記為記為L(GS)： 由語言定義可知：由語言定義可知：（1）一旦文法給定，語言也就確定。）一旦文法給定，語言也就確定。

36、L(GS)=x|Sx且且xVT*2.3.32.3.3 語言的形式定義語言的形式定義 例例3 設有文法設有文法GS ：S01 | 0S1求該文法所描述的語言是什么？求該文法所描述的語言是什么？ 分析分析 由開始符號由開始符號S出發，將推出出發，將推出一些什么句子，找出其中的規律，用一些什么句子，找出其中的規律，用式子或自然語言描述出來。式子或自然語言描述出來。 2.3.32.3.3 語言的形式定義語言的形式定義 我們應用第二個規則我們應用第二個規則n1次，然后再次，然后再應用第一個規則應用第一個規則1次，有：次，有： S0S100S110n-1S1n-10n1n即即S0n1n* *可見，此文法定

37、義的語言為可見，此文法定義的語言為L(GS)= 0n1n | n1S01 | 0S12.3.32.3.3 語言的形式定義語言的形式定義 例例4 設有文法設有文法GS：S0S | 1S |該文法所定義的語言是什么？該文法所定義的語言是什么？ 由該文法所確定的語言為由該文法所確定的語言為 L(GS)=, 0, 1, 00, 01, 10, 11, = x | x0,1* 2.3.32.3.3 語言的形式定義語言的形式定義 例例5 設有文法設有文法GA： 該文法所定義的語言是什么？該文法所定義的語言是什么？ 分析分析 從文法開始符號從文法開始符號A出發可推導出出發可推導出以以y開頭后面跟一個或多個開

38、頭后面跟一個或多個x結尾的符號結尾的符號串，所以該文法定義的語言為串，所以該文法定義的語言為AyBB xB | xL(GA)= yxn | n12.3.32.3.3 語言的形式定義語言的形式定義 從已知文法確定語言的方法從已知文法確定語言的方法： 從文法的從文法的開始符號開始符號出發，出發，反復反復連連續地續地使用規則使用規則替換、展開非終結符，替換、展開非終結符，找出句子的規律，用式子或自然語言找出句子的規律，用式子或自然語言描述出來。描述出來。 2.3.32.3.3 語言的形式定義語言的形式定義 形式語言理論可以證明如下兩點：形式語言理論可以證明如下兩點：(1) 給定一種語言，能確定其文法

39、，但這給定一種語言，能確定其文法，但這種文法種文法不是唯一的不是唯一的(2) 給定一個文法，就能從結構上給定一個文法，就能從結構上唯一唯一確確定其語言定其語言2.3.42.3.4 規范推導和規范歸約規范推導和規范歸約 文法和語言是密切相關的，文法文法和語言是密切相關的，文法所定義的任一句型和句子所定義的任一句型和句子, 都可以根都可以根據文法推導出來。據文法推導出來。我們提出一個問題：我們提出一個問題：這種推導過程是否唯一？這種推導過程是否唯一？2.3.42.3.4 規范推導和規范歸約規范推導和規范歸約 同一個句型同一個句型(句子句子)可以通過可以通過不同不同的推導序列推導出來，這是因為的推導

40、序列推導出來，這是因為在在推導過程中與所選擇非終結符的次推導過程中與所選擇非終結符的次序無關。序無關。2.3.42.3.4 規范推導和規范歸約規范推導和規范歸約例如，設有文法例如，設有文法GN1 N1NNND | DD0 | 1 | 2 N1NNDN2D212 N1NNDDD1D12 N1NNDDDD212句子句子12有下列三種不同的推導序列有下列三種不同的推導序列:2.3.42.3.4 規范推導和規范歸約規范推導和規范歸約 最左最左(最右最右)推導，是指對于一個推導，是指對于一個推導序列中的推導序列中的每一步直接推導每一步直接推導 , 都是對都是對 中的最左中的最左(最右最右)非終結符進非終

41、結符進行替換。行替換。 最右推導也稱為最右推導也稱為規范推導規范推導，用規，用規范推導推導出的句型稱為范推導推導出的句型稱為規范句型規范句型。 2.3.42.3.4 規范推導和規范歸約規范推導和規范歸約 例例 設有文法設有文法GS: 請給出句子請給出句子101001的最右、最左推導。的最右、最左推導。 分析分析 最右推導是指在推導過程中最右推導是指在推導過程中任何一步任何一步 (和和是句型是句型)，都是對，都是對中的中的最右最右非終結符進行替換。非終結符進行替換。SABAA0 | 1BB0 | S12.3.42.3.4 規范推導和規范歸約規范推導和規范歸約SABAS1AAB1AA01A1B01

42、A10011B1001101001句子句子101001的最右推導為的最右推導為: SABAA0 | 1BB0 | S12.3.42.3.4 規范推導和規范歸約規范推導和規范歸約 最左推導是指在推導過程中任何最左推導是指在推導過程中任何一步一步 (和和是句型是句型), 都是對都是對的的最最左左非終結符進行替換。非終結符進行替換。句子句子101001的最左推導為：的最左推導為： SABAA0 | 1BB0 | S1SAB1BB10B10S110AB1101BB11010B11010012.3.42.3.4 規范推導和規范歸約規范推導和規范歸約歸約歸約是與推導相對的概念，推導是把是與推導相對的概念，推導是把句型中的非終結符用規則的一個右部來替句型中的非終結符用規則的一個右部來替換的過程，而換的過程，而歸約則是把句型中的某個子歸約則是把句型中的某個子串用一個非終結符來替換的過程串用一個非終結符來替換的過程。 若用若用表示歸約，設表示歸約