第二章文法和語言一、文法的概念二、符號和符號串三、文法和語言的定義四、文法的類型五、上下文無關文法及其語法樹7/23/20231莆田學院許振和本章要求主要內容：符號串，文法的概念及分類，語言的定義過程重點掌握：上下文無關文法、推導、句型、句子、語言，語法樹、二義性文法、文法的語言生成過程7/23/20232莆田學院許振和構結識知文法和語言符號和符號串字母表和符號串符號串集合的運算文法和語言的形式定義文法的形式定義語言的形式定義語法分析的基本術語規則文法推導和規約句型/句子/語言短語和句柄最左最右推導和規約語法樹和二義性語法樹的構造語法樹與短語文法的二義性文法的實用限制7/23/20233莆田學院許振和語言是由單詞按一定規則（文法）組成句子來表達特定意思。故對語言的分析集中于對句子的分析。而句子的分析依據語言的文法規則。程序設計語言可以通過描述以下兩個要素來定義：

第一方面是程序模式，即語言的語法；第二方面是程序含義，即語言的語義。文法與語言語義分為兩類：

靜態語義動態語義7/23/20234莆田學院許振和一、文法的概念所謂一個語言的語法是指一組規則，用它可以形成和產生一個合適的程序。由單詞符號按照一定的規則構成各種類型的表達式、語句、分程序（程序），即不同的語法范疇。不同的語法范疇具有不同的構成規律。單詞符號的構成規則稱為詞法規則。各種語法范疇構成規則稱為語法規則。描述詞法規則和語法規則的工具是文法。文法表示用語法圖(語法樹)和EBNF(巴科斯-諾爾)描述。目前廣泛使用的手段是上下文無關文法，即用上下文無關文法作為程序設計語言語法的描述工具。7/23/20235莆田學院許振和語言語法：是一組規則,定義符號如何排列，排列與符號含義無關。即程序的結構或形式語義：研究語言所代表的含義語用：語言的實際應用語言的表示方法1、用識別的觀點表示語言，這種方法是給出一種算法由它判定一個句子是否在語言中。2、用產生的觀點表示語言7/23/20236莆田學院許振和〈句子〉∷=〈主語〉〈謂語〉〈主語〉∷=〈代詞〉|〈名詞〉〈代詞〉∷=我|你|他〈名詞〉∷=王明|大學生|工人|英語〈謂語〉∷=〈動詞〉〈直接賓語〉〈動詞〉∷=是|學習〈直接賓語〉∷=〈代詞〉|<名詞>先舉個例子：用EBNF表示7/23/20237莆田學院許振和推導：你是大學生

〈句子〉〈主語〉〈謂語〉〈代詞〉〈謂語〉你〈謂語〉你〈動詞〉〈直接賓語〉你是〈名詞〉你是大學生由上一組規則可以產生句子：你是大學生

這樣的語言描述稱為文法“=>”表示由某條規則的右部替換該規則的左部，把它稱之為推導。7/23/20238莆田學院許振和語句“小八哥吃大花生”分析的語法樹上下〈句子〉〈主語〉〈謂語〉〈形容詞〉〈名詞〉〈動詞〉〈賓語〉小八哥吃〈形容詞〉〈名詞〉

大 花生7/23/20239莆田學院許振和句子的推導

<句子>?<主語><謂語>

?<形容詞><名詞><謂語>

?<小><名詞><謂語>

?<小><八哥><謂語>

?<小><八哥><動><賓語>

?小八哥吃<賓語>

?小八哥吃<形容詞><名詞>

?小八哥吃大<名詞>

?小八哥吃大花生7/23/202310莆田學院許振和〈謂語〉〈主語〉〈形容詞〉〈名詞〉〈動詞〉〈賓語〉小八哥吃花生大

下〈形容詞〉〈名詞〉上

〈句子〉句子的歸約7/23/202311莆田學院許振和二、符號和符號串

