第2章1文法和語言

1、xzhxzh2022-6-29莆田學(xué)院許振和1一、文法的概念一、文法的概念二、符號和符號串二、符號和符號串三、文法和語言的定義三、文法和語言的定義四、文法的類型四、文法的類型五、上下文無關(guān)文法及其語法樹五、上下文無關(guān)文法及其語法樹xzhxzh2022-6-29莆田學(xué)院許振和2本章要求本章要求 主要內(nèi)容主要內(nèi)容：符號串，文法的概念及分：符號串，文法的概念及分類，語言的定義過程類，語言的定義過程 重點(diǎn)掌握重點(diǎn)掌握：上下文無關(guān)文法、推導(dǎo)、：上下文無關(guān)文法、推導(dǎo)、句型、句子、語言，語法樹、二義性句型、句子、語言，語法樹、二義性文法、文法的語言生成過程文法、文法的語言生成過程xzhxzh2022-6-2

2、9莆田學(xué)院許振和3構(gòu)構(gòu)結(jié)結(jié)識識知知文法和語言符號和符號串字母表和符號串符號串集合的運(yùn)算文法和語言的形式定義文法的形式定義語言的形式定義語法分析的基本術(shù)語規(guī)則文法推導(dǎo)和規(guī)約句型/句子/語言短語和句柄最左最右推導(dǎo)和規(guī)約語法樹和二義性語法樹的構(gòu)造語法樹與短語文法的二義性文法的實(shí)用限制xzhxzh2022-6-29莆田學(xué)院許振和4語言是由單詞按一定規(guī)則（文法）組成句子來表達(dá)特定意思。故對語言的分析集中于對句子的分析。而句子的分析依據(jù)語言的文法規(guī)則。程序設(shè)計(jì)語言可以通過描述以下兩個(gè)要素來定義：程序設(shè)計(jì)語言可以通過描述以下兩個(gè)要素來定義： 第一方面是程序模式，即語言的第一方面是程序模式，即語言的語法語法；

3、 第二方面是程序含義，即語言的第二方面是程序含義，即語言的語義語義。文法與語言文法與語言語義語義分為兩類：分為兩類： 靜態(tài)語義靜態(tài)語義 動態(tài)語義動態(tài)語義xzhxzh2022-6-29莆田學(xué)院許振和5一、文法的概念一、文法的概念 所謂一個(gè)所謂一個(gè)語言的語法語言的語法是指一組是指一組規(guī)則規(guī)則，用它可以形，用它可以形成和產(chǎn)生一個(gè)合適的程序。成和產(chǎn)生一個(gè)合適的程序。 由單詞符號按照一定的規(guī)則構(gòu)成各種類型的表達(dá)由單詞符號按照一定的規(guī)則構(gòu)成各種類型的表達(dá)式、語句、分程序（程序），即不同的語法范疇。式、語句、分程序（程序），即不同的語法范疇。不同的語法范疇具有不同的構(gòu)成規(guī)律。不同的語法范疇具有不同的構(gòu)成規(guī)律

4、。 單詞符號的構(gòu)成規(guī)則稱為單詞符號的構(gòu)成規(guī)則稱為詞法規(guī)則詞法規(guī)則。 各種語法范疇構(gòu)成規(guī)則稱為各種語法范疇構(gòu)成規(guī)則稱為語法規(guī)則語法規(guī)則。 描述詞法規(guī)則和語法規(guī)則的描述詞法規(guī)則和語法規(guī)則的工具工具是是文法文法。文法文法表表示用示用語法圖語法圖(語法樹語法樹)和和EBNF(巴科斯-諾爾)描述。描述。 目前廣泛使用的手段是目前廣泛使用的手段是上下文無關(guān)文法上下文無關(guān)文法，即用上，即用上下文無關(guān)文法作為程序設(shè)計(jì)語言語法的描述工具。下文無關(guān)文法作為程序設(shè)計(jì)語言語法的描述工具。xzhxzh2022-6-29莆田學(xué)院許振和6語語言言 語法語法：是一組規(guī)則, 定義符號如何排列，排列與符號含義無關(guān)。即程序的程序的

5、結(jié)構(gòu)或形式結(jié)構(gòu)或形式語義語義：研究語言所代表的語言所代表的含義含義語用：語用：語言的實(shí)際語言的實(shí)際應(yīng)用應(yīng)用語言的表示方法語言的表示方法1、用識別的觀點(diǎn)表示語言，這種方法是給出一、用識別的觀點(diǎn)表示語言，這種方法是給出一種算法種算法 由它判定一個(gè)句子是否在語言中。由它判定一個(gè)句子是否在語言中。2、用產(chǎn)生的觀點(diǎn)表示語言、用產(chǎn)生的觀點(diǎn)表示語言xzhxzh2022-6-29莆田學(xué)院許振和7句子句子 =主語謂語主語謂語主語主語 =代詞代詞|名詞名詞代詞代詞 = 我我|你你|他他名詞名詞 = 王明王明|大學(xué)生大學(xué)生|工人工人|英語英語謂語謂語 =動詞直接賓語動詞直接賓語動詞動詞 = 是是|學(xué)習(xí)學(xué)習(xí)直接賓語直

