编译原理2.2-自动机理论.pptVIP

第3章 自动机理论基础 本章将介绍正规文法和有穷自动机之间的关系，所涉及的内容是编译中词法分析技术和自动生成词法分析程序的理论。 教学要求 掌握：正规式，DFA的概念，NFA的概念 理解：将DFA 转换为NFA，正规文法与有穷自动机间的转换 重点：正规式构造DFA，DFA最小化 难点：正规表达式构造DFA 一、 正规式和正规集 正规集可以用正规表达式（简称正规式）表示。 正规表达式是表示正规集一种方法。一个字集合是正规集当且仅当它能用正规式表示。 正规式和正规集的递归定义： 对给定的字母表? 1)? 和?都是?上的正规式，它们所表示的正规集为{?}和?; 2) 任何a?? ，a是?上的正规式，它所表示的正规集为{a} ; 3) 假定e1和e2都是?上的正规式，它们所表示的正规集为L(e1)和L(e2)，则 i) (e1|e2)为正规式，它所表示的正规集为L(e1)?L(e2)， ii) (e1.e2)为正规式，它所表示的正规集为L(e1)L(e2)， iii) (e1)*为正规式，它所表示的正规集为(L(e1))*， 仅由有限次使用上述三步骤而定义的表达式才是?上的正规式，仅由这些正规式表示的字集才是?上的正规集。 讨论下面两个例子 例1 令?={l，d}，则?上的正规式 r=l(l?d)?定义的正规集为: {l,ll,ld,ldd,……},其中l代表字母,d代表数字,正规式 即是 字母(字母|数字) ? ,它表示的正规集中的每个元素的模式是“字母打头的字母数字串”,就是Pascal和多数程序设计语言允许的标识符的词法规则. 若两个正规式e1和e2所表示的正规集相同，则说e1和e2等价,写作e1=e2。 例如： e1= (a?b)， e2 = b?a 又如： e1= b(ab)? , e2 =(ba)?b e1= (a?b)? , e2 =(a??b?)? 对正规式，下列等价成立： e1|e2 = e2|e1 交换律 e1 |(e2|e3) = (e1|e2)|e3 结合律 e1(e2e3) = (e1e2)e3 结合律 e1(e2|e3) = e1e2|e1e3 分配律 (e2|e3)e1 = e2e1|e3 e1 分配律 e? = ? e = e e1e2 e2 e1 S*=(S|ε)* ?是“连接”的恒等元素（零一律） (a*)*=a* 1、单词的构成规则用状态转换图表示 一个状态图可用于识别一定的字符串，大多数程序设计语言的单词符号都可以用转换图来识别。 识别过程是：从初始状态0开始，若读入一个字母，转入1状态，若再读入字母或数字，仍处于1状态，否则转向2状态，结束一个标识符的识别过程。状态上的*表示多读入一个符号。 例：证明t=baab被下图的DFA所接受。 f（S，baab）=f（f（S，b），aab） = f（V，aab）= f（f（V，a），ab） =f（U，ab）=f（f（U，a），b） =f（Q，b）=Q Q属于终态。 得证。 DFA的确定性表现在： 对任何状态s ∈S，在读入了输入符号a ∈ Σ 之后，能够唯一地确定下一个状态 映射函数δ：S×Σ→S是一个单值函数 从状态转换图来看，若字母表Σ含有n个输入字符，那末任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。 （1）DFA任何状态都没有ε转换，即没有任何状态可以不进行输入符号的匹配就直接进入下一个状态； （2）DFA对任何状态S和任何输入符号a，最多只有一条标记为a的边离开S，即转换函数δ：S ?Σ? S是一个单值部分函数。 例子 NFA M=（{S，P，Z}，{0，1}，f，{S，P}，{Z}） 其中 f（S，0）={P} f（Z，0）={P} f（P，1）={Z} f（Z，1）={P} f（S，1）={S，Z} ∑*上的符号串t被NFA M接受（识别）: 对于Σ*中的任何一个串t，若存在一条从某一初态结点到某一终态结点的通路，且这条通路上所有弧的标记字依序连接成的串(不理采那些标记为ε的弧)等于t，则称t可为NFA M所识别(读出或接受)。 若M的某些结点既是初态结点又是终态结点；或者存在一条从某个初态结点到某个终态结点的道路,其上所有弧的标记均为ε，那么空字ε可为M所接受。 ?-closure(I) =?-closure({1})={1，2}=I J={5，4，3} Ia= ?-closure(J)= ?-closure({5，4，3}) ={5，4，3，6，2，7，8} 把确定化的过程: 不失一般性，设字母表只包含两个a和b，我们构造一张表: 现在把这张表看成一个状态转换矩阵，把其中的每个子集看成一个状态。 这