【编译原理】期末 龙书概念梳理+做题方法（混子保过指南+学霸提分秘籍）

编译原理期末总结 龙书概念梳理+做题方法

词法分析 1 词法分析的任务

从左至右逐个字符地对源程序进行扫描 产生一个个单词符号 即把字符串形式的源程序改造为单词符号串形式的中间程序

词法分析工作由词法分析器完成，又称扫描器

2 词法分析器（Scnner 扫描器）的构造方法

3 词法分析器的工作原理 1 与语法分析器的连接

通常把词法分析器安排成语法分析器的一个子程序 而不是单独的一遍 当被调用时 词法分析器就从源程序字符串中识别出一个/一批单词符号 把它交给语法分析器去处理 语法分析器处理完毕 就开始下一次调用 如此重复 直至源程序处理完毕

2 输入&预处理

输入串一般放在一个缓冲区中 这个缓冲区称为：源程序输入缓冲区 但在许多情况下 把输入串预处理一下 对单词符号的识别工作将是比较方便的 预处理工作包括对空白符、跳格符、回车符和换行符等编辑性字符的处理及删除 注释等 于是 可以构造一个预处理子程序 它从源程序输入缓冲区读入字符串 预处理后 装入 扫描缓冲区 以备扫描器使用

3 扫描&输出

扫描器对扫描缓冲区进行扫描时 一般使用两个指示器 一个指向当前正在识别单词的开始位置（新单词的首字符） 另一个用于向前搜索以寻找单词的终点（新单词的尾字符） 但是不论扫描缓冲区设得多大 都不能保证单词符号不会被缓冲区的边界所打断 一个常用的技术是：把扫描缓冲区一分为二 并使两区首尾相接 形成一个 对半互补缓冲区 将识别出的单词符号交给语法翻译器 词法翻译器的工作就完成啦

4 正规表达式&正规集

相关基础知识 字母表（alphabet） 串（string） 串的连接：串的前后拼接 “幂”运算：串自身多次连接 空串：ε幺元（类似代数系统中乘法的1） 语言（language） ：串的集合 语言的运算 并：L∪M = {s| s∈Lor s∈M} 连接：LM = {st| s∈Land t∈M} 闭包（closure）：L*= ∪Li (i的取值从0到+∞) 正闭包：L+= ∪Li (i的取值从1到+∞)

正规表达式（Regular Expression）是说明单词的模式的一种重要的表示法（记号） 正规表达式所表示的所有的字符串的集合称为正规集（Regular Set） 设Σ为字母表 1 ε是Σ上的正规式 它所表示的正规集分别为{ε} 2 对于任何a∈Σ a都是Σ上的一个正规式 它所表示的正规集为{a} 3 假定U和V都是Σ上的正规式 它们所表示的正规集分别记为L(U)和L(V) 那么 (U|V)、(UV)和(U)也都是正规式 它们所表示的正规集分别为L(U)∪L(V), L(U)L(V)和(L(U)) 即并集 连接和闭包 仅由有限次使用上述三步骤而得到的表达式才是Σ上的正规式RE（Regular Expression） 仅由这些正规式所表示的字集才是Σ上的正规集

正规表达式的运算顺序 括号> 闭包> 连接> 或

正规表达式的等价 若两个正规式所表示的正规集相同，则认为二者等价，记为‘=’

e.g. (a|b)*(aa|bb)(a|b)*对应的正规集是Σ上的所有含有两个相继的a或相继的b的字符串

5 确定的有穷状态自动机DFA

确定有限自动机（DFA）是—个五元式系统： 其中 DFA M＝( S，∑，δ，S0，F ) 1 Ｓ是一个有限集 它的每个元素称为一个状态 2 ∑ 是一个有穷字母集 它的每个元素称为输入字符 3 δ 是一个从Ｓｘ ∑ -> S的单值部分映射 4 S0 属于S 是唯—的初态 5 Ｆ 属于S 是一个终态集（可空）

6 不确定的有穷状态自动机NFA

NFA M＝( S，∑，δ，S0，F ) 1 Ｓ是一个有限集 它的每个元素称为一个状态 2 ∑ 是一个有穷字母集 它的每个元素称为输入字符 3 δ 是一个从Ｓｘ ∑* -> S的子集的映射 δ:S ｘ ∑* -> T（T属于S） 4 S0 属于S 是一个非空的初态集 5 Ｆ 属于S 是一个终态集（可空）

NFA的不确定性表现在 1 多值映射 2 带空转移

词法分析题型

需求转化为RL RL转化为NFA NFA的确定化 DFA的最小化