6、接賓語 =代詞代詞| 先舉個(gè)例子：用先舉個(gè)例子：用EBNF表示表示xzhxzh2022-6-29莆田學(xué)院許振和8推導(dǎo)：推導(dǎo)： 你是大學(xué)生你是大學(xué)生 句子句子 主語謂語主語謂語 代詞代詞謂語謂語 你謂語你謂語 你動詞直接你動詞直接賓語賓語 你是名詞你是名詞 你是大學(xué)生你是大學(xué)生 由上一組規(guī)則可以產(chǎn)生句子：由上一組規(guī)則可以產(chǎn)生句子：你是大學(xué)生你是大學(xué)生 這樣的語言描述稱為文法這樣的語言描述稱為文法 “=”表示由某條規(guī)則的右部替換該規(guī)則的左表示由某條規(guī)則的右部替換該規(guī)則的左部，把它稱之為推導(dǎo)。部，把它稱之為推導(dǎo)。xzhxzh2022-6-29莆田學(xué)院許振和9語句“小八哥吃大花生”分析的語法樹上下句子

7、主語謂語形容詞名詞 動詞 賓語小八哥吃形容詞名詞大花生xzhxzh2022-6-29莆田學(xué)院許振和10句子的推導(dǎo) 小八哥吃 小八哥吃 小八哥吃大小八哥吃大花生xzhxzh2022-6-29莆田學(xué)院許振和11謂語主語形容詞 名詞 動詞賓語小八哥吃花生大下形容詞名詞上句子句子的歸約xzhxzh2022-6-29莆田學(xué)院許振和12二、符號和符號串二、符號和符號串 任何一種語言，都是由該語言的基本字符所組成的字符任何一種語言，都是由該語言的基本字符所組成的字符串的集合。串的集合。1 1、語言語言可以看成在一個(gè)基本符號集上定義的，按一定規(guī)則可以看成在一個(gè)基本符號集上定義的，按一定規(guī)則構(gòu)成的一切基本符號串

8、組成的構(gòu)成的一切基本符號串組成的集合。集合。2 2、字母表字母表( (符號集符號集) )：是字母的有窮：是字母的有窮非空非空集合。集合。用希臘字母用希臘字母或或大寫英文字母大寫英文字母等表示字母表。等表示字母表。3 3、符號（、符號（字符字符）：字母表中的元素。因此字母表也稱為符）：字母表中的元素。因此字母表也稱為符號集。號集。用集合元素表示形式枚舉字母表中的符號。用集合元素表示形式枚舉字母表中的符號。 符號是該語言能識別的符號，字母表是該語言能識別的符號是該語言能識別的符號，字母表是該語言能識別的所有符號的全體（字符集）所有符號的全體（字符集） 4 4、符號串符號串( (字符串字符串) )：

9、字母表的符號組成任何：字母表的符號組成任何有窮序列。有窮序列。例：例：=0=0，1 1 符號集符號集 符號串有：符號串有： 0 0，1 1，0000，0101，1010，1111xzhxzh2022-6-29莆田學(xué)院許振和13例：例：=a=a，b b，c c 符號集符號集 符號串有：符號串有：a a，b b，c c，abab，aacaaaca 在符號串中，符號的順序是很重要的，符號串在符號串中，符號的順序是很重要的，符號串a(chǎn)bab就不就不同于同于ba,abcaba,abca和和aabcaabc也不同。也不同。 【注】【注】不同排列順序表示不同的含義。不同排列順序表示不同的含義。5 5、符號串集

10、合：字母表、符號串集合：字母表 上若干個(gè)符號串組成的集合。上若干個(gè)符號串組成的集合。6 6、符號串的長度符號串的長度：符號串：符號串x x有有m m個(gè)符號，則長度就為個(gè)符號，則長度就為m m，表，表示示|x|=m |x|=m 。 如：如： ababa ababa 則長度是則長度是5 5。 定義在字母表定義在字母表= x,= x,，y y，z z，= =，0 0，1 1，+ +，; ; 上的符號串上的符號串 |x=y+|x=y+；z=0;|=10z=0;|=107 7、空符號串空符號串：用：用表示，長度為表示，長度為0 0，| | | = 0| = 0 若符號串若符號串x ,x ,則有則有x =

