编译原理课件第2章(2）.ppt

《编译原理课件第2章(2）.ppt》由会员分享，可在线阅读，更多相关《编译原理课件第2章(2）.ppt（82页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、前述内容回顾前述内容回顾 编译程编译程序序 编译方式与解释方式的根本区编译方式与解释方式的根本区别别 编译程序的工作过程编译程序的工作过程 编译程序的结构编译程序的结构 编译程序的组织方式编译程序的组织方式 编译程序的构造编译程序的构造第二章第二章 文法和语言的基本知识文法和语言的基本知识 本章主要介绍形式语言理论中的一些最本章主要介绍形式语言理论中的一些最基本的概念和基础知识，它是学习以后各章基本的概念和基础知识，它是学习以后各章节的基石。节的基石。本章内容简介本章内容简介 文法的形式定义文法的形式定义 语言的形式定义语言的形式定义 为语言构造文法与由文法推出语为语言构造文法与由文法推出语言

2、言 语法树及文法的二义性语法树及文法的二义性 文法和语言的分类文法和语言的分类 文法的实用限制文法的实用限制形式语言理论形式语言理论 由由ChomskyChomsky于于19561956年首先提出。年首先提出。是指由数学方法是指由数学方法形式化方法形式化方法研究自然语言（如英研究自然语言（如英语）和人工语言（如程序设计语言）的语法的理论。语）和人工语言（如程序设计语言）的语法的理论。目前在自然语言的翻译、计算机语言的描述和转换、目前在自然语言的翻译、计算机语言的描述和转换、编译程序的构造、模式识别等方面有广泛的应用。编译程序的构造、模式识别等方面有广泛的应用。2.1 2.1 语言成分的基本概念

3、语言成分的基本概念 一个语言的成分包括字母表（一个语言的成分包括字母表（AlphabetAlphabet）,文法（文法（rammarrammar)以及它的语义。以及它的语义。字母表字母表是符号的有穷集，而符号构成了语言中的句子。是符号的有穷集，而符号构成了语言中的句子。语法语法是结构规则的有穷集，这些规则定义了句子中符号的是结构规则的有穷集，这些规则定义了句子中符号的合法上下文。合法上下文。语义语义通常是操作规则的有穷集，这些规则定义了用该语言通常是操作规则的有穷集，这些规则定义了用该语言编写的任何程序在某个计算机上执行的操作性效果。编写的任何程序在某个计算机上执行的操作性效果。字母表中的字母

4、表中的元素元素称为符号。称为符号。1.1.字母表字母表字母表是元素的字母表是元素的有穷非空有穷非空的集合。的集合。例如例如 a a，b b，y y，zz，00，11等。等。2.2.1 2.2.1 字母表与符号串字母表与符号串常用常用 来表示来表示 。注意：注意：字母表中至少包含一个元素。元素可以是字母、数字字母表中至少包含一个元素。元素可以是字母、数字或其他符号。或其他符号。字母表中的元素称为字母表中的元素称为符号符号。符号串符号串是字母表中的符号所组成的任何是字母表中的符号所组成的任何有穷序列有穷序列，通常用小写的字，通常用小写的字母表示。母表示。例：例：0,1 0,1 则则 0000，11

5、11，0101，1010，010.010.是符号串。是符号串。注意：注意：1 1）不包含任何符号的符号串为）不包含任何符号的符号串为空串空串，记为，记为。2 2）符号串中的符号顺序很重要。）符号串中的符号顺序很重要。ababbaba 3 3）符号串）符号串x x中有中有m m个符号，则个符号，则|x|=m m|x|=m m是长度。是长度。字母表与符号串字母表与符号串2.2.符号、符号、符号串及其运算符号串及其运算(P9)(P9)2.2.2符号串运算符号串的连接符号串的连接 设设x和和y是符号串，则称是符号串，则称xy是他们的连接。是他们的连接。例如：例如：x=abc,y=1a 则则 xy=ab

6、c1a,yx=1aabc 即即|x|=3,|y|=2,|xy|=3+2=5注意：对任意一个符号串注意：对任意一个符号串x 我们有我们有x=x=x符号串集合的乘积符号串集合的乘积设设A和和B是符号串的集合，则是符号串的集合，则A和和B的乘积定义为的乘积定义为AB=xy|x A,y B例如：例如：A=a,b B=c,d 则则AB=ac,ad,bc,bd集合的乘积是满足于集合的乘积是满足于x A,y B 的所有符号串的所有符号串xy所构成的集合。所构成的集合。注意：注意：1、对于任何集合、对于任何集合A,有有A=A=A2、=符号串的方幂符号串的方幂设设x是符号串，是符号串，xn 是是x自身连结自身连

7、结n次。并且次。并且x0 则 x1 x x2 xx xn xxx=x xn-1 n个个例如例如,设 x=abc，则，则 x1 abc x2 abcabc 符号串集合的方幂符号串集合的方幂A是符号串的集合，是符号串的集合，An 是集合是集合A自身自身n次相乘，次相乘，并且并且A0 则 A1 A A2 AA An AAA=A An-1 (n0)n个个A例例1 A=a,b A0 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的正闭包

8、A A1 A2 AnA的闭包 A*A0 A1 A2 An A+A=a,bA a,b,aa,ab,ba,bb,aaa,aab,.A*,a,b,aa,ab,ba,bb,aaa,aab,.A表示表示A上元素上元素a,b构成的所有符号串的集合。构成的所有符号串的集合。VTVN=2.2.3.1 3.1 文法的有关概念文法的有关概念 2 2非终结符号非终结符号 非非终终结结符符号号用用来来表表示示语语言言的的语语法法成成分分（或或语语法法范范畴畴、语语法法单单位位），例例如如“赋赋值值语语句句”。非非终终结结符符号号所所形形成成的的集集合合记记为为V VN N。一一般用大写字母来表示。般用大写字母来表示。

9、1 1终结符号终结符号 终结符号是组成语言的基本符号，如保留字、标识符、常数、终结符号是组成语言的基本符号，如保留字、标识符、常数、运算符、界限符等。终结符号是语言的不可再分的基本符号。终运算符、界限符等。终结符号是语言的不可再分的基本符号。终结符号形成的集合记为结符号形成的集合记为V VT T。一般用小写字母表示。一般用小写字母表示。2.3 文法和语言的形式定义文法和语言的形式定义假如有若干条规则有相同的左部，通常写作：假如有若干条规则有相同的左部，通常写作：1 1|2 2|n nn称为称为的的候选式候选式 产产生生式式是是用用来来定定义义一一个个语语法法成成分分的的。它它描描述述了了一一个

10、个语语法法成成分分的的形成规则形成规则。例如标识符的构成规则可描述为：。例如标识符的构成规则可描述为：|3 3产生式产生式：产生式（产生式（规则规则）是一个有序对（）是一个有序对（,），），通常写作通常写作 （或或=）其其中中称称为为产产生生式式的的左左部部，称称为为产产生生式式的的右右部部。(V(VT TVVN N)+，(V(VT TVVN N)*。2.3 文法和语言的形式定义文法和语言的形式定义例如：1）2）3）4）5）man|car 6）the 7）driveThe man drive the carThe car drive the man 一组规则规定一个语言一组规则规定一个语言Th

11、e car drive the car 的语法结构的语法结构The man drive the manV VT T终结符号终结符号集。集。文法文法G G是一个四元组，是一个四元组，GS=GS=（V VT T，V VN N，P P，S S）。）。文法是产生式的文法是产生式的有穷非空有穷非空的集合。的集合。V VN N非终结符号非终结符号集。集。S S 开始符号开始符号。至少要在一条产生式中作为左部出现。至少要在一条产生式中作为左部出现。P P 表示产生式的表示产生式的有穷非空有穷非空的集合。的集合。2.2.3.23.2文法的形式定义文法的形式定义 GG =（A,B,Y,Z,0,1,9A,B,Y,

12、Z,0,1,9，,，P P，）P P 定义为：定义为：|A|B|C|D|E|F|G|U|V|W|X|Y|ZA|B|C|D|E|F|G|U|V|W|X|Y|Z 0|1|2|3|4|5|6|7|8|9 0|1|2|3|4|5|6|7|8|9 例例1 1 定义标识符的文法定义标识符的文法2.3.3 2.3.3 和语言有关的几个概念和语言有关的几个概念1.1.直接推导直接推导 如如果果 是是文文法法G G的的一一条条产产生生式式，而而，是是(VTVN)*中中任任意意一一个个符符号号串串，则则将将 作作用用于于符符号号串串 上上得得到到符符号号串串 ，称称符符号串号串 是符号串是符号串 的的直接推导直接

13、推导，记为，记为 直直接接推推导导的的逆逆过过程程称称为为直直接接归归约约，即即由由符符号号串串 可可直直接接归归约约到到 。直接推导举例直接推导举例 E E+T|T T T*F|F F（E）|i E E+T|T T T*F|F F（E）|i*T F例例1 文法文法GE：*T F*T*F F例例2 见见P14 2.2.推导推导 设设0 0、1 1、n n均为均为(V VT TVVN N)*中的符号串，且有中的符号串，且有 0 01 12 2n-1n-1n n则称以上序列是则称以上序列是长度为长度为n n的推导的推导，即，即0 0可经过可经过n n步推导得到步推导得到n n。显然，这里显然，这里

14、n n1,1,当当n=1,n=1,就是直接推导。就是直接推导。当当n=0n=0时，时，0 0=n .n .当当n n0 0，我们称为，我们称为广义推导广义推导。推导的逆过程称为推导的逆过程称为归约归约，即，即n n可归约到可归约到0 0 。2.3.3 2.3.3 和语言有关的几个概念和语言有关的几个概念2.3.3 2.3.3 和语言有关的几个概念和语言有关的几个概念 如如果果在在某某个个推推导导过过程程中中的的任任何何一一步步直直接接推推导导中中，都都是是对对符符号号串串的的最最左左(右右）非非终终结结符符号号进进行行替替换换，则则称称其其为为最最左左(右右）推推导导。最最右右推推导导又又叫叫

15、做做规规范范推推导导。规规范范推推导导的的逆过程（最左规约）称为逆过程（最左规约）称为规范规约规范规约。3.3.最左推导和最右推导最左推导和最右推导【例例1】设有文法设有文法GN1：N1N NND D D0 1 2=N2=ND=NN1=D2=12 最右推导最右推导=DD=ND=NN1=1D=12 最左推导最左推导=DD=ND=NN1=D2=12 不是最左推导不是最左推导 也不是最右推导也不是最右推导=T*F-i=(E+i)*i-i=F*i-i=(E+T)*i-i=(E)*i-i=(E+F)*i-i=(T+i)*i-F=(F+i)*i-F=(i+i)*i-i=T-i=E-i=E-F=E-TE【例

16、例2】设有文法设有文法GE：EE+T E-T T TT*F T/F F F（E）i请写出字符串请写出字符串(i+i)*i-i 最右推导最右推导=T*i-i，且，且 u u(V(VT TVVN N)*则称符号串则称符号串u u5.5.句子句子 设有文法设有文法GS，如果如果，且，且 u VT*，则称符号串则称符号串u u为为文法文法GS的的句子句子。由此可看出：由此可看出：句型包含句子句型包含句子 S S*u u2.3.3 2.3.3 和语言有关的几个概念和语言有关的几个概念 P15P154.4.句型句型 设有文法设有文法GGS S，如果如果S S*u u为文法为文法GSGS的句型的句型。由规范

17、推导由规范推导(最右推导最右推导)得到的句型称为得到的句型称为规范句型规范句型.【例例1】设有文法设有文法GS：S01 0S1S,01，0S1，00S11,000111 都是句型。都是句型。01和和000111 又是句型。又是句型。S=0S1=01 S =00S11 =000111=T*F-i=(E+i)*i-i=F*i-i=(E+T)*i-i=(E)*i-i=(E+F)*i-i=(T+i)*i-F=(F+i)*i-F=(i+i)*i-i=T-i=E-i=E-F=E-TE【例例2】设有文法设有文法GE：EE+T E-T T TT*F T/F F F（E）I证明：字符串证明：字符串(i+i)*i

18、-i 是文法是文法GE的的句子句子字符串字符串(i+i)*i-i 是是 句子句子方框里面的字符串是方框里面的字符串是 句型句型=T*i-i2.3.3 2.3.3 和语言有关的几个概念和语言有关的几个概念6.6.语言语言 文法文法GSGS产生的所有句子的集合称为产生的所有句子的集合称为G G所定义的所定义的语言语言，记为，记为L L（GSGS），且且u u V VT T*L L（GSGS）=u|=u|S S+u u=由此可知：由此可知：1 1）当文法给定，语言也就确定。当文法给定，语言也就确定。2 2）L(G)L(G)是是V VT T*的子集，即属于的子集，即属于V VT T*的符号串的符号串x

19、 x不一定属于不一定属于L(G)L(G)2.3.3 2.3.3 和语言有关的几个概念和语言有关的几个概念 P17P17 如如果果文文法法的的产产生生式式呈呈UUUU形形式式，则则称称其其为为规规则则递递归归，也也称称直接递归。（直接递归。（U U为非终结符）为非终结符）如果文法中有推导如果文法中有推导 U UU U，则称其为则称其为文法递归，文法递归，也称也称间接递归间接递归。7 7 直接递归与间接递归直接递归与间接递归所谓递归即，所谓递归即，规则的左部或右部具有相同的非终结符。规则的左部或右部具有相同的非终结符。2.3.3 2.3.3 和语言有关的几个概念和语言有关的几个概念如果文法的产生式

20、呈如果文法的产生式呈 UU UU 的形式，则称其为的形式，则称其为 规则左递归。规则左递归。如果文法的产生式呈如果文法的产生式呈 UUUU 的形式，则称其为的形式，则称其为 规则右递归。规则右递归。规则左规则左(右右)递归，也称直接左递归，也称直接左(右右)递归。递归。8.8.规则左递归与规则右递归规则左递归与规则右递归 如果文法中有推导如果文法中有推导 U UU U，则称其为文法则称其为文法左左递归，也称递归，也称间接间接左左递归。递归。如果文法中有推导如果文法中有推导 U UU U，则称其为文法则称其为文法右右递归，也称递归，也称间接间接右右递归。递归。9.9.文法左递归与文法右递归文法左

21、递归与文法右递归 递归举例递归举例 G1S：SSa|Ab|b|c ABc|a BSb|b G2S：Sa|aTb TS,T|S 直接左递归直接左递归直接右递归直接右递归 G3S：SAa|c ABc|a BSb|b间接左递归间接左递归文法递归的作用：文法递归的作用：用较少的产生式产生无穷多个句子，实现用较少的产生式产生无穷多个句子，实现“用有穷表示无穷用有穷表示无穷”。G G4 4：|0|1|2|3|4|5|6|7|8|9 0|1|2|3|4|5|6|7|8|9 2.3.3 2.3.3 和语言有关的几个概念和语言有关的几个概念 乔姆斯基（乔姆斯基（ChomskyChomsky）把文法分成四种类型把

22、文法分成四种类型 ，即即0 0型、型、1 1型、型、2 2型和型和3 3型型 。这这四四类类文文法法的的区区别别在在于于：对对产产生生式式规规则则的的形形式式上上施施加加不不同同的的限限制制。从从0 0型型到到3 3型型对对产产生生式式的的要要求求越越来来越越严严格格,而而其其描描述述语语言的能力是逐步减弱的。言的能力是逐步减弱的。2.3 2.3 文法的分类文法的分类2.3 2.3 文法的分类文法的分类0型文法（无限制文法或短语结构文法型文法（无限制文法或短语结构文法）产生式为产生式为 ：其中：其中：(V(VN NVVT T)*且至少包含一个非终结符且至少包含一个非终结符 (V(VN NVVT

23、 T)*，0 0型文法没有其他任何限制条件，故称无限制文法。型文法没有其他任何限制条件，故称无限制文法。0 0型文法所生成的语言称为无限制语言。型文法所生成的语言称为无限制语言。例如 有0型文法G=(VN,VT,P,S),其中P=S0AB 1B0 BSA|01 A1SB1 A0S0B其描述的0型语言为 L(GS)=对对0 0型文法的产生式做些限制，可得到其它三种类型文法的产生式做些限制，可得到其它三种类型的文法。型的文法。1型文法（上下文有关文法）型文法（上下文有关文法）产生式为产生式为 ：其中：其中：=1 1A A 2 2；=1 12 2；且；且 1|1|1 1，2 2 (V(VN NVVT

24、 T)*，A A V VN N ，(V(VN NVVT T)+，符号串符号串 1 1，2 2 可以认为是上下文，期间的可以认为是上下文，期间的A A可以被符号串可以被符号串 替代。因此替代。因此1 1型文法又称为上下文有关文法。型文法又称为上下文有关文法。此类文法对非终结符此类文法对非终结符A A进行替换时必须考虑上下文，并进行替换时必须考虑上下文，并且且 一般不可以是空串。即一般不可以是空串。即 1|1|1型文法描述的语言成为型文法描述的语言成为上下文有关语言上下文有关语言。文法的分类文法文法的分类文法举例举例 例例1.文法文法G1Z：G1Z=(S，B，C，D，a，b，c，P，S)，其中其中

25、P为为 SaSBC|aBC CBCD CDBD BDBC aBab bBbb bCbc cCcc1 型文法（上下文有关文法）要求：型文法（上下文有关文法）要求：1|，(VNVT)+，(VNVT)*2型文法（上下文无关文法）型文法（上下文无关文法）产生式为产生式为 ：AA 其中：其中：A A V VN N ，(V(VN NVVT T)*，此类文法所定义的语法单位完全独立于它所处的环境，此类文法所定义的语法单位完全独立于它所处的环境，即与上下文无关。即与上下文无关。这种文法用于描述现今大多数程序设计语言的语法结构。这种文法用于描述现今大多数程序设计语言的语法结构。也是我们研究的主要对象。也是我们研

26、究的主要对象。例例2.文法文法G2Z：G2Z=(Z，S，A，B，C，a，b，c，P，Z)，其中其中P为为：ZSC SaAc AaAc|bBb CaCb|BbB|2型文法（上下文无关文法）要求型文法（上下文无关文法）要求：A A VN，(VNVT)*文法的分类文法文法的分类文法举例举例3型文法（正规文法）型文法（正规文法）产生式为产生式为 ：AaAa 或或 AaBAaB 右线性文法右线性文法 AaAa 或或 ABaABa 左线性文法左线性文法 其中：其中：A A，B B V VN N，a a V VT T这种文法用于描述现今大多数程序设计语言的词法结构这种文法用于描述现今大多数程序设计语言的词法

27、结构。2.3 2.3 文法的分类文法文法的分类文法举例举例 例例3.文法文法G3Z：G3Z=(Z，U，V，0，1，P，Z)，其中其中P为为 ZU0|V1 UZ1|1 VZ0|0 左线性左线性3型文法要求：型文法要求：Aa 或或 ABa，A,B VN，a VT 例例4.4.表示标识符的文法表示标识符的文法|可抽象为:I l I l|I l I l|I dI d是左线性文法。是左线性文法。例例5.5.表示无符号整数的文法表示无符号整数的文法|是右线性文法。是右线性文法。文法分类小结1）0型文法到3型文法，其产生式的限制条件是逐渐增加的。2）0型文法 1型文法 2型文法 3型文法3）他们所描述的语言

28、的范围也是逐渐缩小的。根据上述讨论，根据上述讨论，L0 L1 L2 L32型文法型文法1型文法型文法0型文法型文法3型文法型文法四种文法之间的逐级四种文法之间的逐级“包含包含”关系关系2 2型文法型文法（不确定的（不确定的下推自动机）下推自动机）1 1型文法型文法（不确定的（不确定的界限自动机）界限自动机）0 0型文法型文法（图灵机）（图灵机）3 3型文法型文法（有限（有限自动机）自动机）形式语言与自动机形式语言与自动机图灵机图灵机BEGIN两类题型两类题型由语言构造文法由语言构造文法由文法生成语言由文法生成语言例1 设 a,b 设计文法可以描述语言(P12)L=a2n,b2n|n=1 首先我

29、们分析语言字符串的特点：n=1 L=aa,bbn=2 L=aaaa,bbbbn=3 L=aaaaaa,bbbbbbL=aa,bb,aaaa,bbbb,aaaaaa,bbbbbb可看出语言是由偶数个a,偶数个b 组成的集合。下面开始构造文法 Aaa|bb AaaB|bbD BaaB aa DbbD bbG=(VN,VT,P1,S)VN=A,B,D VT=a,b P1 AB|D BaBa aa DbDb bbG=(VN,VT,P2,S)VN=A,B,D VT=a,b 说明同一种语言可以用多种文法来描述说明同一种语言可以用多种文法来描述。P2例2 设 a,b 设计文法可以描述语言L=abna|n=0

30、 首先我们分析语言字符串的特点n=0 L=aan=1 L=aban=2 L=abban L=ab.ba n个b下面开始构造文法 SaBa BBb BG1=(VN,VT,P,S)VN=S,B VT=a,b P例：abna|n0,构造其文法 若若n1，如何？，如何？G2S：SaBa B b b|Bb例3 试构造正规文法描述不以0开头的正奇数。首先我们分析语言字符串的特点 下面开始构造文法1)该语言最简单的形式S1|3|5|7|92)该语言普通形式S1A|2A|3A|4A|5A|6A|7A|8A|9A 19 09 1,3,5,7,9A3)A最简单形式A1|3|5|7|94)A普通形式A 0A|1A|

31、2A|3A|4A|5A|6A|7A|8A|9AG1=(VN,VT,P1,S)VN=S,A VT=0,1,2,3,4,5,6,7,8,9假设没有正规文法限制 S C|AC|ABC A 1|2|3|4|5|6|7|8|9 B 0B|1B|2B|3B|4B|5B|6B|7B|8B|9B B 0|1|2|3|4|5|6|7|8|9 C 1|3|5|7|9G2=(VN,VT,P2,S)VN=S,A,B,C VT=0,1,2,3,4,5,6,7,8,9 19 09 1,3,5,7,9ABC习题2.3-2设 a,b 设计文法可以描述语言 L=anbnci|n=1,i=0 首先我们分析语言字符串的特点：n=1

32、,i=0 L=ab 是语言的最简形式n2,i1 L=aabbc,aabbcc,aaabbbcL是a与b的个数相等，并以c结尾的字符串的集合下面开始构造文法 Sab 最简单形式最简单形式 SSc 产生产生n个个c SA AaAb AabG=(VN,VT,P1,S)VN=S,A VT=a,b,c P1G2S：SAC A aAb|ab C cC|G2=(VN,VT,P1,S)VN=S,A,C VT=a,b,c L=anbnci|n=1,i=0 习题2.3-3设 a,b 设计文法可以描述语言 L=anbncmdm|n=1,m=1 首先我们分析语言字符串的特点：n=1,m=1 L=abcd 是语言的最简

33、形式n=2,m=2 L=aabbccddn=1,m=2 L=abccddn=2,m=1 L=aabbcda与b的个数相等c与d的个数相等下面开始构造文法 SAB 两部分构成两部分构成 AaAb 产生等同数目的产生等同数目的ab Aab A最简单形式最简单形式 BcBd 产生等同数目的产生等同数目的cd Bcd B最简单形式最简单形式G=(VN,VT,P,S)VN=S,A,B VT=a,b,c,dP小结：小结：1 1）首先分析该语言句子的特点。）首先分析该语言句子的特点。2 2）用文法构造语言最简单形式。）用文法构造语言最简单形式。3 3）试用）试用递归规则递归规则构造语言一般形式；可以分部分构

34、构造语言一般形式；可以分部分构 造。引进新的非终结符。造。引进新的非终结符。4 4）对于每个部分也要遵循从简到繁的方法。）对于每个部分也要遵循从简到繁的方法。5 5）最后检查这组规则是否能表示语言的全部句子。）最后检查这组规则是否能表示语言的全部句子。两类题型两类题型由语言构造文法由语言构造文法由文法生成语言由文法生成语言复习语言的形式定义文法文法GSGS产生的所有句子的集合称为产生的所有句子的集合称为G G所定义的所定义的语言语言，记为，记为L L（GSGS），且且 x x V VT T*L L（GSGS）=x|=x|S S+x x=由此可知：由此可知：1 1）当文法给定，语言也就确定。当文

35、法给定，语言也就确定。2 2）L(G)L(G)是是V VT T*的子集，即属于的子集，即属于V VT T*的符号串的符号串x x不一定属于不一定属于L(G)L(G)【例例1】设有文法设有文法GS,求所定义的语言。求所定义的语言。(p15)S01 0S1 L(GS)=0n1n|n=1 S=0S1 =00S11 =0n-1 S 1n-1=0n 1n【例例2】设有文法设有文法GS，求所定义的语言。，求所定义的语言。1)S 0S 2)S 1S 3)S 解解:3）代入）代入1）和）和2）S=0，S=1 1）代表所有以）代表所有以0 开开头的字符串，每次用的字符串，每次用1）产生生0 2）代表所有以）代表

36、所有以1 开开头的字符串，每次用的字符串，每次用2）产生生1 1）和）和2）交替将）交替将产生生01串或串或10串串 L(GS)=1和和0组成的长度为任意的字符串组成的长度为任意的字符串 S=0SS=1S S=01S 或或10S.【例例3】设有文法设有文法GN1，求所定义的语言。，求所定义的语言。1)N1 N 2)N ND|D 3)D 0|1|2其定义的语言其定义的语言 0，1，2+=NND=ND=NN1=DDD.【例例4】设有文法设有文法GS，求所定义的语言。，求所定义的语言。1)S aTd 2)T bT|cT|c|b其定义的语言其定义的语言a b，c+d由文法确定语言的中心思想：由文法确定

