编译原理复习重点

正课：【编译原理】哈工大公开课（高清版）_哔哩哔哩_bilibili

里面的题目与总结很好，强烈推荐！B 站必看编译原理—混子速成期末保过

标 ☆ 的需要重点掌握

第一章概论

编译系统八个组成部分

分析（前端）

词法分析：对构成源程序的字符进行扫描和分解，识别单词(记号)

语法分析：层次结构分析，建立语法树

语义分析、中间代码生成：

考察结构正确的句子是否语义合法，合法则翻译成中间代码。语义分析非常困难，编译器仅完成有限的语义分析。

合成（后端）

包括中间代码优化、目标代码生成和目标代码优化。

代码优化：对中间代码进行优化处理

目标代码生成：把中间代码变换成特定机器上的目标代码

目标代码：编译器的最终输出结果，一般是机器代码

符号表：用来保存已收集信息的数据结构，常用线性表（数组、链表）和 Hash 表实现。信息表管理即符号表管理。

一个表项包括名字域(key)和信息域(value)，名字域可采用直接存储：每个标识符分配最大允许空间，间接表技术：名字域存放指针

属性域可存放多个子域及标志位。

出错处理的原因：编译各个阶段都可能发现错误。内容：报告错误的性质、位置，尽量缩小范围、查找出更多的错误。

第二章文法和语言

符号串的运算

字母表也就是符号集，符号串：由字母表中的符号组成的任何有穷序列

在符号串中，符号是有顺序的，顺序不同，代表不同的符号串，如 ab 和 ba 是不同的不含任何符号的符号串称为空串，用 ε 表示，注意{ε}不等于{}（后者为空集）

PS：↑ 代表次幂运算

闭包

例题：求符号串个数

文法 G[S]

定义：四元组定义(VN 非终结符集, VT 终结符集, P 产生式集, S 开始符号)，不过一般用产生式表达即可

S 是一个非终结符（大写字母或用尖括号），且至少要在一条产生式的左部出现，一般在第一条产生式（因为是开始符号）

①0 型文法：产生式左部至少有一个非终结符
②1 型文法（上下文有关）：产生式左部字符数量一定小于等于右部字符数量，不能越推越少（右比左长）
③2 型文法（上下文无关）：左部只能有唯一一个非终结符
④3 型文法（正规文法、右线性文法）：产生式右部只能以终结符开始
⑤ 其中，这四种文法之间是包含关系

语言、句子

由文法 G 生成的语言记为 L(G),它是文法 G 的一切句子的集合。文法等价：L(G1)=L(G2)。

资料：编译原理文法与语言的相关习题

例题： Z→aZb，Z→ab 则 L(G[Z])的全部元素为{ $a^{n}b^{n}$ | n $\geq$ 1}

例题:构造符合语言的文法

例题：求 L(G)

回答时直接写集合或者用文字回答

推导与归约

直接推导就是用右部替换产生式的左部的过程，直接规约是用左换右，用且只用一条产生式

直接子树：直接子树是子树的一个特例，它特指树中某个节点的直接子节点及其所有后代节点构成的树。换句话说，直接子树是以某个节点的直接子节点为根节点的子树。

ch02-直接子树示例

例题：判断句子是否在 L(G)中，根据文法给出句子的最左最右推导

例题：判断二义性文法

ch02-判断二义性文法

☆：例题：求短语、直接短语、句柄（难）

ch02-求短语直接短语句柄

编译原理之短语&直接短语&句柄定义与区分_编译原理短语,直接短语,句柄-CSDN 博客

例题：文法化简

尽情删，带了会陷入死循环的符号的产生式都删除

第三章词法分析

词法分析的任务是对字符串表示的源程序从左到右地进行扫描和分解，据语言的词法规则识别出一个一个具有独立意义的单词记·号。

源程序——>单词记号，输出的单词记号的表示形式：单词种别，单词自身的值

状态转换图

节点代表状态，用圆圈表示；有限个状态，其中有一个为初态，至少要有一个终态

状态之间用箭弧连接。箭弧上的标记（字符）代表在射出结点（即箭弧始结点）状态下可能出现的输出字符或字符类；

例题：根据文法画状态转换图

终态：某个终结符或终结符号 F。步骤：先构造语法树，然后根据输入的字符进行状态转换。除终态外，状态里一般是非终结符。

ch03-根据文法画状态转换图

例题：根据状态转换图写文法

状态转换矩阵

纵轴为非终结符，横轴为终结符。要能将文法与状态转换矩阵互相转化。

