编译原理课件

前述内参回顾

•编译程序

•编译方式与解释方式的根本区别

-编译程序的工作过程

,编译程序的结构II

•编译程序的组织方式

,编译程序的构造

第二章文法和语言的基本知识

本章主要介绍形式语言理论中的一些最

基本的概念和基础知识，它是学习以后各章

的基石。

本章内参简介

•文法的形式定义

•语言的形式定义

•为语言构造文法与由文法推出语言

­语法树及文法的二义性

・文法和语言的分类

■文法的实用限制

形式语言理论

由Chomsky于1956年首先提出。

；是指由数学方法——形式化方法研究自然语言（如英

语）和人工语言（如程序设计语言）的语法的理论。।

目前在自然语言的翻译、计算机语言的描述和转换、

编译程序的构造、模式识别等方面有广泛的应用。

2A语官的基本^叔।

一个语言的成分包括字母表（Alphabet），文法（G

rammar）以及它的语义。

；字母表是符号的有穷集，而符号构成了语言中的句子。

语法是结构规则的有穷集，这些规则定义了句子中符号

的合法上下文。

语义通常是操作规则的有穷集，这些规则定义了用该语

言编写的任何程序在某个计算机上执行的操作性效果。

2.2.1字母表与符号串

1.字母表.......................

字母表是元素的有穷非空的集合。字母表中的元素称为符号。

例如{a,b,.........y,z},{0,1}等。

，常用X来表示.....................................

注意：字母表中至少包含一个元素。元素可以是字母、数字

或其他符号。।।।।।।।।।

李母表与符号串

2.符号、符号串及其运算（P9）।।।।।

字母表中的元素称为符节；；；；；；；

符号串是字母表中的符号所组成的任何有穷序列，通常用小写的字

母表示。

例：S={0,1}贝|00,11,01,10,010..........是符号串。

注意：1）不包含任何符号的符号串为空串，记为£。；

I挤2）符号串中的符号顺序很重要。abrba।।।।

3）符号串x中有ni个符号，贝||x|=mm是长度。

2.2.2符号串运算

■卷号串;的遂接；；；；；；

设X和y是符号串，则称xy是他们的连接。

例如：x=abc,y=1a

则xy=abc1a,yx=1aabc

即|x|=3,|y|=2,|xy|=3+2=5

注意：对任意一个符号串£；；；

我们有£X=X£=X

■符号串集合的乘积

设A和B是符号串的集合，则A和B的乘积定义为，

AB={xy|xGA,yGB}

例如：A={a,b}B={c,d}

则AB={aGad,bGbd}

集合的乘积是满足于A,yeB的所有符号串xy

k所构成的集合。；；；；；；；；

注意：；；；；；；；；；；

1、对于任何集合A,有{£}A=A{4=A

2、{£}=00/{}

■符号串的方塞

■设X是符号串，X”是X自身连结n次。并且xO=E

■贝ijx1=x

■x2=XX

■Xn=XX..........X=Xxn-1

■、；nk____j______；___J；；；；；；

■例如，设x=abc,则

■x1=abc

■x2=abcabc

■符号串集合的方塞

■A是符号串的集合，An是集合A自身n次相乘，

■并且人。={£}

■则A1=A

■A2=AA

■A』的..,…A=AAn'1(n>0)

■n个A

■例1A={a,b}A0={E}A1={a,b}

■A2={aa,ab‘ba’bb}

■A3={aa,ab,ba,bb}・{a,b}

■={aaa,aab,aba,abb,baa,bab,bba,bbb}

■符号串集合的正闭包A+与闭包A*

■；A型集合

■A的正闭包A+=A1UA2U......UAn

■A的闭包A*=A0UA1UA2U......UAn

■={£}UA+

・A={a,b}

■A+={a,b,aa,ab,ba,bb,aaa,aab9....}

■A*={a,a,b,aa,ab,ba,bb,aaa,aab,....}

■A+表示A上元素a,b构成的所有符号串的集合。

2.3文法和语言的形式定义

2.3.1文法的有关概念

1.终结符号।।।।।।।।।

；终结符号是组成语言的基本符号，如保留字、标识符、常数、

运算符、界限符等。终结符号是语言的不可再分的基本符号。终

।结符号形成的集合记为一般用小写字母表示。

2.非终结符号...........................

；小E终结符号用来表示语言的语法成分（或语法范畴、语法单

后位），例如“赋值语句”。非终结符号所形成的集合记为Vg-

般用大写字母来表示。

vTnvN=0

2.3文法和语言的形式定义

3.产生式：产生式（规则）是一个有序对（a,B）,通常写作

oc—6（或鼠：：=|3）

+

其中0C称为产生式的左部，|3称为产生式的右部。ae（VTUVN）,

|3e（VTUVN）j*o।；

'产生式是用来定义一个语法成分的。它描述了一个语法成分

的形成规则。例如标识符的构成规则可描述为：

＜标识符》一＜字母）|＜标识符X字母）|＜标识符X数字）

假如有若干条规则有相同的左部，通常写作：a-PJp2|...|pn

pn称为a的候选式

例如：1)V句子＞-V主语〉V谓语〉

