編譯原理文法和語(yǔ)言

編譯原理文法和語(yǔ)言1第一頁(yè)，共五十九頁(yè)，2022年，8月28日第2章 文法和語(yǔ)言【學(xué)習(xí)目標(biāo)】本章是為語(yǔ)言的語(yǔ)法描述尋求工具

掌握對(duì)程序設(shè)計(jì)語(yǔ)言給出精確、無(wú)二義（嚴(yán)謹(jǐn)、易讀）的語(yǔ)法描述的手段之一——文法。

對(duì)形式語(yǔ)言的理論有一個(gè)初步基礎(chǔ)

根據(jù)文法的特點(diǎn)指導(dǎo)語(yǔ)法分析過(guò)程2第二頁(yè)，共五十九頁(yè)，2022年，8月28日2.1文法的直觀表示文法：闡明語(yǔ)法的一個(gè)工具，也可以說(shuō)是以有窮的集合刻畫無(wú)窮的集合的一個(gè)工具。語(yǔ)言：程序設(shè)計(jì)語(yǔ)言。一、語(yǔ)言概述語(yǔ)言是由符合語(yǔ)法的句子組成的集合。漢語(yǔ)--所有符合漢語(yǔ)語(yǔ)法的句子的全體英語(yǔ)--所有符合英語(yǔ)語(yǔ)法的句子的全體程序設(shè)計(jì)語(yǔ)言--所有該語(yǔ)言的程序的全體

每個(gè)句子構(gòu)成的規(guī)律——語(yǔ)法研究語(yǔ)言每個(gè)句子的含義——語(yǔ)義

每個(gè)句子和使用者的關(guān)系——語(yǔ)用3第三頁(yè)，共五十九頁(yè)，2022年，8月28日形式語(yǔ)言：只考慮語(yǔ)法而不考慮語(yǔ)義的符號(hào)語(yǔ)言。每種語(yǔ)言具有兩個(gè)可識(shí)別的特性語(yǔ)言的形式與該形式相關(guān)聯(lián)的意義“形式”指語(yǔ)言的所有規(guī)則，描述出現(xiàn)什么符號(hào)串語(yǔ)言可以看成在一個(gè)基本符號(hào)集上定義的，按一定規(guī)則構(gòu)成的基本符號(hào)串組成的所有集合。形式語(yǔ)言理論是對(duì)符號(hào)串集合的表示法、結(jié)構(gòu)及其特性的研究，是程序設(shè)計(jì)語(yǔ)言語(yǔ)法分析研究的基礎(chǔ)。4第四頁(yè)，共五十九頁(yè)，2022年，8月28日表達(dá)語(yǔ)言時(shí)，一般無(wú)法窮盡語(yǔ)言的所有句子，常用規(guī)則加以描述例：漢語(yǔ)句子的構(gòu)成規(guī)則：

〈句子〉∷=〈主語(yǔ)〉〈謂語(yǔ)〉

〈主語(yǔ)〉∷=〈代詞〉|〈名詞〉

〈代詞〉∷=我|你|他

〈名詞〉∷=王明|大學(xué)生|工人|英語(yǔ)

〈謂語(yǔ)〉∷=〈動(dòng)詞〉〈直接賓語(yǔ)〉

〈動(dòng)詞〉∷=是|學(xué)習(xí)

〈直接賓語(yǔ)〉∷=〈代詞〉|〈名詞〉

二、文法的直觀概念5第五頁(yè)，共五十九頁(yè)，2022年，8月28日推導(dǎo)：“我是大學(xué)生”是漢語(yǔ)的一個(gè)句子

〈句子〉〈主語(yǔ)〉〈謂語(yǔ)〉

〈代詞〉〈謂語(yǔ)〉

我〈謂語(yǔ)〉

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

我是〈直接賓語(yǔ)〉

我是〈名詞〉