11、 x= xx = x= xxzhxzh2022-6-29莆田學(xué)院許振和148 8、符號串的運(yùn)算：符號串的運(yùn)算：(1) (1) 符號串的頭符號串的頭( (前綴)和尾和尾( (后綴) 若若z=xy,z=xy,則則x x是是z z的頭，的頭，y y是是z z的尾。的尾。 例：設(shè)例：設(shè)z=abc ,z=abc ,則則z z的頭是的頭是，a a，abab，abcabc 則則z z的尾是的尾是，c c，bcbc，abcabc（2 2）符號串的）符號串的固有頭固有頭(真真前綴)和固有尾和固有尾(真真后綴) 若若z=xyz=xy符號串，符號串，x x非空，則非空，則y y固有尾；固有尾； 若若y y非空，則非

12、空，則x x是固有頭。是固有頭。 例：設(shè)例：設(shè)z=abcz=abc，則，則z z的固有頭是的固有頭是， a a， abab 則則z z的固有尾是的固有尾是 ，c c ，bcbcxzhxzh2022-6-29莆田學(xué)院許振和15 （3）子符號串（子串）從一個(gè)符號串中刪去它的一個(gè)前綴或(和)一個(gè)后綴之后剩余的部分稱為該符號串的子符號串或子串。例如:x = abcd則,a,b,c,ab,bc,cd,abc,bcd及abcd都是x的子字符串。而ac，ad，cb，bd，ba 等都不是x 的子字符串。xzhxzh2022-6-29莆田學(xué)院許振和16（4）符號串的）符號串的連接：連接： 設(shè)設(shè)x x，y y是符

13、號串，連接是符號串，連接xyxy是是y y符號寫在符號寫在x x符號之后。符號之后。記作xyxy。 例如，設(shè)有字符串例如，設(shè)有字符串 j=j=abcabc，k=k=xyzxyz 則則jk=jk=abcabcxyzxyz，kj=kj=xyzxyzabcabc。連接運(yùn)算是有序的。連接運(yùn)算是有序的。一般來說一般來說xyyxxyyx，僅當(dāng)，僅當(dāng)x=yx=y 或其中之一為或其中之一為時(shí)時(shí), ,有有xy=yxxy=yx。 顯然：顯然：x=x=xx=x=x (5) 符號串的符號串的方冪：方冪： 設(shè)設(shè)x是符號串，則是符號串，則z=xxxx，稱，稱z為為x的方冪的方冪, 記記z=xn。 因此因此 x0=, x1

14、=x, x2=xx, x3=xxx 顯然顯然n0時(shí)時(shí), 有有xn =xx n-1 x n-1xn個(gè)xzhxzh2022-6-29莆田學(xué)院許振和17 (6) 符號串的符號串的集合集合： 若集合若集合A A中的一切元素都是某中的一切元素都是某字母表字母表上的符號串，上的符號串，則稱則稱A A為該為該字母表字母表上的符號串集合。上的符號串集合。 兩個(gè)符號串集合兩個(gè)符號串集合A A、B B乘積定義：乘積定義： AB=xy| xAAB=xy| xA且且yByB 例：例：A=a,bA=a,b，B=c,d B=c,d 則則AB=acAB=ac，adad，bcbc，bd bd 注意：注意： 有有A=A=A,

15、A=A=A, A= AA= A = = ，其中，其中 為為空集。空集。 = = 。xzhxzh2022-6-29莆田學(xué)院許振和18 (7) (7) 閉包（閉包（* *） 字母表字母表，用，用* * 表示表示上上所有有窮長所有有窮長的串集合，的串集合，* *稱稱為為的閉包。的閉包。 例：字母表例：字母表=0,1=0,1 則則* *=,0,1,00,01,10,11,000,001,010,0,1,00,01,10,11,000,001,010= =0 01 1 2 2. . n n (8) (8) 正閉包正閉包(+ +) ) + + = =1 1 2 2. . n n + +稱稱的正閉包。的正閉

16、包。顯然：顯然：* * 0 0+ + + + * * *根據(jù)集合根據(jù)集合乘乘積積的定義的定義xzhxzh2022-6-29莆田學(xué)院許振和19如何來描述一種語言？如何來描述一種語言？如果語言是有窮的（只含有有窮多個(gè)句子），可如果語言是有窮的（只含有有窮多個(gè)句子），可以將句子逐一列出來表示以將句子逐一列出來表示如果語言是無窮的，找出語言的有窮表示。語言如果語言是無窮的，找出語言的有窮表示。語言的有窮表示有兩個(gè)途經(jīng)：的有窮表示有兩個(gè)途經(jīng)： 三、文法和語言的形式定義三、文法和語言的形式定義生成方式生成方式 （文法）（文法）：語言中的每個(gè)句子可以用嚴(yán)：語言中的每個(gè)句子可以用嚴(yán)格定義的規(guī)則來構(gòu)造。格定義的

17、規(guī)則來構(gòu)造。 識別方式（自動機(jī)）識別方式（自動機(jī)）：用一個(gè)過程，當(dāng)輸入的一：用一個(gè)過程，當(dāng)輸入的一任意串屬于語言時(shí)，該過程經(jīng)有限次計(jì)算后就任意串屬于語言時(shí)，該過程經(jīng)有限次計(jì)算后就會停止并回答會停止并回答“是是”，若不屬于，要麼能停止，若不屬于，要麼能停止并回答并回答“不是不是”，（要麼永遠(yuǎn)繼續(xù)下去。），（要麼永遠(yuǎn)繼續(xù)下去。）xzhxzh2022-6-29莆田學(xué)院許振和20 1、規(guī)則（產(chǎn)生式、生成式）規(guī)則（產(chǎn)生式、生成式） 形如形如 或或 := 是字母表是字母表V的正閉包的正閉包V+的一個(gè)符號；的一個(gè)符號； 是字母表是字母表V的閉包的閉包V*的一個(gè)符號；的一個(gè)符號； 稱規(guī)則的左部，稱規(guī)則的左部，

18、稱規(guī)則的右部。稱規(guī)則的右部。2、文法的定義文法的定義1文法文法G定義為四元組（定義為四元組（VN，VT，P，S）文法中規(guī)則P的第一種表示法xzhxzh2022-6-29莆田學(xué)院許振和21其中：其中： V VN N 非終結(jié)符號集非終結(jié)符號集 V VT T 終結(jié)符號集終結(jié)符號集 P P 產(chǎn)生式（規(guī)則）產(chǎn)生式（規(guī)則） S S 開始符號或稱作識別符號，它是一開始符號或稱作識別符號，它是一個(gè)非終結(jié)符，至少要在一條規(guī)則中作為左部出現(xiàn)。個(gè)非終結(jié)符，至少要在一條規(guī)則中作為左部出現(xiàn)。規(guī)定：（規(guī)定：（1 1）V VN N ，V VT T，P P是有窮非空集合；是有窮非空集合； （2 2）V VN NVVT T （

19、不含公共元素）（不含公共元素）V=VV=VN NVVT T，稱為文法，稱為文法G G的字母表（字匯表）的字母表（字匯表）xzhxzh2022-6-29莆田學(xué)院許振和22例例1 文法文法G =（VN ，VT ，P，S），）， 其中其中 VN=S，VT =0，1， P=S 0S1，S 01。 非終結(jié)符集中只含一個(gè)元素非終結(jié)符集中只含一個(gè)元素S； 終結(jié)符集由兩個(gè)元素終結(jié)符集由兩個(gè)元素0和和1組成；組成； 有兩條產(chǎn)生式；開始符號是有兩條產(chǎn)生式；開始符號是S。明顯求出：明顯求出：S01，0011，000111，xzhxzh2022-6-29莆田學(xué)院許振和23例例2 文法文法G =（VN ，VT，P，S）

20、其中其中 VN =標(biāo)識符，字母，數(shù)字標(biāo)識符，字母，數(shù)字 VT= a,b ,c,x,y,z,0,1,9 P = 字母字母 字母字母 數(shù)字?jǐn)?shù)字 a b z 1 9 S “” 表示非終結(jié)符xzhxzh2022-6-29莆田學(xué)院許振和24 文法中規(guī)則文法中規(guī)則P的第二種表示法：的第二種表示法： 上例上例1改為：改為： G: S 0S1 S 01 文法中規(guī)則文法中規(guī)則P的第三種表示法：的第三種表示法： 上例上例1改為：改為： GS: S 0S1 S 01一般約定一般約定，第一條產(chǎn)生式的左部是識別符號；用，第一條產(chǎn)生式的左部是識別符號；用尖括號括起來的尖括號括起來的是非終結(jié)符號是非終結(jié)符號，不用尖括號括起

