編譯原理第2章：高級(jí)語(yǔ)言及其語(yǔ)法描述

第二章高級(jí)語(yǔ)言及其語(yǔ)法描述

2.1程序語(yǔ)言的定義2.2程序語(yǔ)言的語(yǔ)法描述22023/11/262.1程序語(yǔ)言的定義一個(gè)程序設(shè)計(jì)語(yǔ)言是一個(gè)記號(hào)系統(tǒng)，其完整的定義應(yīng)包括語(yǔ)法和語(yǔ)義兩個(gè)方面語(yǔ)言的語(yǔ)法是指一組規(guī)則，用它可以形成和產(chǎn)生一個(gè)合適的程序上下文無(wú)關(guān)文法語(yǔ)法只定義什么樣的符號(hào)序列是合法的，與這些符號(hào)的含義毫無(wú)關(guān)系PASCAL語(yǔ)言中：A:=B+C合乎語(yǔ)法規(guī)則，A:=B+不合乎語(yǔ)法規(guī)則闡明語(yǔ)法的一個(gè)工具是文法，這是形式語(yǔ)言理論的基本概念之一32023/11/262.2程序語(yǔ)言的語(yǔ)法描述基本概念字母表、符號(hào)、符號(hào)串、閉包等文法的定義文法的分類Chromsky對(duì)文法的分類文法和語(yǔ)言推導(dǎo)、歸約、句型、句子、語(yǔ)言語(yǔ)法分析樹和二義性42023/11/26基本概念字母表元素的非空有限集，記為

。例：

={a，b，c}字母表中的元素稱為符號(hào)。例：a，b，c，字母表包含了語(yǔ)言中所允許出現(xiàn)的所有符號(hào)符號(hào)串符號(hào)的有窮序列。例：a,aa,ac,abc，..，無(wú)任何符號(hào)的符號(hào)串稱為空符號(hào)串，記為ε52023/11/26基本概念符號(hào)串運(yùn)算符號(hào)串長(zhǎng)度x為符號(hào)串,其長(zhǎng)度|x|等于組成該符號(hào)串的符號(hào)個(gè)數(shù)。例：x=string，則|x|=6,|ε|=0符號(hào)串連接若x、y是定義在Σ上的符號(hào)串，則xy稱為x和y的連接，xy也是Σ上的符號(hào)串εx＝xε=x62023/11/26基本概念符號(hào)串集合的乘積令A(yù)、B為符號(hào)串集合，定義符號(hào)串集合乘積AB＝{xy|x∈A,y∈B}符號(hào)串集合的方冪符號(hào)串集合A，定義A0={ε},A1=A,A2=AA,A3=A2A,…,An＝An-1A=AAn-1，n>0符號(hào)串集合的正閉包A+=A1∪A2∪…∪An…符號(hào)串集合的自反閉包A*={ε}∪A+72023/11/26文法的直觀描述什么是文法文法是定義或描述語(yǔ)法結(jié)構(gòu)一組形式規(guī)則例句：Hegavemeabook.英語(yǔ)中的基本語(yǔ)法規(guī)則：<句子>

<主語(yǔ)><謂語(yǔ)><間接賓語(yǔ)><直接賓語(yǔ)><主語(yǔ)>

<代詞>|<名詞><謂語(yǔ)>

<動(dòng)詞><間接賓語(yǔ)>

<代詞><直接賓語(yǔ)>

<冠詞><名詞><代詞>He|me<名詞>

book<動(dòng)詞>

gave<冠詞>

a|an|the82023/11/26例句：Hegavemeabook.根據(jù)上述語(yǔ)法規(guī)則對(duì)例句進(jìn)行分析，可推出該例句。<句子>=><主語(yǔ)><謂語(yǔ)><間接賓語(yǔ)><直接賓語(yǔ)>

