第3章 文法和語言教學要求：本章是編譯原理課程的理論基礎，要求理解文法、語言、規范推導、規范歸約和短語、簡單短語、句柄的基本概念；掌握語言的求解方法、文法的二義性的判斷方法及句型的分析方法。教學重點：上下文無關文法，語言定義

一、語言語言是由句子組成的集合，是由一組記號所構成的集合。漢語--所有符合漢語語法的句子的全體英語--所有符合英語語法的句子的全體程序設計語言--所有該語言的程序的全體“我是大學生”是否是該語言的句子？〈句子〉::=〈主語〉〈謂語〉〈主語〉::=〈代詞〉|〈名詞〉〈代詞〉::=你|我|他〈名詞〉::=王明|大學生|工人|英語〈謂語〉::=〈動詞〉〈直接賓語〉〈動詞〉::=是|學習〈直接賓語〉::=〈代詞〉|〈名詞〉二、文法一種語言描述工具，用來定義句子的結構，用有限的規則把語言的全部句子描述出來，是以有窮的集合刻劃無窮的集合的工具。“::=”與“→”等價，表示為“由什么組成”或“定義為”〈句子〉〈主語〉〈謂語〉

〈代詞〉〈謂語〉

我〈謂語〉

我〈動詞〉〈直接賓語〉

我是〈直接賓語〉

我是〈名詞〉

我是大學生〈句子〉::=〈主語〉〈謂語〉〈主語〉::=〈代詞〉|〈名詞〉〈代詞〉::=你|我|他〈名詞〉::=王明|大學生|工人|英語〈謂語〉::=〈動詞〉〈直接賓語〉〈動詞〉::=是|學習〈直接賓語〉::=〈代詞〉|〈名詞〉語法變量（在形式語言中又稱“非終結符”）單詞符號（在形式語言中又稱“終結符號”)三、符號和符號串例如：漢語的字母表中包括漢字、數字及標點符號等。C語言的字母表是由字母、數字、若干專用符號及IF、FOR之類的保留字組成。1、字母表和符號串字母表：符號的非空有限集例：={a，b，c}符號：字母表中的元素例：a，b，c符號串：符號的有窮序列例：a,aa,ac,abc，..空符號串：無任何符號的符號串(ε)符號串集合：由符號串構成的集合。2、符號串的運算符號串的長度：符號串中符號的個數.符號串s的長度記為|s|。ε的長度為0符號串的連接：符號串x、y的連接,是把y的符號寫在x的符號之后得到的符號串xy

例x=ST,y=abu則xy=STabu

|x|=2,|y|=3,|xy|=5εx=xε=x方冪：符號串x自身連接n次得到的符號串

xx…xx(n個x)定義為

xnx0=ε,x1=x,x2=xx,x3=xxxx=AB,則

x0=ε,x1=AB,x2=ABAB,x3=ABABAB對于

n>0,xn=xxn-1=xn-1x

3、符號串集合

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

AB=xy|xA且yB若集合A=a,bB=c,d則AB=ac,ad,bc,bd{ε}A=A{ε}=A(∵εx=xε=x)使用*表示上的所有有窮長的串（包括ε）的集合。Σ*稱為Σ的閉包。從*中除去ε得到的集合記為+。

Σ+稱為Σ的正閉包。Σ*=Σ0∪Σ1∪Σ2…∪Σn…Σ+=Σ1∪Σ2…∪Σn…Σ*=Σ0∪Σ+Σ+=ΣΣ*=Σ*ΣΣ+=Σ*-{ε}例：設Σ={0,1}，則Σ*={ε,0,1,00,01,10,11,000,001,010,…}例：設Σ={a,b}，則Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}四、文法和語言的形式定義1、文法的形式定義1）規則（重寫規則、產生式或生成式）：是一個有序對（α，β）。記為α→β或α∷=β，其中α∈V+，β∈V*。α稱為規則的左部(或生成式的左部)。β稱為規則的右部(或生成式的右部)。2）文法G[S]：文法為四元組（VN，VT，P，S）VN：非終結符集VT：終結符集P：產生式（規則）集合S：開始符號（識別符號）VN、VT

和P是非空有窮集。S至少在一條規則中作為左部出現。VN∩VT=φ，S∈VNV=VN∪VT，稱為文法G的字母表（字匯表）例:文法G=（VN，VT，P，S） VN={S},VT={0,1} P={S→0S1,S→01} S為開始符號例:文法G=（VN，VT，P，S） VN={標識符，字母，數字}

VT={a,b,c,…x,y,z,0,1,…,9} P={<標識符>→<字母> <標識符>→<標識符><字母> <標識符>→<標識符><數字> <字母>→a,…,<字母>→z

<數字>→0,…,<數字>→9}