21、，不用尖括號括起來的是來的是終結(jié)符號終結(jié)符號，或者用大寫字母表示，或者用大寫字母表示非終結(jié)符非終結(jié)符號號，小寫字母表示，小寫字母表示終結(jié)符號終結(jié)符號。 xzhxzh2022-6-29莆田學(xué)院許振和25 是文法文法G=（VN ，VT ，P，S）的規(guī)則，）的規(guī)則， 和和 是是V*中的任意符號，若有符號中的任意符號，若有符號V，W滿足：滿足： V= ，W 則說則說 V是直接產(chǎn)生是直接產(chǎn)生W 或或 W是是V的直接推導(dǎo)的直接推導(dǎo) 或或 W直接規(guī)約到直接規(guī)約到V記作記作 V W3 3、直接推導(dǎo)、直接推導(dǎo)“ “ = ”= ” 從識別符號開始，不斷將當(dāng)前符號串中的非終結(jié)從識別符號開始，不斷將當(dāng)前符號串中的非終

22、結(jié)符號替換為該符號的某個(gè)規(guī)則的右部。直到當(dāng)前的符符號替換為該符號的某個(gè)規(guī)則的右部。直到當(dāng)前的符號串中所有的符號都是終結(jié)符號為止。號串中所有的符號都是終結(jié)符號為止。xzhxzh2022-6-29莆田學(xué)院許振和26若有若有 VW ，或，或 V =W ，則記作，則記作 V W (0步或若干步) 例子：例子： 在例在例1中存在序列：中存在序列：V0S1 00S11 000S111 00001111 W記作：記作： 0S1 00001111 0S1 00001111 +*若存在直接推導(dǎo)的序列：若存在直接推導(dǎo)的序列： V=W0 W1 W2 Wn W (n0)則則 稱稱V推導(dǎo)推導(dǎo)W (或或W規(guī)約到規(guī)約到V)