我是大學(xué)生6第六頁(yè)，共五十九頁(yè)，2022年，8月28日2.2符號(hào)與符號(hào)串一、相關(guān)概念程序設(shè)計(jì)語(yǔ)言是由程序構(gòu)成的集合，程序是由基本符號(hào)按照一定的規(guī)則構(gòu)成的集合。1.符號(hào)、字母表和符號(hào)串基本符號(hào)：可以相互區(qū)別的基本元素，如字母，數(shù)字，標(biāo)點(diǎn)符號(hào)。字母表：基本符號(hào)的非空有窮集合，常用Σ表示。例：Σ={0,1}，Σ={a,b,c,…,x,y,z}7第七頁(yè)，共五十九頁(yè)，2022年，8月28日符號(hào)串：由字母表中的符號(hào)構(gòu)成的任何有窮序列稱為符號(hào)串。符號(hào)串中的符號(hào)是有順序的。例如

=｛0,1｝上的符號(hào)串0,1,00,01,11,10

注意：表示空符號(hào)串,它表示不包含任何符號(hào)串，不是空格符。符號(hào)串集合：字母表上若干個(gè)符號(hào)串組成的集合.例：字母表={0,1}的符號(hào)串集合A={1,00,01};

約定：小寫字母a,b,…,r表示符號(hào). 小寫字母s,t,…,z表示符號(hào)串;8第八頁(yè)，共五十九頁(yè)，2022年，8月28日符號(hào)串s的頭（前綴）和尾（后綴）：如果s=xy是一符號(hào)串，那么x是s的頭，y是s的尾。若x是非空，則y是固有尾；若y非空，則x是固有頭。前綴：移走符號(hào)串s尾部的零個(gè)或多個(gè)符號(hào)得到的串。如：設(shè)s=abc,那么s的前綴是ε，a，ab，abc

后綴：移走符號(hào)串s頭部的零個(gè)或多個(gè)符號(hào)得到的串。如：s=abc的后綴是ε，c，bc，abc，s的固有尾是ε，c，bc。

9第九頁(yè)，共五十九頁(yè)，2022年，8月28日符號(hào)串s的子串：從s中刪去任何前綴或后綴得到的串.如:bc是符號(hào)串a(chǎn)bc的一個(gè)子串.對(duì)符號(hào)串s，s和ε兩者都是符號(hào)串s的前綴、后綴和子串。符號(hào)串s的真前綴，真后綴，真子串：任何非空符號(hào)串x，是s的前綴，后綴或子串，并且sx10第十頁(yè)，共五十九頁(yè)，2022年，8月28日2.符號(hào)串的運(yùn)算(1)符號(hào)串相等：符號(hào)串x，y，如果兩者諸符號(hào)依次相等，則兩符號(hào)串相等。(2)符號(hào)串的長(zhǎng)度：符號(hào)串中包含符號(hào)的個(gè)數(shù)。

|abc|=3；||=0；(3)符號(hào)串的連結(jié)：

x=abc，y=def則xy=abcdef；yx=defabc；xyyx x=x=x；11第十一頁(yè)，共五十九頁(yè)，2022年，8月28日(4)符號(hào)串集合的乘積：設(shè)A、B為兩個(gè)符號(hào)串集合，其乘積為AB={xy|xA，yB}；例：A={aa，bb}，B={cc，dd}，則

AB={aacc，aadd，bbcc，bbdd} {}A=A{}=A；(5)空集：不含任何元素的集合稱為空集。記為；對(duì)任何集合A：A=A=;注意：12第十二頁(yè)，共五十九頁(yè)，2022年，8月28日(6)符號(hào)串的方冪：

x是字母表上的符號(hào)串，則x的冪運(yùn)算為：

x0=;x1=x;x2=xx;…xn=xn-1x=xxn-1(n>0) xn表示n個(gè)x相連結(jié)。

eg：x=ok；則x0=;x1=ok;x2=okok;…

(7)符號(hào)串集合的方冪：

A為符號(hào)串集合，則A的冪運(yùn)算為：

A0={};A1=A;A2=AA;...An=An-1A=AAn-1;(n>0)

A={aa，bb}，則A0={}；A1={aa，bb}；

A2=AA={aaaa，aabb，bbaa，bbbb};...13第十三頁(yè)，共五十九頁(yè)，2022年，8月28日(8)符號(hào)串集合的閉包和正閉包

集合A的閉包表示為A*（亦稱為自反閉包或星閉包）定義為：

A*=A0A1A2A3…=Ak，k0