任何一種語言，都是由該語言的基本字符所組成的字符串的集合。1、語言可以看成在一個基本符號集上定義的，按一定規則構成的一切基本符號串組成的集合。2、字母表(符號集)：是字母的有窮非空集合。用希臘字母∑或大寫英文字母等表示字母表。3、符號（字符）：字母表中的元素。因此字母表也稱為符號集。用集合元素表示形式枚舉字母表中的符號。符號是該語言能識別的符號，字母表是該語言能識別的所有符號的全體（字符集）

4、符號串(字符串)：字母表的符號組成任何有窮序列。例：∑={0，1}—符號集符號串有：0，1，00，01，10，117/23/202312莆田學院許振和例：∑={a，b，c}—符號集符號串有：a，b，c，ab，aaca

在符號串中，符號的順序是很重要的，符號串ab就不同于ba,abca和aabc也不同。

【注】不同排列順序表示不同的含義。5、符號串集合：字母表上若干個符號串組成的集合。6、符號串的長度：符號串x有m個符號，則長度就為m，表示|x|=m。

如：ababa

則長度是5。定義在字母表Σ={x,，y，z，=，0，1，+，;}

上的符號串|x=y++；z=0;|=107、空符號串：用ε表示，長度為0，||=0

若符號串x,則有εx=xε=x7/23/202313莆田學院許振和8、符號串的運算：(1)符號串的頭(前綴)和尾(后綴)

若z=xy,則x是z的頭，y是z的尾。例：設z=abc,則z的頭是ε，a，ab，abc

則z的尾是ε，c，bc，abc（2）符號串的固有頭(真前綴)和固有尾(真后綴)

若z=xy符號串，x非空，則y固有尾；若y非空，則x是固有頭。例：設z=abc，則z的固有頭是ε，a，ab

則z的固有尾是ε，c，bc7/23/202314莆田學院許振和（3）子符號串（子串）

從一個符號串中刪去它的一個前綴或(和)一個后綴之后剩余的部分稱為該符號串的子符號串或子串。例如:x=abcd

則ε,a,b,c,ab,bc,cd,abc,bcd及abcd都是

x的子字符串。 而ac，ad，cb，bd，ba

等都不是x的子字符串。7/23/202315莆田學院許振和（4）符號串的連接：

設x，y是符號串，連接xy是y符號寫在x符號之后。記作xy。例如，設有字符串j=abc，k=xyz

則jk=abcxyz，kj=xyzabc。連接運算是有序的。一般來說xy≠yx，僅當x=y 或其中之一為ε時,有xy=yx。顯然：εx=xε=x(5)符號串的方冪：設x是符號串，則z=xx……xx，稱z為x的方冪,記z=xn。因此x0=ε,x1=x,x2=xx,x3=xxx

顯然n>0時,有xn

=x·xn-1＝xn-1·xn個7/23/202316莆田學院許振和

(6)符號串的集合：

若集合A中的一切元素都是某字母表上的符號串，則稱A為該字母表上的符號串集合。兩個符號串集合A、B乘積定義：

AB={xy|x∈A且y∈B}

例：A={a,b}，B={c,d}

則AB={ac，ad，bc，bd}注意：有{ε}A=A{ε}=A,?A=A?=?

，其中?為空集。 ?≠{ε} ?={}≠{ε}

。7/23/202317莆田學院許振和

(7)閉包（∑*）字母表∑，用∑*表示∑上所有有窮長的串集合，∑*稱為∑的閉包。例：字母表∑={0,1}

則∑*={ε,0,1,00,01,10,11,000,001,010……}=∑0∪∑1∪∑2∪.…∪∑n

(8)正閉包(∑+)∑+=∑1∪∑2∪.…∪∑n

∑+稱∑的正閉包。顯然：∑*＝∑0∪∑+∑+＝∑∑*＝∑*∑根據集合乘積的定義7/23/202318莆田學院許振和如何來描述一種語言？如果語言是有窮的（只含有有窮多個句子），可以將句子逐一列出來表示如果語言是無窮的，找出語言的有窮表示。語言的有窮表示有兩個途經：

三、文法和語言的形式定義生成方式（文法）：語言中的每個句子可以用嚴格定義的規則來構造。識別方式（自動機）：用一個過程，當輸入的一任意串屬于語言時，該過程經有限次計算后就會停止并回答“是”，若不屬于，要麼能停止并回答“不是”，（要麼永遠繼續下去。）7/23/202319莆田學院許振和