2)v主语〉一v冠词〉v名词〉

3)v谓语〉一v动词〉v宾语〉

4)v宾语〉一v冠词〉v名词〉

5)v名词〉—»mancar

6)v冠词＞一the

7)v名词＞—＞drive

Themandrivethecar

Thecardrivetheman一组规则规定一个语言

Thecardrivethecar的语法结构

Themandrivetheman

2.3.2文法的形式定义

文法是产生式的有穷非空的集合。

文法G是一个四元组，G[S]=(VrVN,P,S)o；

:1r_终结您号藁。；；；；；；

IVN―u非终结符号集。।1III।

圈S——开始符号。至少要在一条产生式中作为左部出现。

P——表示产生式的有穷非空的集合。

例1定义标识符的文法

G[＜标识符＞]=（{A,B,Y,Z,0,1,...,9},

{＜标识符＞,＜字母＞，＜数字＞},P,＜标识符〉）

P定义为：

＜标识符》一＜字母）I＜标识符＞＜字母》I＜标识符＞＜数字）

＜字母＞-A|B|C|D|E|F|G|.......|U|V|W|X|Y|Z

＜数字＞-01112I314|5I6|7|819

2.3.3和语言有关的几个概念

1.直接推导

如果a->0是文法G的一条产生式，而丫,6是(VTUVN)*中任意

一个符号串，则将a一口作用于符号串ya6上得到符号串丫口6,称

符号串YP6是符号串Ya6的直接推导，记为

ya6=>yP6

:直接推导的逆过程称为直接归约，即由符号串丫口6可直接归约到丫

a6o

直接推导举例

例1文法G[E]：

E->E+T|TT-T*F|F一(E)|i

*TFn*T*FF

例2见P14

2.3.3和语言有关的几个概念

超导；；；；；；；；0

\设鼠0、、、…Qn均为（VTUVJ*中的符号串，且有

0C0=>ot1=>OC2n・・・0C「10an

则称以上序列是长度为n的推导，即a0可经过n步推导得到a

+

今

aoan

显然，这里n“，当n=l,就是直接推导。'；；

当n=0时，oco=ocn.当n》我们称为广义推导。

推导的逆过程称为归约，即明可归约到0t0。

2.3.3和语言有关的几个概念

3.最左推导和最右推导

如果在某个推导过程中的任何一步直接推导an6中，

都是对符号串鼠的最左（右）非终结符号进行替换，则称其

为最左（右）推导。最右推导又叫做规范推导。规范推导的

逆过程（最左规约）称为规范规约。

【例1】设有文法G[NJ

N]-N

N-ND|D

D->0|1|2

N1=>N=>ND=>N2=>D2=>12最右推导

N1=>N=>ND=>DD=>1D=>12最左推导

N1=>N=>ND=>DD=>D2=>12不是最左推导

也不是最右推导

【例2】设有文法G[E]：E=>E-T=>E-F=>E-i

E一E+T|E-T|T

=>T-i=>T*F-i=>T*i-i

T—T*F|T/F|F

F->(E)|i=>F*i・i=>(E)*i・i

=>(E+T)*i-i

=>(E+F)*i・i

请写出字符串（i+i）*i-i最右推导

=>(E+i)*i-i

=>(T+i)*i-F

=>(F+i)*i-F

=>(i+i)*i-i

2.3.3和语言有关的几个概念P15

4.句型

।设有文法G[S],如果S3u，且(VTUVN)*则称符号串u

为文法G⑻的句型。由规范推导(最右推导)得至》的句型称为规范句型.

5.句子；；；；；；；；；；

|设有文法G[S],如果S当u，且UEV/,则称符号串u为

文法G网的句子。