正閉包表示為A+具體定義為

A+=A1A2A3…=Ak，k1

由定義可以看到A*=A0

A+例：Σ={a,b}Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}14第十四頁(yè)，共五十九頁(yè)，2022年，8月28日3、語(yǔ)言(1)由一組符號(hào)所構(gòu)成的集合。即：字母表上的每個(gè)語(yǔ)言是*的一個(gè)子集。例如：字母表Σ={a,b}，Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}集合{ab,aabb,aaabbb,…,anbn,…} 或表示為{w|w∈Σ*且w=anbn,n≥1}為字母表上的一個(gè)語(yǔ)言。集合{a,aa,aaa,…}或表示為{w|w∈Σ*，且w=an，n≥1}為字母表上的一個(gè)語(yǔ)言。(2)ε是一個(gè)語(yǔ)言。(3)即是一個(gè)語(yǔ)言。15第十五頁(yè)，共五十九頁(yè)，2022年，8月28日2.3文法和語(yǔ)言的形式定義如何來(lái)描述一種語(yǔ)言？如果語(yǔ)言是有窮的（只含有有窮多個(gè)句子），可以將句子逐一列出來(lái)表示如果語(yǔ)言是無(wú)窮的，找出語(yǔ)言的有窮表示。語(yǔ)言的有窮表示有兩個(gè)途徑：生成方式（文法）：語(yǔ)言中的每個(gè)句子可以用嚴(yán)格定義的規(guī)則來(lái)構(gòu)造。

識(shí)別方式（自動(dòng)機(jī)）：用一個(gè)過(guò)程，當(dāng)輸入的一個(gè)任意串屬于語(yǔ)言時(shí)，該過(guò)程經(jīng)有限次計(jì)算后就會(huì)停止并回答“是”，若不屬于，要么能停止并回答“不是”，（要么永遠(yuǎn)繼續(xù)下去。）16第十六頁(yè)，共五十九頁(yè)，2022年，8月28日一、規(guī)則（重寫規(guī)則、產(chǎn)生式或生成式）規(guī)則是形如α→β或α∷=β的(α，β)有序?qū)?，其中α∈V+，β∈V*中的一個(gè)符號(hào)α稱為規(guī)則的左部β稱作規(guī)則的右部。例：<句子><主語(yǔ)><謂語(yǔ)>文法可利用規(guī)則來(lái)描述。17第十七頁(yè)，共五十九頁(yè)，2022年，8月28日二、文法的定義1、文法G定義為四元組(VN，VT，P，S)其中VN：非終結(jié)符號(hào)；VT：終結(jié)符號(hào)集；P：規(guī)則集合；VN，VT和P是非空有窮集。

S：開始符或識(shí)別符，是一個(gè)非終結(jié)符，至少要在一條規(guī)則的左部出現(xiàn)。VN∩VT=φ，V=VN∪VT

，V稱為文法G的字母表例1：文法G=(VN，VT，P，S)，其中

VN={S}，

VT={0，1}，

P={S→0S1，S→01}。18第十八頁(yè)，共五十九頁(yè)，2022年，8月28日文法G習(xí)慣上只將規(guī)則寫出。如例1還可以寫成：

G：S→0S1

S→01

或G[S]：S→0S1

S→01

或G[S]：S→0S1|S→0119第十九頁(yè)，共五十九頁(yè)，2022年，8月28日總結(jié)一個(gè)文法的幾種寫法

①G=({S,A}，{a,b}，P，S)

其中P：S→aAb

A→ab

A→aAb

A→ε

②G：S→aAb

A→ab

A→aAb

A→ε

③G[S]：S→aAbA→abA→aAbA→ε

④G[S]：S→aAbA→ab|aAb|ε20第二十頁(yè)，共五十九頁(yè)，2022年，8月28日三、推導(dǎo)的定義用文法定義語(yǔ)言的中心思想是：從文法的開始符號(hào)出發(fā)，反復(fù)使用合適規(guī)則，對(duì)非終結(jié)符施行替換和展開。1、直接推導(dǎo)：

