带铅笔

DFA 正则表达式与自动机

  • 写正则表达式 如果考至少出现两次咋办
  • 正则表达式转化为NFA
  • NFA转化为DFA 子集构造法 必考
  • DFA状态最小化

第三章

写正则表达式

img

正则表达式转化为NFA

**龙书page100 **Thompson 构造法

NFA转化为DFA

龙书page97 子集构造法 不要忘了画start

DFA状态最小化

龙书page114

image-20250531104504378

第一步先区分终止状态和非终止状态

image-20250531104605636

然后去再细分，看到q0和q1输入a的结果都在同一个集合，输入b的结果都在同一个集合，而q5不是，所以分开

image-20250531104709678

不再可细分了，于是结束

eg：考虑正则表达式r=(a|b)*a^+^ (1)请使用Thompson 构造法构造等价的 NFA。 (2)请使用子集构造法构造等价的DFA。(注:请标明状态之间的对应关系)

image-20250531093406156

image-20250531102921554

image-20250531102855171

a->c应该是b

语法分析

第四章

消除左递归

龙书page134

image-20250531212619649

自顶向下分析

龙书page138

计算FIRST和FOLLOW

龙书page140

image-20250531143102771

first其实好算，难算的是follow，follow请严格按照龙书141页上方三条规则去算，一个都别漏！

构造预测分析表

龙书page143最上方

判断是否是LL（1） 存疑，感觉有点抽象，课本上也没有

LL(1)语法（无歧义！非左递归！）

一个语法是LL(1)的，当且仅当any 𝐴 → 𝛼 β满足以下条件：
  • 对于任何终端a，α和β都不能通过左因子化推导出以a开头的字符串
  • α和β中最多有一个能推导出空字符串
  • 如果β⇒∗ε，α不会推导出以FOLLOW(α)中的终端开头的字符串

eg：考虑文法 G：

S→cS (1)

S→AB (2)

A→aA (3)

A→ϵ (4)

B→bBa (5)

B→d (6)

(1) 请为文法 G 计算必要的 FIRST 集合与 FOLLOW 集合：

(2) 请为文法 G 构造预测分析表：

(3) 请问文法 G 是否是 LL(1) 文法，并说明理由。

Three-Address Code SSA

SSA的作用 Direct def-use chains

三地址码 龙书233页

Dominance

The header dominates all blocks in the loop.

  • A dom B
    • if all paths from Entry to B goes through A
  • A post-dom B
    • if all paths from B to Exit goes through A

  • Strict (post-)dominance-A(post-)dom B but A≠B

  • Immediate dominance – A strict-dom B, but there’s no C, such that A strict-dom C, C strict-dom B

image-20250409002154977

  • 时间复杂度：构建支配树的时间复杂度接近线性（O(n)），这使得它在处理大规模控制流图时非常高效。
  • 节点：支配树中的每个节点代表控制流图中的一个基本块（Block）。
  • 边：支配树中的边表示立即支配关系（Immediate Dom Relation）。

最近公共支配节点（Nearest Common Dominator）

  • 最低公共祖先（LCA - Lowest Common Ancestor）：在支配树中，两个节点的最低公共祖先是它们的最近公共支配节点。

Dominance vs. Ctrl Dependence

  • Block B is control dependent on Block A if and only if
    • The execution(执行) result of A determines if B will be executed
  • Block B is control dependent on Block A if and only if
    • A has multiple successors(继承者)
    • Not all successors can reach B
  • By definition,we always need a forward traversal(遍历) from all successors of B to test if A ctrl-depends on B. Too expensive!!

image-20250409003854041

左边两张图是用上面的法则根据最右边的图画出来的

image-20250409004753531

就是去找满足两个条件的

比如要找A的DF，那就在被A dominate的节点（包括他自己）的后继中找不被A dominate的节点

image-20250409005748572

假设我们有一个块集 Bset = {A, B, C}，我们需要计算其 IDF。

  1. 初始步骤：
    • 计算 DF₁ = DF({A, B, C})。
    • 根据支配边界表：
      • DF(A) = {}
      • DF(B) = {F}
      • DF(C) = {E}
    • 所以 DF₁ = {F, E}。
    • 更新 Bset = {A, B, C} ∪ {F, E} = {A, B, C, F, E}。
  2. 迭代步骤：
    • 计算 DF₂ = DF({A, B, C, F, E})。
    • 根据支配边界表：
      • DF(A) = {}
      • DF(B) = {F}
      • DF(C) = {E}
      • DF(F) = {}
      • DF(E) = {F}
    • 所以 DF₂ = {F, E}。
    • 更新 Bset = {A, B, C, F, E} ∪ {F, E} = {A, B, C, F, E}。
  3. 检查固定点：
    • DF₂ = DF₁，达到固定点。

所以IDE({A,B,C}) = {F, E}

image-20250409010214425

image-20250409010949258

通过向上查找Dominator Tree去寻找对应的定义

