




已阅读5页,还剩53页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第*章 编译基础-形式语言,第一节 字母表、串、语言,1 字母表:有穷非空字符集,语言允许使用的字符集可识别符号,例: =a-z,A-Z,0-9,+,_,*,/,/(,),=.,2 字符串:字母表中符号组成的任何有穷序列单词,例:scanf,int,3.1415,x1,100,a,3 字符串运算: A、B为字符串集合 x,y为字符串,连接: xy 称为x和y的连接 例:int x x=100,积:AB=xy/x A,而y B,闭包:A*=A0 A1 A2. An 其中: A0= , Ai= Ai-1 A A+= A*- ,A+中的每一个元素即为一个语句 例: x=3.14159*r*r,形式语言是一个字母表上按某种规则构成的所有串的集合。在语言中这些串称为句子。,对于一个句子,存在两个过程: 读-识别过程-编译的过程 写-推导过程-书写源程序,第二节 文法的引例,句子:I am a teach.,I,am,a,teacher,am,a,teacher, i,第三节 文法的形式定义,一、几个概念,1、非终结符语法变量,2、终结符单词,3、产生式规则,二、文法的定义,文法是一个四元组,表示为: G=(VN,VT,P,S),其中: VN -非终结符 VT -终结符 P-产生式 S-开始符号,P: V+ , V* V=VN VT,例:描述系表结构的文法,其形式描述为G=(VN,VT,P,S),VN = VT =I,am ,a ,teacher S= ,am,a,teacher ,P=,i,再给出一个描述算术表达式的文法例子,p=EE+T|T TT*F|F F(E)|a ,文法G(E):G=(VN,VT,P,S),VN =E,T,F VT =+,*,(,),a S= E,* 句型:S= , V* 为句型 例: I am ,* 句子:S= w, w VT* w为句子 例:Iam a teacher,* 语言:L=w/w w VT* , 且S=w 例:I am a teacher,推导的定义,若存在v w0 w1 . wn=w(n0) 则记为v =+ w,v推导出w,或w归约到v,若有v =+ w,或v=w, 则记为v =* w,例:GE: EE+T|T TT*F|F F(E)|a,EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a,句子:用符号a,+,*,(和)构成的算术表达式,通过对产生式施加不同的限制,Chomsky将文法分为四种类型:,0型文法:对任一产生式,都有 (VNVT)+, (VNVT)*,1型文法:对任一产生式,都有|, 仅仅 S除外,2型文法:对任一产生式A,都有AVN , (VNVT)*,3型文法:任一产生式A的形式都为AaB或 Aa,其中AVN ,BVN ,aVT,文法分类:,文法的类型,自然语言属于上下文有关文法,例:1型(上下文有关)文法 文法GS: SCD AbbA CaCA BaaB CbCB BbbB ADaD C BDbD D AabD,文法的类型,是语法分析的基础,例:2型(上下文无关)文法 文法GS: SAB ABS|0 BSA|1,3型文法,GS: S0A|1B|0 A0A|1B|0S B1B|1|0,GI: I lT I l T lT T dT T l T d,是词法分析的基础,文法的类型,四种文法之间的逐级“包含”关系,0型文法,1型文法,2型文法,3型文法,文法和语言,0型文法产生的语言称为0型语言,1型文法或上下文有关文法( CSG )产生的语言称为1型语言或上下文有关语言(CSL),2型文法或上下文无关文法( CFG )产生的语言称为2型语言或上下文无关语言( CF L ),3型文法或正则(正规)文法( RG )产生的语言称为3型语言正则(正规)语言( RL ),根据形式语言理论,文法和识别系统间有这样的关系,0型文法(短语结构文法)的能力相当于图灵机,可以表征任何递归可枚举集,而且任何0型语言都是递归可枚举的 1型文法(上下文有关文法):产生式的形式为1A212,即只有A出现在1和2的上下文中时,才允许取代A。其识别系统是线性界限自动机。,带 a0 a1 a2 a3 a4 a5 a6 a7 a8 an-1 an,有限控制器,磁头,任何能用图灵机描述的计算都能机械实现,任何能在现代计算机上实现的计算都能用图灵机描述,2型文法(上下文无关文法CFG):产生式的形式为A,取代A时与A的上下文无关。其识别系统是不确定的下推自动机。 3型文法(正规文法RG):产生的语言是有穷自动机(FA)所接受的集合,第五节 正规方法与有穷自动机,一、正规文法,例:文法 G=(VN,VT,P,S) 其中: VN=A,B,C VT=a,b,c S=A P:A aB A aA B bB B bC C cC C c,L(G)=ambncp/m,n,p1,A=aA=aaA=aaaB =aaabB=aaabbbC =aaabbbcC= aaabbbccC = aaabbbccc,最小句子:abc,P:A aB A aA B bB B bC C cC C c,例:写出产生语言L(G)=ambcn/m,n0的正规文法,解:文法 G=(VN,VT,P,S) 其中: VN=A,S VT=a,b S=S P:,最小语言:b,S aS,S b,S bA,A cA,Ac,例:C语言标识符的文法描述 L(G)=w/w为字母或-打头的字母数字串,解:P:,IaB I -B,B aB B dB Ba B d,I a,二、有穷自动机 1。特点:接收离散输入,状态有穷,只需考虑当前输入和当前内部状态,2、原理:有穷自动机控制器读头自左向右逐个扫描并读入输入符号,并且根据控制器的当前状态和当前输入符号控制转入下一个状态,、模型,Main ( ) int I , j , k ;,有穷控制器,例:电梯:当前状态(五楼,向上) 当前输入(二楼,向下),、表示状态图,I,B,T,T,a,-,a,d,其它,例:C语言的标识符,、形式定义 确定的有穷自动机是一个五元组 M=(Q, , ,q0,Z),其中:Q是一有穷状态集,是有穷输入字母表,是Qx Q的映射函数 其含义: ( q1,a)= q2,q0 Q,唯一的初态,Z是的子集,是终态集,例:奇偶测试器,q0,0,q1,1,q1,0,1,自动机:(Q, , ,q0,Z) Q q0, q1 =0,1 q0=q0 Z=q1,映射函数: ( q,)= q ( q,)= q ( q1,)= q ( q1,)= q,例:,三、正规表达式与有穷自动机 关系:等价、交换,文法 G=(VN,VT,P,S)和 自动机 M=(Q, , ,q0,Z),可转换为: VN 为终态 q0 VT ,,S若 ,映射函数: 、: a2 , 则( ,a)= A2 2、: a, 则( ,a)= T 3、( ,a)= 空动作,例:已知正规文法 (A,B,C,a,b,c,P,S 其中: P:A aA A aB B bB B bC C cC Cc 试写出与其等价的,解:(A,B,C,a,b,c, ,S,T),A,B,C,T,a,a,b,b,c,c,映射函数: ( A,a)= A ( A,a)= B (B,b)= B (B,b)= C (C,c)= C (C,c)= T,练习:w/w是和的个数都为偶数的、串 试写出能识别该语言的自动机和描述该语言的文法,第六节 上下文无关文法语法基础,一、上下文无关文法 文法 G=(VN,VT,P,S) : A ( VN VT),例:anbn/n 1 P: S aSb S ab,二、自嵌套性 如果上下文无关文法中存在一个终结符,且 ( , 不空),称该上下文无关文法具有可嵌套性,自嵌套性是上下文无关文法与正规文法的本质区别,例:wcwr/w (a |b), wr是w的反置 P: S aSa S bSb S c,句子abbacabba,三、下推自动机,、模型,输入带,有穷 控制器,下推栈,、操作,、接收,b.空动作 ( q, ,Z)= (q1, ),A、读入输入符号,替换栈顶,改变状 态,读头右移 ( q,a,Z)= (q1, ),空栈:输入串空,栈内也空,终态:规定终态,导致进入终态的串被 认为接收。此时,栈内可能工不 空,、定义 是一个七元组, M=(Q, , ,q0, 0 , ),是有穷输入字母表;,其中:Q是一有穷状态集,是下推字母表,是Qx()x Q x*的映射函 数, 其含义: ( q1,a,Z)= (q2, ),q0 Q,唯一的初态;,F是的子集,是终态集,0 是栈底符号,例:wcwr/w (a |b), wr是w的反置,写出识别该语言的,解:M=(Q, , ,q0, 0 , ) Q q0, q, q a,b; =Z0, q0 q0 0 =0,映射函数: ( q0,a,Z0)= (q1, AZ0),( q0,b,Z0)= (q1, BZ0) ( q1,a,A)= (q1, AA),( q1,a,B)= (q1, AB) ( q1,b,A)= (q1, BA),( q1,b,B)= (q1, BB) ( q1,c,A)= (q2, A),( q1,c,B)= (q2, B) ( q2,a,A)= (q2, ),( q2,b,B)= (q2, ) ( q2, , Z0)= (q0, ),( q0, c, Z0)= (q0, ),句型、推导,EE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a,GE: EE+T|T TT*F|F F(E)|a,EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a,EE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*a,对于句子a+a*a 有不同的推导,规范推导 规范句型,最左(最右)推导:在推导的任何一步,其中、是句型,都是对中的最左(右)非终结符进行替换 最右推导被称为规范推导。 由规范推导所得的句型称为规范句型,语法树,设G=( VN,VT,P,S)为一cfg,若一棵树满足下列4个条件,则此树称作G的语法树(推导树)(派生树):,1. 每个内结点都有一个标记,此标记是VN的一个符号,2. 根的标记是S,3. 若一结点n至少有一个它自己除外的子孙,并且有标记A,则肯定AVN,4. 如果结点n有标记A,其直接子孙结点从左到右的次序是n1,n2,nk,其标记分别为A1,A2,Ak,那么AA1A2,Ak一定是P中的一个产生式,语法树-句型推导的直观表示,给定文法G=(VN,VT,P,S),对于G的任何句型都能构造与之关联的语法树(推导树),语法树的结果:,从左到右读出叶子的标记所构成的符号串称为句子,构造语法树,EE+T,GE: EE+T|T TT*F|F F(E)|a,T+T,F+T,a+T,a+T*F,a+F*F,a+a*F,a+a*a,E,E,+,T,a+a*a,T,F,a,T,*,F,F,a,a,语法树看不出推导顺序,上下文无关文法的语法树的用处,用于描述上下文无关文法句型推导的直观方法,例: GS: SaAS ASbA ASS Sa Aba,S a A S S b A a a b a,句型aabbaa的语法树(推导树),叶子结点:树中没有子孙的结点。 从左到右读出推导树的叶子标记连接成的文法符号串,为GS的句型。也把该推导树称为该句型的语法树。,但是,一个句型是否只对应唯一的一棵语法树呢?一个句型是否只有唯一的一个最左(最右)推导呢?,一棵语法树表示了一个句型的种种可能的(但未必是所有的)不同推导过程.,例:GE: E i E E+E E E*E E (E),E E + E E * E i i i,E E * E i E + E i i,句型 i*i+i 的两个不同的最左推导:,推导2:E E*E i*E i*E+E i*i+E i*i+i,推导1:E E+E E*E+E i*E+E i*i+E i*i+i,二义文法,若一个文法存在某个句子对应两棵不同的语法树,则称这个文法是二义的或者,若一个文法存在某个句子有两个不同的最左(右)推导,则称这个文法是二义的,判定任给的一个上下文无关文法是否二义,或它是否产生一个先天二义的上下文无关语言,这两个问题是递归不可解的,但可以为无二义性寻找一组充分条件,二义文法改造为无二义文法 GE: E i GE:E T|E+T E E+E T F|T*F E E*E F (E)|i E (E) 规定优先顺序和结合律 如果产生上下文无关语言的每一个文法都是二义的,则说此语言是先天二义的。对于一个程序设计语言来说,常常希望它的文法是无二义的,因为希望对它的每个语句的分析是唯一的。,句型的分析,句型分析就是识别一个符号串是否为某文法的句型,是某个推导的构造过程。,从左到右的分析算法,即总是从左到右地识别输入符号串,首先识别符号串中的最左符号,进而依次识别右边的一个符号,直到分析结束。,在语言的编译实现中,把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。,句型的分析算法分类,分析算法可分为: 自上而下分析法: 从文法的开始符号出发,反复使用文法的产生式,寻找与输入符号串匹配的推导。,自下而上分析法: 从输入符号串开始,逐步进行归约,直至归约到文法的开始符号。,两种方法反映了两种语法树的构造过程。,
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年新能源行业氢能应用水平考试-欧盟《氢能战略》实施进展考核试卷
- 国际商事合同中的违约金条款效力认定实务考核试卷
- 2025年水产养殖网箱清洗安全操作考核试卷
- 考点攻克人教版八年级上册物理光现象《光的直线传播》难点解析试题(含详细解析)
- 配电网故障自愈与继电保护协调考核试卷
- 考点解析人教版八年级上册物理物态变化《熔化和凝固》必考点解析试卷(解析版含答案)
- 考点解析-人教版八年级物理上册第5章透镜及其应用-透镜重点解析练习题(解析版)
- 解析卷-人教版八年级上册物理物态变化《熔化和凝固》综合练习试题
- 考点解析-人教版八年级物理上册第4章光现象-光的色散专项测试试卷(解析版)
- 难点解析-人教版八年级物理上册第4章光现象同步测试试卷(详解版)
- 2025杭州桐庐县统计局编外招聘2人考试参考题库及答案解析
- 扶贫项目实施方案及资金管理
- 2025中国华腾工业有限公司招聘笔试历年参考题库附带答案详解(3卷合一)
- 机械设计制造及其自动化专升本2025年智能设备联网试卷(含答案)
- 小学数学期末综合评价标准与表格
- 手术过程及准备流程
- 消防安全知识培训课件及考试题库
- 永久起搏器植入术课件
- 中国移动杭州市2025秋招笔试行测题库及答案通信技术类
- 卫生厅课题申报书范文
- 2025年甘肃省平凉市庄浪县第五幼儿园教育集团保健医招聘考试参考试题及答案解析
评论
0/150
提交评论