=><代詞><謂語(yǔ)><間接賓語(yǔ)><直接賓語(yǔ)>=>He<謂語(yǔ)><間接賓語(yǔ)><直接賓語(yǔ)>=>He<動(dòng)詞><間接賓語(yǔ)><直接賓語(yǔ)>=>Hegave<間接賓語(yǔ)><直接賓語(yǔ)>=>Hegave<代詞><直接賓語(yǔ)>=>Hegaveme<直接賓語(yǔ)>=>Hegaveme<冠詞><名詞>=>Hegavemea<名詞>=>Hegavemeabook92023/11/26用圖形化方式表示這種推導(dǎo)，形成一顆語(yǔ)法分析樹。

<句子><主語(yǔ)><代詞><冠詞>Hea<謂語(yǔ)><間接賓語(yǔ)><直接賓語(yǔ)><動(dòng)詞>gave<代詞>me<名詞>book語(yǔ)法成分（在形式語(yǔ)言中又稱“非終結(jié)符”）單詞符號(hào)（在形式語(yǔ)言中又稱“終結(jié)符號(hào)”)102023/11/26上述定義英文句子的規(guī)則可以說(shuō)就是一個(gè)上下文無(wú)關(guān)文法歸納起來(lái)，一個(gè)上下文無(wú)關(guān)文法G包括四個(gè)組成部分：一組終結(jié)符號(hào)一組非終結(jié)符號(hào)一個(gè)開始符號(hào)一組產(chǎn)生式112023/11/26文法形式化定義文法定義成一個(gè)四元組G=(VN,VT,S,P)VN:非空有限的非終結(jié)符集；VT:非空有限的終結(jié)符集；S:開始符號(hào)；P:產(chǎn)生式集合。其中，VN

∩VT

=Φ，S∈VNP中產(chǎn)生式一般形式為:A

α|β，其中A∈VN

，α,β∈（VN∪VT

）*122023/11/26例1：文法G=(VN,VT,S,P)，其中VN={S}，VT={0，1}，P={S→0S1，S→01}。這里，非終結(jié)符集中只含一個(gè)元素S；終結(jié)符集由兩個(gè)元素0和1組成；有兩條產(chǎn)生式；開始符號(hào)是S132023/11/26一個(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]：A→abA→aAbA→εS→aAb

④G[S]：A→ab|aAb|εS→aAb

142023/11/26文法的分類對(duì)產(chǎn)生式施加不同的限制得到不同類型的文法0型（無(wú)限制文法）:G=(VN,VT,

S,

P)

規(guī)則形式：

;(VN

VT)+,(VN

VT)*且

中至少含有一個(gè)非終結(jié)符1型（上下文有關(guān)）:

規(guī)則

有1,其中

=γ1Aγ2,=γ1δγ2;AVN,

δ

(VN

VT)+,γ1,γ2

(VN

VT)*.規(guī)則形式γ1Aγ2

γ1δγ2;

2型（上下文無(wú)關(guān)）:規(guī)則形式:Aδ

,

AVN

，δ

(VN

VT)+

3型（右線性和正規(guī)文法）:規(guī)則形式:

AB或A（右線性）A,BVN,(VT)*.152023/11/26左線性文法規(guī)則形式:

AB或A（左線性）

A,BVN,(VT)*.正規(guī)文法規(guī)則形式:

AB或A其中A,BVN,VT，如果S

P，則S不能出現(xiàn)在任何產(chǎn)生式右邊正規(guī)文法中只能出現(xiàn)單個(gè)終結(jié)符，右線性文法中可能出現(xiàn)若干個(gè)終結(jié)符組成的串2型文法擴(kuò)充Aδ,

AVN

，δ

(VN

VT)*允許有空產(chǎn)生式：A

