2文法和语言.ppt

《2文法和语言.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章文法和语言本章内容2.1字母表和符号串基本概念和术语2.2文法和语言的形式定义2.3语法树和二义性2.4文法的类型3前言编译过程是十分复杂的信息加工过程，加工对象是用高级语言编写的程序。为完成编译工作，需解决两个问题：如何确切地描述和定义一种程序设计语言如何识别和分析这种语言用一组数学符号和规则来描述语言的方式称为形式描述，把所用的数学符号和规则称为形式语言。2.1字母表和符号串基本概念和术语定义字母表（符号表或符号集）字母表是符号的非空有穷集合。字母表中的元素称为符号任何程序语言都有自己的字母表例如:计算机语言：由符号“0”和“1”组成的字母表,∑={0，1}。Pascal字母表为

2、：∑={AZ,az,09,+,-,*,/,<,=,>,:,,,；，.，,(,),{,},[,]}42.1字母表和符号串基本概念和术语定义符号串符号表中的符号所组成的任何有穷序列。例如：Σ={a,b}ε,a,b,aa,ab,aabba…都是上的符号串通常使用小写字母表示符号串如：x=aabb52.1字母表和符号串基本概念和术语定义符号串的递归定义：（1）字母表Σ上的字符是Σ上的符号串；（2）若x是Σ上的符号串，且a∈Σ，则xa或ax是Σ上的符号串；（3）y是Σ上的符号串，当且仅当y可由(1)和(2)产生。注意：串中字符的有序性62.1字母表和符号串基本概念和术语定义符号串的长度

3、如果某符号串ω中有m个符号，则称其长度为m，记为

4、ω

5、=m例：aba的长度为3。记为：

6、aba

7、=3空串不含任何符号的符号串，记为72.1字母表和符号串基本概念和术语定义设ω是符号串前缀：移走ω的尾部的零个或多于零个符号后的剩余部分称为s的前缀。后缀：移走ω的头部的零个或多于零个符号后的剩余部分。真前缀(真后缀)：若ω的前缀(后缀)不是ω自身则称其为ω的真前缀(真后缀)。子串:从ω中删去一个前缀和一个后缀后的剩余部分则称该符号串的子串。例：符号串s=banana前缀：,b,ba,ban,bana,banan,banana后缀：banana,anana,nana,ana,na,a,子串

8、:banana,anana,banan,anan,…,长度：banana=69符号串的运算定义连接：设x和y是两个符号串，如果将符号串y直接拼接在符号串x之后，则称此操作为符号串x和y的连接，记作xy。例：x=ba,y=nana,xy=banana注意：一般情况下xy≠yx10符号串的运算定义2.62.方幂：设ω是某字母表上符号串，把ω自身连接n次得到符号串z，即v=ωω…ω(n个ω)，称v是符号串ω的n次幂，记作v=ωn。设ω是符号串，则ω0=εω1=ωω2=ωω…ωn=ωω…ω例：x=bax1=ba,x2=baba,x3=bababa,…...11符号串的运算符号串集合：若集合A

9、中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。例：Σ={0,1}A=｛0，1，00，11｝是Σ上的符号串集合注意区分：ε,{ε},{}符号串集合(语言）的运算定义：符号串集合的乘积设A、B是两个符号串集合，AB表示A与B的乘积，则有定义AB={xy

10、(x∈A)∧(y∈B)}例：设A={ab,c},B={d,ef},则AB={abd,abef,cd,cef}注意：{ε}A=A{ε}∅A=A∅13=∅=A符号串集合(语言）的运算定义(符号串集合的方幂)设A是符号串集合，A自身的乘积可以用方幂表示。则有定义设A为字符串集：A0={ε}A1=AA2=AAA3=A2A=AAA…

11、…An=An-1A=AA…A(n个A)显然有：Ai+j=AiAj14符号串集合(语言）的运算符号串集合的方幂例：A={0,1}则A0={ε}A1＝{0,1}A2＝{00,01,10,11}A3＝{000,001,010,011,100,101,110,111}练习：P={ab,x,aby}，则P2=？=PP={abab,abx,ababy,xab,xx,xaby,abyab,abyx,abyaby}15符号串集合(语言）的运算(符号串集合的并)设P、Q为字符串集，集合P∪Q为P和Q的并，它的元素是P或Q中的元素。练习：P={0,1,01}，Q={0,10,11,00},则P∪Q=？P∪Q=

12、{0,1,01,10,11,00}16符号串集合(语言）的运算定义(符号串集合的闭包)设A为符号串集，A的正闭包记作A+，则有A+=A1∪A2∪…∪An∪…A的自反闭包记作A*，则有A*=A0∪A+={ε}∪A+=A+∪{ε}由定义知，A+=AA*A*=A0∪A+17例如，设有A={01,10}，则A*={ε，01，10，0101，0110，1001,1010,010101，010110,…}A+={01，10，0101