发布时间 : 星期五 文章（重庆理工大学计算机学院）编译原理课程设计报告更新完毕开始阅读
步骤2：对NFA 进行确定化，构造状态转换表。 (1) 子集构造法： 初始时，ε_closure(s0)是Dstates中唯一的状态且未被标记； while Dstates中存在一个未标记的状态T do begin 标记T； for 每个输入符号a do begin U:= ε_closure(move(T,a)); ifU没在Dstates中then 将U作为一个未标记的状态添加到Dstates中； end; end; (2) ε_closure的计算，计算ε_closure(T)的简单算法是用栈来保存其弧还没有完成ε转换检查的状态。
将T中所有的状态压入栈stack中： 将ε_closure(T)初始化为T； while栈stack不空 do begin 将栈顶元素t弹出栈； for每个这样的状态u：从t到u有一条标记为ε的边do if u不在ε_closure(T)中do begin 将u添加到ε_closure(T); 将u压入栈stack中; end; end; （4）基本要求
算法实现的基本要求是： (1) 输入一个NFA N；
(2) 输出与之等价的DFA。
（5）测试数据
给定不确定的有穷自动机：
得到与之等价的确定的有穷自动机：
5
（6）输出效果
输出状态转换表表示的确定的有穷自动机如下：
6
3.确定的有穷自动机的化简
（1）目的与要求
通过设计、编写和调试将确定的有穷自动机的状态数变为最少的程序，使学生掌握化简有穷自动机的过程中的相关概念和方法。DFA的表现形式可以是表格或图形。
（2）问题描述
每一个正规集都可以由一个状态数最少的DFA所识别，这个DFA是唯一的（因状态名不同的同构情况除外）。任意给定一个确定的有穷自动机，根据算法设计一个程序，将该DFA化简为与之等价的最简DFA。
（3）算法描述
1．构造具有两个组的状态集合的初始划分Π：接受状态组F，非接受状态组S-F。 2．对Π采用下面所述的过程来构造新的划分Πnew。
for Π中每个组G do begin
当且仅当对任意输入符号a，状态s和t读入a后转换到Π的同一组中；
/*最坏情况下，一个状态就可能成为一个组*/ 用所有新形成的小组集代替Πnew中的G； end
3．如果Πnew=Π，令Πfinal=Π，再执行步骤4；否则，令Π：=Πnew，重复步骤2。 4．在划分Πfinal的每个状态组中选一个状态作为该组的代表。这些代表构成了简化后的DFA M'的状态。另s是一个代表状态，而且假设：在DFA M中，在输入a上有从s到t的转换。令t所在组的代表是r（r可能就是t），那么在M'中有一个从s到r的a上的转换。令包含s0的状态组的代表是M'的开始状态，并令M'的接受状态是那些属于F的状态所在组的代表。注意，Πfinal的每个组或者仅含F中的状态，或者不含F中的状态。
5．如果M'含有死状态（即一个对所有输入符号都有到自身的转换的非接受状态d），则从M'中去掉它；删除从开始状态不可到达的状态；取消从任何其他状态到死状态的转换。
（4）基本要求
算法实现的基本要求是： (1) 输入一个DFA D；
(2) 输出与之等价的最小化的DFA M。
（5）测试数据
给定确定的有穷自动机：
得到最小化的确定的有穷自动机：
7
（6）输出效果
? LR(0)算法分析 1.构造LR(0)项目集规范簇
（1）问题描述
给定一个LR（0）文法，求出其项目集规范簇，结果以图形或表格的形式输出。
（2）算法描述
设有LR(0)文法G，首先求出其所有的项目，然后根据项目求出其LR(0)项目集规范簇，求项目集规范簇的算法为： PROCEDURE itemsets(G'); BEGIN C := { CLOSURE( {S' ?·S} ) }; REPEAT for C中的每个项目集I和每个文法符号X do
8