编译原理 第三章 第二部分.ppt

例：为以下《无符号数》文法中构造DFA文法简写为： 0→d1 0→.3 0→d 1→d1 1→ .2 1→ E4 1→d 1→ . 2→ E4 2→ d2 2→ d 3→ d2 3→ d 4→d6 4→+5 4→–5 4→d 5→d6 5→d 6→d6 6→d 由NFA构造DFA方法 (1)初态记作[S] ，检查S对每个输入符号的映射状态集合，如果不是[S] ,作为新状态加入DFA状态集合. (2)取新状态集中一尚未处理状态，求出其对每个输入符号的映射状态集合，如果得到的状态子集不在新状态集中，将其作为一个新的状态加入。 （3）重复（2）直至所有状态处理完。 （4）将新状态集中含有原来终态的所有新状态作为新的终态。DFA求得. ε对FA识别出的字符串不产生实质性的影响，但需要找出在每个结点上不用匹配任何一个字符（匹配任意个连续的ε ）就可直接到达的状态集合，称为ε 闭包。 从状态q出发，仅经过若干条标记为ε的矢线所能达到的状态组成的集合为ε-Closure(q)。 例3.4 （1）因为ε-Closure(S0)={S0，S1，S2，S3}，故将Q0= {S0，S1，S2，S3}作为未标记的状态置于k’中； （2）此时，k’中仅有唯一未标记的状态Q0，故标记Q0； 作 f’（Q0，a）= ε-Closure（f（{S0，S1，S2，S3}，a）） = ε-Closure（S0）=Q0； f’（Q0，b）= ε-Closure（f{S0，S1，S2，S3}，b） ） = ε-Closure（{S1，S3}）={S1，S3} 且把Q1={S1，S3}作为未加标记的状态加入到k’中； f’（Q0，c）= ={S2，S3},把Q2={S2，S3}作为未加标记的状态加入到k’中； 例3.3 假设一种高级语言具有如下单词,为其构造FA. BEGIN END IF THEN ELSE 标识符 整常数  = = = 分别为各类单词构造NFA: 识别各类单词的NFA 识别各类单词的DFA DFA状态数最小化算法： （1）将状态集K划分为终态子集Z和非终态子集K-Z，记为∏={Z，K-Z}。 （2）对当前∏中的每个子集，检查其中每个状态对识别相同字符是否具有同样的映射，将映射到不同状态子集的称为可以区分的，将其按映射关系进行分裂，产生新的状态子集集合，记为∏new 。 （3）若∏new ∏，重复(2)，直至各子集都不能继续划分。 （4）对最终划分∏的每个状态子集，取其中任一状态作为该子集的代表状态，将原来射入该子集的所有矢线改为射入此代表状态。取含有原任一终态的子集作为新的终态。 例3.6对所给状态图和状态矩阵最小化 定理3.2 对于有同一接受集的FA，与之等价且具有最小状态数的DFA在同构意义下是唯一的。 作业： 3-13（1） 3－12 （1） （3）最小化 * * §3.3 有限自动机（FA） 状态转换图的五要素 1）有限非空状态集K 2）有限输入字母表∑ 3）状态之间的映射关系f 4）初态S0∈K 5）终态集Z∈K 通常把这五要素组成的五元式M=(K,∑,f, S0,Z)称为有限自动机(FA)，它是相应的状态转换图的一种形式描述，或者说，是状态转换矩阵的另一种表示。 1.确定的有限自动机（DFA） 若FA在每个状态，对输入符号的下一状态是唯一的，称此种FA为确定的有限自动机DFA。 2.非确定的有限自动机 若FA在某个状态，对输入符号的下一状态不是唯一的，而是状态集的一个子集，称此种FA为非确定的有限自动机NFA。 3.NFA与DFA的等价性 DFA五元式表示M=(K, ∑,f,S0,Z)中只f与不同：f不必具有单值性，f(Si,aj)={Sk1,Sk2,….,Skm},即f是从k×∑到2k的一个映射。 定理3.1 对字母表∑上的任一NFA M,必存在∑上与M等价的DFAM’。 目前确定化方法只适用于没有ε动作的NFA的确定化。 4.具有ε动作的FA 五元式 M＝（Ｋ，∑，ｆ，Ｓ０，Ｚ），ｆ是K×(∑∪{ε})到2k的映射，称为具有ε动作的FA。 所有的具有ε动作的FA都是NFA 具有ε动作的FA的引入： 引入有ε动作的NFA是为将识别各类单词的FA用ε连接起来，组成一单一的NFA。