考试注意事项：

自动机记得画出开始状态要用start指出，接受状态两个圈，空边需要标出来，有模糊不清的表达及时问老师。

考察点：Re转DFA,Thompson构造法

Thompson这是一个大佬的详解

一般步骤：

将正则表达式先看成多个项目的连接，拆成连接的形式

拆分闭包和或运算。

解答：

考察点：NFA转DFA

SubConstruction 子集构造法依然是大佬的详解

一般步骤：

首先画一个表格（像解答那样），左边是NFA的状态集合，中间是产生的DFA的状态编号，右边是终结符集

根据NFA的初始状态找到他的闭包（从该点经空边可以到达的所有状态的集合），作为DFA的初始状态

从当前状态出发，经过一个非终结符，到达新的状态（新的状态首先是几个初始点，不包括经这些点[这些点可以作为一个状态标识]经空边到达的其他点，可以先找出所有的点，然后根据这些点进一步找到他们闭包集合）

找到所有的闭包集合并填写完毕右侧的所有状态，即获得DFA构造表

根据表格画出DFA即可

解答：

考察点：最小化DFA

可区分：如果当前状态集内的每一个状态经相同终结符，到达不同的状态，或者某一部分可以接受某终结符，另一部分不可以，那么该状态集是可区分的

不可区分：如果当前状态集内的每一个状态都接受某一个终结符，并且到达相同的状态。

一般步骤：

将所有的接受状态和非接受状态分成两个集合

考察每一个状态内的各个元素，使用可区分和不和区分原理将状态拆分

重复执行2步骤直至没有新的状态产生

解答：

解答：

考察点：最左推导过程，分析树、抽象语法树的区别和画法

语法树与抽象语法树（parse tree & abstract syntax tree）

本文中右下角是抽象语法树（啥都没有确实抽象），右上角是分析树。

一般步骤：

操作步骤很单纯，复杂的是人

列题：

解答：

（a）

考察点：正如其名

EBNF用{a}表示重复a

EBNF用[a]表示a可选

例图：

左递归分直接左递归、间接左递归。

消除直接左递归（remove the left recursive）：

消除间接左递归：

消除回溯(提取左公因子) Left factor this grammar：

回溯产生的原因是具有相同的公共前缀,使用提取左公因子的方法需要引入新的非终结符

FISTR集：

首写列出所有非终结符

查看某非终结符B对于的产生式的右部

如果右部的第一个字符为终结符则将该终结符纳入到非终结符B的FISTR集中

如果右部的第一个字符为非终结符A，那么将该非终结符A的FISRT集纳入非终结符B的FIRST集中

如果AFISRT集为空则需要看第二个符号

如果最后右部可以推出空，那么将空纳入非终结符B的FIRST集中

循环执行2直至没有非终结符有新终结符的加入

FEllow集：

首写列出所有非终结符，并把$结束符号放入开始符号的FELLOW集中

查看所有的产生式的右部

如果非终结符A后面紧跟的是终结符，那么将该终结符加入A的FELLOW集中

如果非终结符A后面紧跟的是非终结符，那么将该终结符FIRST集加入A的FELLOW集中

如果非终结符A位于产生式的最右，那么将产生式左部的FELLOW集也加入A的FELLOW集中(如果A不在1最右但是后面的串可以推出空也执行该操作)

循环执行2直至没有非终结符有新终结符的加入

SELECT集：

SELECT集主要用于LL(1)自顶向下的分析法中，用来根据当前非终结符和输入的终结符来选择执行的产生式。

如果右部第一个文法符号是终结符，则将该终结符纳入该产生式的Select 集中。

如果右部第一个文法符号是非终结符，则将该非终结符的First集纳入该产生式的Select 集中。

如果右部First集含空，则将该左部非终结符的Follow集纳入该产生式的Select 集中。