由此可看出：句型包含句子

■【例1】设有文法G[S]：

■S-01I0S1

S=>01

S=>0S1

=>00S11

=>000111

■S,01,0S1,00S11Q00111者B是句型。

■01和000111又是句型。

【例2】设有文法G[E]：E=>E-T=>E-F=>E-i

E一E+T|E-TIT

T—T*F|T/F|F11=>T-i=>T*F-i=>T*i-i

F一(E)|I=>F*i・i=>(E)*i・i

证明：字符串(i+i)*i-i是文法G[E]的=>(E+T)*i-i

句子

=>(E+F)*i・i

字符串(i+i)*i・i是句子=>(E+i)*i-i

方框里面的字符串是句型=>(T+i)*i-F

=>(F+i)*i-F

=>(i+i)*i-i

2.3.3和语言有关的几个概念

6.语言

文法G[S]产生的所有句子的集合称为G所定义的语言，记为L(G[S])

L(G[S])|isi>ui，旦uevj}IIllI

由此可知：1)当文法给定，语言也就确定。

2)L(G)是V/的子集，即属于V/的符号串x不一定属于L(G)

2.3.3和语言有关的几个概念P17

7直接递归与间接递归।|||।

；如果文法的产生式呈U-…U…形式，则称其为规则递归，也

称直接递归。（U为非终结符）IIIII

1如果文法中有推导Um…U…，则称其为文法递归，也称

间接递归。

所谓递归即，规则的左部或右部具有相同的非终结符。

2.3.3和语言有关的几个概念

8.规则左递归与规则右递归

如果文法的产生式呈U-U…的形式，则称其为规则左递归。

如果文法的产生式呈U-...U的形式，则称其为规则右递归。

规则左（右）递归，也称直接左（右）递归。

9.文法左递归与文法右递归

如果文法中有推导U3U…，则称其为文法左递归，也称

间接左递归。III

如果文法中有推导ut...u,则称其为文法右递归，也称

间接右递归。

递归举例

：

GJS]S->Sa|Ab|b|cG2[S]：S^a|s|aTb

A—>Bc|aT—S,T|S

B->Sb|b

t直接左递归Ii直接右递归

G3[S]:S—Aa|c

A—>Bc|a间接左递归

B一Sb|b

2.3.3和语言有关的几个概念

文法递归的作用：

用较少的产生式产生无穷多个句子，实现“用有穷表示无穷”。

G4[＜无符号整数＞]；:；；；；；；；；

,＜无符号整数＞-＜数字＞|＜无符号整数＞＜数字）11；

＜数字）一0|1|2|3|4|5|6|7|8|9

2.3文法的分类

乔姆斯基（Chomsky）把文法分成四种类型，即0型、1型、

2型芾3型；；；；；；；；；

这四类文法的区别在于：对产生式规则的形式上施加不同

的限制。从0型到3型对产生式的要求越来越严格，而其描述语

言的能力是逐步减弱的。

2.3文法的分类

■o型文法(无限制文法或短语结构文法)

■产生式为：OCT|3

■其中：ae(VNUVT)*且至少包含一个非终结符

■pG(VNUVT)\

■。型文法没有其他任何限制条件，故称无限制文法。

■0型文法所生成的语言称为无限制语言。

■例如有0型文法G=(VN，V「P,S)，其中

■P={S—OAB

■1B—0

■B—SA|01

■A1->SB1

■AO—SOB}

■其描述的。型语言为L(G[S])={}

■对0型文法的产生式做些限制，可得到其它三种类

型的文法。

■1型文法（上下文有关文法）

■产生式为：oct。

■其中：ct=*方；P=y向2；且I

11111

■।（VNUVp*1AGVN

■；；3w；（VNUVT）+；；；；；；；

■符号串力，方可以认为是上下文，期间的A可以被符号

串3替代。因此1型文法又称为上下文有关文法。

■此类文法对非终结符A进行替换时必须考虑上下文，并

且3一般不可以是空串。即l4|oc|4||3|

■1型文法描述的语言成为上下文有关语言。

文法的分类文法——举例

例1.文法GJZ]：

GJZ]=({S,B,C,D},{a,b,c},P,S),其中P为

S-aSBC|aBCCB-CD

CD->BDBD-BC

aB->abbBfbb।1

bCfbecC—cc

1型文法(上下文有关文法)要求：

+