α→β是文法G的產(chǎn)生式，若有v，w滿足：v=γαδ，w=γβδ,其中γ∈V*,δ∈V*。則稱v直接推導(dǎo)到w,或w直接歸約到v記作vw，2、推導(dǎo)：如果存在直接推導(dǎo)的序列：v=W0W1

W2…Wn=w,(n＞0)；稱v推導(dǎo)出w(推導(dǎo)長(zhǎng)度為n)，或稱w歸約到v。記作vw。若有vw，或v=w，則記作vw，(n＞=0)*21第二十一頁(yè)，共五十九頁(yè)，2022年，8月28日例3：G：S→0S1，S→010S100S1100S11000S111000S11100001111S0S100S11000S11100001111S

00001111S

S00S11

00S11+**22第二十二頁(yè)，共五十九頁(yè)，2022年，8月28日3、規(guī)范推導(dǎo)最左(最右)推導(dǎo)：在推導(dǎo)的任何一步αβ，其中α、β是句型，都是對(duì)α中的最左（右）非終結(jié)符進(jìn)行替換最右推導(dǎo)被稱為規(guī)范推導(dǎo)。例4：G[E]：E→E+T|T

T→T*F|F

F→(E)|a

EE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*a（最左推導(dǎo)）

EE+TE+T*FE+T*aE+F*aE+a*a

T+a*aF+a*aa+a*a（最右推導(dǎo)）23第二十三頁(yè)，共五十九頁(yè)，2022年，8月28日四、句型、句子和語(yǔ)言的定義1.句型:文法G[S]，若Sx，則稱x是G的句型。2.句子:文法G[S]，若Sx，且x∈VT*，則稱x是G的句子。句子是句型的特殊，只包含終結(jié)符。例5：G：S→0S1，S→01S0S100S11000S11100001111G的句型S,0S1,00S11,000S111,00001111G的句子000011113.語(yǔ)言:文法G的一切句子的集合,記為L(zhǎng)(G)，**24第二十四頁(yè)，共五十九頁(yè)，2022年，8月28日例6文法G[S]： （1）S→aSBE

（2）S→aBE

（3）EB→BE

（4）aB→ab

（5）bB→bb

（6）bE→be

（7）eE→ee

SanBnEnanbnen

則

L（G）={anbnen|n≥1}

因?yàn)镾an-1S（BE）n-1an（BE）n

，繼續(xù)推導(dǎo)時(shí)，將用規(guī)則(3)~(7)替換**25第二十五頁(yè)，共五十九頁(yè)，2022年，8月28日S

aSBE(S→aSBE)

aaBEBE(S→aBE)

aabEBE (aB→ab)

aabBEE (EB→BE)

aabbEE

（bB→bb)

aabbeE

（bE→be)

aabbee

（eE→ee)

G生成的每個(gè)串都在L(G)中L(G)中的每個(gè)串確實(shí)能被G生成26第二十六頁(yè)，共五十九頁(yè)，2022年，8月28日五、語(yǔ)言和文法給定一個(gè)文法，能從結(jié)構(gòu)上唯一確定其語(yǔ)言給定一個(gè)語(yǔ)言，不能唯一確定其文法，即一個(gè)語(yǔ)言可有多個(gè)文法與之對(duì)應(yīng)已知語(yǔ)言描述，寫出文法，應(yīng)滿足：所描述的語(yǔ)言的任何句子都能由該文法產(chǎn)生該文法推導(dǎo)不出不是已知語(yǔ)言的任何句子已知文法，寫出語(yǔ)言描述，應(yīng)滿足：該文法能推導(dǎo)出的任何句子都包含在所描述的語(yǔ)言中描述的語(yǔ)言中不包含該文法推導(dǎo)不出的句子27第二十七頁(yè)，共五十九頁(yè)，2022年，8月28日六、文法的等價(jià)若L（G1）=L（G2），稱文法G1和G2是等價(jià)的

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

