3.4.5 DFA的化简.ppt

3.6 词法分析程序的编写方法 8. retract( )函数，读字符指针回退一个字符。 9. return( )函数，收集并携带必要的信息返回调用程序，即返回语法分析程序。 10. dtb( ) ＋进制转换函数, 它将token中的数字串转换成二进制数值表示, 并以此作为函数值返回。 根据该语言的状态转换图用C语言编写出词法分析程序如下: Scaner( ) { token=NULL; getch( ); getbc( ); if (letter(ch)) { while(letter(ch) || digit(ch)) { concat( ); getch( ); } retract( ); c=reserve( ); if(c!=10) return(c,token); else return( 10,token); } 相对于状态转换图用C语言编写出词法分析程序如下: else if(digit(ch)) { while (digit(ch)) { concat( ); getch( ); } retract( ); return(11,dtb( )); } else switch(ch) { case’+’: return(13, ―); break ; case’-’: return(14, ―); break ; case’*’: return(15, ―); break ; case’/’: return(16, ―); break ; case’’: getch( ); if (ch= = `=′) return(17, ―); else if(ch= = `′) return(18, ―); retract( ); return(19, ―); break; case’: ’: getch( ); if(ch= = ’=’) return(22, ―); retract( ); return(21, ―); break; case’;’: return(23, ―); break; default: error( ); break; } } 由此可知, 只要构造出识别语言单词符号的有穷自动机, 就很容易构造出识别语言单词符号的词法分析程序。 3.6 词法分析程序的编写方法 本章小结 本章重点介绍了词法分析程序的设计思想和构造方法。主要内容有： 1. 词法分析程序的功能是从左到右扫描源程序字符串，根据语言的词法规则识别出各类单词符号。 输出单词符号的形式是二元组: （单词种别，单词自身值） 本章小结 例如定义“标识符”单词的正规式是 l (l | d)* 正规文法是 ＜标识符＞→ l |＜标识符＞l | ＜标识符＞d 2．程序语言单词符号的两种定义方式 正规文法 正规式 本章小结 3．有穷自动机有确定的和非确定两大类： NFA N = (Q , Σ , f , S , Z )其中f是多值映射函数，S为非空初态集。 有穷自动机通常表示为状态转换图，它是有穷自动机的非形式化描述。 DFA M = (Q , Σ , f , S , Z )其中是f单值映射函数，S是唯一初态 本章小结 从单词两种定义方式中构造词法分析程序的过程是： 正规式 正规文法 NFA 分裂法 转换规则 子集法 DFA 分化法 状态 最小化 DFA 词法 分析 程序 4．正规式、正规文法和有穷自动机三者都是描述正规集的工具, 它们的描述能力是等价的，它们之间可相互转换。 5．证明两正规式是等价的,如果它们的最小状态DFA是相同的。也可以利用正规式的基本等价关系将一个正规式化简来证明两正规式之间的等价性或两正规式识别的语言一样。 本章小结 本章小结 例1 构造正规式R=1(0|1)*101的状态最小化的DFA 分