S=<標識符>習慣上只將產生式寫出。并有如下約定：第一條產生式的左部是開始符號用尖括號括起的是非終結符，否則為終結符。或者大寫字母表示非終結符，小寫字母表示終結符G可寫成G[S]，其中S是開始符號例:文法G=（VN，VT，P，S） VN={S},VT={0,1} P={S→0S1,S→01} S為開始符號可寫成：

G：S→0S1 S→01或寫成：

G[S]：S→0S1 S→01

Mini_C介紹

Mini_C語言是在C語言的基礎上定義的一種語言（C語言的子集），它的文法定義如下：1<程序>::=MAIN()<語句塊>2<語句塊>::={<變量聲明列表><語句串>}|{語句串}3<變量聲明列表>::=<變量聲明列表><變量聲明>|<變量聲明>4<變量聲明>::=<變量類型><ID>;5<變量類型>::=int|char|real6<語句串>::=<語句>;|<語句串><語句>;7<語句>::=<賦值語句>|<條件語句>|<循環語句>8<賦值語句>::=<ID>=<算術表達式>9<條件語句>::=if(<條件>)<語句塊>|if(<條件>)<語句塊>else<語句塊>10<循環語句>::=<while語句>|<for語句>

11<while語句>::=while(<條件>)<語句塊>12<for語句>::=for(<賦值語句>;<條件>;<算術表達式>)<語句塊>13<條件>::=<算術表達式><關系運算符><算術表達式>14<關系運算符>::=>|>=|<|<=|==|!=15<算術表達式>::=<算術表達式>+<項>|<算術表達式>-<項>|<項>五、推導的定義1）直接推導“”α→β是文法G的產生式，γ,δ∈V*，若將α→β作用于v=γαδ得到w=γβδ,則記作

vw，讀作v（應用規則α→β）直接產生w（w是v的直接推導或w直接歸約到v）例：G：S→0S1，S→01直接推導：0S10011（v=0S1，w=0011，使用規則S→01，γ=0，δ=1）S0S1（v=S，w=0S1，使用規則S→0S1，γ=ε，δ=ε）0S100S11（v=0S1，w=00S11，使用規則S→0S1，γ=0，δ=1）例文法G=（VN，VT，P，S） VN={標識符，字母，數字}

VT={a,b,c,…x,y,z,0,1,…,9} P={<標識符>→<字母> <標識符>→<標識符><字母> <標識符>→<標識符><數字> <字母>→a,…,<字母>→z<數字>→0,…,<數字>→9}

S=<標識符>指出下面直接推導所使用的規則：<標識符>

<標識符><字母><標識符><字母><數字>

<字母><字母><數字>abc<數字>abc52）長度為n的推導（有限次推導）

若存在v=w0w1...wn=w,(n>0)，

則稱v推導出w（或w歸約到v）.記作

vw。3）若有vw，或v=w，則記為vw++*例：G：S→0S1，S→010S100S11000S11100001111即0S100001111也記作0S100001111+*六、文法的句型、句子的定義1）句型設G[S]是一文法，如果符號串x是從識別符號推導出來的，即Sx，則稱x是文法G[S]的句型。*例：G：S→0S1，S→01S0S100S11000S11100001111*2）句子x僅由終結符號組成（即Sx，且x∈VT*），則稱x是G[S]的句子。3）語言由文法G產生的所有句子組成的集合叫做文法G所成描述的語言，記為L(G)。

例：G：S→0S1，S→01L(G)={0n1n|n≥1}

注：產生式中含有遞歸式，產生的句子是無窮的*L(G)={x|Sx，其中S為文法的開始符號，且x∈VT*}例:文法G[S]： （1）S→dAB （2）A→aA （3）A→a （4）B→Bb （5）B→ε

L（G）=?G生成的每個串都在L(G)中L(G)中的每個串確實能被G生成例：構造生成語言L=的文法。分析：n≧1，所以必須用遞歸規則。a和b的個數一樣多，但c的個數不同，所以將生成含a,b的部分與生成含e的部分分開，A生成ab，B生成e.G[Z]:Z→ABA→aAb|abB→eB|ε≧≧4)文法的等價若L（G1）=L（G2），則稱文法G1和G2是等價的。

如文法G1[A]：A→0R與G2[S]：S→0S1等價

A→01S→01R→A1七、文法的類型（1）0型文法(短語文法)：對任一產生式α→β，都有α∈(VN∪VT)+，β∈(VN∪VT)*

（2）1型文法(上下文有關文法)：

對任一產生式α→β，都有|β|≥|α|，僅僅

S→ε除外。即α1Aα2→α1βα2(A在VN中，其他在V*中，β≠ε)（3）2型文法（上下文無關文法）：對任一產生式α→β，都有α∈VN，β∈(VN∪VT)*

