- 博客(42)
- 收藏
- 关注
RSS订阅原创 编译原理复习笔记 第八章 代码优化 更新中
8-1 流图分析程序的控制流程基本块：满足下列条件的最大的连续三地址指令序列：（1）控制流只能从基本块的第一个指令进入该块。（2）除了基本快的最后一个指令，控制流在离开基本块之前不会跳转或停机基本块的划分算法：输入：三地址指令序列输出：对应的基本块划分流图流图的结点：一些基本块基本块B到基本块C的边：当且仅当基本块C的第一个指令紧跟在B的最后一条指令之后执行8-2 常用的代码优化方法优化分类：机器无关优化 机器相关优化删除公共子表达式如果表达式 x op
2020-07-18 07:14:30
519
原创 编译原理复习笔记 第七章 运行存储分配 更新中
7-1 概述在编译时刻就可以确定大小的数据对象，可以在编译时刻就为他们分配存储空间，这样的分配称为静态存储分配策略。反之，编译时刻不能确定大小的数据对象，采用动态分配。栈式存储分配堆式存储分配活动记录：一个活动一个存储区7-2 静态存储分配适合静态存储分配的语言：（1）数组上下界是实数（2）不允许过程的递归调用（3）不允许动态建立数据实体常用的静态存储分配方法：顺序分配 层次分配顺序分配法：按照过程出现的先后顺序分配存储单元层次分配法：无调用关系的并列过程，
2020-07-17 16:40:30
394
原创 编译原理复习笔记第六章 中间代码生成
各类语句的翻译6-1 类型表达式基本类型是类型表达式可以为类型表达式命名，类型名也是类型表达式将类型构造符作用于类型表达式可以构成新的类型表达式1）数组构造符int[2] [3] = array(2,array(3,int))2）指针构造符T是类型表达式，pointer（T）是表示指针的类型表达式3）笛卡尔乘积构造符4）函数构造符5）记录构造符6-2 声明语句的翻译收集标识符的类型，并分类相对地址根据类型判断宽度名字的类型和相对地址信息保存在符号表中...
2020-07-16 17:56:03
1088
1
原创 编译原理复习笔记 第五章 语法制导翻译 更新中
5-1 语法制导翻译概述语法制导翻译：使用上下文无关文法引导对语言的翻译，是一种面向文法的翻译技术语法制导翻译基本思想：（1）如何表示语义信息？——为CFG中的文法符号设置语义属性，用来表示语法成分对应的语义信息（2）如何计算语义属性？——用与文法符号所在产生式相关联的语义规则来计算的。对于给定的输入串x，构建x的语法分析树，并利用与产生式相关联的语义规则来计算分析树各节点对应的语义属性值。语义规则与语法规则的联系：语法制导定义 SDD：将每个文法符号与语义属性相关联，将产生
2020-07-16 00:15:16
566
原创 数据库-实现篇 第十九讲
数据库的故障类型及其影响DBMS利用内存和外存的存储体系进行数据库管理在内存中，分为程序数据和系统数据数据元素：1数据元素=1磁盘块/内存页，也可以更小或更大事务的四个特性原子性、一致性、隔离性、持久性故障恢复涉及到如何保证原子性、持久性事务故障：程序（事务）自身运行错误引起的故障，影响该程序（事务）本身系统故障：由于掉电、非正常关机引起的故障介质故障：介质损坏引起的故障，影响内存和介质内存储的数据数据库故障恢复的宏观思路保障事物的持久性和原子性事务故障的恢复：撤销事务（消除未
2020-07-07 00:57:16
188
原创 数据库-实现篇 第十八讲 未完结
为什么要进行并发控制为什么要进行并发控制——数据库可能存在不一致三种典型的不一致现象（1）丢失修改（2）不能重复读（3）脏读并发控制及相应的事务处理技术是DBMS的核心技术什么是事务事务：数据库管理系统提供的控制数据操作的一种手段，保证数据库的正确性、一致性事务的宏观性：一个存取或改变数据库内容的程序的一次执行，或着说一条或多条SQL语句被看成一个事务事务一般由程序员提出，因此有开始和结束，结束需要提交或撤销一个事务可以处理一个或一条记录一段程序语句可能
2020-07-06 20:48:20
181
原创 数据库-实现篇 第17讲
为什么要查询优化数据库执行效率三个层面的优化：（1）语义优化：利用模型的语义及完整性规则，优化查询（2）语法优化——逻辑层优化：利用语法结构，优化（3）执行优化——物理层优化查询优化的总体思路逻辑层查询优化策略尽可能将投影、选择操作移动到乘积前面从树叶到树根反映了操作的先后顺序关系代数操作等价变换定理关系代数的5个基本操作：并、差、积、选择、投影两两交换，验证是否等价关系代数操作的七个等价定理：（1）连接与连接，积与积的交换律（2）连接与连接，积和积的结合律
2020-07-06 08:32:37
81
原创 数据库-实现篇 第十六讲
两趟扫描算法的基本思想整个关系一元操作的问题：任何一个元组需要与所有元组进行比较，才能确定最终结果。这些需要内存内存不够存储整个关系怎么办？？——两趟 / 多趟算法两趟算法基本思路：（1）第一趟：划分子集，使子集具有某种特性（有序/具有相同散列值）。处理好之后将结果写回磁盘将磁盘上的数据重新建立数据结构（2）处理全局性的内容操作。多子集归并、相同散列值操作...
2020-07-05 07:53:51
187
原创 数据库-实现篇 第十五讲
查询实现算法概述——关系代数操作数据库查询基本思想：数据库的核心操作（1）基本动作：并、差、积、选择、投影（2）基于关系代数提出的SQL语句，转化为关系代数的组合操作（3）程序执行机构进行解释、拆解查询实现和查询优化：（1）将SQL语句转化为关系代数表达式转化后，若先执行连接操作，则会造成爆炸，故DBMS不能按照该顺序进行执行尽量把选择、投影操作移到乘积的前面去执行（2）改变操作次序（3）为每一个操作选择一个优化的程序进行执行——物理查询优化（4）执行物理查询优化
2020-07-05 07:38:56
142
原创 数据库-实现篇 第十四讲
索引的概念和作用索引：在存储表的基础上的一种辅助存储结构。索引项=索引字段+行指针（索引字段为TABLE中的某些列）对应的存储表称为主文件，索引表称为索引文件。索引文件不改变存储表的物理结构索引文件的组织：（1）排序索引文件——索引字段值排序（2）散列索引为念主文件的组织：（1）堆文件（2）排序文件（3）散列文件（4）聚簇文件可根据不同属性、属性组建立不同的索引文件索引文件比主文件小很多，可以一次性装入内存由索引时，更新操作必须同步更新索引文件访问时间、插入时间、删除时间、
2020-07-04 19:42:12
210
原创 数据库-实现篇 第十三讲（含习题）
存储体系DBMS读取、存取磁盘上的数据磁盘结构特性宏观实现查询、微观算法数据库以表、记录访问数据，内存以磁盘块存储数据存储体系回顾如何高效率存储？——数据组织与索引如何快速检索？——查询实现和查询优化数据库存储体系大多数情况下，数据库保存在磁盘上，讲内容读入到缓冲区被CPU处理磁盘块的组织：第一个磁盘块在目录中保存；操作系统 把文件按照文件块存储在磁盘块上；内存管理（主存）（1）一条记录的地址=存储单元地址=内存地址=页面：页面内偏移量（2）页面=块
2020-07-04 10:21:01
171
原创 数据库-设计篇 第十一讲（含习题）
为什么要数据库建模设计软件实践 VS 用户期望需求理解（1）数据需求理解与表达（2）处理规则需求理解数据建模 与 概念模型概念模型——观念世界 E-R / O-O数据模型——计算机世界 关系、网状、层次数据建模：抽象抽象：理解、区分、命名、表达E-R模型E-R模型：实体-联系模型需要理解、区分、表达什么要素；用什么表达方法；实体与实例实体：客观存在并可相互区分的事物，实体有类、个体的概念属性：刻画实体的特性属性的分类：（1）单一属性与符合属性（2
2020-07-03 23:25:39
1136
原创 数据库-基础篇 第七讲（含习题）未完结
IN 子查询（NOT）IN子查询：表达式 【NOT】in (子查询)例：列出张三、王三同学所有信息：Select *From StudentWhere Sname in(‘张三’，’王三‘)；列出选秀了001号课程学生的学号和姓名：Select S#, SnameFrom StudentWhere S# in(Select S# From SC Where C#=‘001’);列出选秀了001号课程和002号课程的学生的学号：Select S#From SCWhere C#
2020-07-03 21:23:03
455
1
原创 数据库-基础篇 第六讲（含习题）
SQL语言概述（1）DDL语句引导词 Create Alter Drop（2）DML语句引导词：Insert, Delete, Update, Select(3)DCL语句引导词：Grant（授权）, Revoke（收回授权）交互式SQL→嵌入式SQL→动态SQL利用SQL建立数据库学生选课数据库建立数据库（1）定义数据库和表1)create database 数据库名；create database SCT;2)create table 表名（列名 数据类型 [Primar
2020-07-03 11:52:37
5512
3
原创 数据库-基础篇 第五讲（含习题）
关系元组演算关系演算以逻辑谓词演算为基础关系演算可分为关系元组演算和关系域演算（1）关系元组演算以元组变量作为谓词变量的基本对象（2）关系域演算以域变量作为谓词变量的基本对象元组演算公式的基本形式：P(t)的递归定义：（1）原子公式（2）P是公式，非P是公式（3）公式的与、或也是公式（4）存在量词、全称量词（5）运算符优先级：（6）公式只限于以上形式元组演算公示的运用存在量词与全称量词存在量词、全称量词：起到验证的作用...
2020-07-02 23:20:17
1590
原创 数据库-基础篇 第四讲（含习题）
什么是关系代数（1）并、差、笛卡儿积、选择、投影、更名（2）交、连接、关系除关系代数操作以一个多多个关系为输入，输出结果也是关系关系代数操作的分类：（1）集合操作：并、交、差、笛卡尔积（2）纯关系操作：投影、选择、连接、关系除并相容性某些关系代数操作，如并、差、交等，需要满足并相容性并相容性：（1）R和S属性数目相同（2）对应的第 i 个属性域相同并操作差操作广义笛卡尔积RS=SR选择操作选择满足某些条件的行，结果仍为关系选择操作时运算符的优先级：
2020-07-02 21:56:30
2619
原创 数据库-基础篇 第三讲（含习题）
关系模型简述从表及表的处理方式中抽象出来，引入集合和逻辑理论SQL语言建立在关系模型基础上一个关系就是一个Table关系模型：（1）描述DB基本结构形式（2）描述Table和Table之间可能发生的各种操作（关系运算）（3）约束条件（完整性约束）关系模型三要素：（1）基本结构（2）基本操作（3）完整性约束：实体完整性、参照完整性、用户自定义完整性关系运算：关系代数 +关系演算关系演算：元组演算+域演算关系代数：基于集合的运算，一次一集合基于关系代数的数据库语言：计算机可识
2020-07-02 02:04:16
2933
原创 数据库-基础篇 第二讲（含习题）
数据库系统的标准结构DBMS管理数据的三个层次（1）外部层次（用户层次），全局中的某一部分（2）概念层次（逻辑层次），相应关联约束（3）内部层次（物理层次），存储在介质上的数据数据 / 视图某一表现形式下表现出的数据库中的数据模式数据库中的数据进行的结构性的描述三级模式外模式 ——外部视图概念模式——概念视图内部模式——内部视图两层映像：（1）E-C Mapping：外模式→概念模式（2）C-I Mapping：概念模式→内模式数据库系统的标准结构
2020-07-02 00:19:56
1428
原创 数据库-基础篇 第一讲（含习题）
数据库（1） 如何存储数据（2） 如何检索查询，以获取有用信息数据库 源于表，–关系及关系模型Table的构成：表名，表标题，表内容，行/元组/记录，列/字段/属性/数据项关系模式=表名+表标题关系/表=表名+表内容+表标题数据库：相互之间有关联关系的Table集合关系数据库 / 图像数据库 / 工程数据库数据库系统数据库系统（工作环境）数据库：数据（表）集合数据库管理系统：系统软件数据库应用：应用程序数据库管理员（ – 数据库管理系统）计算机基本系统数据库管理
2020-07-01 22:31:36
629
原创 编译原理复习笔记 第四章 语法分析
编译原理第四章4-1 自顶向下分析概述从文法的开始符号S推导出词串w的过程最左推导：总是选择每个句型的最左非终结符进行替换最左句型：最右推导：总是选择每个句型的最右非终结符进行替换最左推导和最右推导具有唯一性扫描器从左向右扫描，故自顶向下的分析采用最左推导自顶向下语法分析的通用形式：递归下降分析：由一组过程组成，每个过程对应一个非终结符预测分析：一种确定的自顶向下分析方法，不需要回溯4-2 文法转换（不是所有的文法都适合自顶向下的分析）问
2020-06-25 18:10:13
1106
原创 编译原理复习笔记 第三章 词法分析
编译原理第三章3-1 正则表达式由较小的表达式递归定义，正则表达式定义的语言r-L（r)可以表示大部分语言十进制整数的RE：(1|…|9)(0|…|9)|0八进制整数的RE：0(1|…|7)(0|…|7)十六进制整数的RE：0x(1|…|9|a|…|f|A|…|F)(0|…|9|a|…|f|A|…|F)*正则文法与正则表达式等价3-2 正则定义正则定义的定义C语言标识符的正则定义：digit→0|1|2|…|9letter_→A|B|…|Z|a|b|…|z|_id→lette
2020-06-25 11:10:52
467
原创 编译原理复习笔记 第二章 程序设计语言及其文法
编译原理第二章2-1 基本概念字母表：有穷符号集合字母表上的运算字母表正闭包/克林闭包串：字母表上的一个克林闭包元素，有穷序列串上的运算：连接、幂2-2 文法的定义句子、单词的构成规则基本符号文法形式化定义S：开始符号，“最大的语法成分”产生式的简写（1）相同左部的简写终结符（1）排在前面的小写字母（2）运算符（3）标点（4）数字（5）粗体字符，id、if等非终结符（1）排在前面的大写字母（2）S，开始符（3）小写斜体的名字（4）E表达式，T项，F因子
2020-06-25 01:29:52
293
原创 编译原理复习笔记 第一章 绪论
编译原理第一章1-11.计算机设计语言2. 编译系统可重定位：内存中存放的起始位置不定加载器：修改可重定位地址连接器：链接库文件；将多个可重定位代码连接到一起；解决外部内存地址1-2 编译系统结构词法分析：分析词性语法分析：识别句子中的各类短语，分析句子结构语义结构：根据句子结构，分析短语成分编译器结构中间表示形式：独立于任何语言1-3 词法分析概述“从左向右”扫描源程序字符，识别单词，确定单词类型，表示为token形式Token:<种别码，属性值&g
2020-06-25 00:04:25
256
转载 形式语言与自动机 考前复习 CH6
下推自动机下推自动机实质上是一种能控制一条输入带和一个栈的有穷自动机, 可以看作带有栈的 ε-NFA. 工作方式类似 ε-NFA, 有一个有穷控制器, 并能够以非确定的方式进行状态转移, 并读 入输入字符; 增加的堆栈, 用来存储无限的信息, 但只能以后进先出的方式使用.6.1.1 形式定义定义.下推自动机 (PDA, Pushdown Automata) P 为七元组：P = (Q,Σ,...
2019-06-26 16:20:26
883
转载 形式语言与自动机 考前复习 CH5
上下文无关文法回文定义.如果语言 L 中的字符串都是回文, 则称 L 为回文语言 L = {w ∈ Σ∗ | w = wR}.5.1.1 形式定义• 产生式 A → α, 读作 A 定义为 α• 如果有多个 A 的产生式A → α1, A → α2, ··· , A → αn，可简写为A → α1 | α2 |···| αn• 文法中变元 A 的全体产生式, 称为 A 产生式续...
2019-06-26 14:15:34
4251
转载 形式语言与自动机 考前复习 CH4
正则语言的性质4.1 证明语言的非正则性“泵引理”是正则语言的一个必要条件: 如果一个语言是正则的, 则一定满足泵引理.4.1.1 正则语言的泵引理定理 5 (正则语言的泵引理 (Pumping Lemma)). .如果语言 L 是正则的, 那么存在正整数 N, 它只依赖于 L, 对 ∀w ∈ L, 只要 |w|≥ N, 就可以将 w 分为三部分 w = xyz 满足: 1. y 6= ...
2019-06-26 10:38:55
1385
转载 形式语言与自动机 练习题总结
例2请设计 DFA, 在任何由 0 和 1 构成的串中, 接受含有 01 子串的全部串{0，1}的子串全部串有：0，1，01，故本题有三种状态未发现 01, 即 0 没有出现过;未发现 01, 但刚刚读入字符是 0;已经发现了 01.因此 DFA A 可定义为：A = ({q1,q2,q3},{0,1},δ,q1,{q3})其中 δ 为:δ(q1,1) = q1 δ(q2,1)...
2019-06-25 23:10:42
7006
翻译 形式语言与自动机 考前复习笔记 CH3
正则表达式3.1.1 语言的运算设 L 和 M 是两个语言, 那么对于空语言 ∅3.1.3 运算符的优先级首先, “括号”优先级最高;其次, “星”运算: r∗;然后, “连接”运算: rs, r·s;最后, “加”最低: r+s, r∪s;3.2 有穷自动机和正则表达式3.2.1 由 DFA到正则表达式, 递归表达式法3.2.2 由 DFA 到正则表...
2019-06-25 23:10:07
739
翻译 形式语言与自动机 复习知识点总结 CH2
2.2 确定的有穷自动机2.2.1 确定的有穷自动机→一个读头→一个有穷控制器（Finite Control）→一条输入带2.2.2 有穷自动机的识别在扫描输入的字符串之前, 读头在输入串的第一个字符下面, 然后从左向右， 一次一个单元格的读入字符, 移动读头, 并修改状态, 然后自动的循环这个过程, 直到扫描完整 个字符串之后, 通过有穷控制器中的当前状态, 对这个字符串进行判断, ...
2019-06-25 20:33:32
1833
翻译 软件构造 线程与进程
进程→正在运行的一个程序的实例→虚拟计算机→有私有专用的内存空间，不共享内存；→通过消息传递交流信息（标准IO流）线程→正在运行的执行路径→虚拟处理器（轻量级进程）→线程在进程内，互相之间共享资源→特殊处理才能实现消息传递、访问私有内存→每个应用程序至少有一个线程，main线程是开始线程，可以通过它创建其他的线程在某时刻，一个运行核心上只有一个线程可以运行进程 / 线程等采...
2019-06-25 04:37:52
110
翻译 面向可维护性
在考试前一天，又看了看自己不太熟悉的知识（虽然不熟悉的很多。。。），再次做以杂记。软件熵：当一个系统被修改后，其混乱程度或者熵趋向于增加。面向可维护性的软件构造的例子：模块化、OO设计原则、OO设计模式、基于状态的构造技术、表驱动的构造技术、基于语法的构造技术可维护性的问题设计结构是否足够简单？模块之间是否松散耦合？模块内部是否高度聚合？是否使用了非常深的继承树，是否使用了dele...
2019-06-24 16:01:04
271
翻译 软件构造 复习笔记九
面向健壮性的软件构造健壮性系统在不正常输入，或不正确外部环境下仍能够表现正常的程度面向健壮性的编程处理未期望的行为和错误终止即使终止执行,也要准确、无歧义展示错误信息错误信息有助于debug正确性：永不给用户错误的结果 , 倾向直接报错→对内，倾向于正确健壮性：尽可能保持软件运行，倾向于容错→对外，倾向于健壮error→defect / fault / bug（缺陷）→f...
2019-06-23 21:29:32
97
翻译 软件构造 复习笔记八
面向维护的软件构造方法软件维护：修复错误、改善性能可维护性的衡量指标：圈复杂度代码行数根据操作符个数生成综合指标可维护性指数（涉及到COM）继承的层次数类之间的耦合度单元测试覆盖率模块化编程：特点：高内聚、低耦合、分离关注点、信息耦合五大标准：8. decomposability 可分解性9. composability 可组合性10. understandab...
2019-06-23 19:42:34
172
原创 软件构造 复习笔记七
面向复用（Reusability）的软件构造方法复用：开发出可复用的软件利：降低重复开发成本弊：性能差，对普适场景没有针对性高复用性软件的特点：规模小，简易于标准兼容灵活可变可扩展泛型、参数化模块化变化的局部性稳定丰富的文档可复用的层级和形态：10. 源代码11. 模块：类、接口12.13. 库级别：API（jar.）13.系统级：框架适用范围↑复用...
2019-06-23 17:19:53
155
原创 软件构造 复习笔记六
面向可理解的软件构造Metrics for Understandability→display,priintMetrics→所有标识符的平均长度→独特命名的比例→代码复杂度，代码行数→注释的密度（MCOMM% = MCOMM / LOC）Documenting in source code1） specifications:pre-condition and post-co...
2019-06-21 16:58:20
85
原创 软件构造 复习笔记五
overload和override的对比Java中的泛型（参数化的多态）通配符：只能在使用中出现，不能定义不能用instance of检验泛型不能构建泛型数组子类型多态LSP原则：子类型的规约不能弱于父类型的规约静态分派：编译阶段确定执行操作动态分派：编译阶段可能绑定到多态操作，运行阶段确定具体执行哪一个推迟绑定：编译阶段不知道类型，一定是动态分派（override是推迟...
2019-06-20 23:36:40
143
原创 软件构造 复习笔记四
ADT与OOPADT不变量必须时刻保证是true，保证程序的正确性，防止表示泄露由ADT自身负责与client端行为无关AF（abstract Function)满射，未必单射，未必双射RI（Rep Invariants) 表示不变量表示某个表示是否合法，表示所有表示值的一个子集对inmmutable ADT在A空间的abstract value应不变，内部R空间可变检查不...
2019-06-19 00:52:20
107
转载 软件构造 复习笔记三
ADT和OOP的相关数据类型——基本数据类型：有值无ID，不可变（不能赋值为null）——对象数据类型：有值有ID静态，动态数据类型检查——静态：编译阶段的检查，切入点“类型”，语法错误，类名函数名错误，参数数目类型错误，返回值类型错误final变量不可变——动态：运行阶段的检查，切入点“值”，非法参数，越界，空指针改变一个变量：将该变量指向另一个存储空间改变一个变量的值：向该变...
2019-06-17 11:22:42
130
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人