不改變描述能力162023/11/26四個(gè)文法類的定義是逐漸增加限制的，因此每一種正規(guī)文法都是上下文無(wú)關(guān)的，每一種上下文無(wú)關(guān)文法都是上下文有關(guān)的，而每一種上下文有關(guān)文法都是0型文法。稱0型文法產(chǎn)生的語(yǔ)言為0型語(yǔ)言。上下文有關(guān)文法、上下文無(wú)關(guān)文法和正規(guī)文法產(chǎn)生的語(yǔ)言分別稱為上下文有關(guān)語(yǔ)言、上下文無(wú)關(guān)語(yǔ)言和正規(guī)語(yǔ)言現(xiàn)今大多數(shù)高級(jí)程序設(shè)計(jì)語(yǔ)言采用上下文無(wú)關(guān)文法來(lái)描述其語(yǔ)法已經(jīng)足夠了172023/11/26文法舉例文法G=({S,A,B},{a,b,c,d,e},S,P),其中，P={S

abcA|edB,AbeB,Bd}文法G是右線性文法改寫為正規(guī)文法正規(guī)文法產(chǎn)生式只能有兩種形式AB或A其中A,BVN,VT相應(yīng)的正規(guī)文法為：G’=({S,A,B,A’,B’,C’,D’},{a,b,c,d,e},S,P’),P’={S

aA’|eB’,A’bC’,C’cA,B’dB,AbD’,D’eB,Bd}182023/11/26192023/11/26S=>0A=>010A=>…=>0(10)*A=>0(10)*202023/11/26文法和語(yǔ)言上下文無(wú)關(guān)文法定義的語(yǔ)言從文法的開始符號(hào)出發(fā)，反復(fù)使用產(chǎn)生式，對(duì)非終結(jié)符進(jìn)行替換和展開，直至推導(dǎo)出語(yǔ)言的各種句子來(lái)推導(dǎo)與歸約的概念推導(dǎo)、最左推導(dǎo)、最右推導(dǎo)、規(guī)范推導(dǎo)歸約、最左歸約、最右歸約、規(guī)范歸約句型、句子、語(yǔ)言的形式定義語(yǔ)法分析樹與二義性212023/11/26推導(dǎo)和歸約222023/11/26最左推導(dǎo)和最右推導(dǎo)規(guī)范推導(dǎo)最右直接推導(dǎo)又稱為規(guī)范直接推導(dǎo)，最右推導(dǎo)又稱為規(guī)范推導(dǎo)232023/11/26最右歸約和最左歸約的定義242023/11/26句型、句子、語(yǔ)言的定義定義2.6設(shè)S是文法G的識(shí)別符號(hào)，如果Su,則稱符號(hào)串u為文法G的句型定義2.7設(shè)S是文法G的識(shí)別符號(hào)，如果Su,uVT*,則稱符號(hào)串u為文法G的句子定義2.7設(shè)S是文法G的識(shí)別符號(hào)，文法G的語(yǔ)言L(G)={u|Su且uVT*},即文法的語(yǔ)言是文法所有句子的集合*

*

*

252023/11/26例2.9文法G=(VN,VT,S,P)，其中VN={S}，VT={0，1}，P={S→0S1，S→01}。這里，非終結(jié)符集中只含一個(gè)元素S；終結(jié)符集由兩個(gè)元素0和1組成；有兩條產(chǎn)生式；開始符號(hào)是S262023/11/26直接推導(dǎo)示例對(duì)于例2.9的文法G，有如下直接推導(dǎo)示例

u=0S1,w=0011,直接推導(dǎo)：0S1=>0011，使用的規(guī)則：S→01，這里γ=0，δ=1。

u=S,w=0S1，直接推導(dǎo)：S=>0S1使用的規(guī)則：S→0S1，這里γ=ε，δ=ε

u=0S1,w=00S11,直接推導(dǎo)：0S1=>00S11，使用的規(guī)則：S→0S1，這里γ=0，δ=1。

272023/11/26對(duì)例2.9的文法，存在直接推導(dǎo)序列v=0S1=>00S11=>000S111=>00001111=w，即0S1=>+00001111，也可記作0S1=>*00001111

S，0S1，000111都是例2.9文法G的句型，其中000111是G的句子282023/11/26考慮例2.9的文法G，有兩條產(chǎn)生式(規(guī)則)：(1)S→0S1和(2)S→01，通過(guò)對(duì)第一個(gè)產(chǎn)生式使用n-1次，然后使用第2個(gè)產(chǎn)生式一次，得到：