37、语言的中心思想：从文法的开始符号出发，反复连续地实验从文法的开始符号出发，反复连续地实验规则，对非终结符施行替换和展开，找出句子的规规则，对非终结符施行替换和展开，找出句子的规律，用式子或自然语言描述出来。律，用式子或自然语言描述出来。形式语言理论可以证明以下两点：形式语言理论可以证明以下两点：（1）G L（G）；文法结构唯一确定语言。）；文法结构唯一确定语言。（2）L(G)G1，G2，Gn；描述一种语言的文法是不唯一的。描述一种语言的文法是不唯一的。例：例：GS S aSb|ab求其所产生的语言。求其所产生的语言。若若S aSb|，如何？如何？L(GS)=anbn|n1L(GS)=anbn|

38、n0已知文法，求语言，通过推导课堂练习课堂练习1：GS S bA A aA|aL(GS)=ban|n1课堂练习课堂练习2：GS S AB A aA|a B bB|bL(GS)=ambn|m,n12.4 语法树的生成和文法的二义性语法树的生成和文法的二义性语法树举例语法树举例已知表达式文法已知表达式文法G2E：E-EE E-E Ea Eb Ec 试问试问-a-bc 是不是是不是L(G2)的句子？若是，请给出该句子的句子？若是，请给出该句子所有可能的语法树；若不是，请说明理由。所有可能的语法树；若不是，请说明理由。已知文法已知文法G G3 3SS：SSaS|SbS|cSd|eS|fSSaS|SbS

