下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
编译原理第二章前后文无关文法和语言本章目的为语言的语法描述寻求工具掌握对源程序给出精确无二义(严谨、简洁、易读)的语法描述手段之一---文法熟练使用文法定义程序设计语言的单词和语法成分对形式语言的理论有一个初步基础问题的提出如何描述定义一种语言?如何识别&分析之?用一组数学规则来描述语言的方式:形式描述形式语言本章内容文法和语言的表示文法和语言的定义句型的分析文法的化简和改造文法和语言的Chomsky分类2.1文法和语言的表示“Whatislanguage?”语言是由句子组成的集合,是由一组符号所构成的集合。语言的表示方法:枚举句子制定有限的规则建立一种装置(自动机),以检验/识别句子符号串2.2文法和语言的定义基本概念和术语文法和语言2.2.1基本概念和术语(一)符号:可以相互区别的记号(元素)。字母表:符号(元素)的非空有穷集合。符号串:由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。定义: 1.空符号串ε(没有符号的符号串)是上的符号串2.若x是上的符号串,a是的元素,则xa是上的符号串3.y是上的符号串,当且仅当它可以由1和2导出区分ε,{ε}和2.2.1基本概念和术语(二)前缀:移走符号串s尾部的零个或多于零个符号得到的符号串真前缀后缀:删去符号串s头部的零个或多于零个符号得到的符号串真后缀子串:从s中删去一个前缀和一个后缀得到的符号串2.2.1基本概念和术语(三)符号串的长度:符号串中符号的个数.符号串s的长度记为|s|。ε的长度为0连接:符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy方幂:符号串自身连接n次得到的符号串an定义为aa…aan个aa1=a,a2=aa则a0=ε符号串集合:若集合A中所有元素都是某字母表上的符号串,则称A为字母表上的符号串集合。2.2.1基本概念和术语(四)两个符号串集合A和B的乘积定义为
AB=xy|xA且yB使用*表示上的一切符号串(包括ε)组成的集合。Σ*称为Σ的闭包。上的除ε外的所有符号串组成的集合记为+。Σ+称为Σ的正闭包。2.2.2文法和语言产生语言有限个规则全部句子语言是由句子组成的集合,是由一组符号所构成的集合。换言之,字母表上的一个语言是上的一些符号串的集合(字母表上的每个语言是*的一个子集)产生句子——推导〈句子〉∷=〈主语〉〈谓语〉〈主语〉∷=〈代词〉|〈名词〉〈代词〉∷=我|你|他〈名词〉∷=王明|大学生|工人|英语〈谓语〉∷=〈动词〉〈直接宾语〉〈动词〉∷=是|学习〈直接宾语〉∷=〈代词〉|〈名词〉王明是大学生推导过程〈句子〉〈主语〉〈谓语〉〈名词〉〈谓语〉王明〈谓语〉王明〈动词〉〈直接宾语〉王明是〈直接宾语〉王明是〈名词〉王明是大学生各个概念非终结符(VN)终结符(VT)开始符(S)规则集(P)规则:有序对(U,u)Uu左部变量右部符号串产生式文法定义2.1文法G=(VN,VT,S,P)V=VN∪VT,V:字汇表(词汇表)
VN∩
VT=φ直接推导定义2.2直接推导 β是α的直接推导:文法G=(VT,VN,S,P)α=U,β=, ,∈(VT∪VN)*如果存在产生式U→则称U可直接推出即:U
,或者:αβGG推导定义2.3推导β是α的推导:α=βα=v0v1v2…
vn=β
,n1
+n0:v0
vn;n1:v0
vn句型、句子定义2.4句型,句子
S
,V*,则是句型S
,VT*,则是句子语言定义2.5语言由文法G生成的语言记为L(G),它是文法G的一切句子的集合:
L(G)={x|S
=>
x,其中S为文法的开始符号,且x∈VT*}*例:G:S→0S1,S→a
L(G)={0na1n|n≥0}递归定义2.6若AA,且和不同时为,则为直接递归。为,则为左递归。若A
A,则A是递归的*语言无限的前提条件是:文法是递归的当语言是无限集时,能否用有限的规则来描述呢?递归例子文法G2[E]: EE+T|T TT*F|F F(E)|i直接递归,间接递归语言等价文法与语言之间无一一对应的关系定义2.7若L(G1)=L(G2),则称文法G1和G2是等价的A-产生式左部变量为A的产生式引理2.1:G=(VN,VT,P,S),ABP,
B1,B2,,Bk是P中的全部B-产生式,
G1=(VN,VT,P1,S),
P1是由P中去除AB
添加
A1,
A2,
,
Ak组成的,则L(G)=L(G1)。一些练习E→E+E∣E*E∣(E)│i,推导出:i+i*i试构造产生标识符的文法2.3句型的分析内容:规范推导和规范归约语法树和二义性短语和句柄句型的分析:构造一算法,用以判断所给的符号串是否为某文法的句型(句子)常见分析方法有自顶向下分析和自底向上分析两类2.3.1规范推导和规范归约推导过程可能不唯一例:文法G2[E]: EE+T|T TT*F|F F(E)|i最左推导最右推导规范推导从符号串到符号串的推导序列
*xUyxuy*
总有
xVT*(yVT*)
时,称为最左(右)推导定义:最左(右)推导所得句型称为左(右)句型;最右推导称为规范推导;右句型称为规范句型。并不是每个句型都有最左和最右推导推导过程可能是带回溯的规范归约若归约的每一步都归约的是当前符号串中最左边的某产生式的右部,则称该归约是规范归约(即最左归约)。规范归约是规范推导的逆过程例:符号串i+i*i的归约过程 EE+T|T TT*F|F F(E)|i问题:如何确定当前符号串中可被归约的最左子串?习题试构造一个2型文法G,使得L(G)={a2mbm∣m≥0}2.3.2语法树和二义性树有且仅有一个无任何前驱的结点,称为根(S)除根外,每个结点恰有一个直接前驱对于任一结点m,从根到m可达每个结点的后继是有序的(从左到右)语法树每个结点有一标记X,XV根的标记为S(开始符)若结点X有后继,则XVNA有k个后继,自左至右为X1,X2,…,Xk,则AX1X2…Xk
P二义性存在某个句子具有两棵不同的语法树例:G[E]:EE+E|EE|(E)|i的句子i+ii例:if-then-else二义性文法是有害的措施:修改文法利用附加条件2.3.3短语和句柄EE(1) +T(1)E(2)+T(2)T(3)*F(3)F(1)i例如:句型=E+T*F+i短语,直接短语,最左直接短语句柄定义2.9一个句型的最左直接短语称为此句型的句柄问题:如何确定一规范句型的句柄?句柄应被归约成哪个非终结符?习题请证实G(S):S→SaS∣SbS∣cSd∣eS∣f是一个二义文法
2.4文法的化简和改造无用符号和无用产生式的删除-产生式的消除单产生式的消除无用符号和无用产生式的删除设G=(VN,VT,P,S)是一文法,XVN∪VT,
X称为是有用的,若X至少出现在一个句子的推导过程中,即X满足:(1)存在,V*,有S*X(2)存在wVT*,使X*w否则,称X是无用的。若一产生式含有无用符号,则此产生式称为无用产生式.消除无用产生式(1)算法2.1将文法G=(VN,VT,P,S),
改造为G1=(V’N,VT,P’,S),
使得对于每个XV’N,存在wVT*,满足X*w。(1)置V’N,P’为空(2)对于P中每个产生式A,若(V’N∪VT)*,则将A加入V’N中(3)重复(2),直到V’N不再增大(4)对于每个AP,若(V’N∪VT)*,则置A
于P’中消除无用产生式(2)算法2.2任给文法G=(VN,VT,P,S),构造G’=(V’N,V’T,P’,S’),使x(V’N∪V’T),,(V’N∪V’T)*,有S*x(1)置V’T为空,
V’N={S}(2)对于AP,若AV’N则置中所有非终结符入V’N,所有终结符入V’T
(3)重复(2),直到V’不再增大(4)令P’={A|AP,(V’N∪V’T)*,AV’N}消除无用产生式例例:文法G=({S,U,V,W},{a,b,c},P,S),其中P:SaS|W|UUaVbV|acWaW-产生式的消除(1)先判断文法是否会产生空串算法2.3
任给文法G=(VN,VT,P,S)(1)作集合W1={A|产生式AP}(2)作集合序列
WK+1=WK∪{B|产生式BP,且WK+}(3)重复(2),直到W不再增大可以用来判断一个文法会不会产生空符号串-产生式的消除(2)算法2.4(1)按算法2.3将VN分成两个不相交的集合:W及VN-W(2)设AX1X2…
Xm是P中的任一产生式,按下面的规则将所有形如AY1Y2…
Ym的产生式放入P’中对于一切1im:(i)若XiW,则取Yi=Xi
(ii)若XiW,则分别取Yi为Xi和,将AX1X2…
Xi-1XiXi+1…
Xm和AX1X2…
Xi-1Xi+1…
Xm加入P’-产生式的消除(例1)例:文法G=({S,A,B,C},{a,b,c},P,S),其中P:SaAABCBbB|CcC|-产生式的消除(例2)例:文法G=({S,A,B},{a,b,c},P,S),其中P:ScS|ABAaAb|BBb|问题:S也能推出。解决单产生式的消除例:文法G=({S,A,B},{a,b},P,S),其中P:SAB|A|BAaAb|abBBb|b2.5文法和语言的Chomsky分类四类文法和语言0型文法:若P中任一产生式都有一般形式V+V*且对,不加任何限制,则称G为0型文法(短语结构文法,记为PSG:PhraseStructureGrammar)。由0型文法生成(或者说:定义)的语言称为0型(递归可枚举)语言。它可由图灵(Turing)机识别。1型文法和语言若一0型文法所有产生式具有形式1A2
12
其中,1,2V*V+AVN,则称G为
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 家政行业家居清洁培训总结
- 2025-2030全球合成油田缓蚀剂行业调研及趋势分析报告
- 2025年全球及中国车辆液压制动管路行业头部企业市场占有率及排名调研报告
- 2025年全球及中国流体摄像三脚架云台行业头部企业市场占有率及排名调研报告
- 2025年全球及中国浓缩杏汁行业头部企业市场占有率及排名调研报告
- 2025-2030全球帐篷地钉行业调研及趋势分析报告
- 2025年全球及中国有隔板高效空气过滤器行业头部企业市场占有率及排名调研报告
- 2025年全球及中国个人护理用辛酰甘氨酸行业头部企业市场占有率及排名调研报告
- 2025-2030全球单摆铣头行业调研及趋势分析报告
- 山东省临沂一中高三9月月考语文(文科)试题(含答案)
- 2024-2025年突发紧急事故(急救护理学)基础知识考试题库与答案
- 左心耳封堵术护理
- 2024年部编版八年级语文上册电子课本(高清版)
- 合唱课程课件教学课件
- 2024-2025学年广东省大湾区40校高二上学期联考英语试题(含解析)
- 旅拍店两人合作协议书范文
- 2024-2030年电炒锅项目融资商业计划书
- 技术成熟度评价标准
- 卫生院中医、康复专科建设实施方案-
- 《公有云服务架构与运维》高职全套教学课件
- 2024中华人民共和国农村集体经济组织法详细解读课件
评论
0/150
提交评论