Regsister Allocation**, **Instruction Scheduling

local register allocation

就是很僵硬的分配，maxlive和k

global register allocation

图染色算法

龙书page358 书上没细讲

  • 建立一个冲突/干扰图
  • 为图找到一个k-着色，或者将代码改为一个可以着色的邻近问题
  • 在几乎所有假设下都是NP完全问题，因此需要使用启发式方法

image-20250505203813097

将图的顶点映射到虚拟寄存器上，将颜色映射到物理寄存器上

从实时范围构建冲突图

给图着色，使没有两个邻居具有相同的颜色

如果图需要超过k种颜色-溢出

image-20250505210714161

  • 顶点的度是可着色性的松散上限值
  • 顶点的度<k时，总是k-可着色的
  • 移除这些顶点并将其推入栈中，直到图为空为止（以后再着色）

image-20250505211607696

image-20250505211628033

image-20250505211706121

类似高中学的着色问题，就是通过一个栈，把值一个一个推进去，再一个一个push出来着色，着色时保证相邻颜色不同

Chaitin算法

当这个算法遇到每个顶点的度数都大于等于k时，需要选择一个值去溢出，把这个值放入溢出列表

如果溢出列表不为空，请插入溢出代码（st和reload），重建冲突图，并重试分配

如果溢出列表不为空，请插入溢出代码，重建冲突图，并重试分配。

image-20250505212232862

image-20250505212246529

此时向代码插入对于R2的st和reload，再重构这个冲突图

image-20250505212330176

后面的步骤就和之前一样了

地址描述符与寄存器描述符的寄存器分配办法

龙书page349 特别是351页例子那张图

Instruction Scheduling

关于 true dependence和fake dependence以及消除fake dependence在龙书page452

list Scheduling

龙书page459

Data Flow Analysis, Symbolic Execution

Data Flow Analysis 尽可能考一个题

龙书page386上面有个例子

symbolic execution

SAT problem

image-20250618161253741

image-20250618161345039image-20250618161420264

DPLL算法

image-20250618161626299

回溯

DPLL 算法示例

原始公式

图中给出的原始公式是： (p∨q∨¬r)∧(p∨q∨r)∧(p∨¬q)∧¬p

步骤分析

  1. 初始公式： (p∨q∨¬r)∧(p∨q∨r)∧(p∨¬q)∧¬p
  2. 选择变量并赋值：
    • 假设 DPLL 算法首先选择变量 p 并尝试赋值为 true。
    • 但是，公式中存在子句 ¬p，这意味着 p 必须为 false 才能满足该子句。
  3. 传播赋值：
    • 将 p=false 代入公式：
      • 子句 ¬p 被满足。
      • 其他子句中 p 的部分被消去，剩下： (q∨¬r)∧(q∨r)∧¬q
  4. 继续处理：
    • 剩下的公式是： (q∨¬r)∧(q∨r)∧¬q
    • 选择变量 q 并尝试赋值为 true：
      • 但是，子句 ¬q 要求 q 必须为 false。
  5. 进一步传播赋值：
    • 将 q=false 代入公式：
      • 子句 ¬q 被满足。
      • 其他子句中 q 的部分被消去，剩下： (¬r)∧(r)
  6. 冲突检测：
    • 剩下的公式是： ¬r∧r
    • 这是一个矛盾（¬r∧r 永远为假），说明当前赋值导致冲突。
  7. 回溯：
    • 由于冲突，DPLL 算法回溯并尝试其他赋值组合。
    • 但在这个例子中，所有可能的赋值组合都会导致冲突，因此公式是不可满足的。

公式 (p∨q∨¬r)∧(p∨q∨r)∧(p∨¬q)∧¬p 是不可满足的（UNSAT）。

image-20250618231732984

Pointer Analysis

image-20250601182542653

Andersen’s Algorithm 必考

image-20250601182907903

image-20250601190647005

image-20250601190741745

Datalog-Based Analysis

Reaching Definition by Datalog

  1. def(B, N, X)
  • 含义：表示在块 B 中的第 N 条语句定义了变量 X。
  • 解释：这表示在块 B 的第 N 条语句中，变量 X 被赋值。

例如：

  • 如果块 B 的第 2 条语句是 X = 5，那么 def(B, 2, X) 为真。
  1. succ(B, N, C)
  • 含义：表示块 C 是块 B 的后继块，且块 B 包含 N 条语句。
  • 解释：这描述了控制流图中的块之间的后续关系。

例如：

  • 如果块 B 的最后一条语句（假设是第 N 条）跳转到块 C，那么 succ(B, N, C) 为真。
  1. rd(B, N, C, M, X)
  • 含义：表示块 C 中第 M 条语句对变量 X 的定义可以到达块 B 中的第 N 条语句。
  • 解释：这表示在块 C 中第 M 条语句定义的 X 的值可能影响块 B 中第 N 条语句的执行。

后两题与ppt例题相似