不讲不考察的内容

参考：编译原理 - 学习笔记 - Zhang T’s Blog

  • 1.5 编译程序的生成

  • 第七章 作用域

  • 第八章

日常课堂笔记

非确定集与确定集的分辨

一个状态（字符集合）在接收到同样的字符串时，会转变到不同的状态（集合），导致了它的非确定性。

NFA 转换为 DFA

所谓的状态闭包是指，从当前节点，经过 ε 符（无条件转移）能到达的所有节点的集合，包括当前节点自己。

分解

A -> 1 -> B 指 B 从 A 接收 1

self 0 指该节点有一个指向自己的、以接收到的字符为 0 为条件的无限循环

1/0 指该节点有两条指向下一节点的、分别以 0 和 1 为条件的状态转移

ε 不代表什么都接收，而是无条件转移的意思

  1. A -> 1(0|1)*(1|0) -> B

    A -> 1 -> C -> E(self 0/1) -> D -> 1/0 -> B

  2. A -> 1*(0|1)0* -> B

    A -> C(self 1) -> C -> 0/1 -> D -> E(self 0) -> B

状态转移矩阵

第一行 I 是起始点的状态闭包，在求第一行 Ia 的时候，除了要列出可以从 I 中某个元素接收 a 的节点，还要在全部列出后补充 Ia 这些节点的状态闭包，即可以从 Ia 某个节点通过 ε 前往的节点。

然后，新的集合添加到下一行，进行重复的步骤。

最后，为每一行从头到尾添加节点编号，进行化简。

DFA 化简

将终止态和非终止态分开

用非终止态开始一个一个字符开始测试

测试完得到一些划分

两个字符到同一个状态集合就算等价，不一定只能是到一个状态

例如，{3,4,5,6} 中的 3,4,5 接收 a 不到达同一个状态，那就也不是同一个功能，需要分开。

LR(0)

编译原理学习笔记（七）~LR (0) 分析_海轰 Pro 的博客 - CSDN 博客

LR(1)

在 LR (0) 的基础后面加 #,{c,d} 等

LL(1)

期中考试复习课

流程

词法分析包括：标识符、常数、字符串、关键字、界符

中间代码、优化器 会出简答题

出错处理：词法分析中关键词与标识符冲突、界符写错（没有大括号），打印 / 显示出来

表格管理：不断地在每个步骤生成结果，保存到表格中

遍

扫描越多遍越不好

文法

ε 空串的意思，起到一个语义复写的作用，把属性复写成综合属性往上传

空集和空字符串不是一个东西

右箭头 产生式符号

右箭头加星号 推导

句型：从开始符号经过 N 步推导，之间生成的任何字符串都是句型

句子：相比句型，只有有终结符的，才是句子

0 型文法最简单、表达能力最强，1 型文法增加了约束条件，2、3 型增加了更多。约束条件越多，表达能力越弱。

第三章

NFA DFA 的区别

  • DFA 只有一个起点
  • NFA 上面是一个字符串，DFA 上面是一个字符
  • NFA 同一个状态出发，同一个条件可以到达不同的状态；DFA 只能到达同一个状态

改写、化简、状态矩阵

就是一开始学的图

确定化

最少化

正规式改写 DFA

1(0|1)*101

自上而下语法树构造

左递归的消除

E->Ex|Ey|z

把所有包含左递归的候选式提取出来 E -> E (x|y)|z

X=x|y Y=z

E->EX|Y

用通用格式改写

E->YE’

E’->XE’|e

再代入 X 和 Y

E->zE’

E’->xE’|yE’|e

直接左递归是指产生式中右边的第一个符号就是左边的符号，间接左递归则不是。

把间接左递归通过代入的方式，改写成直接左递归，再使用直接左递归通用的改写方式

LL(1)

意义

第一个 L：从左往右输入，每次读入一个非终结符进行推导

第二个 L：产生式使用最左推导

1：每次只需要看右边的第一个数字

三个条件

不允许存在左递归

如果一个文法的候选式可以推导出 ε，则 FIRST 和 FOLLOW 集都为空

求 FIRST 集和 FOLLOW 集

求 FOLLOW 集以右边为主

FOLLOW 集里是不可能有 epsilon 的，最多只有#

最后一节新课（第七章）

抽象语法树 (AST)

  • 操作符在中间，左右两边的子结点是两个数

  • 在属性文法阶段生成抽象语法树

  • 逆波兰式：使用后序遍历抽象语法树的结果

  • 考试可能会考给一个逆波兰式，把抽象语法树写出来

  • AST 对编程是很重要的工具，因为操作符就是 “操作码”、子结点就是 “操作数”

DAG 图

DAG 图是抽象语法树的简化表达形式

三地址代码

难度比较大，后面还有四元式、三元式、间接三元式，要注意区别。作用域及其之后的内容不考察。

三地址代码是代码的逻辑表达形式，两个操作数加上一个运算符就是三地址了（如 a+b）

三地址语句是中间代码的一种抽象形式，四元式（操作码、两个操作数、操作结果）是三地址代码在内存中的一种存放形式。因此四元式表格中会有很多操作数是子树的操作结果（帮助自底向上运算）。

三元式相比四元式，省去了操作结果，把需要中间结果参与运算的地方替换成了运算这个中间结果的指令的编号（内存地址）。缺点：如果指令编号发生变化，则绑定操作结果的指令都出错了。为了解决这个缺点，有了间接三元式。

间接三元式的表格中的编号（1、2 等）指的并不是表格第一列的指令编号（内存地址），而是指向了间接码表中的间接代码，间接代码再去指向指令编号。需要调整运算顺序时，只需重新安排间接码表，无需改动三元式。