Review-CompilePrinciple
题目1 正则表达式与自动机
前置知识
自动机：
Automaton/Automata 状态集+转移函数
RE：
RE与DFA与NFA表达能力是等价的，所以可以相互转换
DFA与NFA：
确定性和非确定性有穷自动机
DFA一个状态通过一个字符转移只能有一个确定的状态（也就是隐含了无法使用空串进行转移
NFA 简洁易于理解, 便于描述语言 L(A)
DFA 易于判断 x ∈ L(A), 适合产生词法分析器
用 NFA 描述语言, 用 DFA 实现词法分析器
RE =⇒ NFA =⇒ DFA =⇒ 词法分析器
DFA的死状态：
死状态的画法：圈里面套个类似空集的符号
Thompson 构造法 (从RE到 NFA)
外面的q/f是新增的开始和截止状态
一个例子
画完记得重标下状态序号
子集构造法 (NFA 到 DFA)
一开始的状态可以是0,1,2,4,7
再看通过a,b可以转移到哪里，注意空串转移也算可到
某个状态包含NFA的某一个结束状态，就是DFA的结束状态
可以有多个结束状态，2022-hw2甚至全是结束状态
做的时候直接看某个节点有没有通过某个字符的路径，不需要考虑他空串转移了再继续，因为他空串转移能到的那个状态本身也会在这个集合里
DFA 最小化
一开始分成接受状态，非接受状态，死状态三类
课上的例子遗漏了补充死状态
这三者肯定不等价，然后就是回到死状态的肯定跟不到的不一样，所以要补上死状态
- 先划分等价类
- 再合并状态
题目2 LL语法分析
前置知识
LL1文法：
L的含义：
第一个L表示 从左向右读入词法单元
第二个L表示 总是选择最左边的非终结符进行展开
语法分析的算法主要有两大类LR和LL，LL自顶向下，LR自底向上，我们只考虑无二义性的文法
预测分析表：用于选择产生式
当前读到某个非终结符，该选用那条产生式展开，这就是预测分析表的作用
First集合：对所有产生式的右部求
参照上例
如果当前指针指向的是a2，A有三条展开式，只有第一条的右部的FIRST中包含a2，那么选用第一条产生式
FIRST集合可能会有空串符号
Follow集合：对所有非终结符
其实FOLLOW集合就是对FIRST集合做了进一步补充和防备？
因为FIRST可能推出空串，所以需要FOLLOW集合辅助判断
FOLLOW集合可能有结束符$
• First 集合与 Follow 集合
计算FIRST
例子
看一眼右边所有的可能性，发现要先计算FIRST(X) FIRST(Y) FIRST(Z)，仔细想想这是显然的
推到FIRSTZ 包含于 FIRSTZ，这句显然是废话
继续考虑FIRSTZ集合有没有空串就行了
大致看一下，发现是不行的
计算FOLLOW
注意下图说的是对X，不是对A
如果是开始符号，FOLLOW集合中就加入$
例子：
先看X会在右侧哪里出现和是否是开始符号
X是初始符，放入$
然后发现X会在Z->XYZ中
那么FLX就会包含FIRST(YZ)，先加入FIRSTY，加入了c，发现Y有可能是空串，那么FLX就会包含FIRSTZ，加入a,c,d
然后判断YZ整体会不会空，如果空了就要按照第二条把FOLLOWZ加到FOLLOWX里面
FLZ是空，因为推到了FLZ包含FLZ，不再变化了
• 构造预测分析表
上下两种表述等价，推导符号上面加个*表示经过多次推导（多次推导得到空串和空串属于FIRST alpha是等价的表述
满足两者之一，即可填入
行是终结符和$，列是非终结符
• 判断文法是否是LL(1)文法
预测分析表无冲突，即为LL1文法
题目3 LR语法分析
考试时会给出 LR(0) 自动机
• 掌握 LR(0) 自动机的构造方法以及 SLR(1) 表格的构造方法
• 掌握 LR(0) 自动机与栈之间的交互运行过程
题目4 ANTLR4与“优先级上升算法”
前置知识
消除左递归：
因为自顶向下的算法如LL1没法处理左递归，所以需要先改写一下
书P134
不考查 ANTLR 4 AllStar 算法的其余内容
不考查LR1、LALR1
• 能够根据优先级上升算法改造给定文法
• 能够给出给定输入在改造后的文法下对应的语法分析树
antlr4不能处理间接左递归，但是直接左递归可以，并且处理的很好
注意是非左递归，不是像我们前面一样写成右递归，右递归不太好看，且存在一定问题（结合性问题好像是）
重点：antlr如何处理优先级和直接左递归？
使用该命令可看到antlr把上述语法改写成什么样
看上去大体上是把递归改写成了循环
对应一段带参数的递归函数
这张图上的算法是有助于理解的
优先级怎么定的
例子1+2+3
匹配加法展开后参数_p变成4，目的是为了让加法优先级高的才能继续向下深入展开，因为语法树的优先级越往下展开越高，乘法同理，_p相当于一个判断能否展开的当前优先级
例子1+2*3
根本问题
另一个例子
优先级一定就是要上升+1吗
-右结合
!左结合
改写：
-是右结合，不是左递归的，所以放在上面的部分，并且优先级不变
!左结合左递归但是是一元的左结合运算符，不需要再调用expr[]递归函数
例子：-a+b!
注意从E[4]返回时代码中是返回到第一个括号后，而不是回到最开始，所以开始匹配加号（进入了带*的那个循环里
二元左递归运算符想要右结合
反正就是右结合不升级，左结合升一级
题目5 语法制导的翻译
不考查 ANTLR 4 中的写法
• 语法制导的翻译
题目6 目标代码生成
• 给定一段 C 语言程序 (含过程调用) 与对应的 RISC-V 代码片段, 填充缺失的代码行。
- 标题: Review-CompilePrinciple
- 作者: SYuan03
- 创建于 : 2023-06-22 16:00:22
- 更新于 : 2024-09-30 20:52:04
- 链接: https://bblog.031105.xyz/posts/2023-Spring-Courses-编译原理/review-compileprinciple.html
- 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
