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

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

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

〈代詞〉〈謂語〉

我〈謂語〉

我〈動(dòng)詞〉〈直接賓語〉

我是〈直接賓語〉

我是〈名詞〉

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

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

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

xx…xx(n個(gè)x)定義為

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

x0=ε,x1=AB,x2=ABAB,x3=ABABAB對(duì)于

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

3、符號(hào)串集合

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

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

Σ+稱為Σ的正閉包。Σ*=Σ0∪Σ1∪Σ2…∪Σn…Σ+=Σ1∪Σ2…∪Σn…Σ*=Σ0∪Σ+Σ+=ΣΣ*=Σ*ΣΣ+=Σ*-{ε}例：設(shè)Σ={0,1}，則Σ*={ε,0,1,00,01,10,11,000,001,010,…}例：設(shè)Σ={a,b}，則Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}四、文法和語言的形式定義1、文法的形式定義1）規(guī)則（重寫規(guī)則、產(chǎn)生式或生成式）：是一個(gè)有序?qū)Γé?，β）。記為α→β或α?β，其中α∈V+，β∈V*。α稱為規(guī)則的左部(或生成式的左部)。β稱為規(guī)則的右部(或生成式的右部)。2）文法G[S]：文法為四元組（VN，VT，P，S）VN：非終結(jié)符集VT：終結(jié)符集P：產(chǎn)生式（規(guī)則）集合S：開始符號(hào)（識(shí)別符號(hào)）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為開始符號(hào)例:文法G=（VN，VT，P，S） VN={標(biāo)識(shí)符，字母，數(shù)字}

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

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

S=<標(biāo)識(shí)符>習(xí)慣上只將產(chǎn)生式寫出。并有如下約定：第一條產(chǎn)生式的左部是開始符號(hào)用尖括號(hào)括起的是非終結(jié)符，否則為終結(jié)符?；蛘叽髮懽帜副硎痉墙K結(jié)符，小寫字母表示終結(jié)符G可寫成G[S]，其中S是開始符號(hào)例:文法G=（VN，VT，P，S） VN={S},VT={0,1} P={S→0S1,S→01} S為開始符號(hào)可寫成：

G：S→0S1 S→01或?qū)懗桑?/p>

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

Mini_C介紹

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

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

vw，讀作v（應(yīng)用規(guī)則α→β）直接產(chǎn)生w（w是v的直接推導(dǎo)或w直接歸約到v）例：G：S→0S1，S→01直接推導(dǎo)：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={標(biāo)識(shí)符，字母，數(shù)字}

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

S=<標(biāo)識(shí)符>指出下面直接推導(dǎo)所使用的規(guī)則：<標(biāo)識(shí)符>

<標(biāo)識(shí)符><字母><標(biāo)識(shí)符><字母><數(shù)字>

<字母><字母><數(shù)字>abc<數(shù)字>abc52）長(zhǎng)度為n的推導(dǎo)（有限次推導(dǎo)）

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

則稱v推導(dǎo)出w（或w歸約到v）.記作

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

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

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

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

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

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

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

對(duì)任一產(chǎn)生式α→β，都有|β|≥|α|，僅僅

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

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

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

文法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例：定義標(biāo)識(shí)符的3型（正規(guī)）文法

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

T→dT

T→l

T→d文法和語言0型文法產(chǎn)生的語言稱為0型語言1型文法或上下文有關(guān)文法（CSG）產(chǎn)生的語言稱為1型語言或上下文有關(guān)語言（CSL）2型文法或上下文無關(guān)文法（CFG）產(chǎn)生的語言稱為2型語言或上下文無關(guān)語言（CFL）3型文法或正則（正規(guī)）文法（RG）產(chǎn)生的語言稱為3型語言或正則（正規(guī)）語言（RL）八、上下文無關(guān)文法及其語法樹上下文無關(guān)文法有足夠的能力描述現(xiàn)今程序設(shè)計(jì)語言的語法結(jié)構(gòu)。算術(shù)表達(dá)式語句賦值語句條件語句循環(huán)語句……1、語法樹與推導(dǎo)用于描述上下文無關(guān)文法的句型推導(dǎo)的直觀方法

例:

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

SaASSbAaaba句型aabbaa的語法樹（推導(dǎo)樹）葉子結(jié)點(diǎn)：樹中沒有子孫的結(jié)點(diǎn)。

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

SaASSbAaaba句型aabbaa的語法樹（推導(dǎo)樹）SaASaAaaSbAaaSbbaaaabbaa2、最左（最右）推導(dǎo)：

在推導(dǎo)的任何一步αβ，其中α、β是句型，都是對(duì)α中的最左（右）非終結(jié)符進(jìn)行替換。最右推導(dǎo)被稱為規(guī)范推導(dǎo)。由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。SaASaAaaSbAaaSbbaaaabbaa（最右推導(dǎo)）SaASaSbASaabASaabbaSaabbaa（最左推導(dǎo)）SaASaSbASaSbAaaabAaaabbaa

例:G[S]: S→aAS A→SbA A→SS S→a A→ba問題：一個(gè)句型是否對(duì)應(yīng)唯一的一棵語法樹？例：G[E]:

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

EE+EE*Eiii

EE*EiE+Eii句型

i*i+i的兩個(gè)不同的最左推導(dǎo)：推導(dǎo)2：EE*Ei*Ei*E+Ei*i+Ei*i+i推導(dǎo)1：EE+EE*E+Ei*E+Ei*i+Ei*i+i3、二義文法若一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是二義的。

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

E→E*EE→(E)G[E]:E→T|E+T T→F|T*F F→（E）|i練習(xí)：有文法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）試寫出另一文法，其產(chǎn)生的語言和G[N]產(chǎn)生的語言等價(jià)且是無二義性的。八、句型的分析句型分析就是識(shí)別一個(gè)符號(hào)串是否為某文法的句型，是某個(gè)推導(dǎo)的構(gòu)造過程。在語言的編譯實(shí)現(xiàn)中，把完成句型分析的程序稱為分析程序或識(shí)別程序。分析算法又稱識(shí)別算法。從左到右的分析算法，即總是從左到右地識(shí)別輸入符號(hào)串，首先識(shí)別符號(hào)串中的最左符號(hào)，進(jìn)而依次識(shí)別右邊的一個(gè)符號(hào)。1、自上而下的語法分析：從文法的開始符號(hào)出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找與輸入符號(hào)串匹配的推導(dǎo)。例：文法G：S→cAd

A→ab

A→a

識(shí)別輸入串

w=cabd是否該文法的句子

S S S c A d c A d ab推導(dǎo)過程：cabdcAd

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

A→ab

A→a

識(shí)別輸入串

w=cabd是否該文法的句子

S A A cabd cabd cabd規(guī)約過程：cabdcAd

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