A→01S→01R→A1作業(yè)：P47:1，4，528第二十八頁(yè)，共五十九頁(yè)，2022年，8月28日2.4文法的類型一、文法分類通過(guò)對(duì)產(chǎn)生式施加不同的限制，將文法分為四類設(shè)有文法G=(VN，VT，P，S);0型文法：（短語(yǔ)結(jié)構(gòu)文法）——圖靈機(jī)對(duì)任一產(chǎn)生式α→β，都有α∈(VN∪VT)+，且α至少包含一個(gè)非終結(jié)符，β∈(VN∪VT)*1型文法：（上下文有關(guān)文法）對(duì)任一產(chǎn)生式α→β，都有|β|≥|α|，僅僅S→ε除外。29第二十九頁(yè)，共五十九頁(yè)，2022年，8月28日文法G[S]是1型文法

S→aSBC|aBC CB→DBDB→DC DC→BC aB→ab bB→bb bC→bc cC→cc

SaSBCaaBCBCaabCBCaabbcc*30第三十頁(yè)，共五十九頁(yè)，2022年，8月28日2型文法：（上下文無(wú)關(guān)文法）對(duì)任一產(chǎn)生式α→β，都有α∈VN

，β∈(VN∪VT)*設(shè)文法G＝(VN,VT,P,S)是一個(gè)2型文法，

VN

＝{S,A,B},VT

＝{a,b}其中P為:(0)SaB(1)SbA(2)Aa(3)AaS|bAA(4)Bb(5)BbS|aBB31第三十一頁(yè)，共五十九頁(yè)，2022年，8月28日3型文法：（正規(guī)文法）右線性文法任一產(chǎn)生式的形式都為A→aB或A→a，其中A∈VN

，B∈VN

，a∈VT(a可為ε)左線性文法任一產(chǎn)生式的形式都為A→Ba或A→a，其中A∈VN

，B∈VN

，a∈VT(a可為ε)32第三十二頁(yè)，共五十九頁(yè)，2022年，8月28日例：G[E]：E→E+T|TT→T*F|FF→(E)|aG是上下文無(wú)關(guān)文法。例文法G=({S,A,B},{0,1},P,S)，其中P由下列產(chǎn)生式組成：

S→0AA→1B

S→1BB→1B

S→0B→1

A→0AB→0

A→0S

