编译原理期末复习

2021-01-11 · 88次阅读 · 原创 · 计算机理论

#编译原理

1. 编译的大致过程

1.1 词法分析

词法分析阶段的任务是对构成源程序的字符串从左到右进行扫描和分解，根据语言的词法规则，识别出一个一个具有独立意义的单词( 也称单词符号, 简称符号 )。

1.2 语法分析

在词法分析的基础上, 根据语言的语法规则从单词符号串中识别出各种语法单位 ( 如表达式、说明、语句等 ) ,并进行语法检查,即检查各种语法单位在语法结构上的正确性。

1.3 语义分析和中间代码生成

首先对每种语法单位进行静态的语义审查，然后分析其含义，并用另一种语言形式 (比源语言更接近于目标语言的一种中间代码或直接用目标语言 ) 来描述这种语义。

1.4 代码优化

对前阶段产生的中间代码进行等价变换或改造，以期获得更为高效即省时间和空间的目标代码。

1.5 目标代码生成

将中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。

2. 编译阶段目标程序不同的区别

2.1 高级语言->机器语言

源程序–>编译程序–>机器语言目标程序–>运行

2.2 高级语言->汇编语言

源程序–>编译程序–>汇编语言-目标程序->汇编程序->机器语言目标程序

3. 名词解释

名称	含义
语法	对语言结构的定义
语义	描述了语言的含义
语用	从使用的角度去描述语言
字母表	元素的非空有穷集合，字母表中至少包含一个元素，字母表中的元素, 可以是字母、数字或其他符号
符号（字符）	字母表中的元素称为符号或称为字符。
符号串（字）	符号的有穷序列称为符号串
形式语言	序列的集合称为形式语言，每个形式语言都是某个字母表上按某种规则构成的所有符号串的集合。反之，任何一个字母表上符号串的集合均可定义为一个形式语言
句型	从开始符号推导出的结果（终结符和非终结符的并集）
句子	从开始符号推导出的结果（只包含终结符）
语言	文法G[S]产生的句子集合成为文法G定义的语言
短语	子树的末端节点形成的符号串是相对于子树根的短语
直接短语	简单子树的末端节点形成的符号串是相对于简单子树根的直接短语
句柄	最左简单子树的末端节点形成的符号串时句柄，即为最左直接短语
素短语	0.短语，1.至少包含一个终结符，2.不包含更小素短语
最左素短语	最左边的素短语
FIRST	$FIRST(a) = \{a\\|\alpha\rArr a...(\alpha若干步推导)，且a\in V_T\}$ ，终结首符集， $\alpha$ 推导出的第一个终结字符，且若 $\alpha \rArr \varepsilon$ ，则 $\varepsilon \in FIRST(\alpha)$
FOLLOW	$FOLLOW(A) = \{a\\|S\rArr ...Aa...(S若干步推导)，且 a \in V_T\}$ ，紧挨着A的终结符号集合，且若 $S\rArr ...A$ (若干步骤)，则 $\$\in FOLLOW(A)$ ，开始符号串一定包含$
SELECT	$SELECT(A\rarr \alpha) = \begin{cases} FIRST(\alpha),若\alpha \nRightarrow \varepsilon(若干步推导) \\ FIRST(\alpha)\bigotimes\{\varepsilon\}\bigcup FOLLOW(A)，若\alpha \in \varepsilon(若干步推导) \end{cases}$

4. DFA与NFA区别

DFA －> M=(Q, $\Sigma$ , f, S, Z)：Ｑ为有穷状态集合， $\Sigma$ 为有穷输入字母表，f为单值函数，S为唯一初态，Z为终态集合。

NFA －> M=(Q, $\Sigma$ , f, S, Z)：Ｑ为有穷状态集合， $\Sigma$ 为有穷输入字母表，f为多值函数（允许 $\varepsilon$ 出现），S为非空初态集，Z为终态集合。

其与DFA的差别：

目的地不确定：f为多值函数

初态不确定：S为非空初态集

可接受空字： $f(q_i,\varepsilon) = \{q_j,q_m,,,,q_k\}$

##　5. 注意点

正规式－>正规文法：a.去除 $\varepsilon$ ，b.左右线性一致
DFA、NFA的状态转换图：a.初态需要双箭头指向其，b.终态需要打双圆圈，c.状态转换链接为单箭头。
状态转换矩阵的终态加上 * 号。
NFA－>DFA：a.状态集合只要包含了终结符即为一个终态且打上双圆圈，b.只有 $\varepsilon$ 才可以无限次迭代下去，c.只有可以接收当前字符之后才可以加入 $\varepsilon$ 进行递推。习题3.11，3.1-2
DFA最小化过程中：终态集和非终态集都要进行划分。

标题：	编译原理期末复习
链接：	https://www.fightingok.cn/detail/26
更新：	2022-09-18 22:32:30
版权：	本文采用 CC BY-NC-SA 3.0 CN 协议进行许可