23、 ，記，記V W (至少一步) *一樣的一樣的xzhxzh2022-6-29莆田學(xué)院許振和274、句型的定義、句型的定義 設(shè)設(shè)GS是文法，如果符號串是文法，如果符號串x是從識別符號（開是從識別符號（開始符號）推導(dǎo)出來的（即始符號）推導(dǎo)出來的（即S x）則稱）則稱x是文法是文法GS的的句型。句型。 若若x僅由僅由終結(jié)符號終結(jié)符號組成（組成（Sx x VT*）則稱則稱x為為GS的的句子句子。*例：例： S，0S1，000111都是文法都是文法G的句型，的句型，000111是是G的句子。的句子。結(jié)論結(jié)論句子一定是句型，句型不一定是句子。句子一定是句型，句型不一定是句子。xzhxzh2022-6-29

24、莆田學(xué)院許振和285、語言的定義：、語言的定義： L(G)表示表示文法文法G產(chǎn)生的語言定義為：產(chǎn)生的語言定義為： 集合集合 x Sx， S為文法開始符號，為文法開始符號， x VT* 該集合為語言，用該集合為語言，用L(G)表示。表示。從定義可知：從定義可知： x是句型且是句型且x是文法是文法G的句子。的句子。注：語言是文法所產(chǎn)生的所有句子組成的集合。注：語言是文法所產(chǎn)生的所有句子組成的集合。例： 例1的句子表示為： L(G)0n1n n1因?yàn)镾0S100S11 0n1n重復(fù)利用規(guī)則S0S1*xzhxzh2022-6-29莆田學(xué)院許振和29四、文法的類型：四、文法的類型：科學(xué)家科學(xué)家Choms

25、ky把文法分成以下四種類型：把文法分成以下四種類型：0型型 短語文法短語文法1型型 上下文有關(guān)文法上下文有關(guān)文法2型型 上下文無關(guān)文法上下文無關(guān)文法3型型 正規(guī)文法正規(guī)文法文文 法法 類類 型型逐 漸 增 加 限 制如果文法是正規(guī)文法如果文法是正規(guī)文法一定也是上下文無關(guān)文法一定也是上下文無關(guān)文法xzhxzh2022-6-29莆田學(xué)院許振和30文法的類型文法的類型2型文法型文法1型文法型文法0型文法型文法四種四種文法文法之間之間的的逐級逐級“包含包含”關(guān)系關(guān)系3型文法型文法xzhxzh2022-6-29莆田學(xué)院許振和31 設(shè)設(shè)G=(VN,VT,P,S)，如果它的每一個(gè)產(chǎn)生式，如果它的每一個(gè)產(chǎn)生式

26、 滿足：滿足：(VNVT)*且至少包含一個(gè)非終結(jié)符，且至少包含一個(gè)非終結(jié)符， (VN VT)*，則，則G是是0型文法型文法。 0型文法又稱為無限制文法，有時(shí)也稱為短語文型文法又稱為無限制文法，有時(shí)也稱為短語文法。法。0型文法對應(yīng)的語言稱為型文法對應(yīng)的語言稱為0型語言或稱遞歸可枚型語言或稱遞歸可枚舉集，它們的識別系統(tǒng)為圖靈機(jī)（舉集，它們的識別系統(tǒng)為圖靈機(jī)（Turing機(jī)）。機(jī)）。設(shè)設(shè)G=(VN,VT,P,S)，如果它的每一個(gè)產(chǎn)生式，如果它的每一個(gè)產(chǎn)生式 滿足：滿足： | | |，僅僅，僅僅S 除外，則文法除外，則文法G是是1型文型文法法。xzhxzh2022-6-29莆田學(xué)院許振和32下文只講上

27、下文無關(guān)文法和正規(guī)文法下文只講上下文無關(guān)文法和正規(guī)文法 4 4個(gè)文法類的定義是個(gè)文法類的定義是逐漸增加限制逐漸增加限制的，的，因此，每一種正規(guī)文法都是上下文無關(guān)的，因此，每一種正規(guī)文法都是上下文無關(guān)的，每一種上下文無關(guān)文法都是上下文有關(guān)的，每一種上下文無關(guān)文法都是上下文有關(guān)的，而每一種上下文有關(guān)文法都是而每一種上下文有關(guān)文法都是0 0型文法。型文法。1型文法相對應(yīng)的語言稱為型文法相對應(yīng)的語言稱為1型語言或上下文型語言或上下文有關(guān)語言，它的識別系統(tǒng)是線性界限自動機(jī)。有關(guān)語言，它的識別系統(tǒng)是線性界限自動機(jī)。xzhxzh2022-6-29莆田學(xué)院許振和331、上下文無關(guān)文法：、上下文無關(guān)文法： 設(shè)設(shè)