G是正規(guī)文法。33第三十三頁(yè)，共五十九頁(yè)，2022年，8月28日二、四類文法之間的關(guān)系四種文法之間的逐級(jí)“包含”關(guān)系2型文法1型文法0型文法3型文法34第三十四頁(yè)，共五十九頁(yè)，2022年，8月28日2.5上下文無(wú)關(guān)文法及其語(yǔ)法樹上下文無(wú)關(guān)文法有足夠的能力描述程序設(shè)計(jì)語(yǔ)言的語(yǔ)法結(jié)構(gòu)例:文法G[E]：E→a|E+E|E*E|(E)E表示算術(shù)表達(dá)式,a表示程序的“變量”，該文法定義了由變量，+，*,(和)組成的算術(shù)表達(dá)式的語(yǔ)法結(jié)構(gòu)句型推導(dǎo)的直觀表示---語(yǔ)法樹35第三十五頁(yè)，共五十九頁(yè)，2022年，8月28日設(shè)G為一上下文無(wú)關(guān)文法，若一棵樹滿足下列4個(gè)條件，則稱作G的語(yǔ)法樹(推導(dǎo)樹，派生樹）1.每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是V的一個(gè)符號(hào)2.根的標(biāo)記是文法開始符號(hào)S3.如果結(jié)點(diǎn)n至少有一個(gè)除自己外的子孫并有標(biāo)記A，則肯定A∈VN4.如果結(jié)點(diǎn)n有標(biāo)記A,其直接子孫結(jié)點(diǎn)從左到右的次序是n1，n2，…，nk，其標(biāo)記分別為A1，A2，…，Ak，那么A→A1A2，…，Ak一定是P中的一個(gè)產(chǎn)生式語(yǔ)法樹的結(jié)果：從左到右讀出葉子的標(biāo)記而構(gòu)成的行一、語(yǔ)法樹36第三十六頁(yè)，共五十九頁(yè)，2022年，8月28日G[E]：E→E+T|T

T→T*F|F

F→(E)|a

EE+TT+TF+Ta+Ta+T*F

a+F*Fa+a*Fa+a*a

EE+TEE+TTEE+TTFEE+TTFaT*FFaa給定文法G=(VN,VT,P,S)，對(duì)于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹(推導(dǎo)樹)37第三十七頁(yè)，共五十九頁(yè)，2022年，8月28日用于描述上下文無(wú)關(guān)文法句型推導(dǎo)的直觀方法葉子結(jié)點(diǎn)：樹中沒有子孫的結(jié)點(diǎn)。

從左到右讀出推導(dǎo)樹的葉子標(biāo)記連接成的文法符號(hào)串，為G[S]的句型。該推導(dǎo)樹稱為該句型的語(yǔ)法樹。用于描述上下文無(wú)關(guān)文法句型推導(dǎo)的直觀方法用于描述上下文無(wú)關(guān)文法句型推導(dǎo)的直觀方法例:G[S]: S→aAS A→SbA A→SS S→a A→ba用于描述上下文無(wú)關(guān)文法句型推導(dǎo)的直觀方法句型aabbaa的語(yǔ)法樹（推導(dǎo)樹）

S

aASSbAa

a

b

a38第三十八頁(yè)，共五十九頁(yè)，2022年，8月28日推導(dǎo)過(guò)程中施用產(chǎn)生式的順序例:G[S]: S→aAS A→SbA A→SS S→a A→baSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa

S

aASSbAa

a

b

a39第三十九頁(yè)，共五十九頁(yè)，2022年，8月28日例：G[E]：E→E+T|T

T→T*F|F

F→(E)|a試給出表達(dá)式a+a*a的推導(dǎo)，并畫出語(yǔ)法樹。

左:EE+TT+TF+Ta+Ta+T*F

a+F*Fa+a*Fa+a*a

右:

EE+TE+T*FE+T*aE+F*aE+a*aT+a*aF+a*aa+a*a

混合:EE+TT+TT+T*FF+T*FF+F*Fa+F*Fa+F*aa+a*a40第四十頁(yè)，共五十九頁(yè)，2022年，8月28日例如，有一個(gè)2型文法G=({S,A,B},{a,b},P,S),其中P:(0)SaB|bA(1)Aa|aS|bAA(2)Bb|bS|aBB采用最左推導(dǎo)產(chǎn)生句子aabbab:SaBaaBBaabSBaabbAB

aabbaBaabbab一棵語(yǔ)法樹表示了一個(gè)句型的種種可能的不同推導(dǎo)過(guò)程，一個(gè)句型是否只對(duì)應(yīng)唯一的一棵語(yǔ)法樹呢?是否只有唯一的一個(gè)最左(最右)推導(dǎo)呢?41第四十一頁(yè)，共五十九頁(yè)，2022年，8月28日語(yǔ)法樹其中P:(0)SaB|bA(1)Aa|aS|bAA(2)Bb|bS|aBB分析句子aabbabSaBaBBbSbbAa42第四十二頁(yè)，共五十九頁(yè)，2022年，8月28日例：G[E]:

E→a E→E+E E→E*E E→(E)

EE+EE*Eaaa

EE*EaE+Eaa句型a*a+a的兩個(gè)不同的最左推導(dǎo)：(1)EE+EE*E+Ea*E+Ea*a+Ea*a+a(2)EE*Ea*Ea*E+Ea*a+Ea*a+a43第四十三頁(yè)，共五十九頁(yè)，2022年，8月28日

若一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹，則稱這個(gè)文法是二義的?；蛘?，若一個(gè)文法存在某個(gè)句子有兩個(gè)不同的最左（右）推導(dǎo)，則稱這個(gè)文法是二義的文法的二義性和語(yǔ)言的二義性是兩個(gè)不同的概念。因?yàn)榭赡苡袃蓚€(gè)不同的文法G和G′，其中G是二義的，但是卻有L(G)=L(G′)，也就是說(shuō)，這兩個(gè)文法所產(chǎn)生的語(yǔ)言是相同的。

