文法和語言第2章一個程序設計語言是一個記號系統，它的完整定義應包括兩個方面:語法

指一組規則，用它可以形成和產生一個合適的程序。語義靜態語義

是一系列限定規則，并確定哪些合乎語法的程序是合適的；動態語義

也稱作運行語義或執行語義，表明程序要做些什么，要計算什么。文法是闡明語法的一個工具2.2符號和符號串字母表字母表是元素的非空有窮集合符號字母表中的元素稱為符號符號串由符號組成的任何有窮序列符號串x的長度：x所包含的符號個數，記作|x|空符號串符號串的頭、尾、固有頭、固有尾符號串的連接設x和y是符號串，它們的連接xy是把y的符號寫在x的符號之后得到的符號串。符號串的方冪設x是符號串，把x自身連接n次得到符號串z，即z=xx...xx，稱為符號串x的方冪。

α0=ε,αn=ααn-1=αn-1α（n>0）符號串集合及其運算若集合A中的一切元素都是字母表上的符號串，則稱A為該字母表上的符號串集合。合并：字符串集合A和B的合并A∪B={α|α∈A或α∈B}。乘積：字符串集合A和B的乘積AB={αβ|α∈A且β∈B}。

顯然{ε}A=A{ε}=A。冪：An=An-1A=AAn-1（n>0），并規定A0={ε}。正閉包：A+=A1∪A2∪…∪An∪…。閉包：A*=A0∪A+。

顯然Σ*=Σ0∪Σ1∪Σ2∪…∪Σn∪…。

Σ*表示Σ上的所有有窮長的串的集合2.3文法和語言的形式定義引例1

∑={a},A={an|n≥1}引例2

∑={a,b},A={anbm|n,m≥1}引例3

∑={a,b},A={anbn|n≥1}定義2.1-文法

文法G定義為四元組(VN，VT，P，S)。其中

VN:非終結符的非空有窮集；

VT:終結符的非空有窮集；

P:產生式（也稱規則）的非空有窮集；

S:開始符號，它是一個非終結符，至少要在一條規則中作為左部出現。

通常用V表示VNVT，V稱為文法G的文法符號集。例1

∑={a,b},A={ambn|m≥n≥0}例2

∑={a,b},A={wwR|wR是w的反向串}例3

G[S]:

SaSBE|aBE

EBBE

aBab

bBbb

bEbe

eEee定義2.2-直接推導、直接歸約

設是文法G=(VN，VT，P，S)的規則，和是V*中的任意符號串。若有符號串v，w滿足：v=，w=，則說v（應用規則）直接產生w，或說w是v的直接推導，或說w直接歸約到v，記作vw。定義2.3-推導

若存在vw0w1...wn=w(n>0)，則說v推導出w，或說w歸約到v，記為

v

w。定義2.4-星推導

若有vw，或v=w，則記為

v

w。最左（最右）推導如果在推導的任何一步，其中∈V*，都是對中的最左（最右）非終結符進行替換，則稱這種推導為最左（最右）推導規范推導在形式語言中，最右推導常被稱為規范推導。定義2.5-句型、句子

設有文法G。若Sx，則稱x是文法G的句型；

若Sx，且x∈VT*，則稱x是文法G的句子。

規范句型由規范推導所得的句型稱為規范句型。定義2.6-語言

由文法G生成的語言記為L(G),它是文法G的一切句子的集合。

定義2.7-文法等價

若L(G1)=L(G2)，則稱文法G1和G2是等價的。2.4文法的類型Chomsky分類0型文法–短語文法

對任一產生式α→β，都有α∈(VN∪VT)+且至少含有一個非終結符，β∈(VN∪VT)*1型文法-上下文有關文法（CSG）

對任一產生式α→β，都有|β|≥|α|，僅僅S→ε除外2型文法-上下文無關文法（CFG）

對任一產生式α→β，都有α∈VN，β∈(VN∪VT)*3型文法-正規文法（RG）

任一產生式α→β的形式都為A→aB或A→a，其中A∈VN，B∈VN，a∈VT0型文法產生的語言稱為0型語言

1型文法或上下文有關文法產生的語言稱為1型語言或上下文有關語言

2型文法或上下文無關文法產生的語言稱為2型語言或上下文無關語言

3型文法或正規文法產生的語言稱為3型語言正則規語言例

給出一個正規文法G，使

L(G)={anbm|n,m≥1}2.5上下文無關文法及其語法樹引例

G[S]:

SaAS|a

ASbA|SS|ba

寫出aabbaa的最左推導和最右推導。給定文法G=(VN,VT,P,S)，對于G的任何句型都能夠造與之關聯的語法樹。這棵樹滿足下列4個條件：每個結點都有一個標記，此標記是V的一個符號。根的標記是S。若一結點n至少有一個它自己除外的子孫，并且有標記A，則肯定A∈VN。如果結點n有標記A,其直接子孫結點從左到右的次序是n1，n2，…，nk，其標記分別為A1，A2，…，Ak，那么A→A1A2…Ak一定是P中的一個產生式。一棵語法樹表示了一個句型的種種可能的(但未必是所有的)不同推導過程，包括最左(最右)推導。從左到右讀出推導樹的葉子標記連接成的文法符號串為G的句型。若一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是二義的。或者說，若一個文法存在某個句子有兩個不同的最左（右）推導，則稱這個文法是二義的。例1

G[E]:

EE+E|E*E|(E)|I例2

G[E]:

E-EE|-E|a|b|c

文法的二義性和語言的二義性是兩個不同的概念。因為可能有兩個不同的文法G和G′，其中G是二義的，但是卻有L(G)=L(G′)，也就是說，這兩個文法所產生的語言是相同的。2.6句型的分析句型分析句型分析就是識別一個符號串是否為某文法的句型，是某個推導的構造過程。分析程序（識別程序）在語言的編譯實現中，把完成句型分析的程序稱為分析程序或識別程序。分析算法自上而下分析法自下而上分析法

考慮文法G[S]：

ScAd

Aab

Aa

識別輸入串w=cabd是否該文法的句子。自上而下分析法的主要問題：

假定要被替換的最左非終結符是V且有n條產生式：Vα1|α2|…|αn，那么如何確定用哪個右部去替換V？

自下而上分析法的關鍵問題：

從當前串中選擇一個可以歸約到某個非終結符的子串（稱為“可歸約串”）。定義3.8-短語，直接短語，句柄

設文法G[S]

如果有S

αAδ且Aβ，則稱β是句型αβδ相對于非終結符A的短語。

如果有Aβ，則稱β是句型αβδ相對于非終結符A的直接短語（簡單短語）。

一個句型的最左直接短語稱為該句型的句柄。例

設文法G[E]：

E→E+T|T

T→T*F|F

F→(E)|i

求句型i*i+i的短語、直接短語和句柄2.7有關文法實用中的一些說明在實用中，我們將限制文法中不