28、G=（VN ，VT ，P，S），若），若P中的每一個(gè)產(chǎn)生式中的每一個(gè)產(chǎn)生式 滿足：滿足： 是一非終結(jié)符，是一非終結(jié)符，(VN VT)*，則此文法稱為則此文法稱為上下文無關(guān)文法上下文無關(guān)文法 (2型型文法文法) 。 2型文法相對應(yīng)的語言稱為型文法相對應(yīng)的語言稱為2型語言或上下文無關(guān)語言，它的識別系統(tǒng)型語言或上下文無關(guān)語言，它的識別系統(tǒng)為下推為下推自動機(jī)自動機(jī)(PDA)。例6：G(S,A,B,a,b,P,S)，P的產(chǎn)生式如下：SaB SbAAbAA AaAaSBbBbSBaBB上下文無關(guān)文法上下文無關(guān)文法xzhxzh2022-6-29莆田學(xué)院許振和34該文法可以寫成：該文法可以寫成：SaB | b

29、AA a | aS | bAAB b | Bs | aBB2、正規(guī)文法：、正規(guī)文法： 設(shè)G=（VN ，VT ，P，S），若），若P中的每一個(gè)產(chǎn)中的每一個(gè)產(chǎn)生式都是生式都是AaB或Aa，A,B都是非終結(jié)符，a是終結(jié)符，則G是正規(guī)文法（也稱右線性文法）。 3型文法對應(yīng)的語言稱為型文法對應(yīng)的語言稱為3型語言或正規(guī)語言（正則語言，型語言或正規(guī)語言（正則語言，或正則集）?；蛘齽t集）。xzhxzh2022-6-29莆田學(xué)院許振和35例6：G(S,A,B,0,1,P,S)，P的產(chǎn)生式如下：S0A S1BS0 A0SA0AA1BB1B0B1B正規(guī)文法正規(guī)文法該文法可以寫成：該文法可以寫成：S 0 | 0A |

30、 1BA 0S | 0A | 1BB 0 | 1 | 1Bxzhxzh2022-6-29莆田學(xué)院許振和36 Chomsky語言層，對應(yīng)的文法、語言和自動語言層，對應(yīng)的文法、語言和自動機(jī)關(guān)系如圖機(jī)關(guān)系如圖2-2所示。所示。 圖圖2-2 Chomsky文法、語言及自動機(jī)關(guān)系文法、語言及自動機(jī)關(guān)系xzhxzh2022-6-29莆田學(xué)院許振和37五、上下文無關(guān)文法及其語法樹五、上下文無關(guān)文法及其語法樹1、語法樹（推導(dǎo)樹）的定義：、語法樹（推導(dǎo)樹）的定義： 給定文法給定文法G=（VN，VT，P，S），對于），對于G的任何句型都能的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹，須構(gòu)造與之關(guān)聯(lián)的語法樹，須滿足條件滿足條

31、件為：為： 每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是V的一個(gè)符號。的一個(gè)符號。 根的標(biāo)記是根的標(biāo)記是S。 若一結(jié)點(diǎn)若一結(jié)點(diǎn)n至少有一個(gè)它自己除外的子孫，并且有標(biāo)記至少有一個(gè)它自己除外的子孫，并且有標(biāo)記A，則則A肯定在肯定在VN中。中。 如果結(jié)點(diǎn)如果結(jié)點(diǎn)n的直接子孫，從左到右的次序是結(jié)點(diǎn)的直接子孫，從左到右的次序是結(jié)點(diǎn)n1,n2,nK，其標(biāo)記分別為，其標(biāo)記分別為A1,A2,A K ，那么，那么A A1A2AK一定是一定是P中的一個(gè)產(chǎn)生式。中的一個(gè)產(chǎn)生式。 描述上下文無關(guān)文法的句型推導(dǎo)的直觀方法 。xzhxzh2022-6-29莆田學(xué)院許振和38例例8：G=( S,A,a,b,

32、P,S )，其中，其中P為：為：S aASA SbAA SSS aA ba語法樹：語法樹：SaASaSbAaab說明語法樹滿足說明語法樹滿足： 樹根是樹根是S。 k每個(gè)節(jié)點(diǎn)的標(biāo)記都是每個(gè)節(jié)點(diǎn)的標(biāo)記都是V的一個(gè)符號。的一個(gè)符號。 A有自己的子孫有自己的子孫( S,b,A) ，A VN中。中。SbA是是A SbA的產(chǎn)生式，的產(chǎn)生式，aAS是是S aAS的產(chǎn)生式。的產(chǎn)生式。xzhxzh2022-6-29莆田學(xué)院許振和39 結(jié)點(diǎn)：每個(gè)樹的結(jié)點(diǎn)對應(yīng)于一個(gè)符號。結(jié)點(diǎn)的名字就是結(jié)點(diǎn)：每個(gè)樹的結(jié)點(diǎn)對應(yīng)于一個(gè)符號。結(jié)點(diǎn)的名字就是該符號。該符號。 邊：兩個(gè)結(jié)點(diǎn)之間的連線。邊：兩個(gè)結(jié)點(diǎn)之間的連線。 根結(jié)點(diǎn)：沒有邊進(jìn)

