七、思考题 实验 五 名称 DFA的最小化(Minimizing definitely finite automata ） 一、背景资料 NFA确定化的实质是以原有状态集上的子集作为DFA上的一个状态，将原状态间的转换为该子集间的转换，从而把不确定有限自动机确定化。经过确定化后，状态数可能增加，而且可能出现一些等价状态，这时就需要简化。 二、实验目的要求 输入： DFA。 输出： 最小化的DFA。 三、实验原理 所谓自动机的化简问题即是对任何一个确定有限自动机DFA M，构造另一个确定有限自动机DFA M’，有L（M）＝L（M’），并且M’的状态个数不多于M的状态个数，而且可以肯定地说，能够找到一个状态个数为最小的M’。 下面首先来介绍一些相关的基本概念。 设Si是自动机M的一个状态，从Si出发能导出的所有符号串集合记为L（Si）。 设有两个状态Si和Sj，若有L（Si）＝L（Sj），则称Si和Sj是等价状态。 下图所示的自动机中L（B）＝L（C）＝{1}，所有状态B和状态C是等价状态。 0 A B 1 1 C D 1 又例如终态导出的符号串集合中必然包含空串ε，而非终止状态导出的符号
串集合中不可能包含空串ε，所以终态和非终止状态是不等价的。 对于等价的概念，我们还可以从另一个角度来给出定义。 给定一个DFA M，如果从某个状态P开始，以字符串w作为输入，DFA M将结束于终态，而从另一状态Q开始，以字符串w作为输入，DFA M将结束于非终止状态，则称字符串w把状态P和状态Q区分开来。 把不可区分开来的两个状态称为等价状态。 设Si是自动机M的一个状态，如果从开始状态不可能达到该状态Si，则称Si为无用状态。 设Si是自动机M的一个状态，如果对任何输入符号a都转到其本身，而不可能达到终止状态，则称Si为死状态。 化简DFA关键在于把它的状态集分成一些两两互不相交的子集，使得任何两个不相交的子集间的状态都是可区分的，而同一个子集中的任何两个状态都是等价的，这样可以以一个状态作为代表而删去其他等价的状态，然后将无关状态删去，也就获得了状态数最小的DFA。 下面具体介绍DFA的化简算法： （1） 首先将DFA M的状态划分出终止状态集K1和非终止状态集K2。 K＝K1∪K2 由上述定义知，K1和K2是不等价的。 （2） 对各状态集每次按下面的方法进一步划分，直到不再产生新的划分。 设第i次划分已将状态集划分为k组，即： K＝K1(i)∪K2(i)∪…∪Kk(i) (i)对于状态集Kj（j=1,2,…,k）中的各个状态逐个检查，设有两个状态Kj’、 Kj’’∈Kj(i)，且对于输入符号a，有： F（Kj'，a）＝Km F（Kj''，a）＝Kn 如果Km和Kn属于同一个状态集合，则将Kj’和Kj’’放到同一集合中，否则将Kj’和Kj’’分为两个集合。 （3） 重复第（2）步，直到每一个集合不能再划分为止，此时每个状态集合中的状态均是等价的。 （4） 合并等价状态，即在等价状态集中取任意一个状态作为代表，删去其他一切等价状态。 （5） 若有无关状态，则将其删去。 根据以上方法就将确定有限自动机进行了简化，而且简化后的自动机是原自动机的状态最少的自动机。 四、材料、试剂及仪器 微机
五、实验步骤（包括操作方法、数据处理） 六、注意事项 要求： ⑴ 实现子集划分算法； ⑵ 输出界面如下： DFA的图形形式 最小DFA的图形形式 七、思考题 实验 六 名称 计算first集合和follow集合（Computing the first set and follow set） 一、背景资料 如果一个文法具有以下两个特点： （1） 每个产生式的右部都由终结符开始； （2） 如果两个产生式有相同的左部，那么他们的右部则由不同的终结符开始。 显然对于这样的文法，其推导过程完全可以根据当前的输入符号，决定选哪 个产生式往下推导，分析过程是惟一确定的，可以采用不带回溯的自上而下的预测分析方法。 如果两个产生式的左部相同，而右部都由非终结符开始，例如，存在A→α / β, α 和β均以非终结符开始，那么就很难决定何时使用A→α 选项，何时使用A→β选项。 二、实验目的要求 输入：任意的上下文无关文法。 输出：所输入的上下文无关文法一切非终结符的first集合和follow集合。
三、实验原理 设文法G[S]＝（VN，VT，P，S），则首字符集为： * FIRST（α）＝{a | α?aβ，a∈VT，α,β∈V *}。 *若α?ε，ε∈FIRST（α）。 由定义可以看出，FIRST（α）是指符号串α能够推导出的所有符号串中处于串首的终结符号组成的集合。所以FIRST集也称为首符号集。 设α＝x1x2…xn，FIRST（α）可按下列方法求得： 令FIRST（α）＝Φ，i＝1； （1） 若xi∈VT，则xi∈FIRST（α）； （2） 若xi∈VN； ① 若ε?FIRST（xi），则FIRST（xi）∈FIRST（α）； ② 若ε∈FIRST（xi），则FIRST（xi）－{ε}∈FIRST（α）； （3） i＝i+1，重复（1）、（2），直到xi∈VT，（i＝2，3，…，n）或xi∈VN且若ε?FIRST（xi）或i>n为止。 当一个文法中存在ε产生式时，例如，存在A→ε，只有知道哪些符号可以合法地出现在非终结符A之后，才能知道是否选择A→ε产生式。这些合法地出现在非终结符A之后的符号组成的集合被称为FOLLOW集合。下面我们给出文法的FOLLOW集的定义。 设文法G[S]＝（VN，VT，P，S），则 FOLLOW（A）＝{a | S?… Aa …，a∈VT}。 *若S?…A，#∈FOLLOW（A）。 由定义可以看出，FOLLOW（A）是指在文法G[S]的所有句型中，紧跟在非终结符A后的终结符号的集合。 FOLLOW集可按下列方法求得： （1） 对于文法G[S]的开始符号S，有#∈FOLLOW（S）； （2） 若文法G[S]中有形如B→xAy的规则，其中x，y∈V *，则FIRST（y）－{ε}∈FOLLOW（A）； （3） 若文法G[S]中有形如B→xA的规则，或形如B→xAy的规则且ε∈FIRST（y），其中x，y∈V *，则FOLLOW（B）∈FOLLOW（A）； 四、材料、试剂及仪器 微机 五、实验步骤（包括操作方法、数据处理）
六、注意事项 ⑴ 能处理含ε—产生式的上下文无关文法； ⑵ 程序的输出应包括first集合、follow集合以及所给定的文法是否为LL（1）文法的信息，输出界面如下： 非终first 结符 判定结论 follow 七、思考题 实验 七 名称 自动生成LR（0）分析表（Generating LR(0) analyzing table） 一、背景资料 LR（K）分析方法是1965年Knuth首先提出的，这里的L是指从左至右扫描输入符号串，R是指构造一个最右推导的逆过程，K是指为了做出分析决定而向前看的输入符号的个数。LR（K）分析方法是当前最广义的无回溯的“移进- 归约”方法。根据栈中的符号串和向右顺序查看输入串的K(K?0)个符号，就能惟
编译原理实验课程教案 - 图文