正则表达式（正规式）

**和一般的正则表达式在语法上有所不同，**更精确、严格、有限

给定字母表 Σ, Σ 上的正则表达式由且仅由以下规则定义:

ϵ 是正则表达式； ∀a ∈ Σ, a 是正则表达式；如果 r 是正则表达式, 则 (r) 是正则表达式；

如果 r 与 s 是正则表达式, 则 rs(连接), r|s(可选), r∗(闭包) 也是正则表达式。

例题：根据模式串求正则式

匹配模式串"Chapter i"或“Section j”: (Chapter|Section)\s\d+

Chapter：直接匹配文本字符串"Chapter"。
\s：匹配任意空白字符，例如空格、制表符等。它用于匹配"Chapter"与整数之间的空格。
\d+：匹配一个或多个数字。\d代表数字字符（0-9），而+表示前面的字符（即数字）可以重复一次或多次。

NFA

非确定有穷自动机，定义是一个五元式，初态不唯一，有向边上可以为字符串，

一个状态对某个字符可以有多条出边，可以有标识为 ϵ 的边。NFA M 所能接受的全部字符串，记为 L(M)

正则表达式转 NFA

最外层符号逐步替换

☆： DFA

确定有穷自动机，初态唯一，有向边上只有一个字符，不允许 𝜀 出现在边上，一个状态对某个字符最多只有一条出边

**等价性：**对于每个 NFA M 存在一个 DFA M’，使得 L(M)=L(M’)。DFA 是 NFA 的特例。

参考资料：编译原理正则表达式到 NFA&DFA 的转化 CSDN 博客

编译原理第三章（有穷自动机 DFA、NFA 与正则文法、正规式）CSDN 博客

☆： NFA 确定化（转 DFA）和 DFA 最小化

NFA 转 DFA 步骤：

ε-closure 运算：设 I 是状态集的一个子集，则 I 的 ε-闭包 ε-closure(I) 为：

若状态 s∈I，则 s∈ε-closure(I)若状态 s∈I，则从 s 出发经过任意条 ε 弧可以到达的任何状态 s’，都属于 ε-closure(I)

再定义 Ia 运算：设 a 为 Σ 中的一个字符，定义 Ia=ε-closure(J)，

其中，J 为 I 中的某个状态出发经过一条 a 弧而到达的状态集合，Ia 即是为这样的集合作 ε-闭包

例题

ch03-NFA转DFA例题2

练习题：确定化

练习题：最小化

先把不可能的状态删掉

例题：构造正规式的 DFA

先把 S,A,F 写出来，用空串边连接。注意闭包运算中包含空串。

第四章语法分析

语法树

如果一个文法存在某个句型对应两棵或两棵以上不同的语法树，则称为这个文法为二义文法。

按照语法树的建立方法，可以把语法分析分为两类：自上而下语法分析法与自下而上语法分析法。

目标对任何输入串是用确定的语法分析建立对应唯一的语法树。

根据文法构建的语法树

自顶向下的语法分析

核心：推导。参考资料：编译原理-语法分析_编译原理语法分析-CSDN 博客

自上而下的语法分析方法就是对任何输入串（由 token 串构成的源程序），试图用一切可能的办法，从文法开始符号（根结点）出发，自上而下的为输入串建立一棵语法树，或者说，为输入串寻找一个最左推导。

回溯：产生的根本原因在于某个非终结符的多个候选式存在公共左因子，消除回溯的方法是改造的方法是提取公共左因子

对A→δα1|δα2|…|δαn，提取公共左因子后为：
 	A->δA'
    A'->α1|α2|…|αn

左递归

会导致无限循环

直接左递归	若文法 G 中有形如 A->Aα 的产生式，则称该产生式对 A 直接左递归。
间接左递归	若文法 G 中没有形如 A->Aα 的产生式，但是 A 经过有限步骤推导可以得到 A->Aα，则称该产生式对 A 间接左递归。

例题：消除左递归

消除直接左递归：实际是将直接左递归改成了直接右递归，这样在最左推导中就不会陷入死循环
假设文法中A的产生式如下：
    A->Aα1|Aα2|β1|βn
则消除直接左递归如下所示：
    A->β1A'|βnA'
    A->α1A'|α2A'|ε

☆： LL(1)

LL(1) 分析法又称预测分析法，是一种不带回溯的且无二义性的非递归自上而下分析法。代码实现常用。

第一个“L”表明自上而下分析是从左至右扫描输入串的。

