第二章形式语言理论.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
3、自身连接n次得到的符号串an = aaaa 例如 a1=a a2=aa 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 A AK = AAA(k
4、个),集合的闭包 闭包 集合的闭包 *定义如下: * = 0 1 2 3 例:设有字母表=0,1 则*=012 =,0,1,00,01,10,11,000, 即*表示上所有有穷长的串的集合。,正闭包 + = 123称为的正闭包。 + 表示上的除外的所有有穷长串的集合 自反闭包* = 0+ + = * = * ,2.2文法和语言,1、文法定义: 文法G(Grammar)定义为四元组(VN,VT,P,S) VN (Nonternimal):非终结符集 VT (Terminal):终结符集 P (Production):产生式(规则)集合 S:开始符号或识别符号,说明: V=VNVT,V称为文法G的
5、字母表 P中产生式形如:,其中V+且至少含一个非终结符,V* VN,VT和P是非空有穷集 VNVT= S是一个非终结符,且至少要在一条产生式的左部出现 非终结符代表一个语言中的语法成分,如,它是构成程序的一个语法成分,这个符号本身不会在程序中出现,而终结符是组成程序的具体的符号。,2. 推导和规范推导: 是文法G的产生式,若有v,w满足: v=,w=, 其中,V* 则称v直接推导出w,也称w直接归约到v, 记作 v w 直接推导就是用产生式的右部替换产生式的左部的过程 直接归约就是用产生式的左部替换产生式的右部的过程,2、直接推导序列: 或 + 若存在v =u0 u1 . un=w, (n0)
6、 则称v + w,v推导出w,或w归约到v(至少有1步推导),这个直接推导序列的长度为n。 3、广义推导: 或 * 若有v + w 或 v=w, 则记为v * w,v广义推导出w,w广义规约到v(可以包含0步推导),+ ,* ,三种推导的比较,直接推导()的长度为1 直接推导序列( +)的长度n1 广义推导( *)的长度0,规范推导与规范规约,考虑两种特殊推导:最左推导和最右推导,即 对于一个推导序列中的每一步直接推导,都是对最左(最右)非终结符进行替换。 最右推导也称规范推导,它的逆过程称为最左规约,也称规范规约。,2.3 文法的分类,Chomsky对文法中的规则施加不同限制,将文法和语言分
7、为四大类: 0型文法(PSG) 0型语言或短语结构语言 1型文法(CSG) 1型语言或上下文有关语言 2型文法(CFG) 2型语言或上下文无关语言 3型文法(RG)3型语言或正则(正规)语言,如果对于某文法G,P中每个规则具有下列形式: 其中V+ , V*,则该文法G为(Chomsky)0型文法或短语结构文法。相应的语言 称为0型语言或短语结构语言。 如文法G,其中VN=A,B,S VT=0,1 P= S0AB 1B0 BSA|01 A1SB1 A0S0B ,0型文法,1型文法(上下文有关) 它是0型文法的特例, 对P中的任一产生式,都有| 1, 仅仅 S除外,但S不得出现在任何产生式的右部。
8、 例 文法GS: SaSBE SaBE EBBE aBab bBbb bEbe eEee 1型文法产生式的一般形式是 A, , V* ,AVN , V ,它表示当A的上文为且下文为时可把A替换成,因此称1型文法为上下文有关文法。,2型文法(上下文无关文法) 它是1型文法的特例,对任一产生式,都有 VN , (VNVT)* 例 文法GS: SAB ABS|0 BSA|1 2型文法产生式的一般形式是: A,它表示不管A的上下文如何都可把A替换成,因此被称为上下文无关文法。 通常程序设计语言的文法,可用2型文法来描述,因此我们重点研究2型文法。,3型文法(右线性文法和正规文法) 它是2型文法的特例,
9、任一产生式的形式都为 AaB或 Aa,其中A ,BVN ,aVT * 在正规文法中,任一产生式的形式都为 AaB或 Aa,其中A ,BVN ,aVT 例如 文法GS: S0A|1B|0 A0A|1B|0S B1B|1|0 在程序设计语言中,正规文法通常用来描述单词的结构。,四种文法之间的逐级“包含”关系,2.4语言和语法,1、句型和句子 设有文法GS,若符号串是从开始符推导出来的,即 S =* ,则称是文法G的句型。若仅由终结符组成,即 S =* ,且VT*,则称是文法G的句子。 例 文法GS: S0S1, S01 因为S 0S1 00S11 000S111 00001111 所以S,0S1
10、,00S11 ,000S111,00001111都是G的句型,00001111是G的句子 由规范推导所得的句型称为规范句型,2、语言的定义 由文法G生成的语言记为L(G),它是文法G的一切句子的集合,即 L(G)=x|S =* x,且 xVT* 例 文法G: S0S1, S01 S0S1 00S11 03S13 0n-1S1n-1 0n1n L(G)=0n1n|n1 3、文法和语言的关系: 文法G生成的每个终结符号串都在L(G)中 L(G)中的每个串确实能被G生成,2. 语法树,1、定义:语法树是这样的一个语法结构,它的结点由符号组成。根结点对应于开始符号。只有非终结符号对应的结点有子结点。并
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第二 形式语言 理论
链接地址:https://www.31doc.com/p-2260174.html