属性文法&语法制导翻译 1 属性文法 1.1 属性文法的概念

属性文法是在上下文无关文法的基础上为每个文法符号（终结符或非终结符）配备若干个相关的“值”（称为属性）

1.2属性文法的分类

综合属性 用于“自下而上”传递信息 继承属性 用于“自上而下”传递信息

综合属性

在语法树中 一个结点的综合属性的值由其子结点或其自身的某些属性值确定 通常使用自下而上的方法在每一个结点处使用语义规则计算综合属性的值 仅仅使用综合属性的属性文法称 S-属性文法

继承属性

在语法树中 一个结点的继承属性值由该结点的父结点 兄弟结点和其自身的某些属性值确定 通常用继承属性来表示程序语言结构中的上下文依赖关系

ps. 终结符只有综合属性 由词法分析器提供 非终结符既可以有综合属性也可以有继承属性 文法开始符号的所有继承属性作为属性计算前的初始值

1.3 良定义的属性文法

属性之间不存在循环依赖关系的属性文法称为良定义的属性文法 这类文法的依赖图是有向无环图

1.4 基于属性文法的处理方法

基础文法用于构造输入符号串的语法分析树 在此基础之上 根据属性间的依赖关系建立依赖图 再按照图的某一种拓扑排序来遍历语法树 遍历的同时使用语义规则进行处理

输入串⇒语法树⇒依赖图⇒拓扑序⇒遍历语法树

1.5 S-属性文法

只含有综合属性的属性文法

1.6 L-属性文法

如果对于每个产生式A→X1X2…Xn的每个语义规则中 每个属性或者是综合属性 或者是Xj(1≤j≤n)的一个继承属性且这个继承属性仅依赖于 1 产生式Xj的左边符号X1,X2,…Xj-1的属性 2 A的继承属性

L-属性文法也就是“左属性”文法 计算每一个继承属性时不能引用右边符号的属性 也就是说 在这类属性文法的依赖图中 不能有从右到左的边 由此定义可知 S属性文法一定是L属性文法

2 语法制导定义SDD

语法制导定义(Syntax-Directed Definition)把： ①每个文法符号和一个属性（attribute）集合相关联 ②每个产生式和一组语义规则（semantic rules）相关联 这些规则用于计算与该产生式中符号相关联的属性值

3 语法制导翻译SDT

由源程序的语法结构所驱动的基于属性文法的处理办法

工具-依赖图

依赖图(Dependency Graph)描述了语法树中结点属性之间的相互依赖关系 依赖图是一个有向图 在图中为每一个属性设置一个结点 如果属性b依赖属性c 则从属性c的结点有一条有向边连到属性b的结点

运行时存储空间组织 1 活动 活动的含义

一个过程的活动指的是该过程的一次执行

活动的生存期

过程P一个活动的生存期 指的是从执行该过程的第一步操作到最后一步操作之间的操作序列 包括执行P时调用其他过程花费的时间

2 存储分配策略

运行时的存储空间组织基本使用三种分配策略：

2.1 静态分配策略

在编译时对所有对象分配固定的存储单元 且在运行时保持不变

2.2 栈式动态分配策略

在运行时把存储器作为一个栈进行管理 每当调用一个过程 它所需要的存储空间就动态地分配于栈顶 调用完毕 它所占空间就予以释放

2.3 堆式动态存储策略

在运行时把存储器组织成堆结构 以方便用户对存储空间的申请与归还（分配与回收）

3 存储组织

4 存储空间的栈式分配

活动记录

编译程序使用一个连续的存储块来管理过程在一次执行中所需要的所有信息

当某个过程被调用时 就在栈顶创建该过程对应的活动记录 当该过程运行完毕 就将其活动记录从栈顶撤销

活动记录包含

连接数据 返回地址 执行call指令时程序计数器的值 动态链（控制链） 指向调用该过程前的最新活动纪录的指针 运行时 运行栈上各数据区按动态建立的次序结成链 链头在栈顶 静态链（访问链） 指向静态直接外层的活动纪录的指针 用来访问非局部数据 形式单元 存放相应的实在参数的地址或值 局部数据区 局部变量、内情向量、临时工作单元（例如表达式求值的中间结果）

C语言的活动记录

C语言的特点是：不含分程序结构 过程定义不允许嵌套 但允许过程的递归调用 并且活动记录简化为： C的非局部数据：全局变量 全部放入静态数据区即可

常见概念辨析题

辨析DFA和NFA的异同 辨析自上而下语法分析和自下而上语法分析的异同 比较栈和堆 常见的优化方法