39、|cSd|eS|f请证明该文法是二义性文法。请证明该文法是二义性文法。(提示提示:句子句子fbfaffbfaf)二义性举例二义性举例2.5 文法的实用限制文法的实用限制文法的压缩文法的压缩(P30)(P30)1.1.文法不能含有多余产生式：文法不能含有多余产生式：无法推导出终结符号串的产生式。（无用非终结符）无法推导出终结符号串的产生式。（无用非终结符）从开始符号出发的所有推导都不会用到的产生式。从开始符号出发的所有推导都不会用到的产生式。（不可达文法符号）（不可达文法符号）2.文法不能含有有害产生式：文法不能含有有害产生式：UU有关文法的实用限制有关文法的实用限制(P26)1、若文法中有如若

40、文法中有如U U的规则，则这就是的规则，则这就是有害规则有害规则，它会引，它会引起二义性，而无任何用处。起二义性，而无任何用处。例如存在例如存在U U，U a|b,则有两棵语法树：则有两棵语法树：UaUUa文法中不能含有文法中不能含有有害规则有害规则和和多余规则多余规则 2、多余规则多余规则：（1）某条规则）某条规则U u的左部非终结符的左部非终结符U（U不是识别符号），不在任不是识别符号），不在任何其他规则右部出现，即所有的推导始终不会用到此规则。何其他规则右部出现，即所有的推导始终不会用到此规则。（2）在推导句子的过程中，一旦使用了该规则，将推不出任何终结）在推导句子的过程中，一旦使用了该