a->P1<|«|<|P|，ae(VNUVT),pe(VNUVTf

■2型文法(上下文无关文法)

■产生式为：A->[3

■其中：AGVN,|3G(VNUVT)*JII「I

■此类文法所定义的语法单位完全独立于它所处的环境，

即与上下文无关。

■这种文法用于描述现今大多数程序设计语言的语法结构。

也是我们研究的主要对象。

文法的分类文法——举例

例2.文法G2[Z]：

G2[Z]=({Z,S,A,B,C},{a,b,c},P,Z),

其中P为：Z-SCS-aAc

A-*aAc|bBbC-aCb|E

裳.瞿iiB-bB|E1111

2型文法(上下文无关文法)要求：

AfAGVN,PG(VNUVT)*

■3型文法（正规文法）

■产生式为：A-a或A—aB右线性文法

■A—a或A—Ba左线性文法

■其中：A,BGVN,aeVT

■这种文法用于描述现今大多数程序设计语言的词法结构。

2.3文法的分类文法——举例

例3.文法G3[Z〕：

G3[Z]=({Z,U,V},{0,1},P,Z),其中P为

IIIZ->UO|V1Illi

U->Z1|1IIIII

平11V-Z0|0

左线性3型文法要求：A->a或A-Ba,A,BeVN,aeVT

例4.表示标识符的文法

〈标识符》一〈字母＞|〈标识符〉〈字母〉|〈标识符》V数字〉

可抽象为：1-1IIIIId

奉左线性文净；；；；；；；

例5.表示无符号整数的文法；；；；；

〈无符号整数〉一〈数字》I〈无符号整数X数字》

〈无符号整数〉一〈数字》I〈数字〉〈无符号整数》；

是右线性文法。

文法分类小结

・1）。型文法到3型文法，其产生式的限制条件是逐

渐增加埠。；；；；；；；；；

-2）0型文法＞1型文法＞2型文法＞3型文法：

・3）他们所描述的语言的范围也是逐渐缩小的。

形式语言与自动机

0型文法（图灵机）

1型文法（不确定的

界限自动机）

2型文法（不确定的

工j学动机）

3型文法（有限

自动机）

N

0

g山

■

两类题型

■由语言构造文法

■由文法生成语言

■例1设Z={a，b}设计文法可以描述语言(P12)

■L={a2n,b2n|n>=1}

'首先我们分析语言字符串的特点：；；.

■n=1L={aa,bb}

■n=2L={aaaa,bbbb}

■n=3L={aaaaaa,bbbbbb}

■L={aa,bb,aaaa,bbbb,aaaaaa,bbbbbb......}

■可看出语言是由偶数个a,偶数个b组成的集合。

■下面开始构造文法

■A—aa|bb

■A—aaB|bbD

PI

■B—aaBIaa

■D—bbDIbbj

■G=(VN，VT,PJ,S)

"VN={A,B,D}VT={a,b}

■A—B|D

■B一aBaIaa>P2

■D—bDbIbb

■G=(VN，VT,P2,S)

■VN={A,B,D}VT={a,b}

■说明同一种语言可以用多种文法来描述。

■例2设Z={a,b}设计文法可以描述语言

■L={abna|n>=0}

'首先我们分析语言字符串的特点；；

■n=0L={aa}

■n=1L={aba}

■n=2L={abba}

■nL={ab.....ba}

"------Y------'

■n个b

例：{atPa吟o0},构造其文法

o

■下面开始构造文法o

------------X--、

■S->aBa若n2L如何？二>1^

■B—BbyPV

■:B—E；；J；；

G2[S]:

S一aBa

・GI=（VN，VT，P.S）।।B一b|Bb

"VN={S,B}VT={a,b}

■例3试构造正规文法描述不以0开头的正奇数。

■首先我们分析语言字符串的特点

1〜90〜9135,7,9

下面开始构造文法

1）该语言最简单的形式

■S—1I3I5I7I9

2）该语言普通形式

S—1A|2A|3A|4A|5A|6A|7A|A|9A

-3)A最简单形式

■A-1|3|5|7|9

■4)A普通形式

■A->0A|1A|2A|3A|4A|5A|6A|7AA|9A

■G1=(VN,VT,Pi,S)

VT={04,2,3,4,5,6,7,8,9}

■VN={S,A}

■假设没有正规文法限制

1〜90〜9135,7,9

ABC

S—CACIABC

234567rU

ki

A一1oB1B2B3B4BLJ5B6B

|8B|9

-0|1|2|3|4|5|6|7|9

CT1|3|5|7|9

■G2=(VN,VT,P2,S)

■VN={S,A,B,C}VT={0,1,2,3,4,5,6,7,

■习题2.3・2

・设2={a,b}设计文法可以描述语言；

■L={anbnci|n>=1,i>=0}

■首先我们分析语言字符串的特点：

■n=1,i=0L={ab}是语言的最简形式

■n>2,i>1L={aabbc,aabbcc,aaabbbc......}

・L是a与b的个数相等，并以c结尾的字符串的集合

L={anbnc'|n>=1,i>=0}

下面开始构造文法

S—ab]一最简单形式

S->Sc一产生n个c

S—A>P1

A—aAbG2[S]：

S-AC

A—>ab>A—aAb|ab

C->cC|E

G=(VN,VT,Pj,S)G2=(VN,VT,P1,S)

VN={S,A,C}VT={a,b,c}

VN={S,A}VT={a,b,c)

■习题2.3-3

■设Z={a,b}设计文法可以描述语言；

■L={anbncmdm|n>=1,m>=1}

■首先我们分析语言字符串的特点：

■n=1,m=1L={abcd）是语言的最简形式

■n=2,m=2L={aabbccdd}

■n=1,m=2L={abccdd}

■n=2,m=1L={aabbcd}

•a与b的个数相等c与d的个数相等

■下面开始构造文法

■S—AB]一两部分构成

■A—aAb一产生等同数目的ab

■A-ab'P一A最简单形式

■B—>cBd一产生等同数目的cd

■B―cd」一B最简单形式

•G=(VN，VT,P,S)

■VN={SAB}VT={a,b,c,d}

小结：

1）首先分析该语言句子的特点」：；—

2）用;文法初造;语言;最简;单/式。；；；।।

3）试用递归规则构造语言一般形式；可以分部分构

；造;。引进新的非终结符。；；；；；

4）对于每个部分也要遵循从简到繁的方法。

5）最后检查这组规则是否能表示语言的全部句子。

两类题型

■由语言构造文法

■由文法生成语言

复习——语言的形式定义

文法G[S]产生的所有句子的集合称为G所定义的语言，记为L(G[S])

，(6南)=|xIjst>xi,本}；；\；；

由此可知：1)当文法给定，语言也就确定。

