编译原理第02章文法和语言的基本知识

《编译原理第02章文法和语言的基本知识》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章文法和语言的基本知识字母表和符号串文法和语言的形式定义短语、直接短语和句柄语法树和文法的二义性文法和语言的分类2.0概述对程序设计语言的描述是从语法、语义和语用三个因素来考虑。语法是对语言结构的定义。语用则是从使用的角度去描述语言。语义是描述了语言的含义。2.0概述例如赋值语句s＝2*3.1416*r*(r+h)的非形式化的描述为：语法：赋值语句由一个变量，后随一个赋值号“＝”，再在其后面跟一个表达式构成。语义：首先计算语句右部表达式的值，再将结果送给左部变量中。语用：赋值语句可用来计算和保存表达式的值。形式语言理论是用来对程序设计语言三要素进行形式化描述的方法。2.1字母表和符号串元

2、素的非空有穷集合。例如，∑={a,b,c}是字母表1.字母表程序设计语言的字母表∑={x

3、x∈ASCII字符}∑'={0,1}字母表中的元素称为符号或称为字符。例如，前述例子中2.符号（字符）a、b、c是字母表Σ中的符号；0、1是字母表Σ'中的符号。2.1字母表和符号串例如，设有字母表∑={a,b,c}符号的有穷序列称为符号串。符号串总是建立在某个特定字母表上的且只由字母表上的有穷多个符号组成。则有符号串a，b，ab，ba，cba，abc…3.符号串（字）2.1字母表和符号串说明:不包含任何符号的符号串,称为空符号串，用ε表示。符号串中符号的顺序是很重要的。ab和ba是字母表Σ上的两个不同的

4、符号串。空符号串由0个符号组成，其长度

5、ε

6、=02.1字母表和符号串2.2符号串的运算设x和y是符号串，则串xy称为它们的连结。则XY＝abc10a，YX＝10aabc注意：对任意一个符号串x，1.符号串的连结例如，设X＝abc，Y＝10a我们有εx＝xε＝x2.2符号串的运算2.符号串集合的乘积设A和B是符号串的集合,则A和B的乘积定义为：集合的乘积是满足于x∈A,y∈B的所有符号串xy所构成的集合。AB={xy

7、x∈A,y∈B}{}A=A{}=A2.2符号串的运算例如：设A={aa,b},B={c,d}则AB={aac,aad,bc,bd}所以,对任意集合A,有:2.2符号串的运算区

8、分：是符号串,不是集合{}表示由空符号串所组成的集合空集合Φ={}。2.2符号串的运算3.符号串的幂运算设x是符号串,则x的幂运算定义为：x0=x1=xx2=xxx3=xxx…xn=xx…x=xxn-1(n>0)n注意：x0≠12.2符号串的运算例如,设x＝abc则x0=x1=abcx2=xx=abcabc…2.2符号串的运算4.符号串集合的幂运算设A是符号串的集合，则集合A的幂运算定义为：A0={}A1=AA2=AA…An=AA…A=AAn-1(n>0)n2.2符号串的运算例如，设A={a,b}，则A0={}A1=A={a,b}A2=AA={aa,ab,ba,bb}…A3=A

9、AA=A2A={aaa,aab,aba,abb,baa,bab,bba,bbb}2.2符号串的运算5.集合A的正闭包A＋与闭包A*设A是符号串的集合，则A的正闭包A＋和A的闭包A*的定义为:A+=A1∪A2∪…∪An…A*=A0∪A1∪A2∪…∪An…={ε}∪A+2.2符号串的运算例如，设A={a,b},则：A+={a,b,aa,ab,ba,bb,aaa,aab,…}A*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}即：闭包为集合中元素的任意组合。闭包比正闭包多含一个空符号串。2.3文法和语言的形式定义用A表示∑+A→0A→1A→A0A→A1∑+=∑1∪∑2∪∑3∪…={0

10、,1,00,10,11,01,000,100,…}2.3.1文法的形式定义规则是一个符号与一个符号串的有序对（A,β），通常写作：A→β（或A∷＝β)1.规则也称产生式规则的作用是告诉我们如何用规则中的符号串生成语言中的序列。2.3.1文法的形式定义例如，前述例中一组规则描述的语言序列只可能是由0和1组成的符号串。A→0A→1A→A0A→A12.3.1文法的形式定义规则中符号非终结符号：出现在规则左部能派生出符号或符号串的那些符号，用大写字母表示或用尖括号把非终结符号括起来。例如，上例中的A。终结符号：不属于非终结符号的那些符号，通常用小写字母表示。例如，上例中的0和1。2.3.1文法的形式

11、定义规则的非空有穷集合，通常表示成四元组VN是规则中非终结符号的集合。VT是规则中终结符号的集合。P是文法规则的集合。2.文法G={VN,VT,P,S}2.3.1文法的形式定义S是一个非终结符号，称为文法的开始符号或文法的识别符号，它至少要在一条规则中作为左部出现。由它开始，识别出我们所定义的语言。由文法定义可知，文法是对语言结构的定义和描述，文法四大要素中关键是规则的集合。2.3.1文法的形式定义缩写为：A