《形式语言理论》PPT课件.ppt
《《形式语言理论》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《形式语言理论》PPT课件.ppt(49页珍藏版)》请在三一办公上搜索。
1、第二章 形式语言理论,形式语言,Chomsky于1956年提出了一种用来描述语言的数学系统。人们把用一组数学符号和规则来描述语言的方式称为形式描述,而把所用的数学符号和规则称为形式语言。形式语言,只是从语法上研究语言。它是抽象的数学系统,用于模拟程序设计语言的语法,或者是并不很成功地模拟自然语言如英语的语法。形式语言理论是编译理论的重要基础,它主要研究组成符号语言的符号串的集合及它们的表示法、结构与特性。,形式语言和编译理论中的最基本概念符号串和符号串集合,2.1字母表和符号串,字母表定义:元素的非空有穷集合,记为。例:=01=ab,c元素也称为符号,字母表也称符号集。程序语言的字母表由字母数
2、字和若干专用符号组成。,符号串定义:由字母表中的符号组成的任何有穷序列 例:0,00,10是字母表=01上的符号串 a,ab,aaca是=ab,c上的符号串在符号串中,符号是有顺序的,顺序不同,代表不同的符号串,如:ab和ba不同不含任何符号的符号串称为空串,用表示注意:并不等于空集合 符号串长度:符号串中含有符号的个数如:|abc|=3|=0,符号串的运算符号串的连接:设x、y是符号串,它们的连接是把y的符号写在 x的符号之后得到的符号串xy 例如 x=ST,y=abu,则 xy=STabu 显然x=x=x符号串的方幂:把符号串a自身连接n次得到的符号串an=aaaa例如 a1=a a2=a
3、a a0=,符号串集合:定义:若集合A中所有元素都是某字母表上的符号串,则称A为字母表上的符号串集合。符号串集合的乘积:符号串集合A和B的乘积定义为:AB=xy|xA且yB,即AB是由A中的串x和B中的串y连接而成的串xy组成的集合。若集合A=ab,cde B=0,1 则 AB=ab0,ab1,cde0,cde1 显然 A=A=A,符号串集合的方幂:设A是符号串的集合,则称Ai为符号串集A的方幂,其中i是非负整数。具体定义如下:A0=A1=A,A2=A AAK=AA.A(k个),集合的闭包闭包集合的闭包*定义如下:*=0 1 2 3例:设有字母表=0,1则*=012=,0,1,00,01,10
4、,11,000,即*表示上所有有穷长的串的集合。,正闭包+=123称为的正闭包。+表示上的除外的所有有穷长串的集合自反闭包*=0+=*=*,2.2文法和语言,1、文法定义:文法G(Grammar)定义为四元组(VN,VT,P,S)VN(Nonternimal):非终结符集VT(Terminal):终结符集P(Production):产生式(规则)集合S:开始符号或识别符号,说明:V=VNVT,V称为文法G的字母表P中产生式形如:,其中V+且至少含一个非终结符,V*VN,VT和P是非空有穷集VNVT=S是一个非终结符,且至少要在一条产生式的左部出现非终结符代表一个语言中的语法成分,如,它是构成程
5、序的一个语法成分,这个符号本身不会在程序中出现,而终结符是组成程序的具体的符号。,2.推导和规范推导:是文法G的产生式,若有v,w满足:v=,w=,其中,V*则称v直接推导出w,也称w直接归约到v,记作 v w直接推导就是用产生式的右部替换产生式的左部的过程直接归约就是用产生式的左部替换产生式的右部的过程,2、直接推导序列:或+若存在v=u0 u1.un=w,(n0)则称v+w,v推导出w,或w归约到v(至少有1步推导),这个直接推导序列的长度为n。3、广义推导:或*若有v+w 或 v=w,则记为v*w,v广义推导出w,w广义规约到v(可以包含0步推导),+,*,三种推导的比较,直接推导()的
6、长度为1直接推导序列(+)的长度n1广义推导(*)的长度0,规范推导与规范规约,考虑两种特殊推导:最左推导和最右推导,即 对于一个推导序列中的每一步直接推导,都是对最左(最右)非终结符进行替换。最右推导也称规范推导,它的逆过程称为最左规约,也称规范规约。,2.3 文法的分类,Chomsky对文法中的规则施加不同限制,将文法和语言分为四大类:0型文法(PSG)0型语言或短语结构语言1型文法(CSG)1型语言或上下文有关语言2型文法(CFG)2型语言或上下文无关语言3型文法(RG)3型语言或正则(正规)语言,如果对于某文法G,P中每个规则具有下列形式:其中V+,V*,则该文法G为(Chomsky)
7、0型文法或短语结构文法。相应的语言 称为0型语言或短语结构语言。如文法G,其中VN=A,B,S VT=0,1 P=S0AB 1B0 BSA|01 A1SB1 A0S0B,0型文法,1型文法(上下文有关)它是0型文法的特例,对P中的任一产生式,都有|1,仅仅 S除外,但S不得出现在任何产生式的右部。例 文法GS:SaSBE SaBEEBBEaBab bBbb bEbe eEee1型文法产生式的一般形式是 A,,V*,AVN,V,它表示当A的上文为且下文为时可把A替换成,因此称1型文法为上下文有关文法。,2型文法(上下文无关文法)它是1型文法的特例,对任一产生式,都有VN,(VNVT)*例 文法G
8、S:SAB ABS|0 BSA|12型文法产生式的一般形式是:A,它表示不管A的上下文如何都可把A替换成,因此被称为上下文无关文法。通常程序设计语言的文法,可用2型文法来描述,因此我们重点研究2型文法。,3型文法(右线性文法和正规文法)它是2型文法的特例,任一产生式的形式都为 AaB或Aa,其中A,BVN,aVT*在正规文法中,任一产生式的形式都为 AaB或Aa,其中A,BVN,aVT 例如 文法GS:S0A|1B|0A0A|1B|0SB1B|1|0在程序设计语言中,正规文法通常用来描述单词的结构。,四种文法之间的逐级“包含”关系,2.4语言和语法,1、句型和句子设有文法GS,若符号串是从开始
9、符推导出来的,即 S=*,则称是文法G的句型。若仅由终结符组成,即 S=*,且VT*,则称是文法G的句子。例 文法GS:S0S1,S01因为S 0S1 00S11 000S111 00001111所以S,0S1,00S11,000S111,00001111都是G的句型,00001111是G的句子由规范推导所得的句型称为规范句型,2、语言的定义由文法G生成的语言记为L(G),它是文法G的一切句子的集合,即 L(G)=x|S=*x,且 xVT*例 文法G:S0S1,S01S0S1 00S11 03S13 0n-1S1n-1 0n1nL(G)=0n1n|n13、文法和语言的关系:文法G生成的每个终结
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 形式语言理论 形式语言 理论 PPT 课件
链接地址:https://www.31ppt.com/p-5507629.html