第2章形式语言概论ppt课件.ppt

《第2章形式语言概论ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章形式语言概论形式语言理论是编译的重要理论基础。本章主要介绍编译理论中用到的有关形式语言理论的最基本概念，重点介绍如何采用形式化的方法描述程序设计语言。第2章形式语言概论字母表和符号串文法和语言的形式定义短语、直接短语和句柄语法树和文法的二义性文法和语言的分类概述对程序设计语言的描述是从语法、语义和语用三个因素来考虑。语法是对语言结构的定义。语用则是从使用的角度去描述语言。语义是描述了语言的含义。概述例如赋值语句s＝2*3.1416*r*(r+h)的非形式化的描述为：语法：赋值语句由一个变量，后随一个

2、赋值号“＝”，再在其后面跟一个表达式构成。语义：首先计算语句右部表达式的值，然后把所得结果送给左部变量中。语用：赋值语句可用来计算和保存表达式的值。概述这种非形式化的描述,不够清晰和准确,为了精确定义和描述程序设计语言,需采用形式化的方法。所谓形式化的方法,是用一整套带有严格规定的符号体系来描述问题的方法。形式语言理论是编译的重要理论基础。重点介绍如何采用形式化的方法描述程序设计语言。字母表和符号串元素的非空有穷集合。例如，∑={a,b,c}1.字母表根据字母表的定义，Σ是字母表，它由a、b、c三个元素组

3、成。字母表和符号串是一个字母表，由0、1两个元素组成。注意:例如，∑'={0,1}(2)字母表中的元素,可以是字母、数字或其他符号。(1)字母表中至少包含一个元素。字母表和符号串字母表中的元素称为符号或称为字符。例如，前述例子中2.符号（字符）a、b、c是字母表Σ中的符号；0、1是字母表Σ'中的符号。字母表和符号串例如，设有字母表∑={a,b,c}符号的有穷序列称为符号串。符号串总是建立在某个特定字母表上的且只由字母表上的有穷多个符号组成。则有符号串a，b，ab，ba，cba，abc…3.符号串（字）字母

4、表和符号串说明:不包含任何符号的符号串,称为空符号串，用ε表示。符号串中符号的顺序是很重要的。ab和ba是字母表Σ上的两个不同的符号串。空符号串由0个符号组成，其长度

5、ε

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

7、y

8、x∈A,y∈B}{}A=A{}=A符号串的运算例如：设A={a,b},B={c,d}则AB={ac,ad,bc,bd}由于对任意的符号串x，总有x=x=x所以,对任意集合A,我们有:符号串的运算特别指出的是，是符号串,不是集合，而{}表示由空符号串所组成的集合,但这样的集合不是空集合Φ={}。符号串的运算3.符号串的幂运算设x是符号串,则x的幂运算定义为：x0=x1=xx2=xxx3=xxx…xn=xx…x=xxn-1(n>0)n注意：x0≠1符号串的运算例如,设x＝abc则x0=x

9、1=abcx2=xx=abcabc…符号串的运算4.集合的幂运算设A是符号串的集合，则集合A的幂运算定义为：A0={}A1=AA2=AA…An=AA…A=AAn-1(n>0)n符号串的运算例如，设A={a,b}，则A0={}A1=A={a,b}A2=AA={aa,ab,ba,bb}…A3=AAA=A2A={aaa,aab,aba,abb,baa,bab,bba,bbb}符号串的运算5.集合A的正闭包A＋与闭包A*设A是符号串的集合，则A的正闭包A＋和A的闭包A*的定义为:A+=A1∪A2∪…∪An…A

10、*=A0∪A1∪A2∪…∪An…={ε}∪A+符号串的运算可见,集合A的正闭包表示A上元素a,b构成的所有符号串的集合,集合A的闭包比集合A的正闭包多含一个空符号串。例如，设A={a,b},则：A+={a,b,aa,ab,ba,bb,aaa,aab,…}A*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}文法和语言的形式定义每个形式语言都是某个字母表上按某种规则构成的所有符号串的集合。反之，任何一个字母表上符号串的集合均可定义为一个形式语言。形式语言序列的集合称为形式语言。文法和语言的形式定

11、义对每个具体语言,都有语法和语义两个方面，形式语言是指不考虑语言的具体意义，即不考虑语义。文法和语言的形式定义形式语言的描述对形式语言的描述有两种方法，一种方法是当语言为有穷集合时，用枚举法来表示语言。文法和语言的形式定义均表示字母表A上的一个形式语言。由于这三个语言均是有限符号串的集合，因此，可枚举出其全部句子来表示该语言。例如，设有字母表A={a,b,c}，则L1={a,b,c}L2={a,aa,ab,ac}L3={c,c