即A→β(A在VN中，β在V*中，)（4）3型文法（正規文法）：任一產生式α→β的形式都為A→aB或A→a，其中A∈VN，B∈VN，a∈VT例：1型（上下文有關）文法

文法G[S]： S→aSBE S→aBE EB→BE aB→ab bB→bb bE→be eE→ee例：2型（上下文無關）文法

文法G[S]： S→aB|bA A→a|aS|bAA B→b|bS|aBB

文法G[S]： S→0A|1B|0 A→0A|1B|0S B→1B|1|0例：定義標識符的3型（正規）文法

文法G[I]： I→lT I→l T→lT

T→dT

T→l

T→d文法和語言0型文法產生的語言稱為0型語言1型文法或上下文有關文法（CSG）產生的語言稱為1型語言或上下文有關語言（CSL）2型文法或上下文無關文法（CFG）產生的語言稱為2型語言或上下文無關語言（CFL）3型文法或正則（正規）文法（RG）產生的語言稱為3型語言或正則（正規）語言（RL）八、上下文無關文法及其語法樹上下文無關文法有足夠的能力描述現今程序設計語言的語法結構。算術表達式語句賦值語句條件語句循環語句……1、語法樹與推導用于描述上下文無關文法的句型推導的直觀方法

例:

G[S]: S→aAS A→SbA A→SS S→a A→ba

SaASSbAaaba句型aabbaa的語法樹（推導樹）葉子結點：樹中沒有子孫的結點。

從左到右讀出推導樹的葉子標記，所得的句型為推導樹的結果。也把該推導樹稱為該句型的語法樹。推導過程中施用產生式的順序例:G[S]: S→aAS A→SbA A→SS S→a A→ba

SaASSbAaaba句型aabbaa的語法樹（推導樹）SaASaAaaSbAaaSbbaaaabbaa2、最左（最右）推導：

在推導的任何一步αβ，其中α、β是句型，都是對α中的最左（右）非終結符進行替換。最右推導被稱為規范推導。由規范推導所得的句型稱為規范句型。SaASaAaaSbAaaSbbaaaabbaa（最右推導）SaASaSbASaabASaabbaSaabbaa（最左推導）SaASaSbASaSbAaaabAaaabbaa

例:G[S]: S→aAS A→SbA A→SS S→a A→ba問題：一個句型是否對應唯一的一棵語法樹？例：G[E]:

E→i E→E+E E→E*E E→(E)

EE+EE*Eiii

EE*EiE+Eii句型

i*i+i的兩個不同的最左推導：推導2：EE*Ei*Ei*E+Ei*i+Ei*i+i推導1：EE+EE*E+Ei*E+Ei*i+Ei*i+i3、二義文法若一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是二義的。

或者，若一個文法存在某個句子有兩個不同的最左（右）推導，則稱這個文法是二義的。產生某上下文無關語言的每一個文法都是二義的，則稱此語言是先天二義的。排除文法二義性的兩種方法：（1）在語義上加些限制（如優先順序和結合律）。（2）重構無二義性的文法。G[E]:E→IE→E+E

E→E*EE→(E)G[E]:E→T|E+T T→F|T*F F→（E）|i練習：有文法G[N]：N→SE|ES→SD|DE→0|2|4|6|8|10D→0|1|2|3|4|5|6|7|8|9（1）證明此文法有二義性（2）此文法描述的語言是什么？（3）試寫出另一文法，其產生的語言和G[N]產生的語言等價且是無二義性的。八、句型的分析句型分析就是識別一個符號串是否為某文法的句型，是某個推導的構造過程。在語言的編譯實現中，把完成句型分析的程序稱為分析程序或識別程序。分析算法又稱識別算法。從左到右的分析算法，即總是從左到右地識別輸入符號串，首先識別符號串中的最左符號，進而依次識別右邊的一個符號。1、自上而下的語法分析：從文法的開始符號出發，反復使用各種產生式，尋找與輸入符號串匹配的推導。例：文法G：S→cAd

A→ab

A→a

識別輸入串

w=cabd是否該文法的句子

S S S c A d c A d ab推導過程：cabdcAd

S2、自下而上的語法分析：從輸入符號串開始，逐步進行歸約，直至歸約到文法的開始符號。例：文法G：S→cAd

A→ab

A→a

識別輸入串

w=cabd是否該文法的句子

S A A cabd cabd cabd規約過程：cabdcAd

S3、句型分析的有關問題1）如何選擇使用哪個產生式進行推導？ 假定要被代換的最左非終結符號是V，且有n條規則：V→A1|A2|…|An，那么如何確定用哪個右部去替代V？2）如何識別可歸約的串？ 在自下而上的分析方法中，在分析程序工作的每一步，都是從當前串中選擇一個子串，將它歸約到某個非終結符號，該子串