第二个“L”表明分析过程中将用最左推导。“1”表明只需向右查看一个符号就可决定如何推导，即选择哪个产生式（规则）进行推导。

预测分析法：

LL（1）分析法的基本思想是根据输入串的当前输入符号来唯一确定选用某条规则（产生式）来进行推导。当这个输入符号与推导的第一个符号相同时，再取输入串的下一个符号，继续确定下一个推导应选的规则。如此下去，直到推导出被分析的输入串为止。

一个 LL（1）分析器通常由以下三个部分组成：

LL（1）分析表（也称预测分析表）：它用一个矩阵（或二维数组）表示，概括了相应文法的全部信息。矩阵的每一行与文法的一个非终结符相关联，而每一列与文法的一个终结符或界符“#”相关联。
先进后出分析栈：用于存放分析过程中的文法符号。分析开始时，栈底先放入一个“#”，然后再压入文法的开始符号。
控制程序（表驱动程序）：用于根据分析表和栈中的符号来控制分析过程。

初态：栈：结束符# 和开始符 S，指针：输入串 ω 的第一个符号

动作选择：栈顶符号为 x，输入符号为 a

1、若 x == a == #，则符号串和栈均为空则输入串 ω 是文法的一个合法句子，分析过程结束

2、若 x == a ≠ #，则 x 出栈，指针移向下一个符号，继续下一次匹配

3、若 x 为非终结符，则查分析表，若 M[x，a]中存放 x→α，则 x 出栈，将 α 串逆序压入栈中，

若 M[x，a]中为出错标志，则调用出错处理程序 error( )

First(α)是文法 G 的符号串 α 的首终结符集，即由该候选式推导出的所有符号串中的第一个终结符或可能的 ε的集合**，**其中 α 可能是文法符号、ε 或者候选式，或候选式的一部分。当 α 是终结符，则 First(α)就是 α

Follow(A)就是所有句型中出现在紧接 A 之后的终结符号或者#,#表示输入符号串的结束标记，

Follow 集是由 First 集合决定的

例题：求 First 集和 Follow 集

例题：判断是否 LL(1)

重要例题：预测分析表

预测分析表的每个单元格都表示一个特定的非终结符在给定终结符（或输入结束符）下的推导规则。

如果某个单元格有内容，则表示在该情况下应该应用相应的推导规则；如果单元格为空（即 error），则表示在当前输入符号下，无法确定应用哪个推导规则（意味着输入不符合文法规则）。

第一问是为了让第二问构造起来更方便

递归下降分析方法

算法：最左深度搜索。递归下降分析是直接以程序的方式模拟产生式产生语言的过程，即为每一个非终结符构造一个函数，每个函数的函数体按非终结符的候选式分情况展开，遇到终结符就进行比较，看是否与输入的符号相同；遇到非终结符就调用该非终结符对应的函数。

代码实现 LL(1)：编译原理：LL(1)语法分析器的实现（内含代码详细注释)-CSDN 博客

【编译原理】实验三 LL(1)分析法(LL1 分析表的自动生成)_ll(1)分析法实验-CSDN 博客

自底向上的语法分析

核心：规约。分析能力：LR(0)<SLR(1)<LALR(1)<LR(1)。范围：LR(0)>SLR(1)>LR(1)。不用消除左递归

**前缀：**从一个符号串 w 的尾部删去 0 个或若干个符号之后剩余的部分称为 w 的前缀。原符号串本身也是前缀，但不是真前缀。

w=abcd，那么它的前缀可以是 a、ab、abc、abcd。后缀：和前缀概念类似。

活前缀：不包含句柄右侧任一符号的规范句型的前缀称为该句型的活前缀。

例如：Bab 是下面那个文法的一个句型，其中 b 是句柄。那么针对这个句型的活前缀有：ε、B、Ba 和 Bab

☆： LR(0)

分析表构造关键是画出 DFA

编译原理 12：活前缀、项目集规范族、LR（0）分析表_LR(0)项目集的计算-CSDN 博客

编译原理 LR(0)项目集规范族的构造和分析表的构造-CSDN 博客

族：元素是集合的集合

移进-归约冲突：某一产生式的右部是另一产生式右部的前缀

归约-归约冲突：不同产生式有相同的右部或者产生式的右部是另一产生式右部的后缀

LR(0)构造分析表步骤

1.扩展文法（仅在开始符号对应的产生式不止一个时使用）

2.求出项目集规范族 3.构造 DFA 4.构造 LR(0)分析表（根据自己画出的 DFA 图，将分析表填充）

