编译原理笔记16：⾃下⽽上语法分析（3）构造DFA、DFA对下⼀
步分析的指导（有效项⽬）
看了前⾯的内容，我们已经了解到：分析表和驱动器算法，是 LR 分析器的核⼼。
在分析的过程中，语法分析器总是根据栈顶的状态、当前剩余输⼊的第⼀个终结符查询分析表，以确定改变格局的动作并执⾏，实现对栈和剩余输⼊的内容的修改，从⼀个格局转移到另⼀个格局，如此往复直⾄分析完毕（或报错）。
下⾯我们就来研究⼀下如何从⽂法构造 DFA —— 这是构造 LR(0) 、SLR(1) 分析表的第⼀步。
由 NFA ⽤⼦集法构造 DFA
前⼀篇博客中讲解了该如何构造 NFA，有了 NFA 就可以使⽤⼦集法构造 DFA 了。树像什么
构造⽅法与词法分析的 NFA 转 DFA 类似，此处不再重复，接下来说⼀些该 DFA 的特点。
DFA 中的每个状态都是原 NFA 的状态集（因为 DFA 是 NFA 使⽤⼦集法构造的）。⽽⼜因 NFA 的每个状态都对应⼀个项⽬，所以 DFA 中的每个状态⼜是⼀个项⽬集。
DFA 的初态由原 NFA 初态求 ε-闭包得到，DFA 中的所有状态都是其终态。
（类⽐⼦集法构造词法分析 DFA——DFA 的终态是包含原 NFA 终态的那些状态，⽽原来的那个 NFA 穷人读后感
本⾝就已经所有状态均为终态了，也就是说从初态出发到达任何⼀个状态的路径所标记的连接都是该 DFA 可识别的活前缀。同理，原来的句柄识别态到这⾥依然是适⽤的，就是图中的1、8、10、6、7、11、9 ）
薄雾浓云
该识别活前缀的 NFA 和原来的词法分析 NFA 有⼀个重⼤差别：词法分析 NFA 状态号就只是⼀个编号，⽽此处的状态编号却是和项⽬相对应的——每个编号就对应着⼀个项⽬，⽽且状态的转移关系也是基于这些项⽬建⽴起来的。
那么。。其实也可以直接从项⽬构造 DFA
由 LR(0) 项⽬直接构造识别活前缀的 DFA
LR(0) 项⽬集规范族：构成识别⼀个⽂法活前缀的 DFA 的项⽬集（状态）的全体，称为这个⽂法的 LR(0) 项⽬集规范族。这个规范族提供了建⽴⼀类 LR(0) 和 SLR 分析器的基础。
实际上，这个【规范族】就是我们要构造的识别活前缀的 DFA 的状态的全体——上⾯那个 DFA 中所有的矩形状态加起来就是了。主要是因为DFA 的每个状态都是⼀个 LR(0) 项⽬集，所以就想起来这么个骚名字叫做【LR(0) 项⽬集规范族】
卖房子怎么找客户
该 DFA 就能够⽤来识别活前缀了。与词法分析 DFA 不同的是，该 DFA 的任何⼀个状态都是终态。这也就意味着，从初态开始到任⼀个状态所
形成的路径上⾯的标记连接起来，都是⼀个 DFA 能够识别的活前缀。⽐如，对于状态3（即 I3），其能够识别的活前缀有 F 和 E-F；状态6能够识别的活前缀只有 E-
现在，我们再回头看⼀下移进规约的过程就会发现⼀些有意思的东西
确实，每个时刻，栈中的内容都和分析表、⾃动机有着关联。我们可以尝试去读栈中任⼀时刻的元素（从栈底到栈顶），这些状态号、⽂法符号相间的序列均能在上图左边的 DFA 中和⼀条路径相匹配。
DFA 指导下⼀步分析
给老人的祝福语1. DFA 每个状态识别的活前缀不同；
2. 对语法结构正确的输⼊序列进⾏分析的任⼀时刻，若此时分析器正处于 DFA 的某状态 i ，则状态 i 识别的活前缀出现
在栈中，且状态 i 正位于栈顶。语法分析器正是根据此刻状态 i 中包含的 LR(0) 项⽬来指导下⼀步分析的；
3. 状态 i 中出现的 LR(0) 项⽬对状态 i 能够识别的活前缀有效。
好的，DFA 看起来是个好东西，那么我们现在假设栈顶是 5 状态，此时 DFA 怎么指导下⼀步的分析呢？
有效项⽬
若存在最右推导：S' =*> αAω => αββω ，则称项⽬ A → β.β 对活前缀 αβ 有效。
沈阳市医疗保险管理中心
项⽬ A → β.β 对活前缀 αβ 有效，作⽤是说明：在当前活前缀为 αβ 的情况下，当前状态中的 A → β.β 这个项⽬可以指导下⼀步的分析动作为： αAω => αββω 。
我觉得吧：已经读到并且已经⼊栈的东西，全都是活前缀。活前缀呢，就是仍然可以活动的前缀——根据其后添加的符号不同，这个活前缀可能会变成某个句柄——也就是说，活前缀能够在后⾯加⼊某些新的符号之后成为某个产⽣式的右部，也就可以被⽤这个产⽣式规约掉。
菊花茶
对于符号串 αββω ，看起来应该是可以使⽤ A → ββ 对其进⾏规约。读写头在读输⼊序列的时候是⼀个⼀个符号去读，读到了要移进的也是⼀个接着⼀个压栈。当栈中是 αβ （即当前活前缀是 αβ ）时，如果我们已经知道有这么个项⽬： A → β.β ，那就说明如果下⼀个读到了 β ，栈顶就能够形成该产⽣式的句柄，我们也就可以利⽤这个项⽬的下⼀步项⽬ A → ββ. 进⾏规约了。
121211211121212121112212皮蛋制作
这其实就体现了 DFA 对分析的指导作⽤。
可知：同⼀项⽬集中的所有项⽬，对此项⽬集的所有活前缀均有效。即，项⽬集中的每个项⽬均有同等权利指导下⼀步动作。有效项⽬的意义：
1. 项⽬到⽬前为⽌的分析均是正确的；
2. 可以指导下⼀步的分析：
1. A → α.aβ（可移进项）：若当前剩余输⼊为终结符 a ，则移进 a；
2. B → β. （可规约项）：按产⽣式 B → β 进⾏规约。