2)L⑹是V/的子集，即属于V/的符号串x不一定属于L(G)

■【例1】设有文法G[S],求所定义的语言。(p15)

■S—01I0S1

s=>osi

=>00S11....

=>On-1SlnA=>Onln

■L(G[S])={On1nIn>=1}

■【例2】设有文法G[S],求所定义的语言。

■1）ST0S

■3）S-w

S=>IS.......

S=>01S.......或IOS.........

■解：3）代入1）和2）S=>0,S=>1

■口）代表所有以。开头的字符串，每次用1）产生0

■；，2）代表所有以1开头的字符串，每次用2）产生1

■1）和2）交替将产生01串或10串

■L（G[S]）={1和0组成的长度为任意的字符串}

■【例3】设有文法G[N1],求所定义的语言。

■1)N1-N

■2)N—NDID

■3)D一0|C|2

N1=>N=>ND=>NND=>DDD

■其定义的语言｛0,1,2)+

■【例4】设有文法G[S],求所定义的语言。

■1)S—aTd

-2)T—bT|cT|c|b

■其定义的语言a{b,c}+d；；；；；；

■由文法确定语言的中心思想：।।।।।

祢；从文法的开始符号出发，反复连续地实验

规则，对非终结符施行替换和展开，找出句子的规

律，用式子或自然语言描述出来。

■形式语言理论可以证明以下两点：

(1)G-L(G)；文法结构唯一确定语言。

(2)L(G)->G1,G2,……,Gn；

描述一种语言的文法是不唯一的。

已知文法，求语言，通过推导

/\

例：

G[S]；\L(G[S]>{anbn|n>l}

S-aSb|ab

求其所产生的语言。；'

1L(G[S])={anbn|n>0}

cTZ若S一aSb|S,或口何？一

y—----------------->—_____

口，><___________________________>

课堂练习1：G[S]<X

n

S-bA\\L(G[S]>{ba|n>l}

A一aA|aWl>1

课堂练习2:G[S]

mn

S—ABL(G[S])={ab|m?n>l}

A一aA|awi>1__________________________>