《形式语言理论》PPT课件.ppt

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

1、第二章形式语言理论形式语言Chomsky于1956年提出了一种用来描述语言的数学系统。人们把用一组数学符号和规则来描述语言的方式称为形式描述，而把所用的数学符号和规则称为形式语言。形式语言，只是从语法上研究语言。它是抽象的数学系统，用于模拟程序设计语言的语法，或者是并不很成功地模拟自然语言如英语的语法。形式语言理论是编译理论的重要基础，它主要研究组成符号语言的符号串的集合及它们的表示法、结构与特性。形式语言和编译理论中的最基本概念——符号串和符号串集合2.1字母表和符号串字母表定义:元素的非空有穷集合，记为∑。例：∑={0‚1}Α={a‚b,c}元素也称为符号，字母表也称符号集。程序语言的

2、字母表由字母数字和若干专用符号组成。符号串定义:由字母表中的符号组成的任何有穷序列例：0,00,10是字母表∑={0‚1}上的符号串a,ab,aaca是Α={a‚b,c}上的符号串在符号串中，符号是有顺序的，顺序不同,代表不同的符号串，如:ab和ba不同不含任何符号的符号串称为空串，用ε表示注意:{ε}并不等于空集合{}符号串长度:符号串中含有符号的个数如:

3、abc

4、=3

5、ε

6、=0符号串的运算符号串的连接：设x、y是符号串,它们的连接是把y的符号写在x的符号之后得到的符号串xy例如x="ST"，y="abu"，则xy="STabu"显然εx=xε=x符号串的方幂：把符号串a自身连接n次得到

7、的符号串an=aa…aa例如a1=aa2=aaa0=ε符号串集合：定义:若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。符号串集合的乘积：符号串集合A和B的乘积定义为:AB={xy

8、x∈A且y∈B}，即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=AAAK=AA......A(k个)集合的闭包闭包集合Σ的闭包Σ*定义

9、如下：Σ*=Σ0∪Σ1∪Σ2∪Σ3∪…例：设有字母表Σ={0，1}则Σ*=Σ0∪Σ1∪Σ2∪…={ε,0,1,00,01,10,11,000,…}即Σ*表示Σ上所有有穷长的串的集合。正闭包Σ+=Σ1∪Σ2∪Σ3∪…称为Σ的正闭包。+表示上的除ε外的所有有穷长串的集合自反闭包Σ*=Σ0∪Σ+Σ+=ΣΣ*=Σ*Σ2.2文法和语言1、文法定义:文法G(Grammar)定义为四元组（VN，VT，P，S）VN(Nonternimal)：非终结符集VT(Terminal)：终结符集P(Production)：产生式（规则）集合S：开始符号或识别符号说明:V=VN∪VT，V称为文法G的字母表P中产生

10、式形如：α→β,其中α∈V+且至少含一个非终结符，β∈V*VN,VT和P是非空有穷集VN∩VT=φS是一个非终结符，且至少要在一条产生式的左部出现非终结符代表一个语言中的语法成分，如<赋值语句>，它是构成程序的一个语法成分，这个符号本身不会在程序中出现，而终结符是组成程序的具体的符号。2.推导和规范推导：α→β是文法G的产生式，若有v，w满足：v=γαδ,w=γβδ,其中γ,δ∈V*则称v直接推导出w,也称w直接归约到v,记作vw直接推导就是用产生式的右部替换产生式的左部的过程直接归约就是用产生式的左部替换产生式的右部的过程2、直接推导序列：或+若存在v=u0u1...un=w,

11、(n>0)则称v+w，v推导出w，或w归约到v（至少有1步推导），这个直接推导序列的长度为n。3、广义推导：或*若有v+w或v=w，则记为v*w，v广义推导出w，w广义规约到v（可以包含0步推导）+*三种推导的比较直接推导（）的长度为1直接推导序列（+）的长度n≥1广义推导（*）的长度≥0规范推导与规范规约考虑两种特殊推导：最左推导和最右推导，即对于一个推导序列中的每一步直接推导，都是对最左（最右）非终结符进行替换。最右推导也称规范推导，它的逆过程称为最左规约，也称规范规约。2.3文法的分类Chomsky对文法中的规则施加不同限制，将文法和语言分为四大类：0型文法（PSG

12、）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={S→0AB1B→0B→SA

13、01A1→SB1