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

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

1、1学习本章的目的构造编译程序的算法是从研究源程序及目标程序产生的，首先找到源语言的形式描述，根据这种描述，构造出相应的分析加工程序。语言分语法，语义和语用。程序语言语法的形式描述是很好用的，语义的形式描述不那么好用，但它推动语言理论的发展。2一、字母表字母表是元素的非空有穷集合。任何程序语言都有自己的字母表，例如:1.计算机语言：由符号“0”和“1”组成的字母表,∑={0，1}2.ASCII字符集；3.Pascal字母表为：∑={AZ,az,09,+,-,*,/,<,=,>,:,',',;，.，,(,),{,},[,]}

2、4.字母表中的元素称为符号,例如,26个英文字母中的元素a、b、c等称为符号.2.1字母表和符号串3二.符号串的定义(1)ε是∑上的一个空符号串。(2)若x是∑上的符号串，而a是∑的元素,则xa是∑上的符号串。(3)y是∑上的符号串,当且仅当它由(1)和(2)导出。由字母表中的符号所组成的的任何有穷序列被称之为该字母表上的符号串,也称作"字"。2.1字母表和符号串4设s是符号串前缀：移走s的尾部的零个或多于零个符号后缀：删去s的头部的零个或多于零个符号子串:从s中删去一个前缀和一个后缀子序列:从s中删去零个或多于零个符号(这些符

3、号不要求是连续的）逆转（用SR表示）：将S中的符号按相反次序写出而得到的符号串。长度：是该符号串中的符号的个数。例如

4、aab

5、=3,

6、ε

7、=0。三术语5例：符号串s=banana前缀：,b,ba,ban,bana,banan,banana后缀：banana,anana,nana,ana,na,a,子串:banana,anana,banan,anan,…,真前缀，真后缀，真子串:x≠sx≠子序列:baa(这些符号不要求是连续的）逆转（用SR表示）：ananab长度：banana=661.连接：设x和y是符号串，它们

8、的连接xy是把y的符号写在x的符号之后得到的符号串。例如，x=ba,y=nana,xy=banana.2.方幂：x0=;x1=x;x2=xx;……;xn=xn-1x;例如,x=ba,x1=ba,x2=baba,x3=bababa,…...四.符号串的运算73.乘积.设A和B是符号串，AB表示A与B乘积,则定义AB={xy

9、x∈A,y∈B}如,设A={ab,c},B={d,efg},则AB={abd,abefg,cd,cefg}特别有{}A=A{}=A,8设L和M是两个符号串集合，则4.合并：L∪M＝｛s

10、sLorsM}

11、5.语言L的自反闭包，记作L*，L*是L各种连接全部包含起来.规定:L0={ε}L*＝∪Li(i>=0)={ε}∪L+=L0∪L1∪L2∪L3∪…6．语言L的正闭包，记作L+（L+＝LL*）L+＝∪Li(i>=1)=L1∪L2∪L3∪L4∪…四.符号串集合(语言）的运算9用*表示上的一切符号串（包括ε）组成的集合。Σ*称为Σ的闭包。上的除ε外的所有符号串组成的集合记为+。Σ+称为Σ的正闭包。例：Σ={a,b}Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,a

12、ab,…}10如：L={A~Z,a~z}D={0~9}1．L∪D={A~Z,a~z,0~9}2．LD是由所有用一个字母后跟一个数字组成的符号串构成的集合。3．L4是由所有的四个字母的符号串构的集合。4．L（L∪D)*是由所有的字母打头的字母和数字组成的符号串所构成的集合.5．D+是由所有的长度大于等于1的数字串所构成的集合.例11文法和语言的形式定义文法是描述语言的语法结构的形式规则.用数学方式表达出来.如何来描述一种语言？如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示.如果语言是无穷的，找出语言的有穷表示。语

13、言的有穷表示有两个途经：生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造。识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，（要么永远继续下去。）12文法即是生成方式描述语言的：语言中的每个句子可以用严格定义的规则来构造.下面给出文法的定义.进而在文法的定义的基础上,给出推导的概念,句型、句子和语言的定义.13定义一个上下文无关文法,G=（VT，VNS,P），其中：且VT∩VN＝Φ；VT是一个非空有穷终结符号集合；VN是一个非空有

14、穷的非终结符号集合;SVN，称为开始符号。P是一个产生式的非空有穷集合，每个产生式是一个序偶对(α,β),其中α∈V+，β∈V*。其形式是αβ(或α::＝β)α::=γα称产生式的左部;β称产生式的右部。产生式被称重写规则,即能将一个符串用另一个符号串替换.