44第四十四頁(yè)，共五十九頁(yè)，2022年，8月28日如果產(chǎn)生上下文無(wú)關(guān)語(yǔ)言的每一個(gè)文法都是二義的，則說(shuō)此語(yǔ)言是先天二義的。對(duì)于一個(gè)程序設(shè)計(jì)語(yǔ)言來(lái)說(shuō)，常常希望它的文法是無(wú)二義的，因?yàn)橄Ｍ麑?duì)它的每個(gè)語(yǔ)句的分析是唯一的。二義文法改造為無(wú)二義文法G[E]:E→aG[E]：E→T|E+T E→E+ET→F|T*F E→E*EF→（E）|a E→(E)規(guī)定優(yōu)先順序和結(jié)合律45第四十五頁(yè)，共五十九頁(yè)，2022年，8月28日2.6句型的分析句型分析就是識(shí)別一個(gè)符號(hào)串是否為某文法的句型，是某個(gè)推導(dǎo)的構(gòu)造過(guò)程。在語(yǔ)言的編譯實(shí)現(xiàn)中，完成句型分析的程序稱為分析程序或識(shí)別程序。分析算法稱識(shí)別算法。從左到右的分析算法，即總是從左到右地識(shí)別輸入符號(hào)串，首先識(shí)別符號(hào)串中的最左符號(hào)，進(jìn)而依次識(shí)別右邊的一個(gè)符號(hào)，直到分析結(jié)束。46第四十六頁(yè)，共五十九頁(yè)，2022年，8月28日一、句型的分析算法分類分析算法可分為：自上而下分析法：

從文法的開始符號(hào)出發(fā)，反復(fù)使用文法的產(chǎn)生式，尋找與輸入符號(hào)串匹配的推導(dǎo)。自下而上分析法：

從輸入符號(hào)串開始，逐步進(jìn)行歸約，直至歸約到文法的開始符號(hào)。兩種方法反映了兩種不同的語(yǔ)法樹的構(gòu)造過(guò)程。47第四十七頁(yè)，共五十九頁(yè)，2022年，8月28日1、自上而下的語(yǔ)法分析例：文法G：S→cAd

A→ab

A→a

識(shí)別輸入串w=cabd是否為該文法的句子

S S S

cA d

cA d

a

b推導(dǎo)過(guò)程：S

cAd

cAd

cabd48第四十八頁(yè)，共五十九頁(yè)，2022年，8月28日2、自下而上的語(yǔ)法分析例：文法G：S→cAd

A→ab

A→a

識(shí)別輸入串w=cabd是否該文法的句子

S

A

A

cabd

ca

bd

ca

b

d

規(guī)約過(guò)程構(gòu)造的推導(dǎo)：cAd

cabdScAd49第四十九頁(yè)，共五十九頁(yè)，2022年，8月28日3、句型分析的有關(guān)問(wèn)題1）在自上而下的分析方法中如何選擇使用哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)？

假定要被代換的最左非終結(jié)符是B，且有n條規(guī)則：B→A1|A2|…|An，如何確定用哪個(gè)右部去替代B？2）自下而上分析法中，分析程序工作的每一步，都是從當(dāng)前串中選擇一個(gè)子串，將它歸約到某個(gè)非終結(jié)符，該子串稱為“可歸約串”,如何識(shí)別可歸約串？3）存在確定和不確定分析，本課只討論確定分析50第五十頁(yè)，共五十九頁(yè)，2022年，8月28日4、短語(yǔ)、直接短語(yǔ)、句柄的定義對(duì)于文法G[S]（1）句型的短語(yǔ):S=>

αAδ且A

=>β，則稱β是句型αβδ相對(duì)于非終結(jié)符A的短語(yǔ)。（2）句型的直接短語(yǔ)：若有A

β，則稱β是句型αβδ相對(duì)于非終結(jié)符A的直接短語(yǔ)。（3）句型的句柄：一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄。*+51第五十一頁(yè)，共五十九頁(yè)，2022年，8月28日語(yǔ)法樹子樹分析法：短語(yǔ)：任意一顆子樹的葉子結(jié)點(diǎn)從左至右順序排列的字符串（按給定句型排除）。直接短語(yǔ)：只有父子兩層的子樹的葉子結(jié)點(diǎn)從左至右順序排列的字符串。句柄：最左最下的只有父子兩層的子樹的葉子結(jié)點(diǎn)從左至右順序排列的字符串。52第五十二頁(yè)，共五十九頁(yè)，2022年，8月28日例1：考慮文法G[E]:ET|E+T