1、規則（產生式、生成式）

形如→β或

::=β是字母表V的正閉包V+的一個符號；

β是字母表V的閉包V*的一個符號；稱規則的左部，β稱規則的右部。2、文法的定義〈1〉文法G定義為四元組（VN，VT，P，S）文法中規則P的第一種表示法7/23/202320莆田學院許振和其中：VN——非終結符號集

VT——終結符號集

P——產生式（規則）

S——開始符號或稱作識別符號，它是一個非終結符，至少要在一條規則中作為左部出現。規定：（1）VN，VT，P是有窮非空集合；（2）VN∩VT＝

（不含公共元素）V=VN∪VT，稱為文法G的字母表（字匯表）7/23/202321莆田學院許振和例1文法G=（VN，VT，P，S），其中VN={S}，VT={0，1}，

P={S→0S1，S→01}。非終結符集中只含一個元素S；終結符集由兩個元素0和1組成；有兩條產生式；開始符號是S。明顯求出：S＝{01，0011，000111，…}7/23/202322莆田學院許振和例2文法G=（VN，VT，P，S）其中VN={標識符，字母，數字}VT={a,b,c,…,x,y,z,0,1,…,9}

P={<標識符>→〈字母〉<標識符>→<標識符><字母〉<標識符>→<標識符><數字〉<字母>→a

<字母>→b…<字母>→z<數字>→1…<數字>→9｝S＝<標識符>“<>”表示非終結符7/23/202323莆田學院許振和<2>文法中規則P的第二種表示法：上例1改為：G:S→0S1S→01<3>文法中規則P的第三種表示法：上例1改為：G[S]:S→0S1S→01一般約定，第一條產生式的左部是識別符號；用尖括號括起來的是非終結符號，不用尖括號括起來的是終結符號，或者用大寫字母表示非終結符號，小寫字母表示終結符號。7/23/202324莆田學院許振和<1>→

是文法G=（VN，VT，P，S）的規則，和是V*中的任意符號，若有符號V，W滿足：

V=

，W＝

則說V是直接產生W

或W是V的直接推導或W直接規約到V記作VW3、直接推導“=>”

從識別符號開始，不斷將當前符號串中的非終結符號替換為該符號的某個規則的右部。直到當前的符號串中所有的符號都是終結符號為止。7/23/202325莆田學院許振和若有VW，或V=W，則記作VW(0步或若干步)

例子：在例1中存在序列：V＝0S100S11000S11100001111＝W記作：0S1000011110S100001111+＋+*若存在直接推導的序列：

V=W0

W1W2…Wn

＝W(n>0)則稱V推導W(或W規約到V)，記VW(至少一步)

*一樣的7/23/202326莆田學院許振和4、句型的定義設G[S]是文法，如果符號串x是從識別符號（開始符號）推導出來的（即Sx）則稱x是文法G[S]的句型。若x僅由終結符號組成（SxxVT*）則稱x為G[S]的句子。**例：S，0S1，000111都是文法G的句型，000111是G的句子?！冀Y論〗句子一定是句型，句型不一定是句子。7/23/202327莆田學院許振和5、語言的定義：

L(G)表示文法G產生的語言定義為：集合｛xSx，S為文法開始符號，

xVT*

｝該集合為語言，用L(G)表示。從定義可知：x是句型且x是文法G的句子。注：語言是文法所產生的所有句子組成的集合。例：例1的句子表示為：

L(G)＝｛0n1n

n1｝因為S0S100S11…0n1n重復利用規則S0S1*7/23/202328莆田學院許振和四、文法的類型：科學家Chomsky把文法分成以下四種類型：0型短語文法1型上下文有關文法2型上下文無關文法3型正規文法文法類型逐漸增加限制如果文法是正規文法一定也是上下文無關文法7/23/202329莆田學院許振和文法的類型2型文法1型文法0型文法四種文法之間的逐級“包含”關系3型文法7/23/202330莆田學院許振和設G=(VN,VT,P,S)，如果它的每一個產生式滿足：(VN∪VT)*且至少包含一個非終結符，(VN∪VT)*，則G是0型文法。

0型文法又稱為無限制文法，有時也稱為短語文法。0型文法對應的語言稱為0型語言或稱遞歸可枚舉集，它們的識別系統為圖靈機（Turing機）。設G=(VN,VT,P,S)，如果它的每一個產生式滿足：||≥||，僅僅S除外，則文法G是1型文法。7/23/202331莆田學院許振和下文只講上下文無關文法和正規文法

4個文法類的定義是逐漸增加限制的，因此，每一種正規文法都是上下文無關的，每一種上下文無關文法都是上下文有關的，而每一種上下文有關文法都是0型文法。1型文法相對應的語言稱為1型語言或上下文有關語言，它的識別系統是線性界限自動機。7/23/202332莆田學院許振和1、上下文無關文法：設G=（VN，VT，P，S），若P中的每一個產生式→滿足：

是一非終結符，(VN∪VT)*，則此文法稱為上下文無關文法(2型文法)。

2型文法相對應的語言稱為2型語言或上下文無關語言，它的識別系統為下推自動機(PDA)。例6：G＝({S,A,B},{a,b},P,S)，P的產生式如下：S→aB

S→bAA→bAA

A→aA→aSB→bB→bSB→aBB上下文無關文法7/23/202333莆田學院許振和該文法可以寫成：S→aB

|bAA→a

|aS|bAAB→b|Bs|aBB2、正規文法：設G=（VN，VT，P，S），若P中的每一個產生式都是A→aB或A→a，A,B都是非終結符，a是終結符，則G是正規文法（也稱右線性文法）。

3型文法對應的語言稱為3型語言或正規語言（正則語言，或正則集）。7/23/202334莆田學院許振和例6：G＝({S,A,B},{0,1},P,S)，P的產生式如下：S→0AS→1BS→0A→0SA→0AA→1BB→1B→0B→1B正規文法該文法可以寫成：S→0|0A|1BA→0S|0A|1BB→0|1|1B7/23/202335莆田學院許振和

Chomsky語言層，對應的文法、語言和自動機關系如圖2-2所示。圖2-2Chomsky文法、語言及自動機關系7/23/202336莆田學院許振和五、上下文無關文法及其語法樹1、語法樹（推導樹）的定義：給定文法G=（VN，VT，P，S），對于G的任何句型都能構造與之關聯的語法樹，須滿足條件為：

每個結點都有一個標記，此標記是V的一個符號。

根的標記是S。

若一結點n至少有一個它自己除外的子孫，并且有標記A，則A肯定在VN中。

如果結點n的直接子孫，從左到右的次序是結點n1,n2,…,nK，其標記分別為A1,A2,…,AK

，那么AA1A2…AK一定是P中的一個產生式。描述上下文無關文法的句型推導的直觀方法。7/23/202337莆田學院許振和例8：G=({S,A},{a,b},P,S)，其中P為：SaASASbAASSSaAba語法樹：SaASaSbAaab說明語法樹滿足：樹根是S。每個節點的標記都是V的一個符號。A有自己的子孫(S,b,A)，AVN中。SbA是A

SbA的產生式，aAS是S

aAS的產生式。7/23/202338莆田學院許振和結點：每個樹的結點對應于一個符號。結點的名字就是該符號。邊：兩個結點之間的連線。根結點：沒有邊進入的結點。分支：某個結點向下射出的邊和其結點稱為分支。（父子結點，兄弟結點）子樹：語法樹的某個結點和它向下射出的部分。末端結點：沒有向下射出的邊的結點成為末端結點。在相對于句型的語法樹中，末端結點可能是非終結符號語法樹的相關概念7/23/202339莆田學院許振和葉子結點：樹中沒有子孫的結點。

從左到右讀出推導樹的葉子標記連接成的文法符號串，為G[S]的句型。也把該推導樹稱為該句型的語法樹。語法樹的結果：從左到右讀出葉子的標記而構成的行謂之句子7/23/202340莆田學院許振和語法樹的理解：語法樹表示了在推導過程中用到什么樣的產生式和用到哪些非終結符，并沒有表明采用的順序。例9：上式推導樹是aabbaa句型的語法樹。推導如下：

SaASaAaaSbAaaSbbaaaabbaa

SaASaSbASaSbAaaabAaaabbaa

SaASaSbASaabASaabbaSaabbaa都是同一個語法樹7/23/202341莆田學院許振和2、最左推導（或最右推導）：若β（任何一條），、β是句型，都是對中的最左（最右）非終結符進行替換，則稱為最左（最右）推導。在形式語言中，最右推導常被稱為規范推導。由規范推導所得的句型稱為規范句型。

一棵語法樹表示了一個句型的種種可能的(但未必是所有的)不同推導過程，包括最左(最右)推導。但是，一個句型是否只對應唯一的一棵語法樹呢?一個句型是否只有唯一的一個最左(最右)推導呢?7/23/202342莆田學院許振和3、文法的二義性的定義：如果一個文法存在某個句子對應兩棵不同的語法樹，則說這個文法是二義的。若一個文法中存在某個句子，它有兩個不同的最左（最右）推導，則這個文法是二義的。一個句型是否只對應唯一的一棵語法樹？一個句型是否只有唯一的一個最左（最右）推導？不是7/23/202343莆田學院許振和例10：文法G＝({E},{+，×，i，(，)}，P，E)，其中P為：EiEE+EEE×EE(E)則句型i×i+i的推導：推導1：EE+EE×E+Ei×E+Ei×i＋Ei×i＋i推導2：EE×Ei×Ei×E＋Ei×i＋Ei×i＋i產生兩個不同的語法樹：7/23/202344莆田學院許振和iEEE×iEE＋iEE＋EEE×iii該文法為二義性7/23/202345莆田學院許振和[例]句子abaabb的兩棵語法樹

為什么？

對于一個文法G而言，如果L(G)中存在一個句子對應兩棵或兩棵以上的語法樹，那么該文法就稱為二義性的。

7/23/202346莆田學院許振和二義文法改造為無二義文法如果規定“×”和“＋”的優先性，并服從左結合，上式就可以構出無二義性。例如：文法G[E]:ET|E+TTF|T×FF(E)|i注意，文法的二義性和語言的二義性是兩個不同的概念。因為可能有兩個不同的文法G和G`，其中G是二義的，但是卻有L(G)=L(G`)。

