概念题
1. 编译器和解释器？典型的编译系统通常包含哪些部分？各个环节的作用是什么？
- 编译器将源程序编译成机器语言，执行机器语言程序速度更快。
- 解释器逐个语句地解释并执行源程序，因此效率低，但错误诊断效果更好。
① 词法分析（Lexical Analysis）：
词法分析器读入源程序的字符流，将其组织成有意义的词素(Lexeme)序列，产生如下的词法单元作为输出：<token-name, attribute-value>
从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。
- 输入：源程序
- 输出：单词符号(词法单元)
- 词法规则表示：正则表达式
- 识别方法：有穷自动机
② 语法分析（Syntax Analysis）：
分析语法结构，并使用各个词法单元的第一个分量来创建中间表示形式，如语法树(Syntax Tree)
- 输入：从词法分析器获得一个由词法单元组成的串
- 输出：验证这个串可以由源语言的文法生成。
- 语法规则表示：上下文无关文法
- 识别方法：语法分析树
③ 语义分析(Semantic Analysis)：
使用语法树和符号表来检查源程序是否和语言定义一致
执行类型检查、自动类型转换等
④ 中间代码生成：
生成等价的低级或类机器语言的中间表示
一般使用三地址代码作为中间表示形式
⑤ 代码优化器：
对中间代码进行改进，以生成“更好”的目标代码。
⑥ 代码生成：
将中间代码映射到目标语言指令。
需要合理分配寄存器以存放变量的值
前端和后端？
（来自第一章）编译器可以分为分析部分和综合部分
分析部分 (前端/Front end)
- 把源程序分解成单词元素，以及相应的语法结构
- 使用这个结构创建源程序的中间表示
- 同时收集和源程序相关的信息，存放到符号表
综合部分 (后端/Back end)
- 根据中间表示和符号表信息构造目标程序
（来自第六章）前端是对源语言进行分析并产生中间表示
处理与源语言相关的细节，与目标机器无关
前端后端分开的好处：不同的源语言、不同的机器可以得到不同的编译器组合
程序语言的定义
一个程序语言主要由语法和语义两个方面定义。
语法：用来形成和产生一个合式（符合某种范式）的程序的规则，包括词法规则和语法规则。
- 词法规则是单词符号的形成规则。单词符号一般包括：各种类型的常数、标识符、基本字、算符和界符等。
- 语法规则是语法单位的形成规则。语法单位包括表达式、语句、分程序、函数、过程和程序等等。
语义：定义每个程序在运行时做什么事情，没有公认的形式系统描述语义。
考语法多一些（语义没有明确定义）
2. 一般文法的形式化定义。
文法：描述语言语法结构的形式规则，即语法规则。
根据语法规则可推导出句子（语言）。
由文法G 的开始符号S 推导出的所有句子构成的集合称为文法G 生成的语言，记为L(G ) 。
形式化定义
文法可以定义为一个四元组
： 终结符（terminal）集合：基本符号，也称为token
： 非终结符（nonterminal）集合：语法成分的符号
P ： 产生式集合
产生式(production) 描述了将终结符和非终结符组合成串的方法α→β读作：α 定义为βα∈( ∪ )+， 且α中至少包含中的一个元素： 称为产生式的头 (head ) 或左部(left side)β ∈( ∪ )* ： 称为产生式的体(body)或右部(right side)
S ：开始符号
S ∈ 。 开始符号(start symbol) 表示的是该文法中最大的语法成分
终结符 a, b, c 非终结符 A, B, C 文法符号 X, Y, Z
文法二义性 Ambiguity
可通过不同的推导过程得到同一个句子。
如果一个文法可以为某个句子生成多棵语法分析树（同样对应多个最左/右推导），这个文法就是二义的。
二义性文法对同一句子有多个最左推导或多个最右推导。
如何消除二义性？
引入规则或优先级来消除文法的二义性。
3. 上下文无关文法和正则文法的形式化定义。
上下文无关文法：对每个语法结构的处理与其所在上下文无关。
可用来处理大多数程序语言。
形式语言分类
从0型文法到3型文法，其限制逐渐增强，因此表达能力减弱。
0型文法 (Type-0 Grammar)
α → β
无限制文法(Unrestricted Grammar)/短语结构文法
(Phrase Structure Grammar, PSG)
∀α → β∈P， α中至少包含1 个非终结符
0型语言
由0型文法G 生成的语言L(G )
1型文法 (Type-1 Grammar)
α → β
上下文有关文法(Context-Sensitive Grammar , CSG )
∀α → β∈P， ｜α｜ ≤ ｜β｜
产生式的一般形式： α1Aα2 → α1βα2 ( β≠ε )
上下文有关语言（ 1 型语言）
由上下文有关文法 (1 型文法) G生成的语言L(G )
CSG 中不包含ε-产生式
（1）式子左边可以有多个字符，但必须有一个终结符（2）式子右边可以有多个字符，可以是终结符，也可以是非终结符，但必须是有限个字符
2型文法 (Type-2 Grammar)
α → β
上下文无关文法 (Context-Free Grammar, CFG )
∀α → β∈P， α ∈ （非终结符集合）
产生式的一般形式： A→β
上下文无关语言（ 2 型语言）
由上下文无关文法 (2 型文法) G生成的语言L(G )
（1）式子左边只能有一个字符，而且必须是非终结符【产生式左侧不允许有终结符】（2）式子右边可以有多个字符，可以是终结符，也可以是非终结符，但必须是有限个字符
3型文法 (Type-3 Grammar)
α → β
正则文法 (Regular Grammar, RG )
右线性(Right Linear)文法： A→wB 或 A→w
左线性(Left Linear) 文法： A→Bw 或 A→w
左线性文法和右线性文法都称为正则文法
（1）式子左边只能有一个字符，而且必须是非终结符（2）式子右边最多有二个字符，而且如果有二个字符必须是一个终结符和一个非终结符（如果只有一个字符，那么必须是终结符）（3）式子右边的格式一定要一致，也就是说如果有一个是（终结符+非终结符）那么所有的式子都必须是（终结符+非终结符）；如果有一个是（非终结符+终结符），那么所有的式子都必须是（非终结符+终结符）
正则语言（ 3 型语言）
由正则文法 (3型文法) G生成的语言L(G )
正则文法能描述程序设计语言的多数单词
补充：构造文法（23年考过）
4. 有穷自动机的形式化定义。
是对一类处理系统建立的数学模型这类系统具有一系列离散的输入输出信息和有穷数目的内部状态 （状态：概括了对过去输入信息处理的状况）系统只需要根据当前所处的状态和当前面临的输入信息就可以决定系统的后继行为。每当系统处理了当前的输入后，系统的内部状态也将发生改变
有穷自动机FA是一种识别器的数学模型，包含：
- 不确定的有穷自动机(Nondeterministicfinite automata, NFA)：边上的标号没有限制，一个符号可出现在离开同一个状态的多条边上，ε可以做标号；
- 确定的有穷自动机(Deterministicfinite automata, DFA)：对于每个状态以及每个符号，有且只有一条边(或最多只有一条边)
DFA是NFA的一个特例 FA边上的标号也就是字母表中的符号。
NFA形式化定义：
DFA形式化定义：
语法分析器分类
常用语法分析方法：
- 自顶向下语法分析器(通常用于处理LL文法)：从语法分析树的根部开始构造语法分析树
- 自底向上语法分析器(通常用于处理LR文法)：从语法分析树的叶子开始构造语法分析树
这两种方法：总是从左到右、逐个扫描词法单元；只能处理特定类型的文法，但足以描述程序设计语言
句柄
句柄：和某个产生式体匹配的子串，代表相应最右推导中的一个反向步骤。
作用：利用句柄进行移入-归约语法分析
5. 推导和归约的形式化定义。
推导：从开始符号出发，每步把一个非终结符号替换为它的某个产生式的体。
定义：如果 是一个产生式，那么
每个推导步骤需要做两个选择：
- 替换哪个非终结符号(顺序问题)
- 选择一个以此非终结符号作为头的产生式（选择问题）
最左推导：每次选择最左非终结符号
最右推导：总是选择最右边的非终结符号
归约：一个与某产生式体相匹配的特定子串被替换为该产生式头部的非终结符号
一次归约是一个推导步骤的反向操作。
自底向上语法分析的目标是反向构造一个推导过程。
根据句柄进行归约
6. 左递归的定义，以及如何消除。
自顶向下的语法分析技术（最左推导）不能处理左递归的情况，因此需要消除左递归。但是自底向上的技术可以处理左递归。
- 输入：没有环和ε产生式的文法G
- 输出：等价的无左递归的文法
通用形式——递归下降分析(Recursive-Descent Parsing)
由一组过程组成，每个过程对应一个非终结符
从文法开始符号S对应的过程开始，其中递归调用文法中其它非终结符对应的过程。如果S 对应的过程体恰好扫描了整个输入串，则成功完成语法分析
可能需要回溯(backtracking)， 导致效率较低
预测分析 (Predictive Parsing)
预测分析是递归下降分析技术的一个特例，通过在输入中向前看固定个数（通常是一个）符号来选择正确的A-产生式。
- 可以对某些文法构造出向前看k个输入符号的预测分析器，该类文法有时也称为LL(k) 文法类
预测分析不需要回溯，是一种确定的自顶向下分析
7. 简述 LL 语法分析。简述递归和非递归的 LL(1)的异同(优缺点)。
LL语法分析是一种自顶向下的分析方法，通常用于分析上下文无关文法。它通过从文法的起始符号开始，逐步向下推导，直至得到输入串。
LL分析器根据文法的推导规则和输入符号选择正确的产生式，因此要求文法是无歧义的，并且符合特定的条件。
- L 代表从左到右扫描输入串（即输入是从左到右处理的）。
- L 代表在每一步选择产生式时，基于当前输入符号进行左推导。
LL(1)文法要求在每一步选择产生式时，必须只依据当前输入符号来决定使用哪个产生式。这使得LL(1)语法分析具有高效的性能。
第一个L表示从左到右扫描输入；第二个L表示产生最左推导
LL(1)的1表示每一步只需要向前看一个输入符号来决定语法分析动作。
递归的预测分析法：在递归下降分析中，根据预测分析表进行产生式的选择；根据每个非终结符的产生式和LL(1)文法的预测分析表，为每个非终结符编写对应的过程
非递归的预测分析：不需要为每个非终结符编写递归下降过程，而是根据预测分析表构造一个自动机，也叫表驱动的预测分析
大题要求：给定文法，写出FIRST集、FOLLOW集、SELECT集+证明该文法是LL(1)文法→构造预测分析表→对于给定句子的分析（非递归，按照栈的形式来写）
【有时需要先消除左递归，对文法做出初步改造再分析】
证明该文法是LL(1)文法， 需要证明同一非终结符的各个产生式的可选集互不相交
LL(1)是自顶向下的语法分析 LR是自底向上的语法分析
8. 简述 LR 语法分析。简述 LR(0),SLR, LR(1)和 LALR 之间的异同。
① LR(k)的语法分析概念：L表示最左扫描，R表示反向构造出最右推导，k表示最多向前看k个符号
② SLR语法分析：根据LR(0)自动机构造语法分析表
SLR（Simple LR）是对LR(0)的扩展，利用文法的Follow 集信息来消除LR(0)中的部分冲突。SLR分析器在决定是否归约时，不仅考虑当前栈顶符号，还结合文法符号的Follow 集来避免冲突。
每个SLR文法都是LR(1)文法。
SLR语法分析表的分析能力较弱
LR(1)语法分析表的状态数量很大
③ LR(1)是最强大的LR分析类型之一，LR(1)分析器在决策时不仅考虑当前栈顶符号，还根据下一个输入符号（即1个后续符号）来决定是否进行移入或归约。
④ LALR的思想就是将具有相同核心的LR(1)项集进行合并
不会产生新的移入/归约冲突，但可能产生新的归约/归约冲突
因为移入动作仅由核心决定，不考虑向前看符号
因此，LALR的算法可描述为：
- 首先构造LR(1)项集
- 若没有冲突，则将具有相同核心的项集合并
- 根据合并后的项集族构造语法分析表
LALR分析器是LR(1)和SLR的折衷方案。LALR通过合并LR(1)中具有相同核心（即栈中符号和状态相同）的状态，减少状态数，解决了LR(1)中表过大的问题。
大题考法：判断是否为LR(0)文法：写出分析表，不存在语义分析动作冲突，因此为LR(0)文法
先列出产生式→增广文法→写出项集→利用GOTO函数得到最终的项集→构建语法分析表
大题考法：写出SLR(1)分析表
在LR(0)的基础上，考虑FOLLOW集，避免冲突
若证明是否是SLR(1)文法：写出LR(0)自动机，如果某个项集中存在冲突，则不是LR(0)文法；若能通过写出FOLLOW集解决冲突（见下方注释讲解），则是SLR(1)文法；
大题考法：写出LR(1)分析表
证明LR(1)文法：写出LR(1)的DFN，通过展望符可以解决冲突即为LR(1)文法
语法制导SDD翻译
语法制导翻译：使用上下文无关文法来引导对语言的翻译，是一种面向文法的翻译技术。
SDD是对上下文无关文法（CFG）的推广，将每个文法符和一个语义属性集合相关联。
将每个产生式和一组语义规则相关联，这些规则用于产生该产生式中各文法符号的属性值。
如果X是一个文法符号，a是X的一个属性，则用X.a表示属性a在某个标号为$X 的分析树结点上的值。
SDT是对SDD的补充
- 在产生式右部嵌入了程序片段的CFG，这些程序片段称为语义动作。按照惯例，语义动作放在花括号内
- 一个语义动作在产生式中的位置决定了这个动作的执行时间
SDD：
是关于语言翻译的高层次规格说明
隐蔽了许多具体实现细节，使用户不必显式地说明翻译发生的顺序
SDT：
可以看作是对SDD的一种补充，是SDD的具体实施方案
显式地指明了语义规则的计算顺序，以便说明某些实现细节
//在语法制导翻译中，空返产生式的作用（M->e）
记录下一个即将产生的四元式的地址。？？
结合具体例子谈一谈回填思想
回填技术
生成跳转指令时不指定跳转目标，而是使用列表记录这些不完整指令的标号
当知道正确的跳转目标时再填写目标
列表中的每个指令都指向同一个目标
基本思想
记录B中跳转指令如goto S.next的标号，但不生成跳转目标，这些标号被记录到B的综合属性B.falselist中
当S.next的值成为已知时 (即S的代码生成完毕时)，把B.falselist中的所有指令的目标都填上这个
9. 三地址代码的定义以及其在编译过程中的作用。
三地址代码是语法树或DAG的线性表示形式
一条指令的右侧最多有一个运算符
三地址代码的名字对应语法树或DAG的内部节点
三地址代码适用于目标代码的生成和优化
三地址代码包含地址和指令：
地址包括：（源程序的）名字、常量、临时变量
指令包括：
x = y op z
x = op y
x = y
goto L
if x goto L 或 if False x goto L
if x relop y goto L
x = y [ i ] 或 x [ i ] = y
x = &y， x = *y, *x = y
语句：do i = i + 1; while (a[i] < v);
三地址代码是一种中间代码形式，它将高级语言的语句转换为三元组的形式，三地址代码包含三个部分：操作符、源操作数和目标操作数。三地址代码的使用可以使得编译器在优化代码时更加方便，同时也使得目标代码更加简洁和易于理解。（来自网络）
10. 文法符号的综合属性和继承属性的定义。
综合属性：用于自下而上的传递信息的属性，由其子节点的属性值确定
继承属性：用于自上而下的传递信息的属性，由其父节点或、和兄弟节点的某些属性值确定。
综合属性 synthesized attribute
在分析树上结点N的综合属性通过N的子节点和N本身的属性值来定义。
终结符可以具有综合属性。终结符的综合属性值是由词法分析器提供的词法值，因此在SDD中没有计算终结符属性值的语义规则。
继承属性 inherited attribute
在分析树上N结点的继承属性只能通过N的父节点、兄弟节点或者N本身的属性值来定义。
终结符没有继承属性，终结符从词法分析器处获得的属性值被归为综合属性值。
副作用 属性文法
在SDD中，副作用是指在语法规则的语义动作中对属性进行修改或操作的行为。一个没有副作用的SDD也称为属性文法（在属性文法的语义规则中，仅仅通过其它属性值和常量来定义一个属性值）
依赖图
- 依赖图是一个描述了分析树中结点属性间依赖关系的有向图
- 分析树中每个标号为X的结点的每个属性a都对应着依赖图中的一个结点
- 如果属性X.a的值依赖于属性Y.b的值，则依赖图中有一条从Y.b的结点指向X.a的结点的有向边
11. S-SDD 和 L-SDD 的定义以及它们之间的关系。
S-SDD（S属性定义）
定义：仅仅使用综合属性的SDD
如果一个SDD是S属性的，可以按照语法分析树节点的任何自底向上顺序来计算它的各个属性值
S-属性定义可以在自底向上的语法分析过程中实现
仅仅使用综合属性的SDD称为S属性的SDD，也叫S-属性定义，S-SDD。
L-SDD（L属性定义）
思想：在一个产生式所关联的各属性之间，依赖图的边可以从左到右，但不能从右到左
注意：若同时有综合属性和继承属性，不一定有可行的属性求值顺序。但是L-属性定义一定有可行顺序
一个SDD是L-属性定义，当且仅当它的每个属性要么是一个综合属性，要么是满足如下条件的继承属性：假设存在一个产生式，其右部符号(1≤i≤n)的继承属性仅依赖于下列属性：
- A的继承属性
- 产生式中左边的符号 的属性
- 本身的属性，但的全部属性不能在依赖图中形成环路
关系：每个S-属性定义(S-SDD)都是L-属性定义(L-SDD)
大题考法：SDD转为SDT L-SDD用LR语法分析的文法修改规则
S-SDD→SDT转换规则：
- 将每个语义动作都放在产生式的最后
- 因为S-SSD只有综合属性
L-SDD→SDT转换规则：
- 将计算某个非终结符号A的继承属性的动作插入到产生式右部中紧靠在A的本次出现之前的位置上
- 将计算一个产生式左部符号的综合属性的动作放置在这个产生式右部的最右端
在LR语法分析中实现SDT
实现方法：
- SDT可以在LR语法分析过程中实现
- 当归约发生时执行相应的语义动作
如何修改文法来利用LR语法分析进行翻译？
- 首先构造SDT，在各个非终结符之前放置语义动作来计算它的继承属性，并在产生式后端放置语义动作计算综合属性
- 对每个内嵌的语义动作，向文法中引入一个标记非终结符来替换它。每个这样的位置都有一个不同的标记，并且对于任意一个标记M都有一个产生式M→ε。
- 如果标记非终结符M在某个产生式A→α{a}β中替换了语义动作a，对a进行修改得到a'，并且将a'关联到M→ε上。动作a'
(a) 将动作a需要的A或α中符号的任何属性作为M的继承属性进行复制
(b) 按照a中的方法计算各个属性，但是将计算得到的这些属性作为M的综合属性
大题考法：画出注释语法分析树
后缀表达式
后缀表达式又称为逆波兰表示法：
把运算对象写在前面，把操作符写在后面（后缀）
这种表示法无需使用括号，例：(a+b)*c可写成ab+c*
有向无环图DAG 语法树
语法树也是一种中间表示形式：
它刻画了源程序的自然层次结构
适用于静态类型检查等处理
DAG
DAG是一种更简洁的中间表示
用同样的语法制导定义构造语法树和DAG
DAG的区别在于，每次构造新节点时首先检查是否已存在
因此DAG能够自动提取左公因子
对比语法树和DAG
语法树中，公共子表达式每出现一次，就有一棵对应子树
有向无环图(Directed Acyclic Graph,DAG) 能够指出表达式中的公共子表达式，更简洁地表示表达式
12. 机器无关优化中的全局优化和局部优化相关概念。
什么是机器无关优化？机器无关代码优化的任务：
- 输入：直接翻译的中间代码
- 输出：优化后的中间代码
- 优化方法：构造流图
- 局部优化：DAG转换
- 全局优化：数据流分析
全局优化：
检查信息如何在一个程序的多个基本块之间流动
全局公共子表达式、复制传播、死代码消除、代码移动、归纳变量和强度消减
局部优化：
仅对各个基本块本身进行局部优化
局部公共子表达式、消除死代码、代数恒等式、数组引用、指针赋值和过程调用
活跃变量 不活跃变量
i：x = … 对x赋值
j：y = x op z j语句的运算分量为x
且从i 开始有一条路径到达j，且路径上没有对x 赋值，那么j 就使用了i 处计算得到的x的值z
我们说变量x 在语句i 后的程序点上活跃
- 程序执行完语句i 时，x 中存放的值将被后面的语句使用
- 不活跃是指变量的值不会被使用，而不是变量不会被使用
如何计算活跃性与后续使用信息？
输入
基本块B，开始时B中的所有非临时变量都是活跃的
输出
各个语句i上变量的活跃性、后续使用信息
方法
从B的最后一个语句开始反向扫描
对于每个语句i：x = y + z
- 令语句i 和x、y、z 的当前活跃性信息/使用信息关联
- 设置x 为“不活跃”和“无后续使用”
- 设置y 和z 为“活跃”，并指明它们的下一次使用设置为语句i
![7) a[t4] a+t4*w = 0.0 不能被设置为不活跃](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F8a3485cc-1a44-46e7-a6d3-30753d51dd42%2F9d0b5d67-f26e-471d-aaac-59c6117a179b%2Fimage.png?table=block&id=165eefba-b209-802f-b14c-dbf9ccb20c1d&t=165eefba-b209-802f-b14c-dbf9ccb20c1d&width=511&cache=v2)
中间代码优化有哪几种
会让列出几个常用手段，要会列出！记住概念！！！
全局优化方式：
1. 全局公共子表达式
如果E
- 在某次出现之前必然已被计算过，且
- E的运算分量在该次计算后没有被改变
- 那么，E的本次出现就是一个公共子表达式
如果上次E值赋给了x，且x值没有被修改过，那么我们可使用x，而无需计算E
2. 复制传播
形如u =v的复制语句使得语句后面的程序点上u的值等于v的值
- 如果在某个位置上u一定等于v，那么可以把u替换为v
- 有时可以彻底消除对u的使用，从而消除对u的赋值语句
消除公共子表达式时引入了复制语句
如果尽可能用t来替换c，可能就不需要c=t这个语句
3. 死代码消除
如果一个变量在某个程序点上的值可能会在之后 被使用，那么这个变量在这个点上活跃的；否则 这个变量就是死的，此时对该变量的赋值就是没 有用的死代码
死代码多半是因为前面的优化而形成的
4. 代码移动
循环中的代码会被执行很多次
- 循环不变表达式：循环的同一次运行的不同迭代中，表达式的值不变
把循环不变表达式移动到循环入口之前计算可以提高效率
- 循环入口：进入循环的跳转都以这个入口为目标
5. 归纳变量和强度消减
归纳变量
- 每次对x赋值都使x增加c
- 归纳变量可以通过每次迭代进行一次简单的增量运算（加法或减法）来计算。
强度消减
- 把一个高代价的运算（比如乘法）替换为一个代价较低的运算（比如加法）
- 如果一组归纳变量的值的变化保持步调一致，可以将这组变量删剩一个。
- 处理循环时，可按照“从里到外”的方式进行工作。
局部优化方式：
1. 寻找局部公共子表达式
建立某个结点M之前，检查是否存在一个结点N，它和M具有相同的运算符和子结点 (顺序也相同)
如果存在，则不需要生成新的结点，用N代表M
两个b+c不是公共子表达式，因为两个b的值不一样，在中间过程b被重新赋值了
2. 消除死代码
在DAG图上消除没有附加活跃变量的根结点，即消除死代码
如果图中c、e不是活跃变量 (但a、b是)，则可以删除标号为e、c的结点
3. 基于代数恒等式的优化
4. 数组引用的表示
a[j]可能改变a[i]的值，因此不能像普通运算符一样构造结点
- x = a[i] a[j] = y z = a[i]
从数组取值的运算x = a[i]对应于=[]的结点
- 这个结点的左右子节点是数组初始值a0和下标i
- 变量x是这个结点的标号之一
对数组赋值的运算a[j] = y对应于[]=的结点
- 这个结点的三个子节点分别表示a0、j和y
- 杀死所有依赖于a0的变量
5. 指针赋值和过程调用
通过指针进行取值/赋值：x = *p、*q = y
- x使用了任意变量，因此无法消除死代码
- *q = y对任意变量赋值，因此杀死了全部其他结点
可通过 (全局/局部) 指针分析部分地解决这个问题
过程调用也类似，必须安全地假设它
- 使用了可访问范围内的所有变量
- 修改了可访问范围内的所有变量
基本块划分
中间代码划分成为基本块 (Basic block)，基本块的特点：
- 控制流只能从基本块的第一条指令进入
- 除基本块的最后一条指令外，控制流不会跳转/停机
流图的结点是基本块，流图的边指明了哪些基本块可以跟在一个基本块之后运行
输入：三地址指令序列
输出：基本块的列表
可能会考基本块划分
方法：
确定首指令leader (基本块的第一个指令)：
- 第一个三地址指令
- 任意一个(条件或无条件) 转移指令的目标指令
- 紧跟在一个(条件或无条件) 转移指令之后的指令
确定基本块：
- 每个首指令对应于一个基本块：从首指令开始到下一个首指令
往年题
2024.06（大数据） | |
ㅤ | |
2023-2024（软工） | |
2022-2023 | |
2021-2022 | |
2020-2021 | |
2019-2020 |
听说CSDN上面很多计算机学院的题，其中根据sdt写四元式和dag优化目标代码这种，软件几乎是不太会考的
2024 大数据
听说多了判断题
2022-2023 第二学期大数据
一、简答题（5*5）
- 画出编译原理的程序框图
- 什么是文法的二义性？为什么要消除二义性？如何消除二义性？
- 简述推导和归约的概念
- 简述递归下降语法分析技术的基本思想
- 简述划分基本块的算法
二、词法分析（20）
根据正则式写出NFA ,确定化，最小化。
三、语法分析
G(S)文法如下：
S→CCC→cCC→d
- G(S)对应的First和Follow是什么？证明是G(S)是LL(1)。
- 写出G(S)的预测分析表。
- 根据预测分析表，写出cdccccd的TOP-DOWN的推导过程。
四、语义分析
给出以下文法：
E→aA|bBA→cA|dB→cB|d
- 证明是LR(0)
- 写出预测分析表
- 根据预测分析表，写出accd自底向上的推导过程
五、语法制导翻译
写出语法制导翻译的基本思想。并说明抽象语法树在语法制导翻译中的角色。
六、代码优化
说明局部优化和全局优化的不同。写出至少四个优化方法，并简述其算法。
2023-2024 期末
2023.12.18
一、简答题
1.什么是编译？编译系统主要由哪几部分构成？
2.什么是有穷自动机？NFA和DFA的区别是什么？
3.给定一个文法s-sas/空，判断它是否有二义性。
4.什么是推导，什么是归约。
5.根据要求写出文法。
给出正规式构造文法 （ab的nc的n）
二、应用题
1.写出倒数第二个字符是1的比特串的文法，画出NFA，DFA和最小化DFA
2.给定了一个文法，证明该文法是LL1文法，画出预测分析表，给出id+id*id的推导过程
3.证明该文法是LR1文法而不是LR0文法，并画出项集族和预测分析表。
给出串（忘了是啥了）的推导过程
三、简答题（语法制导翻译和代码优化）
1.给定了产生式和对应的语法注释。请你画出依赖图。
解释什么是综合属性，什么是继承属性
画出6+9*4的注释分析树（大意是这样）
2.举出代码优化的至少四种方法，并解释
2020-2021
一、简答题（30分）
- 编译程序由哪几部分构成，各自作用是什么？
- 简述算符优先文法原理
- 代码优化目的是什么？有哪些代码优化方法？简述技术。
- 写出比101大的二进制数的正规表达式
- 解释语法制导翻译（是2004年原题 网上可以找到）
二、NFA 确定化 最小化（也是2004年原题）
三、LL(1)文法分析表
四、LR(1)文法 画分析表
五、语法制导翻译 控制语句
六、DAG优化中间代码 生成目标代码