編譯原理-第3章文法和語法

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

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

〈代詞〉〈謂語〉

我〈謂語〉

我〈動詞〉〈直接賓語〉

我是〈直接賓語〉

我是〈名詞〉

我是大學生〈句子〉::=〈主語〉〈謂語〉〈主語〉::=〈代詞〉|〈名詞〉〈代詞〉::=你|我|他〈名詞〉::=王明|大學生|工人|英語〈謂語〉::=〈動詞〉〈直接賓語〉〈動詞〉::=是|學習〈直接賓語〉::=〈代詞〉|〈名詞〉語法變量（在形式語言中又稱“非終結符”）單詞符號（在形式語言中又稱“終結符號”)三、符號和符號串例如：漢語的字母表中包括漢字、數(shù)字及標點符號等。C語言的字母表是由字母、數(shù)字、若干專用符號及IF、FOR之類的保留字組成。1、字母表和符號串字母表：符號的非空有限集例：={a，b，c}符號：字母表中的元素例：a，b，c符號串：符號的有窮序列例：a,aa,ac,abc，..空符號串：無任何符號的符號串(ε)符號串集合：由符號串構成的集合。2、符號串的運算符號串的長度：符號串中符號的個數(shù).符號串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）規(guī)則（重寫規(guī)則、產生式或生成式）：是一個有序對（α，β）。記為α→β或α∷=β，其中α∈V+，β∈V*。α稱為規(guī)則的左部(或生成式的左部)。β稱為規(guī)則的右部(或生成式的右部)。2）文法G[S]：文法為四元組（VN，VT，P，S）VN：非終結符集VT：終結符集P：產生式（規(guī)則）集合S：開始符號（識別符號）VN、VT

和P是非空有窮集。S至少在一條規(guī)則中作為左部出現(xiàn)。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={標識符，字母，數(shù)字}

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

<數(shù)字>→0,…,<數(shù)字>→9}

S=<標識符>習慣上只將產生式寫出。并有如下約定：第一條產生式的左部是開始符號用尖括號括起的是非終結符，否則為終結符?；蛘叽髮懽帜副硎痉墙K結符，小寫字母表示終結符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<語句>::=<賦值語句>|<條件語句>|<循環(huán)語句>8<賦值語句>::=<ID>=<算術表達式>9<條件語句>::=if(<條件>)<語句塊>|if(<條件>)<語句塊>else<語句塊>10<循環(huán)語句>::=<while語句>|<for語句>

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

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

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

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

<標識符><字母><標識符><字母><數(shù)字>

<字母><字母><數(shù)字>abc<數(shù)字>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，所以必須用遞歸規(guī)則。a和b的個數(shù)一樣多，但c的個數(shù)不同，所以將生成含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型文法（正規(guī)文法）：任一產生式α→β的形式都為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型（正規(guī)）文法

文法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型文法或正則（正規(guī)）文法（RG）產生的語言稱為3型語言或正則（正規(guī)）語言（RL）八、上下文無關文法及其語法樹上下文無關文法有足夠的能力描述現(xiàn)今程序設計語言的語法結構。算術表達式語句賦值語句條件語句循環(huán)語句……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、最左（最右）推導：

在推導的任何一步αβ，其中α、β是句型，都是對α中的最左（右）非終結符進行替換。最右推導被稱為規(guī)范推導。由規(guī)范推導所得的句型稱為規(guī)范句型。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）在語義上加些限制（如優(yōu)先順序和結合律）。（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]產生的語言等價且是無二義性的。八、句型的分析句型分析就是識別一個符號串是否為某文法的句型，是某個推導的構造過程。在語言的編譯實現(xiàn)中，把完成句型分析的程序稱為分析程序或識別程序。分析算法又稱識別算法。從左到右的分析算法，即總是從左到右地識別輸入符號串，首先識別符號串中的最左符號，進而依次識別右邊的一個符號。1、自上而下的語法分析：從文法的開始符號出發(fā)，反復使用各種產生式，尋找與輸入符號串匹配的推導。例：文法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規(guī)約過程：cabdcAd

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