產生某上下文無關語言的每一個文法都是二義的，則稱此語言是先天二義的。判定任給的一個上下文無關文法是否二義，或它是否產生一個先天二義的上下文無關語言，這兩個問題是遞歸不可解的。但可以為無二義性尋找一組充分條件。7/23/202347莆田學院許振和本章重點：1、符號、符號串、句型、句子、語言2、理解有關文法、閉包、正閉包、規則、推導3、文法的類型7/23/202348莆田學院許振和課堂習題與練習：1、假設G是一個文法，S是文法的開始符號，如果Sx，則稱x是__________。*句型2、文法G產生的_________的全體是該文法描述的語言。句子3、喬姆斯基定義的四種形式語言文法分別為:(1)文法(又"稱

(2)文法)、

(3)文法(又稱

(4)文法)、

(5)文法(又稱

(6)文法)、

(7)文法(又稱

(8)文法)。答案：(1)0型(2)短語結構(3)1型(4)上下文有關

(5)2型(6)上下文無關(7)3型(8)正規7/23/202349莆田學院許振和4、如果一個文法滿足

，則稱該文法是二義文法。①文法的某一個句子存在兩棵（包括兩棵）以上的語法樹②文法中存在某個句子，它有兩個（包括兩個）以上的最右（最左）推導③文法中存在某個句子，它有兩個（包括兩個）以上的最右（最左）歸約④在進行歸約時，文法的某些規范句型的句柄不惟一可選項有：a.①b.②c.③d.④e.②③f.①②③g.①②③④答案：gg7/23/202350莆田學院許振和5、一個語言的文法是【

】。

a.唯一