编译原理

编译程序基本任务：将源语言程序翻译成等价的目标语言程序。 编译过程

词法分析：从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描 和分解，从而识别出一个个单词。

语法分析：在词法分析的基础上将单词序列分解成各类语法短语。 语义分析：审查源程序有无语义错误，为代码生成阶段收集类型信息。 中间代码生成：将源程序变成一种内部表示形式（中间代码）。

代码优化：对中间代码进行变换或进行改造，目的是使生成的目标代码更为高效。 目标代码生成：把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或 汇编指令代码。 编译和解释程序的区别：

编译程序是一个语言处理程序，它把一个高级语言程序翻译成某个机器的汇编或二进制代码程序，这个二进制代码程序在机器上运行得出结果，其中编译和运行是两个分开的阶段。

解释程序接受某个语言的程序并立即运行，不需要在运行前把源程序翻译成目标代码，也可以让我们实现在某台机器上运行程序并生成结果。 构造一个编译程序的三要素：源程序、目标程序、编译方法 第三章

静态语义是一系列限定规则，并确定哪些呵护语法的程序是合适的；

动态语义也称作运行语义或执行语义，表明程序要做些什么，要计算什么。 句型，句子

文法描述的语言是该文法一切句子的集合 等价文法：语言相同 文法类型

0型：A推出B

1型：B长度大于等于A（上下文有关） 2型：A为非终结符，（上下文无关） 3型：A推出bC（正规文法） 最左推导：最左非终结符替换 最右推导：规范推导，规范句型

二义文法：有两个不同的最左/最右推导 句型分析：

分析程序：完成句型分析的程序

自上而下：从开始符号出发，寻找匹配于输入符号串的推导

自下而上：从输入符号串开始，逐步进行归约，直至规约到文法的开始符号 短语，直接短语，句柄（最左直接短语）

不可到达：不在任何规则右部出现；不可终止：不能推出终结符号串。 第四章：

词法分析：读入源程序，输出单词符号。 将词法分析工作分离的考虑：

使整个编译程序的结构更简洁、清晰和条理化 编译程序的效率会改进。 增强编译程序的可移植性

正规式：也称正则表达式，是表示正规集的工具。 算符优先顺序：先闭包，再连接，最后或。（均左结合） 正规文法和正规式等价性：

对任意正规文法，存在一个定义同一语言的正规式。反之亦然。 转换规则：A——xB，B——y A=xy

A——xA|y A=x*y A——x A——y A=x|y

有穷自动机：DFA，NFA

状态图，矩阵表示（非终态标0，终态标1）

NFA为DFA的特例，对于每个NFA，存在一个DFA，二者等价。 连个状态等价：一致性：同时为可接受或不可接受状态。

蔓延性条件：对于所有输入符号，状态s和t必须转换到等价等状态里。

正规式和有穷自动机的等价性：

自动机转换为正规式：

x，y结点。X所有空弧连接初态，所有终态空弧连接y。 消除结点：ab，a|b，ab*c

正规文法和有穷自动机得等价性：

正规文法构造自动机

字母表与终结符集相同

每个非终结符生成状态，开始符为开始状态 增加Z为终态 规则转换为函数

第五章：

语法分析是编译程序的核心部分。

自顶向下分析：面向目标分析法。从文法的开始符号出发，考虑如何根据当前的输入符 号唯一地确定选用哪个产生式替换相应非终结符以往下推导，或如何构 造一棵相应语法树。

First，follow，select。

上下文无关文法为LL1的充要条件：对于每个非终结符的两个产生式，select集交为空。 LL1：从左向右扫描输入串；最左推导；向右看一个符号便可决定选用哪个规则推导。 判别LL1文法的步骤

求出能推出空的非终结符 计算first集 计算follow集 计算select集 非LL1转化为LL1

提取公因子

消除左递归 A——Ax（直接）A——Bx B——Ay（间接）

直接：A=Ab|c——A=cB B=bB

间接：通过产生式的非终结符替换，将间接左递归变为直接左递归，消除之。 、

预测分析法：自顶向上分析的一种方法。

预测分析器组成：预测分析程序

先进后出栈 预测分析表

构造一文法的预测分析表，先判断是否为LL1文法，再构造。

求空，first，follow，select，分析表

一个文法消除左递归，提取左公因式后，不一定是LL1的。 第七章

一个LR分析器由三部分组成

总控程序

分析表或分析函数 分析栈

活前缀：一个或若干规范句型 的前缀。 第九章

符号表的功能：

收集符号属性

上下文语义的合法性检查的依据

作为目标代码生成阶段地址分配的依据 符号的主要属性和作用

符号名 符号类型

符号的存储类别

符号的作用域及可视性 符号变量的存储分配信息 符号的其他属性 符号表项的排列

线性组织

排序组织及二分法 排列组织

第十一章

优化技术

删除多余运算 代码外提 强度削弱 变换控制条件

合并已知量与复写传播 删除无用赋值