S=>0S1=>00S11=>…=>0n-1S1n-1=>

0n1n

可以推知L(G)中的元素僅是這樣的串(0n1n)。從而可證明L(G)={0n1n|n≥1}.292023/11/26文法等價(jià)若L(G1)=L(G2)，則稱文法G1和G2是等價(jià)的。

也就是說(shuō)，如果兩個(gè)文法定義的語(yǔ)言一樣，則稱這兩個(gè)文法是等價(jià)的。

例如文法G[A]：

A→0R

A→01

R→A1

和例2.9的文法等價(jià)。302023/11/26證明(i*i+i)是算術(shù)表達(dá)式文法G=(VN,VT,S,P)VN={E}VT={i,+,*,(,)}S=EEi|E+E|E*E|(E)描述了算術(shù)表達(dá)式證明(i*i+i)是算術(shù)表達(dá)式如果能從文法G中推導(dǎo)出(i*i+i),則可證明它是算術(shù)表達(dá)式312023/11/26推導(dǎo)過(guò)程E=>(E)產(chǎn)生式：E(E)=>(E+E)產(chǎn)生式：EE+E=>(E*E+E)產(chǎn)生式：EE*E=>(i*E+E)產(chǎn)生式：Ei=>(i*i+E)產(chǎn)生式：Ei=>(i*i+i)產(chǎn)生式：Ei存在一個(gè)從E到(i*i+i)的推導(dǎo)，證明了(i*i+i)是文法G所定義的一個(gè)算術(shù)表達(dá)式322023/11/26語(yǔ)法分析樹我們用一張樹型結(jié)構(gòu)的圖來(lái)描述一個(gè)句子的推導(dǎo)，這種表示稱為語(yǔ)法樹。語(yǔ)法樹的根結(jié)由文法開始符號(hào)標(biāo)記。隨著推導(dǎo)的進(jìn)行，當(dāng)某個(gè)非終結(jié)符被它的候選式所替換時(shí)，此非終結(jié)符生出其下一代新結(jié)，候選式中自左至右沒(méi)有符號(hào)對(duì)應(yīng)著一個(gè)新結(jié)。性質(zhì)：在語(yǔ)法樹生長(zhǎng)的任何時(shí)候，所有那些沒(méi)有后代的端末結(jié)自左至右的排列起來(lái)，就是一個(gè)句型。語(yǔ)法分析樹的生成過(guò)程：書中第31頁(yè)332023/11/26(i*i+i)的語(yǔ)法樹E=>(E)產(chǎn)生式：E(E)=>(E+E)產(chǎn)生式：EE+E=>(E*E+E)產(chǎn)生式：EE*E=>(i*E+E)產(chǎn)生式：Ei=>(i*i+E)產(chǎn)生式：Ei=>(i*i+i)產(chǎn)生式：EiE=>(E)產(chǎn)生式：E(E)=>(E*E)產(chǎn)生式：EE*E=>(i*E)產(chǎn)生式：Ei=>(i*E+E)產(chǎn)生式：EE+E=>(i*i+E)產(chǎn)生式：Ei=>(i*i+i)產(chǎn)生式：Ei342023/11/26文法的二義性一個(gè)文法，如果它的一個(gè)句子有兩棵或兩棵以上的語(yǔ)法樹，則稱此句子具有二義性。如果一個(gè)文法含有二義性的句子，則該文法具有二義性。換一個(gè)說(shuō)法：如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵或兩棵以上不同的語(yǔ)法樹，則稱該文法是二義的352023/11/26例1．注：文法的二義性是不可判定的，但可以通過(guò)約定加以改造。例2．文法G1：A→AN|NN→0|1|…|9

則L(G1)為無(wú)符號(hào)整數(shù)例3．文法G2：B→aBb|ab,求L(G2)

解：B=>aBb=>aaBbb=>aaaBbbb=>……

即，

∴L(G2)={anbn|n≥1}362023/11/26例題構(gòu)造文法生成下列語(yǔ)言(1){an|n≥1}S

aA|

A

aA|

或

S

aS|

(2){an