第03章词法分析与有穷自动机.pptVIP

第三章 词法分析与有穷自动机 3.1 词法分析程序的功能 3.2 单词符号及输出单词的形式 3.2 单词符号及输出单词的形式 3.2 单词符号及输出单词的形式 3.2 单词符号及输出单词的形式 3.2 单词符号及输出单词的形式 3.2 单词符号及输出单词的形式 3.2 单词符号及输出单词的形式 3.2 单词符号及输出单词的形式 3.2 单词符号及输出单词的形式 3.2 单词符号及输出单词的形式 3.3 单词符号的两种定义方式 3.3.1 正规式和正规集 3.3.1 正规式和正规集 3.3.1 正规式和正规集 3.3.1 正规式和正规集 3.3.1 正规式和正规集 3.3.1 正规式和正规集 3.3.1 正规式和正规集 3.3.1 正规式和正规集 3.3.1 正规式和正规集 3.3.1 正规式和正规集 3.3.1 正规式和正规集 3.3.2 正规文法与正规式 3.3.2 正规文法与正规式 3.3.2 正规文法与正规式 3.3.2 正规文法与正规式 3.3.2 正规文法与正规式 3.3.2 正规文法与正规式 3.3.2 正规文法与正规式 3.3.2 正规文法与正规式 3.3.2 正规文法与正规式 3.3.2 正规文法与正规式 3.3.2 正规文法与正规式 3.3.2 正规文法与正规式 3.3.2 正规文法与正规式 3.3.2 正规文法与正规式 3.4 正规式与有穷自动机 3.4.1 确定有穷自动机 3.4.1 确定有穷自动机 3.4.1 确定有穷自动机 3.4.1 确定有穷自动机 3.4.1 确定有穷自动机 3.4.1 确定有穷自动机 3.4.1 确定有穷自动机 3.4.2 非确定有穷自动机 3.4.2 非确定有穷自动机 3.4.2 非确定有穷自动机 3.4.2 非确定有穷自动机 3.4.2 非确定有穷自动机 3.4.2 非确定有穷自动机 3.4.2 非确定有穷自动机 3.4.3 由正规式R构造NFA 3.4.3 由正规式R构造NFA 3.4.3 由正规式R构造NFA 3.4.3 由正规式R构造NFA 3.4.3 由正规式构造NFA 3.4.3 由正规式构造NFA 3.4.4 NFA确定化为DFA的方法 3.4.4 NFA确定化为DFA的方法 3.4.4 NFA确定化为DFA的方法 3.4.4 NFA确定化为DFA的方法 3.4.4 NFA确定化为DFA的方法 3.4.4 NFA确定化为DFA的方法 3.4.4 NFA确定化为DFA的方法 3.4.4 NFA确定化为DFA的方法 3.4.4 NFA确定化为DFA的方法 3.4.4 NFA确定化为DFA的方法 3.4.4 NFA确定化为DFA的方法 3.4.4 NFA确定化为DFA的方法 3.4.4 NFA确定化为DFA的方法 3.4.4 NFA确定化为DFA的方法 3.4.4 NFA确定化为DFA的方法 3.4.4 NFA确定化为DFA的方法 3.4.4 NFA确定化为DFA的方法 3.4.4 NFA确定化为DFA的方法 3.4.4 NFA确定化为DFA的方法 3.4.4 NFA确定化为DFA的方法 3.4.4 NFA确定化为DFA的方法 3.4.4 NFA确定化为DFA的方法 由定义可知,ε– closure(I) 表示所有那些从I中的元素出发经过ε道路所能到达的NFA的状态所组成的集合, I中任何状态也在其中，因为它们是通过ε通路到达自身的。该集合对DFA来说是一个状态。 ε – closure({0})={0,1,2,3}, 即{ 0,1,2,3} 中的任一状态都是从NFA的初态0出发， 经任意条ε道路可到达的状态。 通过下图理解状态集合 I 的ε闭包。 这个状态集合实际就是要求的DFA的初态。 ε ε 0 1 2 3 4 5 6 7 8 9 ε ε ε ε ε b b 因为在状态A中只有状态0有b的转移，转移 到的状态为4和7。 若令A={0,1,2,3},则 那么令B= ε – closure({4,7})={4,5,6,7,8,9} 即是DFA在状态A下遇到输入符号b，转移到 的后继状态。 J=f(A,b)=f(0,b)∪f(1,b)∪f(2,b)∪f(3,b)={4,7} ε