第三章正则语言.ppt

编译原理 Principles of Compiler 第三章 正则语言 正则语言(Regular Language) 一种最简单的形式语言。 计算机程序设计语言的词法属于正则语言的范畴。 本章内容：正则语言的三种模型 有穷状态自动机 正则表达式 正则文法 3.1 有穷状态自动机 一个识别? = { a, 1 }中所有标识符的程序： int nStatus = 0; while( ch = getch() ) { if( nStatus == 0 ) if( ch == ‘a’ ) nStatus = 1; else return ERROR; else if( ch != ‘a’ ch != ‘1’ ) return ERROR; } return 0; 3.1 有穷状态自动机 识别算法可以用图形表示： 3.1 有穷状态自动机 有穷状态自动机( Finite Automata ) 一台只有一个变量的计算机。 变量的取值范围有限，变量的一个值称为该计算机的状态。 计算机从初始状态开始运行，从坐向右读入输入的字符。 每读一个字符，根据一定规则修改状态值。 如果输入结束，当前状态为接受状态，则接受输入的串；否则拒绝输入串。 3.1 有穷状态自动机 FA的表示方法---状态图： 3.1 有穷状态自动机 FA的表示方法---迁移表： FA的语法 一台FA M = ( Q, ?, ?, q0, F )，其中： Q为一个非空有穷的状态集合； ?为有穷的字母表( 符号集 )； ?：Q ? ? → Q为状态迁移函数； q0 ? Q为初始状态； F ? Q为接受状态集合。 3.1 有穷状态自动机 M = ( Q, ?, ?, q0, F )，其中： Q = { 0, 1 }； ? = { a, 1 } ； ? = { ((0, a), 1), ((1, a), 1), ((1, 1), 1)； q0 = 0； F = { 1 }。 FA的语义( FA与语言的关系 ) FA的运行： 给定一台FA M = ( Q, ?, ?, q0, F ) M的一个运行是一个有穷的状态序列? = s0s1…sn，其中： s0 = q0； sn ? F； ?0?in( ?a??( ?(si, a) = si+1 ) )。 例： 01，011，0111都是图中自动机的运行。 FA的语义( FA与语言的关系 ) FA接受（识别）的串： 给定一台FA M = ( Q, ?, ?, q0, F ) 称一个串? = a1a2…an被M接受（识别），如果M存在一个运行? = s0s1…sn，使得： ?0?in(?(si, ai+1) = si+1 )。 如果串?不被M接受，则称M拒绝? 。 FA M的语言L(M)为所有M接受的串的集合。 FA的语义( FA与语言的关系 ) 例： FA与正则语言 定义：称FA M识别语言L，如果M恰好接受L中的所有串。 定义：一个语言是正则的，当且仅当存在一台FA识别它。 3.2 正则语言的封闭性 正则语言在并运算下的封闭性 定理：如果L1与L2为正则语言，则L1?L2也是正则语言。 证明思路：构造一台FA恰好识别L1?L2。 3.2.3 正则语言的补运算 语言的性质 语言是符号串的集合 补运算 封闭性 如果语言A为正则语言，那么A的补集也是正则语言 语言封闭性的意义 证明思路 由于A为正则语言所以存在一台DFA M恰好识别A 根据M，构造一台DFA M’，恰好识别A的补集 对任何一个符号串，如果M接受，则M’拒绝 如果M拒绝，则M’接受 证明L(M’) = A的补集 例：一个正则语言的补集 补自动机的构造 原始自动机 证明 证明方法 3.3 非确定性的有穷自动机 在FA的计算过程中，有的时候需要“猜测”的功能 例：证明正则语言在乘积运算下封闭 普通的FA无法“猜测” 需要一种机制能够同时计算所有的可能-非确定性 3.3 非确定性的有穷自动机 NFA( Nondeterministic Finite Automata ) DFA( Deterministic Finite Automata ) NFA与DFA的区别 从DFA的每一个状态出发，对于字母表中的每一个符号，最多只有一条迁移，而NFA可以有多条。 NFA允许“空转移”，也就是能够不读入任何符号就迁移到另外的状态。 3.3 非确定性的有穷自动机 3.3 非确定性的有穷自动机 NFA的计算方式 每当遇到多种选择的时候就分裂，并发计算这些选择。 当输入结束的时候，只要有一个分支接受，则接受。 例： 输入为1011 3.3.1 NF