41、规则，将推不出任何终结符号串。即该规则中含有推不出任何终结符号串的非终结符。符号串。即该规则中含有推不出任何终结符号串的非终结符。例如给定例如给定GS，若其中关于若其中关于U的规则的规则只只有如下一条：有如下一条：U xUy 该规则是多余规则。该规则是多余规则。若还有若还有U a，则此规则则此规则并非多余并非多余若某文法中无有害规则或多余规则，则称该文法是若某文法中无有害规则或多余规则，则称该文法是压缩过的压缩过的。文法文法G1S：SAa|cc AAe|Ca|a CCb Db|Db 文法文法G1S：SAa|cc AAe|Ca|a CCb Db|Db 文法文法G1S：SAa|cc AAe|Ca|

42、a CCb Db|Db 文法压缩举例文法压缩举例 文法文法G2S：SAa|cc AAe|a 文法文法G1S：SAa|cc AAe|Ca|a CCb Db|Db 2.4 文法的实用限制文法的实用限制其它限制其它限制1.文法不能含有空产生式：文法不能含有空产生式：U2.文法不能含有左递归：文法不能含有左递归：UUy2.6.4 分析方法简介分析方法简介1.自上而下分析方法的基本思想自上而下分析方法的基本思想2.自下而上分析方法的基本思想自下而上分析方法的基本思想2.6.4 2.6.4 文法在内存中的表示文法在内存中的表示用链表的结构来表示文法的具体产生式用链表的结构来表示文法的具体产生式每个非终结符的定义图结构如下每个非终结符的定义图结构如下:名字名字右部后继右部后继下一个侯选式下一个侯选式定义定义写成高级语言的结构型数据形式写成高级语言的结构型数据形式 Type struc=boxes;Boxes=record Name:array 1.10 of char;Def:struc;Nexty:struc;Rights:struc;End;第章内容小结第章内容小结 文法的形式定义文法的形式定义 语言的形式定义语言的形式定义 为语言构造文法及由文法生成语言为语言构造文法及由文法生成语言 与语法分析有关的概念与语法分析有关的概念 文法的实用限制文法的实用限制THE ENDTHANKS！