编译原理考试复习

第一章 绪论

• 由于计算机不能对程序进行翻译或进行解释，所以计算机执行某高级语言程序，需经两个阶段，即编译阶段和运行阶段
• 编译系统 = 编译程序 + 运行系统
  • 运行系统 ：由辅助子程序构成的子程序库。如：数据格式转换子程序、标准函数、动态存储分配子程序等等。
  • 编译程序：先把全部源程序翻译为目标程序，然后再次执行，该目标程序可以反复执行。
  • 解释程序：对源程序逐句翻译，目标代码只能执行一次，若需要重新执行，则必须重新解释源程序，目前已不多见。

• 编译程序的编译过程

编译程序构成(考点1)

1. 词法分析器：
   1. 识别出源程序的各个基本语法单位（单词或语法符号）
   2. 删除无用的空白字符及其它与输入介质相关的非实质性字符（空格、回车等）
   3. 删除注释
   4. 进行词法检查，报告所发现的错误
2. 语法分析器：
   • 以词法分析程序输出的单词流为输入，分析源程序的结构，判断它是否为相应程序设计语言的合法程序。
   • 方法：试图为源程序构造一个语法树。
   • 词法分析器把源程序转换成了一个词素序列，它让我们知道了一个符号序列’i’、’f’是一个关键词”if”，而一个符号序列’1’、’2’、’3’、’4’是一个常量”1234”等等。但是，词法分析器的工作也到此为止了，它不能说明几个词素之间的关系。例如，对于词素串”int”、”x”、”=”、”1”、”;”，词法分析器不知道它是一个语句；对于词素串”int”、”x”、”==”、”1”、”;”，词法分析器不能检测出它的语法错误。为此，在词法分析之后，还需进行语法分析。
   • 一个语法分析器从词法分析器获得一个词素序列，并验证这个序列是否可以由源语言的文法生成。语法分析器会构造一棵语法分析树，并把它传递给编译器的其他部分进一步处理，在构建语法分析树的过程中，就验证了这个词素序列是否符合源语言的文法。
3. 语义分析器：

• 语法特征：描述各成份的形式或结构
• 语义特征：描述各语法成份的含义和功能，即规定它们的属性或在执行应进行的运算或操作
  1. 中间代码生成：
• 为了处理方便和便于代码优化，在语义分析后通常并不直接产生目标代码，而是生成介于二者之间的中间代码。
  1. 代码优化器：
• 代码优化的目的是生成质量较高的目标代码
  1. 目标代码生成程序：
• 将中间代码翻译成为目标程序
  1. 错误检查和处理程序：
• 准确地报告源程序中错误的种类及位置
  1. 信息表管理程序：
• 编译过程中，需经常收集、记录或查询程序中所出现的各种量的有关属性（信息）
  • 为此，编译程序需要建立一批不同用途的表格

第二章 形式语言基本知识

• 考点二，概念及术语

• 字母表：

  • 字母表（符号表、符号集） 由若干元素（符号、字母）组成的有限非空集合

• 符号串：

  1. 用字母表中符号所组成的任何有限序列
  2. 符号串的长度 = 符号串中所含符号的个数 例：aba的长度为3。记为：|aba|=3
  • $\Phi$ 不含任何元素的空集 { }
  • { $\epsilon$ } ‘’ 集和
  • $\epsilon$ ‘’ 空串
  1. 连接：
     • $\alpha$和$\beta$ $\alpha\beta\neq\beta\alpha$ $s\epsilon=\epsilon s=s$
  2. 前缀：
     • 把从x的尾部删去若干个（包括0）符号之后所余下的部分称x 的前缀
     • $x = abc$
     • $\epsilon,a,ab,abc$
  3. 后缀：
     • $x = abc$
     • $\epsilon,c,bc,abc$
  4. 子串：
     • $y=abcd$
     • $\epsilon,a,b,c,d,ab,bc,cd,abc,bcd,abcd$