例题：判断 LR(0)并构造分析表

构造 DFA：

分析表如下：

☆： SLR(1)

4. 构造【SLR(1)分析表 + 判断是否是 SLR(1)文法】_构造 slr(1)分析表-CSDN 博客

2023 最新编译原理期末救急速成构造 SLR(1)分析表

1.拓广文法（加 S`） 2.自动机(加点)，点在式子最后就是归约 3.分析表（必须要做好第一步第二步）

☆： LR(1)

《编译原理》LR 分析法与构造 LR(1) 分析表的步骤 - 例题解析_编译原理 lr(1)题库-CSDN 博客

编译原理实验之 LR(1) 分析器设计 | 作弊

分析表与栈

LALR(1) (了解)

同心：如果除展望符外，两个 LR(1)项目集是相同的，则称这两个 LR(1)项目集是同心的。寻找具有相同核心的 LR (1) 项集，并将这些项集合并为一个项集。所谓项集的核心就是其第一分量的集合。然后根据合并后得到的项集族构造语法分析表。

练习题

ch04-语法分析练习题

第五章语义分析与代码生成

语义分析的任务

1、语义检查：类型是否相符、变量是否声明

2、语义处理：将执行语句翻译成中间代码

语法制导的翻译方法：即在语法分析建立 AST 的同时，直接生成中间代码，适用于文法比较简单的语言

每个产生式配上一个语义子程序，当对产生式进行推导或归约时，调用相应的语义程序，进行语义分析

中间代码生成过程：就是遍历“头结点”所指向链表的过程

翻译成三地址码

选择语句翻译

if a<b then a:=a+b else a:=a-b 的翻译
   if a < b goto 102
   goto 105
   t1 = a + b
   a = t1
   goto 107
   t2 = a - b
   a = t2

☆：循环语句翻译

while a>b do if c<d then e:=f+g; 的翻译
   if a > b goto 102
   goto 107
   if c < d goto 104
   goto 106
   t1 = f + g
   e = t1
   goto 100

函数调用翻译

不考

栈寻址与栈帧（了解）

函数栈帧（详细图解）_函数调用栈帧过程(带图详解)-CSDN 博客

第六章中间代码生成

基本块划分

基本块：程序中的一段语句序列，只有一个入口语句和一个出口语句

**入口语句：**程序的第一条语句，能由转向语句转移到的语句，紧跟在转向语句后的语句；**出口语句：**转向语句、停止语句

划分基本块的算法：

1、找出所有入口语句和出口语句 2、划分基本块 3、删除未被划入基本块的语句

例题

程序流图（了解）

程序流图 G = ( N , E , n0)，程序结构的图形表示，

N 为结点的集合，每个结点代表一个基本块，E 为有向边的集合，n0 程序第一条语句的基本块结点

基本块 Bi 与 Bj 之间有一条有向边：

1：Bj 紧跟在 Bi 之后，且 Bi 的出口语句不是无条件转向或停止语句

2：Bi 的出口语句为转向语句，其转向点恰为 Bj 的入口语句

代码优化

优化代码题可以将步骤写清楚详细一些

局部优化

基本块内的优化。合并已知量/常量传播，删除公共子表达式（将公共子表达式提取出来成为单独的表达式），删除无用赋值（赋值后从未使用），删除死代码（条件永为真或永为假导致某段代码永远不会被执行），复写传播

例题：

循环优化（了解）

必经结点集：程序流图中结点 n 的所有必经结点的集合，称为 n 的必经结点集，记为 D(n)

程序流图 G = (N, E, n0)中，n → d 是回边，M 是 G 中到达 n 而不经过 d 的结点集，则{n, d} ∪ M 构成一个循环

全局优化的一种，方法有：

1、代码外提：循环不变运算提到代码外

2、强度削弱：i 每循环一次增加或减少 c，j 相应增加或减少 c1c，因此，计算 j 的乘法可由加法来代替：j= j + c1*c

3、删除归纳变量：如果“基本归纳变量”为判断条件，且基本归纳别无它用，则可将其删除。

例如：j = 10 * i + 5，判断条件为 i < 10 ，则将 i < 10 改为 j < 105，同时删除 i 相关的语句

寄存器分配

任务：将中间代码翻译成等价的目标代码。输入：中间代码、符号表；输出：目标代码：机器代码、汇编码

例题：目标代码生成（了解）

目标机指令系统的指令分成如下的形式(和汇编类似)：
存取指令：LD ST
输入输出：IN OUT
运算型指令：ADD SUB MUL DIV GT GE...
转移型指令：JMP  JMPT JMPF
地址运算指令和块传递指令：LEA  MOVEB

循环中的寄存器分配（了解）：固定分配寄存器以提高效率

☆：活跃变量分析

活跃变量的定义：在程序的控制流图中，如果存在一条从某个程序点开始的路径，沿途会用到变量 x 在该点的值，则称变量 x 在该点是活跃的。反之，如果不存在这样的路径，则变量 x 在该点不活跃

变量的活跃范围或作用域：指的是变量在代码中能够被访问或识别的区域。

活跃区间：变量从一次定值（即被赋予一个值）到下一次定值之前的最后一次引用之间的区间。这个区间描述了变量在程序执行过程中的生命周期。

PS：定值-引用链（Definition-Use Chains）是活跃变量分析中的一个概念，它表示变量的一个赋值到所有可能的引用点的集合。

变量的活跃信息是反向传播的！！

def[n]：在基本块 n 中定值但定值前在 n 中没有引用的变量集合 use[n]：在基本块 n 中引用但引用前在 n 中没有被定值的变量集合

in[n]：在基本块 n 的入口处的活跃变量集合 out[n]：在基本块 n 的出口处的活跃变量集合

反向传播的迭代算法

ch06-活跃变量分析反向传播

ch06-活跃变量分析示例

☆：线性扫描算法

伪代码：LinearScanRegisterAllocation
    active ←{}   //这是分配了寄存器的变量集合
    foreach live interval i, in order of increasing start point //依次按起点先后遍历各活跃区间
        ExpireOldIntervals(i)  //把i开始前变不活跃变量占用寄存器空间腾出来。
        if length(active) = R then //如果寄存器不够了
            SpillAtInterval(i) //溢出i
        else
            register[i] //从可用的寄存器中选一个,将i加入active集合，并按终点从小到大进行排序
ExpireOldIntervals(i)//把i开始前就变得不活跃变量占用寄存器空间腾出来。
    foreach interval j in active, in order of increasing end point
        if endpoint[j] ≥ startpoint[i] then
            return
        remove j from active
        add register[j] to pool of free registers
SpillAtInterval(i)//将i的endpoint跟当前所有占用寄存器的变量的endpoint比，endpoint最大的不占寄存器被溢出。
    spill ← last interval in active // 把当前end point最大的进行溢出
    if endpoint[spill] > endpoint[i] then
        register[i] ← register[spill]
        location[spill] ← new stack location
        remove spill from active
        add i to active, sorted by increasing end point
    else
        location[i] ← new stack location

图着色算法：

假设对一个图进行 k 着色，先找到一个少于 k 个边的节点。如果从图中删除该节点并对剩下的部分着色，之后再重新添加它，便可以找到这个节点的颜色。原因：少于 k 个邻居，一定有颜色剩余。

从图中找到一个边少于 k 的节点，删除它。递归地为图形的其余部分着色。重新添加被删除节点，为其指定有效颜色

SSA 静态单赋值（了解）

SSA（Static Single Assignment，静态单赋值）是一种中间代码表示形式，核心思想是确保每个变量在程序中只被赋值一次

将代码转换为 SSA 形式

变量重命名；插入 Φ 函数

条件常量传播

第七章运行时存储空间（了解概念）

运行时的存储组织及管理是目标程序运行时所需要存储空间的组织与管理以及源程序中变量存储空间的分配，通常由操作系统负责

静态存储分配：每个变量所需空间的大小在编译时已知且运行时不变，直接分配

**动态存储分配：**在目标程序运行时进行分配；编译时要生成进行动态分配的目标指令。

当进入一个过程时，在栈顶为其分配一个数据区。当退出一个过程时，撤消该过程的数据区。

☆：活动记录

栈里的一个数据结构，保存程序运行时被激活函数

内容：CPU 现场、实际参数的个数、形式参数、局部变量、临时变量

1、返回地址：记录函数执行完毕后应该返回到的下一条指令地址。

2、动态链接：函数的调用，指向主调程序的活动记录。在程序运行时建立的，用于支持动态作用域或动态函数调用。

3、静态链接：函数嵌套的定义，指向非局部变量所在的活动记录。在编译时确定的，用于将内层函数链接到其外层函数的作用域链上，内层函数被调用时，它可以通过静态链访问到外层函数的局部变量。

讨论一个活动记录中的数据安排；程序执行过程中所有活动记录的组织方式

☆：参数传递

按值传递/传值/值调用：将实参的值复制给形参；按结果传递：将形参的值复制给实参

传地址/按引用调用/按址传递（指针）：实参与形参都指向同一内存区域，对形参的修改将改变实参

传值得结果/传结果：实质是形参具有两个单元。第一个单元存放的实参的地址。第二个单元存放的实参的值，在过程中对形参的任何引用和赋值看成是对它的第二个单元的直接访问。但是在调用返回之前必须把第二个单元的值存放到第一个单元指示的地址中。

按名传递/传名：不对参数进行预先估值。每次使用实际参数时，需要重新评估该参数的值。

例题

实验--UESTC

实验一词法分析

转载：Flex 词法分析实验实现（电子科技大学编译技术 Icoding 实验）_flex 实现词法分析-CSDN 博客

配置环境

安装 WSL | Microsoft Learn，设置 WSL 开发环境 | Microsoft Learn

wsl 需要 hyper-v，只有 Windows 10（专业版或企业版），或 Windows 11（专业版或企业版）

linux 和 windows 环境：strdup 函数在 windows 不可用，可以使用_strdup 替代，且需要在.l 文件#include <string.h>

windows 的命令行输入重定向：

cmd:test.exe < test1.sy
powershell:get-content .\test1.sy | .\test.exe

实验二递归下降分析器

编译工程附录：flex 使用 - 知乎

实验三 LR 语法分析

编译工程附录：Bison 基础 - 知乎

编译所需命令：

bison -d lrparser.y
flex lrlex.l
gcc -o rdparser lrparser.tab.c lex.yy.c ast.c

实验四中间代码生成

安装 llvm 和 clang。好难，这部分真不会。

22 年回忆版真题

24 年回忆版真题

一、简答

1、解释器和编译器的异同

2、词法分析的任务和单词记号的类别

3、活动记录的含义与内容

4、栈式分配中的动态连接作用

5、符号表的作用及实现的数据结构

二、给文字描述，用正则表达式表示模式串，并画 NFA 和 DFA

三、消除文法中的左递归并给出一段字符串的最右推导

四、求 First 集和 Follow 集，画 LL(1)预测分析表

五、给 C 语言代码写三地址码

六、很简单的局部优化代码

七、SLR(1)项目族、分析表绘制与判断

八、给流程图，分析活跃变量，根据图着色算法分配寄存器

第一章 概论​

编译系统八个组成部分​

分析（前端）​

合成（后端）​

第二章 文法和语言​

符号串的运算​

闭包​

例题：求符号串个数​

文法 G[S]​

语言、句子​

例题:构造符合语言的文法​

例题：求 L(G)​

推导与归约​

例题：判断句子是否在 L(G)中，根据文法给出句子的最左最右推导​

例题：判断二义性文法​

☆： 例题：求短语、直接短语、句柄（难）​

例题：文法化简​

第三章 词法分析​

状态转换图​

例题：根据文法画状态转换图​

例题：根据状态转换图写文法​

状态转换矩阵​

正则表达式（正规式）​

例题：根据模式串求正则式​

NFA​

正则表达式转 NFA​

☆： DFA​

☆： NFA 确定化（转 DFA）和 DFA 最小化​

NFA 转 DFA 步骤：​

例题​

练习题：确定化​

练习题：最小化​

例题：构造正规式的 DFA​

第四章 语法分析​

语法树​

根据文法构建的语法树​

自顶向下的语法分析​

左递归​

例题：消除左递归​

☆： LL(1)​

预测分析法：​

例题：求 First 集和 Follow 集​

例题：判断是否 LL(1)​

重要例题：预测分析表​

递归下降分析方法​

自底向上的语法分析​

☆： LR(0)​

LR(0)构造分析表步骤​

例题：判断 LR(0)并构造分析表​

☆： SLR(1)​

☆： LR(1)​

LALR(1) (了解)​

练习题​

第五章 语义分析与代码生成​

翻译成三地址码​

选择语句翻译​

☆：循环语句翻译​

函数调用翻译​

栈寻址与栈帧（了解）​

第六章 中间代码生成​

基本块划分​

例题​

程序流图（了解）​

代码优化​

局部优化​

例题：​

循环优化（了解）​

寄存器分配​

例题：目标代码生成（了解）​

☆：活跃变量分析​

反向传播的迭代算法​

☆：线性扫描算法​

SSA 静态单赋值（了解）​

将代码转换为 SSA 形式​

条件常量传播​

第七章 运行时存储空间（了解概念）​

☆：活动记录​

☆：参数传递​

例题​

实验--UESTC​