华中科技大版 编译原理课件
更新时间:2023-04-20 21:28:01 阅读量: 实用文档 文档下载
华中科技大学出版社出版,编译原理课件,主编何炎祥
第二章 形式语言概论本章主要介绍形式语言理论中的一些最 基本的概念和基础知识,它是学习以后 各章节的基石。
华中科技大学出版社出版,编译原理课件,主编何炎祥
内容回顾(1)翻译程序作用
翻译程序
编译方法解释方法
编译程序概述编译的组成和流程 编译程序结构
编译各部分的功能 编译的实施和逻辑结构
华中科技大学出版社出版,编译原理课件,主编何炎祥
内容回顾(2)信息表管理程序
源 程 序
词 法 分 析 程 序
语 法 分 析 程 序
语 义 分 析 程 序
中 间 代 码 生 成
代 码 优 化 程 序
目 标 代 码 生 成
目 标 代 码
错误检查和处理程序编译程序结构
华中科技大学出版社出版,编译原理课件,主编何炎祥
内容概要符号的有穷集合
一个语言的成分包括字母表(Alphabet),文法 (Grammar)以及它的语义。 结构规则的
形式语言理论
操作规则的 有穷集合
有穷集合
Chomsky于1956年提出 讨论语言和文法的数学机制以及语言和文法的分类
是编译程序的重要理论基础
本章将主要讨论字母表、符号串、产生式文法系 统以及句子分析等方面的内容。
华中科技大学出版社出版,编译原理课件,主编何炎祥
2.1 字母表与符号串字母表:元素的非空有穷集合。记作∑。
符号:字母表中的元素。符号串:符号的有穷序列。
空符号串:什么符号也不包括的符号串,记作ε。
符号串的运算
② 符号串的长度。 ③ 符号串的连接。 ④ 符号串集合的乘积。 ⑤ 符号串的方幂。 ⑥ 符号串集合的方幂。 ⑦ 符号串集合的正闭包。 ⑧ 符号串集合的自反闭包。
华中科技大学出版社出版,编译原理课件,主编何炎祥
符号串的长度符号串所包含符号的个数,称为符号串的长度。设x是一符 号串,它的长度记为|x|,|ε| = 0
符号串的连接设x,y是两个符号串,则xy称为x与y的连接。
符号串集合的乘积设A、B是两个符号串集合,AB表示A与B的乘积,则定义
AB={xy | x A, y B}Example
设A={ ab, c }, B= { d, efg },则 AB={abd, abefg, cd, cefg}
华中科技大学出版社出版,编译原理课件,主编何炎祥
符号串的方幂同一符号串的连接可写成方幂形式。设x是一符号串,则定 义 x0 = ε, x1 = x, x2 = xx, x3 = xxx,…
符号串集合的方幂A0 = {ε}, A1 = A, A2 = AA, A3 = AAA,…
符号串集合的正闭包和自反闭包设符号串集合A,A的正闭包记为A+,自反闭包记为A*,则
A+=A1∪A2∪… ∪ An∪… A*={ε}∪A+ = A+∪ {ε}
华中科技大学出版社出版,编译原理课件,主编何炎祥
、{}、 { }的区别
特别指出的是:
是空符号串, 不是集合
{ }表示由空符号串 所组成的集合Φ={} , 表示空集
Φ,即空符号串不等于空集
华中科技大学出版社出版,编译原理课件,主编何炎祥
2.2 文法及其分类
文法: 定义或描述语言的语法结构的一组形式规则。
He gave me a book.<句子> <主语><谓语><间接宾语><直接宾语> <主语> <代词> <谓语> <动词> <间接宾语> <代词> <直接宾语> <冠词> <名词> <代词> He <代词> me <名词> book <冠词> a
<动词> gave
华中科技大学出版社出版,编译原理课件,主编何炎祥
2.2.1 产生式的定义
定义2.1 设VN、 VT分别是非空有限的非终结符号集 和终结符号集,V= VT ∪ VN ,VT VN= 。一个产 生式是一个序偶对(α ,β ),其中,α V+, β V* ,通常表示为 α →β 或 α ::=β
如果产生式集合中的产生式有共同的左部,如 α →β ,α →γ ,则可简写为 α →β |γ
华中科技大学出版社出版,编译原理课件,主编何炎祥
文法的定义
定义2.2 文法G是一个四元组, G=(VT,VN,S,P) ,其中, VN、 VT分别是非空有限的非终结符号集 和终结符号集, VT VN= ,P是产生式集,S VN 称为文法的识别符号或开始符号。
例2.1 文法
G1=(VT,VN,S,P) VN={S,B,C,D} VT={a,b,c} P={S→aSBC, S→abc, CB→CD, CD→BD, BD→BC, bB→bb, bC→bc, cC→cc}
华中科技大学出版社出版,编译原理课件,主编何炎祥
2.2.2 文法分类0型文法又称为短语结构文法 ,它的能力相当于图灵机。 若对0型文法的产生式作某些 限制,则可给出其它三种类型 Chomsky将文法分为四种类型:0型、1型、2型和3 的文法。
型。
0型文法(无限制的文法)
其产生式具有以下形式: 0型文法 → G1=(VT,VN,S,P) VN={S,B,C,D} 其中, (VN∪VT)+, (VN∪VT)* VT={a,b,c} P={S→aSBC, S→abc, CB→CD, CD→BD, BD→BC, bB→bb, bC→bc, cC→cc}
华中科技大学出版社出版,编译原理课件,主编何炎祥
文法分类
符号串 1和 2可以认 为是上下文,其间的 A可以被符号串 替代 ,因此1型文法又称为 上下文有关文法。
1型文法(上下文有关文法) 其产生式具有以下形式:
→ 1型文法 其中 = 1A 2 ; = 1 2 ; 1 , 2 (VN∪VT)* ;A VN ; G6=(VN,VT,P,S) (VN={S,X,Y,Z} ∪VT)+。 其中, VN
VT={x,y,z} P={S→xSYZ xYZ, xY→xy,yY→yy, yZ→yz zZ→zz}
华中科技大学出版社出版,编译原理课件,主编何炎祥
文法分类
2型文法产生式的左部是单个非终结符 ,右部是由终结符和非终结符组成的 符号串。2型文法又称为上下文无关文 法。很适合描述现今的程序设计语言 ,是我们学习的重点。
2型文法(上下文无关文法) 在1型文法的产生式中,上下文 1和 2用空符号串 代替,则有以下形式的产生式,称为2型文法: A→ 2型文法
G3=(VN,VT,P,E)
其中,
其中,A VN, (VN∪VT)+。VN={E,T,F}VT={+,*,(,),i } P={E→E+T T,T→T F F,F→(E) i }
华中科技大学出版社出版,编译原理课件,主编何炎祥
文法分类
3型文法(右线性文法和正规文法) 如果P中的产生式只含有下面的两种形式:
A→a ,
A→aB
3型文法 则称该文法为3型文法,又称为右线性文法或正规 G4=(VN,VT,P,S) 文法。其中,A,B VN,a VT*。 其中, V ={S,A,B}N
VT={0, 1 } P={S→0 1 1A 0B,A→1A 0B,B→0 1 0B }
华中科技大学出版社出版,编译原理课件,主编何炎祥
四种类型描述能力比较
0型
1型 2型3型
华中科技大学出版社出版,编译原理课件,主编何炎祥
文法分类的意义
每类文法都和一种自动机相关
右线性文法→有穷状态自动机
上下文无关文法→下推自动机上
下文有关文法→双向、线性有界自动机 短语结构文法→图灵机
正规文法只能用于描述单词的构成 上下文无关文法有足够的能力描述现今大多数程 序设计语言的语法结构
华中科技大学出版社出版,编译原理课件,主编何炎祥
文法举例(1)G6=(VN,VT,P,S) 其中, VN={S,X,Y,Z}例 1
VT={x,y,z}zZ→zz}
1型文法
P={S→xSYZ xYZ, xY→xy,yY→yy, yZ→yz
G7=(VN,VT,P,S) 其中, VN={S,T}
例 2
VT={a,b,c,d}P={S→aTd, T→bT|cT|b|c}
2型文法
华中科技大学出版社出版,编译原理课件,主编何炎祥
文法举例(2)G8=(VN,VT,P,B) 其中, VN={B}例 3
VT={(,)}P={B→(B)|BB|()}
2型文法
G9=(VN,VT,P,S)其中, VN={S} VT={0,1} P={S→0S1, S→01} G10=(VN,VT,P,A) 其中, VN={A,B,C,D}
例 4
2型文法
例 5
VT={x,y, z}
3型文法
P={A→xB|yC, B→zB|y|yC, C→xD, D→yD|x}
正在阅读:
华中科技大版 编译原理课件04-20
幼儿园暑假开学安全第一课教案(精选7篇)03-26
小学《多彩的超轻粘土》校本课程教案03-25
JC70DB10绞车使用说明书-ok05-19
有源滤波实际效益分析02-03
本科急救护理学教学大纲109-09
关于印发《兵团质量奖评审实施细则》的通知03-25
文化旅游品牌建设的基本方略与路径选择01-24
2018年医院质控科工作计划12-01
小学音乐教学经验交流材料(多篇)03-08
- 教学能力大赛决赛获奖-教学实施报告-(完整图文版)
- 互联网+数据中心行业分析报告
- 2017上海杨浦区高三一模数学试题及答案
- 招商部差旅接待管理制度(4-25)
- 学生游玩安全注意事项
- 学生信息管理系统(文档模板供参考)
- 叉车门架有限元分析及系统设计
- 2014帮助残疾人志愿者服务情况记录
- 叶绿体中色素的提取和分离实验
- 中国食物成分表2020年最新权威完整改进版
- 推动国土资源领域生态文明建设
- 给水管道冲洗和消毒记录
- 计算机软件专业自我评价
- 高中数学必修1-5知识点归纳
- 2018-2022年中国第五代移动通信技术(5G)产业深度分析及发展前景研究报告发展趋势(目录)
- 生产车间巡查制度
- 2018版中国光热发电行业深度研究报告目录
- (通用)2019年中考数学总复习 第一章 第四节 数的开方与二次根式课件
- 2017_2018学年高中语文第二单元第4课说数课件粤教版
- 上市新药Lumateperone(卢美哌隆)合成检索总结报告
- 华中
- 编译
- 课件
- 原理
- 科技
- 新目标初中英语课件初一第二单元
- Lecture 2《英语词汇学》第二章教案
- 山西师大人文地理实习报告
- 与心血管病战斗到底.docx
- 2014-2022年中国廉租房市场竞争及投资策略研究报告
- 共青团什么旗帜更加高扬_高扬爱国主义旗帜思想汇报范文
- 九年级英语总复习教学案
- 财务报表分析”中的30个基本指标
- 一年级下学期语文月考试卷āáǎàōóǒò
- 五年级上册北师大版数学平行四边形的面积课件
- 加强专业和课程建设 提升学院教育教学水平
- 大学英语精读第四册课文翻译
- 英美概况关于英联邦ppt
- 大体积混凝土专项施工方案
- 对加入WTO后我国境外劳务输出的战略思考
- 300MW循环流化床锅炉调试
- 《大学生职业生涯规划书》写作要点
- 2014年小班下学期教研活动计划
- 心理学y 过程性评测4
- 山钢集团纪念五四运动94周年座谈会发言稿