• 符号串集合

  1. 和
     • $A+B或A\cup B$
  2. 积
     • $A·B 或 AB$
  3. 方幂 这个是积
     • x为字符串
     • $x^0=\epsilon$ $x^1=x$ $x^2=xx$
  4. 闭包 这个是和
     • $V^*=V^0\cup V^1\cup V^2 ······$ 含 $\epsilon 及 V^0$
  5. 正比包
     • $V^+$ 不含 $\epsilon 及 V^0$

  用A、B、C等表示字母表或符号串集

  用a,b,c,…,S,T,U,…,X,Y,Z 等表示符号

  用s,t,u,…,x,y,z等表示符号串

  

• 考点三

• 上下文无关文法：

  • 所有的产生式左边只有一个非终结符
  • $::= \ \rightarrow —>$ 组成 等价
  • $==> \Rightarrow$推导

• 推导：从语言最大的一个语法范畴（本例中是<句子>）开始，反复用语法规则中“::=” 右侧的符号串取代其左侧符号，直到所得的符号串中不再含有可被替换语法范畴。每次替换称为一步（直接）推导，并用符号“$\Rightarrow$”表示。

• 文法及语言的形式定义 $G$就是文法

  • $G=(V_N,V_T,P,S)$
  • $V_N$：非终结符号符集
  • $V_T$：终结符号集
    1. $V_N\cap V_T = \Phi$
    2. $S\in V_N$
  • P：产生式 （变化的方法）
  • S：语句 开始符号或称作识别符号，它是一个非终结符，至少要在一条规则中作为左部出现

• 四种类型的文法（文法和语言的关系）

  1. 0型文法 0型（递归可枚举）语言 PSG （短语结构文法）

     • P中含有$\alpha(\alpha \in V^+) \rightarrow \beta (\beta \in V^*)$
     • 简单来说就是包含 $aa \rightarrow a | a \rightarrow \epsilon$ （推着推着人没了）
       • 字符串推字符串，越推越少

  2. 1型文法 1 型(前后文有关)文法 CSG

     • ​ $\alpha_1A\alpha_2 \rightarrow \alpha_1\beta\alpha_2 (\alpha_1,\alpha_2\in V^*)(\beta \in V^+)(A\in V_N)$
       • 好像是这样 $V_N\rightarrow V_N or V_T$
       • ？？必须得前后都有东西？

  3. 2型文法 2型 (前后文无关)文法 CFG 上下文无关文法

     • $A \rightarrow \beta (\beta \in V^+)(A\in V_N)$

     • 就像之前的$<句子>\rightarrow<主语短语><动词短语>$

     • $<名词>\rightarrow 书$

  4. 3型文法

     • $A\rightarrow aB \ 或 \ A \rightarrow a$ 其中 $A,B\in V_N \ a\in V_T$ 右线性文法
     • $A\rightarrow Ba \ 或 \ A \rightarrow a$ 其中 $A,B\in V_N \ a\in V_T$ 左线性文法
     • 通常，把左线性文法和右线性文法都称为3型文法（正规文法）
     • 3型文法产生的语言称为3型（正规）语言，它可由有限自动机识别。正规语言可用正规表达式表示。
     • 注：若一文法既含左线性又含右线性产生式，则它不一定是3型文法！
       3型文法还可拓广定义为 $A\rightarrow \alpha B \ 或 \ A \rightarrow \alpha \ \ (\alpha\in V_T^+)$

  5. $L_3\subset L_2\subset L_1 \subset L_0$

• 推导：

还有一种

• 句子和句型
  • 语言：文法推导到最后的所有结果的集合
    
  • 综合的来看
    

• 考点四

• 最左与最右推导

• 最左（右）推导所得句型称为左（右）句型（答案？）
• 其中最右推导成为规范推导，右句型称为规范句型
• 推导的逆过程称作归约，自底向上

• 例如 $a\rightarrow b+i$与$b\rightarrow i$ 如果句子为$b+i$ 优先使用前面的等价反推，而不是使用后面的

• 例如：最左规约 最右推导成就最左规约
  

• 语法树

• 二义性
  • 同结果不同过程
  • 原因：在产生句子的过程中某些直接推导有多于一种选择，推导顺序不同
    

