编译原理第三章(1425KB).PPT

* “分割法”：把一个DFA(不含多余状态)的状态分割成一些不相关的子集，使得任何不同的两个子集状态都是可区别的，而同一个子集中的任何状态都是等价的. 例1:最小化 5 7 2 4 3 6 1 srart a a a a a a a b b b b b b b 状态集的划分 将所有DFA的终态与其它状态划分成两个子集G1,G2; 分别从两个子集G1,G2中寻找等价状态进行化简。 * 解: (一)区分终态与非终态 1 2 3 4 5 6 6 3 7 3 1 5 4 6 7 3 7 4 1 4 2 1 2 a b 5 6 7 3 7 4 1 4 2 a b 1 2 3 4 6 3 7 3 1 5 4 6 1 2 3 区号 区号 5 7 2 4 3 6 1 srart a a a a a a a b b b b b b b 将所有DFA的终态与其它状态划分成两个子集 * 1 2 3 4 5 6 6 3 7 3 1 5 4 6 7 3 7 4 1 4 2 a b 1 2 4 3 1 2 4 3 1 2 3 4 5 6 6 3 7 3 1 5 4 6 7 3 7 4 1 4 2 a b 5 区号 区号 1 2 3 4 5 a b 5 2 1 4 3 5 5 2 3 1 1 5 5 2 4 3 a a a a a b b b b b 5 6 7 3 7 4 1 4 2 a b 1 2 3 4 6 3 7 3 1 5 4 6 1 2 3 区号 将区号代替 状态号得: * 3.4.6有穷自动机到正规式的转换 正规式到有穷自动机转换的逆过程 * 3.6词法分析程序的编写方法 * 第三章 词法分析 3. 1 词法分析程序的功能：词法分析器的功能，输出，把它组织成单独程序 3 . 2 单词及输出单词的形式 3 . 3 语言单词符号的两种定义方式 3 . 4 正规式与由穷自动机 3 . 5 正规文法与有穷自动机 3 . 6词法分析程序的编写方法 * = 8 0 ; 0 1 3 4 2 5 6 e n i L 字母 字母 字母 字母 数字 数字 数字 = = ； ； 0 1 2 4 5 6 3 L i n e = 8 0 ; ? id , ‘Line’? ? = , ?? ? ? num, ‘80’? ? ;, ?? ? 数字 数字 字母 字母 1 1 = = 0 0 0 3 ; ; 1 输入 输出 有穷自动机 * 3.1 词法分析程序的设计 3.1.1 词法分析程序的功能 源程序 单词符号 词法分析器 * While i＜＞j do if i＞j then i:＝i-j else j:=j－I ‘while’，‘i’，‘＜＞’，‘j’， ‘do’， ‘if’，‘i’，‘＞’，‘j’,‘then’, i, :=’ , i, ’-’ , j, else, j, :=, j, -, ‘i 词法分析器 * 3.2单词符号及输出单词的形式 3.2.1语言的单词符号 程序语言单词的分类： 1．关键字(保留字或基本字)：if，else，for 2．标识符：用来表示各种名字，变量名、常量名、数组名等等 3．常数：256，3 .14，true 4． 运算符：如，＋、－、*、/ 等等 5．分界符：如逗号，分号，冒号等 * 3.2.2词法分析器的输出单词的形式： （单词种别，单词自身的属性值） 单词种别提供给语法分析程序使用；单词自身的属性值提供给语义分析程序使用。 单词种别具体的分类设计以方便语法分析程序使用为原则。关键字可分成一类，也可以一个关键字分成一类。常数可统归一类，也可按类型（整型、实型、布尔型等），每个类型的常数划分成一类。单词自身的属性值提供的内容，是由词法分析和语义分析的任务划分决定的。 * 例如：图3．1的源程序经词法分析器〈while，—— 〉 〈id，指向i的符号表人口的指针〉 〈relational－op ， NE 〉 〈id，指向j的符号表人口的指针〉 〈do，—— 〉 〈if，——〉 〈id，指向i的符号表入口的指针〉 ???? 〈id，指向j的符号表入口的指针〉 * 词法分析器的手工构造 为了构造词法分析器，要研究构词法，每种词类的结构模式以及识别它的数学模型——有穷自动机。它的模拟程序可以作为词法分析器的控制程序。 3.3语言单词符号的两种定义方式 正规文法 正规式 * 一. 正规表达式的定义 ?是字母表