33、入的結(jié)點(diǎn)。根結(jié)點(diǎn)：沒有邊進(jìn)入的結(jié)點(diǎn)。 分支：某個(gè)結(jié)點(diǎn)向下射出的邊和其結(jié)點(diǎn)稱為分支。（父分支：某個(gè)結(jié)點(diǎn)向下射出的邊和其結(jié)點(diǎn)稱為分支。（父子結(jié)點(diǎn)，兄弟結(jié)點(diǎn)）子結(jié)點(diǎn)，兄弟結(jié)點(diǎn)） 子樹：語法樹的某個(gè)結(jié)點(diǎn)和它向下射出的部分。子樹：語法樹的某個(gè)結(jié)點(diǎn)和它向下射出的部分。 末端結(jié)點(diǎn)：沒有向下射出的邊的結(jié)點(diǎn)成為末端結(jié)點(diǎn)。在末端結(jié)點(diǎn)：沒有向下射出的邊的結(jié)點(diǎn)成為末端結(jié)點(diǎn)。在相對于句型的語法樹中，末端結(jié)點(diǎn)可能是非終結(jié)符號相對于句型的語法樹中，末端結(jié)點(diǎn)可能是非終結(jié)符號語法樹的相關(guān)概念語法樹的相關(guān)概念xzhxzh2022-6-29莆田學(xué)院許振和40葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)：樹中：樹中沒有子孫的結(jié)點(diǎn)沒有子孫的結(jié)點(diǎn)。從左到右從左到右

34、讀出推導(dǎo)樹的讀出推導(dǎo)樹的葉子標(biāo)記葉子標(biāo)記連接成的連接成的文文法符號法符號串串，為，為GS的的句型句型。也把該推導(dǎo)。也把該推導(dǎo)樹稱為該樹稱為該句型句型的的語法樹語法樹。語法樹的結(jié)果：語法樹的結(jié)果：從左到右讀出葉子的標(biāo)記而構(gòu)成的行謂之句子從左到右讀出葉子的標(biāo)記而構(gòu)成的行謂之句子xzhxzh2022-6-29莆田學(xué)院許振和41語法樹的理解：語法樹的理解： 語法樹表示了在推導(dǎo)過程中用到什么樣的產(chǎn)生式語法樹表示了在推導(dǎo)過程中用到什么樣的產(chǎn)生式和用到哪些非終結(jié)符，并沒有表明采用的順序。和用到哪些非終結(jié)符，并沒有表明采用的順序。例例9：上式推導(dǎo)樹是：上式推導(dǎo)樹是aabbaa句型的語法樹。句型的語法樹。推導(dǎo)如

35、下：推導(dǎo)如下：? SaAS aAa aSbAa aSbbaa aabbaa? SaAS aSbASaSbAaaabAaaabbaa? SaAS aSbASaabASaabbaSaabbaa都是同一個(gè)語法樹xzhxzh2022-6-29莆田學(xué)院許振和422、最左推導(dǎo)、最左推導(dǎo) （或最右推導(dǎo)）：（或最右推導(dǎo)）：若若（任何一條），（任何一條）， 、是句型，都是對是句型，都是對 中的中的最左（最右）非終結(jié)符進(jìn)行替換，則稱為最左（最最左（最右）非終結(jié)符進(jìn)行替換，則稱為最左（最右）推導(dǎo)。右）推導(dǎo)。 在形式語言中，在形式語言中，最右最右推導(dǎo)常被稱為推導(dǎo)常被稱為規(guī)范規(guī)范推導(dǎo)。推導(dǎo)。 由規(guī)范推導(dǎo)所得的句型稱為規(guī)