• 考点5短语、直接短语和句柄

• 考点6 无用符号和无用产生式的删除

  • 两部走，简单粗暴
    

• 背后原理

• 例题：

• 考点7 $\epsilon -产生式消除$

• 例题：

第三章 词法分析及语法分析

术语

• 模式(pattern)：产生和识别元素的规则
• 记号(token)： 按照某个模式(或规则)识别出的元素(一组)。记号的区分:记号=记号的类别+记号的属性
• 单词(lexeme)：被识别出的元素自身的值(一个)，也称为词值

左右线性文法构造转换图 考点8

正规文法

• 左线性文法
  • https://blog.csdn.net/Wonz5130/article/details/89326488

• 右线性文法
  

FDA 确定有限自动机 考点9

• 每一项哪些内容

• FDA接受集

非确定有限自动机 NFA

• 更直观，更又好
• 
  • 状态转换函数不唯一为0次及以上的转换
  • 初始集也不唯一
    

• 两者识别能力相同

• NFA转DFA 考点10

• 带空的 考点11

• 考点12

  • 最小化，简单来说就是分类，关键看有没有转换到不同状态
    
    

• 考点13

• 推论中的公理
  

第四章 语法分析器

基础知识

• 消除左递归，好像只要求最简单的直接左递归

• first和follow集

• 回溯：

  • 来自递归下降
    

• 考点14

• 为了消除递归下降的语法分析过程中的回溯，我们必须确定对每个非终结符号应用哪一个产生式而不是一次次地尝试。假设有一组产生式A→α|β，其中α、β的首符号不同并且α、β不能都生成空串ε，对输入符号a，我们必须确定应用哪一个产生式：

  1. 如果a是α的首符号，那么可以应用产生式A→α；如果a是β的首符号，那么可以应用产生式A→β；
  2. 如果α可能生成空串ε，并且a可能紧跟在A之后，那么也可以应用产生式A→α；如果β可能生成空串ε，并且a可能紧跟在A之后，那么也可以应用产生式A→β；
  3. 如果前两步都没有找到匹配的产生式，那么从A推导得到的串的前缀都不能匹配a。

• 实际上，步骤1就是FIRST(α)或者FIRST(β)，步骤2就是FOLLOW(A)，步骤3报告了一个语法错误，经过上述步骤后，我们可以唯一确定一个产生式（或者发现一个语法错误）。到此，我们知道了如何根据FIRST和FOLLOW集合实现无回溯的递归下降的语法分析。

• 考点16

考点

1. 绪论
2. 文法和语言的基本概念和术语
3. 推导、句型、句子以及文法和语言的关系
4. 规范推导、规范规约、推导方法以及语法树和二义性
5. 短语、直接短语和句柄
6. 空符号串—产生式的消除算法
7. 文法的化简与改造：消除无用产生式的算法
8. 正规文法和状态转化图
9. 有限自动机
10. 非确定有限自动机的确定化
11. 具有空符号串动作的FA
12. 确定化有限自动机状态数的最小化
13. 正规式与正规集
14. 预测分析表
15. LL(1)分析法
16. 回溯的消除，LL（1）文法（定义）

作业

• 字母表：
  • 若干元素（符号、字母）组成的有限非空集合，or，一个高级语言程序能够使用全体字符构成集合
• 符号串：
  • 用字母表中符号所组成的任何有限序列
• 推导：
  • 从文法的开始符号出发，反复连续使用所有可能的产生式，将一个符号串中的非终结符用某个产生式右部进行替换和展开，直到全部为终结符为止
• 最左推导：
  • 在整个推导过程中，每一步都是替换句型中最左边的非终结符
• 句型：
  • 若$S$是文法$G$的开始符号，从开始符号$S$符号出发推导出的符号串称为文法$G$的一个句型
• 句子：
  • 若$X$是文法$G$的一个句型，且$X\in V^*_T$，称$X$是文法$G$的一个句子
• 语言：
  • 从文法$G$的开始符号$S$出发，能推导出的句子的全体