第三章词法分析

null词法分析词法分析第三章 词法分析第三章 词法分析词法分析器(Scanner)的功能 正规表达式 状态转换图 词法分析器的设计与实现 有穷自动机FA3.1 词法分析（扫描）器的功能3.1 词法分析（扫描）器的功能功能：输入源程序，输出单词符号(token)。即：把构成源程序的字符串转换成单词符号的序列 单词符号的形式 按照最小的语义单位设计 通常表示为二元组： （单词种别，属性值 ） 关键——找出符号的分割符1) 单词符号的表示1) 单词符号的表示常用单词种别—分类（肖军模P53，杜P46） 各关键字（保留字、基本字），各种运算符，各种分界符——各用一个种别码标识 其它标识符——用一个种别码标识 整、实、字符常数——各用一个种别码标识 属性（值）——单词的值 常数的值，标识符的名字等 保留字、运算符、分界符的属性值可以省略例 3-1: 单词符号序列 while(*pointer!='\0'){pointer++;} 例 3-1: 单词符号序列 while(*pointer!='\0'){pointer++;} while (WHILE， _ ) ( (SLP， _ ) * (FETCH， _ ) pointer (IDN， 符号表入口指针) != (RELOP， NE ) '\0' (CONST， 0 ) ) (SRP， _ ) { (LP， _ ) pointer (IDN， 符号表入口指针) ++ (INC， _ ) ; (SEMI， _ ) } (RP， _ ) 跟实现有关2）相关问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 2）相关问题超前扫描 双字符运算符（**, /*,:=,…） DO 90 k=1,10 DO 90 k=1.10 预处理问题 剔除源程序中的无用符号、空格、换行、注释等 扫描器的运行方式 作为独立的遍：简单，但需增加额外的开销 作为独立的子程序：节省内存扫描器作为独立的子程序扫描器作为独立的子程序2）相关问题2）相关问题符号表的存储 线性表 哈希表 发现词法错误 行、列计数 发现并定位词法错误一种符号表的数据结构一种符号表的数据结构2）相关问题2）相关问题输入缓冲区2）相关问题2）相关问题双缓冲区问题__超前扫描导致的效率问题每次移动向前指针都需要做两次测试？如何设计和实现扫描器大小问题128Byte*2|1024Byte*2|4096Byte*2if forward在缓冲区第一部分末尾 then begin 重装缓冲区第二部分; forward := forward +1 end else if forward在缓冲区第二部分末尾 then begin 重装缓冲区第一部分; 将forward移到缓冲区第一部分开始 end else forward:= forward +1; forward := forward + 1; if forward↑= eof then begin if forward在第一部分末尾 then begin 重装第二部分; forward := forward +1 end else if forward在第二部分末尾 then begin 重装第一部分; 将forward 移到第一部分开始 end else /* eof 在表示输入结束 */ 终止词法分析 end 3.2 记号的描述__正规(表达)式3.2 记号的描述__正规(表达)式例：标识符的文法描述 约定：用digit表示数字：0,1,2,…,9; 用letter表示字母：A,B,…,Z,a,b,…,z G =({digit,letter}, {S}, P, S) S→letter L→letter|letter T S→S digit T→Letter T|letter S→S letter T→digit T|digit 左线性 右线性 表示集合：{letter}{letter,digit}* 1) 正规式：正规语言的另一种描述方法1) 正规式：正规语言的另一种描述方法例3-2：标识符的另一种表示 letter(letter|digit)* | 表示"或" * 表示Kleene闭包 Letter和(letter|digit)*的并列表示两者的连接 正规式 r 表示正规集,相应的正规集记为 L(r) 正规(表达)式(Regular Expression——RE)正规(表达)式(Regular Expression——RE)设∑是一个字母表， ⑴ Φ是∑上的RE，L(Φ)=Φ； ⑵ ε是∑上的RE，L(ε)={ε}； ⑶ 对于a∈∑，a是RE，L(a)={a}； ⑷如果r和s是RE，L(r)=R,L(s)=S，则： r与s的“和” (r|s)是RE，L(r|s)=R∪S； r与s的“乘积” (rs)是RE，L(rs)=RS； r的克林闭包(r*)是RE，L(r*)=R*。 ⑸ 只有满足⑴、⑵、⑶、⑷的才是RE。 运算的优先级运算的优先级运算优先级和结合性: *高于“连接” 和| ， “连接” 高于 | |具有交换律、结合律 “连接” 具有结合律、和对|的分配律 ( )指定优先关系 意义清楚时，括号可以省略 例：L(a(a|b)*(ε|((.|_)(a|b)(a|b)*))) {a}{a,b}*({ε}∪{.,_}{a,b}{a,b}* )2) 正规文法与正规式2) 正规文法与正规式正规文法与正规式等价 对任何正规文法，存在定义同一语言的正规式 对任何正规式，存在生成同一语言的正规文法例 3-3 标识符定义的转换例 3-3 标识符定义的转换引入 S S→letter (letter|digit)* 引入A消除闭包 S→letter A A→(letter|digit)A|ε 执行连接对|的分配律 S→letter A A→letter A|digit A|ε 例3-4正规式到正规文法的转换例3-4正规式到正规文法的转换a(a|b)*(ε|((.|_)(a|b)(a|b)*)) = a(a|b)* |a(a|b)*.(a(a|b)*|b(a|b)*) |a(a|b)*_(a(a|b)*|b(a|b)*) =aA|aC A=aA|bA|ε C=aC|bC|.B|_B B=aA|bAS→aA|aC A→aA|bA|ε C→aC|bC|.B|_B B→aA|bA正规式到正规文法的转换正规式到正规文法的转换按如下方法构造正 规定 关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定 义式，并逐步将其转换成正则文法 引入开始符号S，从如下正规定义式开始 S→r 对r中的形如r1|r2|…|rn的子串 用产生式组 A→ r1|r2|…|rn 表示正规式到正规文法的转换正规式到正规文法的转换对r中的形如r1*的子串 用产生式组 A→ε|r1A 表示 对r中的形如r1+的子式子， 用产生式组 A→ r1| r1A 表示 执行连接对|的分配律 正规式到正规文法的转换用到了正规定义式的概念。正规文法到正规式的转换正规文法到正规式的转换代入：对于 A→xB, B→y，构造 A→xy 递归：对于 A→xA|y，构造 A→x*y 多候选式：对于 A→x，A→y，构造A→x|y S→0A A→1B B→2B|2C C→3C|3 S→01B S→012*2C S→012*23*3=012+3+ 一个语言的文法描述不是唯一的（文法的等价）3) 高级语言词法的简单描述3) 高级语言词法的简单描述词法 单词符号的文法，用来描述高级语言中的：标识符、常数、运算符、分界符、关键字 思考如何定义高级语言中的整数、实数……等的相应正则文法。例 3-5：某简易语言的词法——正规定义式例 3-5：某简易语言的词法——正规定义式 词法规则 单词种别 属性 <标识符>→<字母>(<字母>|<数字>)* IDN 符号表入口 <无符号整数>→ <数字> (<数字>)* NUM 数值 <赋值符>→ := ASG 无 其它单词→字符本身 单词名称 无 变换为正规文法变换为正规文法<标识符>→letter<标识符尾> <标识符尾>→ε|letter<标识符尾>|digit<标识符尾> <整数>→digit <整数尾> <整数尾>→ε| digit<整数尾> <赋值号>→:= <加号>→+ <等号>→= … (其它：实数、算术运算符、关系运算符、分号、括号等）问题：如何识别记号？3.3 记号的识别──状态转换图3.3 记号的识别──状态转换图1 状态转换图（有穷自动机 FA M=(Q，∑，δ，q0，F) ） 用来描述词法分析器识别记号时要做的动作 结点：状态用○表示；终态用◎表示 有向弧 ── 箭头 弧标记 ── 输入字符 标识符的状态图<标识符>→<字母>(<字母>|<数字>)* 123letterletter,digit其它开始终态初态例3-5的状态图例3-5的状态图letter,digitletter（IDN，入口）digitdigit(其它) (其它)（NUM，值）（ASG，_）=：+（ADD，_）s+（INC，_）其它IDN→letter(letter|digit)*NUM→digit(digit)*ASG→:=INC→++利用状态转换图识别单词利用状态转换图识别单词1. 从初态出发 2. 读入一字符 3. 按当前字符转入下一状态 4. 重复 2,3 直到无法继续转移 #. 在遇到读入的字符是Token的分割符时，若当前状态是终止状态，说明读入的字符组成一单词；否则，说明输入不符合词法规则。2、从正规文法出发，构造状态图2、从正规文法出发，构造状态图1.以每个非终结符为状态结点，开始符号对应初态 S； 2.增设一个终态 T； 3.对于规则 A→aB，画从状态 A 到 B 的弧，标为 a； 4.对于规则 A→a，画从状态 A 到终态 T 的弧，标为 a。 * 对于规则 A→rs*，画从状态 A 到状态 N 的弧，标为 r和状态N到N的标记为s的弧例 3-6 Ｃ语言无符号整数的识别 1、正规定义式描述例 3-6 Ｃ语言无符号整数的识别 1、正规定义式描述八进制数: ( OCT，值 ) oct→0(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)* 十进制数: ( DEC，值 ) dec→(1|...|9)(0|...|9)* |0 十六进制数: ( HEX，值 ) hex→0x(0|1|...|9|a|...|f|A|…|F)(0|...|9|a|...|f |A|…|F)*2、识别不同进制数的状态图2、识别不同进制数的状态图342100-70-7(其它)56101-90-9 (其它)十进制整数八进制整数oct→0(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)*dec→(1|...|9)(0|...|9)* |02、识别不同进制数的状态图2、识别不同进制数的状态图状态图合并 1、从开始状态出发； 2、选择输入符号，构成目标状态集 3、从新状态集出发，重复1、2910810 (其它)十六进制整数7x0-9,a-f0-9,a-fhex→0x(0|1|...|9|a|...|f|A|…|F)(0|...|9|a|...|f |A|…|F)*3、Ｃ语言无符号整数识别的状态图3、Ｃ语言无符号整数识别的状态图（HEX，值）（OCT，值）9,10810其他2,6,7x0-9 ,a-f0-9,a-f 3,40-70-7其他51-90-9其他（DEC，值）其他3.4 词法分析程序的设计与实现3.4 词法分析程序的设计与实现状态转移图——教材P68 状态转移图的实现——教材P68-72 子程序 scan( ) 输入：字符流 输出： Symbol:单词种别 Attr:属性（全局变量）数据结构与子例程数据结构与子例程数据结构 ch 当前输入字符 token 输入缓冲区(字符数组) symbol 单词种别（子程序的返回值） attr 属性（全局变量） 子例程 Lookup(token):将 token 存入符号表，返回入口指针 isKeyword(token):判别 token是关键字？返回关键字种别或 -1 getchar():从输入缓冲区中读入一个字符放入ch isLetter() isalpha() 例3-3的状态图的实现算法例3-3的状态图的实现算法1. getchar() 2. WHILE ch 是空格 //跳过空格 2.1 DO getchar(); 3. CASE ch OF 4. isdigit(ch) : 4.1 ch→token; getchar(); 4.2 WHILE isdigit(ch) DO ch→token; getchar(); 4.3 输入指针回退一个字符； 4.4 将token中的字符串变成数值→attr 4.5 返回 NUMnull5. isletter(ch) : 5.1 ch→token; getchar(); 5.2 WHILE isletter(ch) OR isdigit(ch) DO ch→token; getchar(); 5.3 输入指针回退一个字符; 5.4 key = isKeyword(token); 5.5 IF key≥0 THEN 返回 key 5.6 Lookup(token)→attr; 5.7 返回 IDN 6 ':' : getchar(); 6.1 IF ch等于'=' THEN 返回 ASG 6.2 出错处理null7 '+' : 返回 ADD 8 '-' : 返回 SUB 9 '*' : 返回 MUL 10 '/' : 返回 DIV 11 '=' : 返回 EQ 12 '>' : 返回 GT 13 '<' : 返回 LT 14 '(' : 返回 LP 15 ')' : 返回 RP 16 ';' : 返回 SEMI 17 其它 : 出错处理 18 END OF CASE需要说明的问题需要说明的问题缓冲区预处理，超前搜索 关键字的处理，符号表的实现 Lookup：查找效率，算法的优化实现 词法错误处理 由于高级语言的词组成的集合为3型语言，所以，这里讨论的词法分析技术可以用于处理所有的3型语言，也就是所有的可以用3型文法描述的语言。如：信息检索系统的查询语言、命令语言等LEX简介：实现过程LEX简介：实现过程Lex源程序Lex.yy.cLex编译器词法分析器LLex.yy.cC编译器Token序列词法分析器L输入流LEX简介：Lex程序结构LEX简介：Lex程序结构声明部分 (正规定义式) %% 转换规则 (识别规则) %% 辅助过程%{ 常量定义 %} 正规定义扫描器的自动生成：LEX简介扫描器的自动生成：LEX简介1、正规定义式 letter→A|B|C|…|Z|a|b|c|…|z digit→0|1|2|…|9 identifier→letter(letter|digit)* integer→digit(digit)* 2、识别规则 正规式 动作描述 token1 {action1} token2 {action2} …… tokenn {actionn}null%{ #include #include #include #define BEGIN 1 #define END 2 #define IF 3 #define THEN 4 #define ELSE 5 #define ID 6 #define INT 7 #define LT 8 #define LE 9 #define EQ 10 #define NE 11 #define GT 12 #define GE 13 %} digit [0-9] alpha [a-zA-Z]alnum [a-zA-Z0-9] %% begin {OUT(BEGIN,NULL);} end {OUT(END,NULL);} if {OUT(IF,NULL);} then {OUT(THEN,NULL);} else {OUT(ELSE,NULL);} {alpha}{alnum}* {OUT(ID,yytext);} {digit}+ {OUT(INT,yytext);} “<” {OUT(LT,NULL);} “<=” {OUT(LE,NULL);} “=” {OUT(EQ,NULL);} “<>” {OUT(NE,NULL);} “>” {OUT(GT,NULL);} “>=” {OUT(GE,NULL);} %% OUT(int c, char *val) {…}有穷自动机有穷自动机确定的有穷自动机 不确定的有穷自动机 从NFA到DFA的转换 确定的有限自动机的化简 正规表达式与有穷自动机的等价有穷自动机有穷自动机具有离散输入输出的系统的数学模型 具有有限个内部状态 系统只需根据当前所处的状态和面临的输入就能确定后继的行为，处理完当前输入后系统的状态将发生变化 具有初始状态和终止状态 例：电梯、文本编辑程序、词法分析程序……有穷自动机模型有穷自动机模型设想有个按钮，启动后，自动机一个动作一个动作地做下去，…，直到没有输入，停。如果停在终态，接收；如果停在非终态，不接收。一个动作： 【p，a】→q，读头前进一格。FA能接收的符号行的集合即为其接收的语言。有穷自动机的用处有穷自动机的用处有穷自动机是许多重要类型的硬件和软件的有用模型 数字电路的设计和检查软件 典型编译器的词法分析器 扫描大量文本来发现单词、短语或其他模式的出现的软件 所有只有有穷个不同状态的系统（如通信 协议 离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载 或安全交换信息的协议）的验证软件例如：一个奇偶校验器例如：一个奇偶校验器测试输入中1的个数的奇偶性，并且只接收含有奇数个1的那些输入串。问题：有穷自动机的形式描述？ 关键是如何描述动作？注意：状态有记忆功能，记住输入串的部分特征。3.5 确定的有限自动机 DFA3.5 确定的有限自动机 DFADFA的定义 DFA的三种表示 DFA接受的语言 DFA判定w是否属于L(M)的模拟算法确定的有穷自动机的定义确定的有穷自动机的定义定义 一个确定的有穷自动机 M（记作DFA M）是一个五元组 Ｍ＝（Σ，Ｑ，ｑ0，Ｆ，δ），其中 （ａ）Ｑ是一个有穷状态集合。 （ｂ）Σ是一个字母表，它的每个元素称 为一个输入符号。 （ｃ）ｑ0∈Ｑ，ｑ0 称为初始状态。 （ｄ）Ｆ∈Ｑ，Ｆ称为终结状态集合。 （ｅ）δ是一个从Ｑ×Σ到Ｑ的单值映射 δ(p，ａ)＝ｑ（p,ｑ∈Ｑ，ａ∈Σ） 表示当前状态为p,输入符号为a时，自动机将转换到下一个状态ｑ，ｑ称为p的一个后继。DFA的表示DFA的表示例3．3 设ＤＦＡ　Ｍ＝（｛ａ，ｂ｝，｛０，１，２， ３｝，０，｛３｝，δ）其中 δ（０，ａ）＝１，δ（１，ａ）＝3 δ（２，ａ）＝１，δ（３，ａ）＝３ δ（０，ｂ）＝２，δ（１，ｂ）＝２ δ（２，ｂ）＝３，δ（３，ｂ）＝３ 一个ＤＦＡ有三种表示： （1）转换函数； （2）转移矩阵； （3）状态转换图。nullnull从状态转换图看，从初态出发，沿任一条路径到达接受状态，这条路径上的弧上的标记符号连接起来构成的符号串被接受。 如：abab0123aaaabbbbDFA M接受的语言问题：如何形式描述DFA接收的语言？DFA M接受的语言DFA M接受的语言如果对所有ｗ∈Σ*，a∈Σ，ｑ∈Ｑ以下述方式递归地扩展δ的定义 δ'（ｑ，ε）＝ｑ， δ'(ｑ，ｗａ）＝δ(δ'(ｑ，w），ａ）， 则M所接收的语言为： Ｌ（Ｍ）＝｛ｗ｜ｗ∈Σ*，若存在ｑ∈Ｆ， 使δ（ｑ０，ｗ）＝ｑ｝ 对于例3.3的DFA M和w=baa， δ(0，baａ）=δ(2,aａ）= δ(1,ａ）=3DFA M判定 ｗ∈?Ｌ(Ｍ）的算法：DFA M判定 ｗ∈?Ｌ(Ｍ）的算法：输入：ｗ＃ q := q0; a := nextchar; while a <> “＃" do begin q := move(q,a); a := nextchar; end; if q in F then return ("yes") else return ("no");3.6非确定的有穷自动机NFA M3.6非确定的有穷自动机NFA M定义 非确定的有限自动机Ｍ是一个五元组 M＝（Σ，Ｑ，q０，Ｆ，δ） 其中Σ，Ｑ，q０，Ｆ的意义和ＤＦＡ的定义一样，而δ是一个从ＱΣ∪{ε}到Ｑ的子集的映射，即δ：ＱＳ２Ｑ，其中S= Σ∪{ε}。 类似于ＤFA，NFA M亦可用状态转换图表示，同样也可以定义NFA M接受的语言。FA的等价性FA的等价性定理3 . 1 对任何一个NFA M，都存在一个 DFA M´，使L(M´)=L(M) 证明思想：让DFA的每个状态对应NFA的一个状态集。这个DFA用它的一个状态去记住NFA在读输入符号后到达的所有状态。也就是说，在读了输入a1a2…an后，DFA到达一个代表NFA的状态子集T的状态。这个子集T是从NFA的开始状态沿着那些标有a1a2…an的路径能到达的所有状态的集合。 从识别语言的角度看就是 等价的状态从NFA构造DFA的算法从NFA构造DFA的算法将T中所有的状态压入栈stack中； 将ε-closure(T)初始化为T; while 栈stack不空 do begin 将栈顶元素t 弹出栈； for 每个这样的状态u：从t到u有一条标记为ε的边 do begin 将u添加到ε-closure(T)； 将u压入栈stack中 end end 图3.26 ε-closure的计算null算法3.2 (子集构造算法)从NFA构造DFA。 输入：一个NFA N； 输出：一个接受同样语言的DFA D。 方法：为D构造转换表Dtran，DFA的每个状态是NFA的状态集，D将“并行”地模拟N对输入串的所有可能的移动。 初始时，ε-closure(s0)是Dstates中唯一的状态且未被标记； while Dstates中存在一个未标记的状态T do begin 标记T; for 每个输入符号a do begin U := ε-closure(move(T，a)); if U没在Dstates中 then 将U作为一个未标记的状态添加到Dstates中； Dtran[T, a] := U end end nullA＝{0，l，2，4，7} B＝{1，2，3，4，6，7，8} C＝{1，2，4，5，6，7} D＝{1，2，4，5，6，7，9} E＝{ l，2，4，5，6，7，10}ε-closure(0)，即A＝{ 0，l，2，4，7} ε-closure(move（A, a）) = ε-closure(move{0，l，2，4，7}，a)＝ ε-closure({3，8})＝{ l，2，3，4，6，7，8}=B, Dtran[A，a]＝B ε-closure(move（A, b）) =ε-closure({5}) = {1, 2, 4, 5, 6, 7} = C，Dtran[A，b]＝C …*有穷状态自动机的构造 *有穷状态自动机的构造 例3.4.1 构造一个DFA，它接受的语言为{x000y|x，y∈{0，1}*} q0——M的启动状态； q1——M读到了一个0，这个0可能是子串“000”的第1个0； q2——M在q1后紧接着又读到了一个0，这个0可能是子串“000”的第2个0； q3——M在q2后紧接着又读到了一个0，发现输入字符串含有子串“000”；因此，这个状态应该是终止状态。*有穷状态自动机的构造*有穷状态自动机的构造δ(q0,1)= q0——M在q0读到了一个1，它需要继续在q0 “等待”可能是子串“000”的第1个0的输入字符0； δ(q1,1)= q0——M在刚刚读到了一个0后，读到了一个1，表明在读入这个1之前所读入的0并不是子串“000”的第1个0，因此，M需要重新回到状态q0，以寻找子串“000”的第1个0； *有穷状态自动机的构造*有穷状态自动机的构造δ(q2,1)= q0——M在刚刚发现了00后，读到了一个1，表明在读入这个1之前所读入的00并不是子串“000”的前两个0，因此，M需要重新回到状态q0，以寻找子串“000”的第1个0； δ(q3,0)= q3——M找到了子串“000”，只用读入该串的剩余部分。 δ(q3,1)= q3——M找到了子串“000”，只用读入该串的剩余部分。 *有穷状态自动机的构造*有穷状态自动机的构造M=({q0，q1，q2，q3}，{0，1}，{ (q0,0)= q1，δ(q1,0)= q2，δ(q2,0)= q3，δ(q0,1)= q0，δ(q1,1)= q0，δ(q2,1)= q0，δ(q3,0)= q3，δ(q3,1)= q3}，q0，{q3}) *有穷状态自动机的构造*有穷状态自动机的构造一种更为直观的表示*有穷状态自动机的构造*有穷状态自动机的构造例3.4.2构造一个DFA，它接受的语言为{x000|x∈{0，1}*}。 状态q0读到的0可能是输入字符串的最后三个0的第1个0； 在状态q1紧接着读到的0可能是输入字符串的最后三个0的第2个0； 在状态q2紧接着读到的0可能是输入字符串的最后三个0的第3个0；*有穷状态自动机的构造*有穷状态自动机的构造在状态q3紧接着读到的0也可能是输入字符串的最后三个0的第3个0； 如果在状态q1，q2，q3读到的是1，则要重新检查输入串是否以三个0结尾。 *有穷状态自动机的构造*有穷状态自动机的构造例3.4.3 构造一个DFA，它接受的语言为{0n1m2k|n,m,k≥1}。 q0——M的启动状态； q1——M读到至少一个0，并等待读更多的0； q2——M读到至少一个0后，读到了至少一个1，并等待读更多的1； q3——M读到至少一个0后跟至少一个1后，并且接着读到了至少一个2。 *有穷状态自动机的构造*有穷状态自动机的构造先设计“主体框架”再补充细节*有穷状态自动机的构造*有穷状态自动机的构造 当FA一旦进入状态qt，它就无法离开此状态。所以，qt相当于一个陷阱(死)状态(trap)。一般地，我们将陷阱状态用作在其他状态下发现输入串不可能是该FA所识别的语言的句子时进入的状态。在此状态下，FA读完输入串中剩余的字符。 *有穷状态自动机的构造*有穷状态自动机的构造例3.4.4 构造接受{x|x∈{0，1}*，且x含有子串00或11}的FA。*有穷状态自动机的构造*有穷状态自动机的构造例3.4.5 构造接受{x|x∈{0，1}*，且x 的倒数第10个字符为1}的FA。*有穷状态自动机的构造*有穷状态自动机的构造例3.4.6 接受语言{0n1m2k|n，m，k≥0}的NFA*有穷状态自动机的构造*有穷状态自动机的构造接受语言{0n1m2k|n，m，k≥0}的ε-NFA确定的有限自动机的化简确定的有限自动机的化简一. 何谓确定的有限自动机的化简 所谓一个DFA M=(, Q, q0, F, )的化简是指寻找一个状态数比较少的DFA M´,使 L(M)=L(M´)。而且可以证明， 存在一个最少状态的DFA M´, 使L(M)=L(M´)。 二.等价状态的定义 设p,q Q ，若对任何w * , (p,w) F 当且仅当 (q,w) F ，则称p和q是等价状态。否则，称p和q是可区别的。nullq1q2q3q4q1q2q3q6q4q5q7baaaaaaaaaaabbb,bbbbbbbnull1.等价状态定义了状态集合上的等价关系。因此，状态集合能被划分成等价类； 2 .两个状态p和q等价应满足如下条件： （a）一致性条件， p和q必须同时或为接受 状态或为非接受状态； （b）蔓延性条件，对于a  ， （p,a)=r, （q,a)=s, r和s必须等价; 相反, r和s不等价, 则p和q不等价。 判定两个状态p和q不等价，只要找到一个w*， 使（p,w)F 且（q,w)  F，或者相反。 w称为判别序列。null三. 方法： 构造一张表，对每一个状态对（qi,qj）（i]为： <单词> → <标识符> | <整数> <标识符> → <标识符> <字母> | <标识符> <数字> | <字母> <整数> → <整数> <数字> | <数字> <字母> → A | B | … | Y | Z <数字> → 1 | 2 | … | 8 | 9 | 0 将该文法改写为正规文法 4）上机题 设计并实现一个词法分析函数，每次返回一个单词种别和属性；编制主程序完成测试（输入和输出）。实验 报告 软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载 要求实验报告要求实验题目 实验目的 实验内容和要求 给出语言的词法规则描述 标识符、关键字、整常数、字符常数、浮点常数 单界符：＋，－，×，：，… 双界符：/*，:=，… 注释 出错处理：位置、类型等 数据结构设计：符号表、关键字等 状态转换图和程序框图 测试 测试样例 输出结果