36、范句型。由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。 一棵語法樹表示了一個(gè)句型的種種可能的一棵語法樹表示了一個(gè)句型的種種可能的( (但未必是所有但未必是所有的的) )不同推導(dǎo)過程，包括最左不同推導(dǎo)過程，包括最左( (最右最右) )推導(dǎo)。但是，一個(gè)推導(dǎo)。但是，一個(gè)句型是否只對應(yīng)唯一的一棵語法樹呢句型是否只對應(yīng)唯一的一棵語法樹呢? ?一個(gè)句型是否只一個(gè)句型是否只有唯一的一個(gè)最左有唯一的一個(gè)最左( (最右最右) )推導(dǎo)呢推導(dǎo)呢? ?xzhxzh2022-6-29莆田學(xué)院許振和433、文法的二義性的定義：、文法的二義性的定義： 如果一個(gè)文法存在某個(gè)句子對應(yīng)兩棵不同的語如果一個(gè)文法存在某個(gè)句子對應(yīng)兩棵不同的語法樹

37、，則說這個(gè)文法是法樹，則說這個(gè)文法是二義二義的。的。 若一個(gè)文法中存在某個(gè)句子，它有兩個(gè)不同的若一個(gè)文法中存在某個(gè)句子，它有兩個(gè)不同的最左（最右）推導(dǎo)，則這個(gè)文法是最左（最右）推導(dǎo)，則這個(gè)文法是二義二義的。的。 一個(gè)句型是否只對應(yīng)唯一的一棵語法樹？一個(gè)句一個(gè)句型是否只對應(yīng)唯一的一棵語法樹？一個(gè)句型是否只有唯一的一個(gè)最左（最右）推導(dǎo)？型是否只有唯一的一個(gè)最左（最右）推導(dǎo)？ 不是不是xzhxzh2022-6-29莆田學(xué)院許振和44例例10：文法：文法G( E, +，i，(，) ，P，E )，其中其中P為：為：EiE E+EE EEE ( E )則句型則句型ii+i的推導(dǎo)：的推導(dǎo)：推導(dǎo)推導(dǎo)1：EE+

38、E EE+E iE+E iiE iii推導(dǎo)推導(dǎo)2：E EE iE iEE iiE iii產(chǎn)生兩個(gè)不同的語法樹：產(chǎn)生兩個(gè)不同的語法樹：xzhxzh2022-6-29莆田學(xué)院許振和45iEEEiEEiEEEEEiii該文法為二義性該文法為二義性xzhxzh2022-6-29莆田學(xué)院許振和46 例例 句子句子abaabbabaabb的兩棵語法樹的兩棵語法樹 為什么？ 對于一個(gè)文法對于一個(gè)文法G G而言，如果而言，如果L(G)L(G)中存在一個(gè)中存在一個(gè)句子對應(yīng)兩棵或兩棵以上的語法樹，那么該文法句子對應(yīng)兩棵或兩棵以上的語法樹，那么該文法就稱為二義性的。就稱為二義性的。 xzhxzh2022-6-29莆

39、田學(xué)院許振和47二義文法改造為無二義文法二義文法改造為無二義文法 如果規(guī)定如果規(guī)定“”和和“”的優(yōu)先性，并服從左結(jié)合，上的優(yōu)先性，并服從左結(jié)合，上式就可以構(gòu)出無二義性。式就可以構(gòu)出無二義性。例如：文法例如：文法GE: E T | E+TT F | TFF( E ) | i注意，文法的二義性和語言的二義性是兩個(gè)不同的概念注意，文法的二義性和語言的二義性是兩個(gè)不同的概念。 因?yàn)榭赡苡袃蓚€(gè)不同的文法因?yàn)榭赡苡袃蓚€(gè)不同的文法G和和G，其中，其中G是二義是二義的，但是卻有的，但是卻有L(G)=L(G)。 產(chǎn)生某上下文無關(guān)語言的每一個(gè)文法都是二義的，產(chǎn)生某上下文無關(guān)語言的每一個(gè)文法都是二義的，則稱此語言是

40、則稱此語言是先天二義的。先天二義的。 判定任給的一個(gè)上下文無關(guān)文法是否二義，或它是判定任給的一個(gè)上下文無關(guān)文法是否二義，或它是否產(chǎn)生一個(gè)先天二義的上下文無關(guān)語言，這兩個(gè)問題是否產(chǎn)生一個(gè)先天二義的上下文無關(guān)語言，這兩個(gè)問題是遞歸不可解的。但可以為無二義性尋找一組充分條件。遞歸不可解的。但可以為無二義性尋找一組充分條件。xzhxzh2022-6-29莆田學(xué)院許振和48本章重點(diǎn)：本章重點(diǎn)：1、符號、符號串、句型、句子、語言、符號、符號串、句型、句子、語言2、理解有關(guān)文法、閉包、正閉包、規(guī)則、理解有關(guān)文法、閉包、正閉包、規(guī)則、推導(dǎo)推導(dǎo)3、文法的類型、文法的類型xzhxzh2022-6-29莆田學(xué)院許振和49課堂習(xí)題與練習(xí)：課堂習(xí)題與練習(xí)：1、假設(shè)G是一個(gè)文法，S是文法的開始符號，如果Sx，則稱