編譯原理第2章：高級語言及其語法描述

第二章高級語言及其語法描述

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

。例：

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

<主語><謂語><間接賓語><直接賓語><主語>

<代詞>|<名詞><謂語>

<動詞><間接賓語>

<代詞><直接賓語>

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

book<動詞>

gave<冠詞>

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

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

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

∩VT

=Φ，S∈VNP中產生式一般形式為:A

α|β，其中A∈VN

，α,β∈（VN∪VT

）*122023/11/26例1：文法G=(VN,VT,S,P)，其中VN={S}，VT={0，1}，P={S→0S1，S→01}。這里，非終結符集中只含一個元素S；終結符集由兩個元素0和1組成；有兩條產生式；開始符號是S132023/11/26一個文法的幾種寫法

①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文法的分類對產生式施加不同的限制得到不同類型的文法0型（無限制文法）:G=(VN,VT,

S,

P)

規(guī)則形式：

;(VN

VT)+,(VN

VT)*且

中至少含有一個非終結符1型（上下文有關）:

規(guī)則

有1,其中

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

δ

(VN

VT)+,γ1,γ2

(VN

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

γ1δγ2;

2型（上下文無關）:規(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)在任何產生式右邊正規(guī)文法中只能出現(xiàn)單個終結符，右線性文法中可能出現(xiàn)若干個終結符組成的串2型文法擴充Aδ,

AVN

，δ

(VN

VT)*允許有空產生式：A

不改變描述能力162023/11/26四個文法類的定義是逐漸增加限制的，因此每一種正規(guī)文法都是上下文無關的，每一種上下文無關文法都是上下文有關的，而每一種上下文有關文法都是0型文法。稱0型文法產生的語言為0型語言。上下文有關文法、上下文無關文法和正規(guī)文法產生的語言分別稱為上下文有關語言、上下文無關語言和正規(guī)語言現(xiàn)今大多數(shù)高級程序設計語言采用上下文無關文法來描述其語法已經(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ī)文法產生式只能有兩種形式AB或A其中A,BVN,VT相應的正規(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文法和語言上下文無關文法定義的語言從文法的開始符號出發(fā)，反復使用產生式，對非終結符進行替換和展開，直至推導出語言的各種句子來推導與歸約的概念推導、最左推導、最右推導、規(guī)范推導歸約、最左歸約、最右歸約、規(guī)范歸約句型、句子、語言的形式定義語法分析樹與二義性212023/11/26推導和歸約222023/11/26最左推導和最右推導規(guī)范推導最右直接推導又稱為規(guī)范直接推導，最右推導又稱為規(guī)范推導232023/11/26最右歸約和最左歸約的定義242023/11/26句型、句子、語言的定義定義2.6設S是文法G的識別符號，如果Su,則稱符號串u為文法G的句型定義2.7設S是文法G的識別符號，如果Su,uVT*,則稱符號串u為文法G的句子定義2.7設S是文法G的識別符號，文法G的語言L(G)={u|Su且uVT*},即文法的語言是文法所有句子的集合*

*

*

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

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

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

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

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

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

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

0n1n

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

也就是說，如果兩個文法定義的語言一樣，則稱這兩個文法是等價的。

例如文法G[A]：

A→0R

A→01

R→A1

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

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

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

即，

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

aA|

A

aA|

或

S

aS|

(2){an