编译原理4.ppt

* 六、编写词法分析程序 根据画出的状态转换图（识别单词）构造词法分析程序，每个状态对应一段程序，完成到达此状态的工作；词法分析程序的控制程序模拟状态转换图的状态转换。 在识别标识符的过程中，要拼写出来，并和保留字区别开来。 * = 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型语言。 3型语言可以用RE、RG、FA描述。 掌握下面涉及的一些概念，它们之间转换的技巧、方法或算法。 非形式描述的语言 ? 正规式 正规式 ? NFA 非形式描述的语言 ? NFA NFA ? DFA DFA ? 最简DFA 非形式描述的语言 ? DFA(或最简DFA) * 本 章 要 点 词法分析程序的编写: 用正规式编写词法，设置单词种别和属性 从单词的描述出发，逐步实现词法分析程序 正规表达式 ↓ 正规文法 ↓ 状态图 ↓ 识别过程的实现算法 ↓ 程序实现和测试 * 词法分析技术的其他应用: 查询语言，信息检索系统 识别由正规式描述的字符串 命令语言 识别命令格式 报文的处理 识别报文格式 应用范围： 数据格式可以用三型文法描述。 * 4.9 LEX语言 一组单词的正规式及其相应的语义动作叫做LEX语言。 它是用来描述词法分析程序的，因此通过LEX编译程序便可生成词法分析程序。 LEX编译程序 LEX 源程序 词法 分析器L 词法分析器L 输入串 单词 符号串 * LEX语言的组成 LEX源程序主要包括两部分，正规式的辅助定义和识别规则。 辅助定义是如下形式的LEX语句： D1?R1 D2?R2 …… Dn?Rn 每个Ri是一个正规式， Di是代表这个正规式的简名。 限定：在Ri中只许出现字母表Σ中的字符和前面已定义的简名D1,D2,…,Di-1，不得出现未定义的的简名。 * 语义动作的组成 当为每个正规式配上相应的语义规则后便形成LEX语句形式： P1 {A1} P2 {A2} … … Pm {Am} Pi为正规式，表明了这种词法分析程序只能识别具有句型为P1,P2,…,Pm的单词符号。 {Ai}为对应的语义子程序，式一段子程序，当识别出句型为Pi的单词之后，所应采取的动作，最基本的是返回Pi的二元式形式。 * 词法分析程序的控制程序的约定： 最长子串匹配原则 逐一扫描输入串的每一个字符，寻找一个最长子串匹配某个Pi，把这个串放入TOKEN缓冲区，然后调用相应Ai子程序，输出该单词的二元式交给语法分析程序处理。 优先原则 在LEX源程序中，语句的前后顺序是有意义的，认为排在前面的语句优先级高。 * LEX编译程序的构造 LEX编译程序旨在把一个LEX源程序改造成一个词法分析程序L。 LEX编译程序的生成过程： (1)对每个正规式Pi构造一个相应的NFA Mi； (2)引进一个初态X，通过弧，把这些NFA Mi连成一个新的NFA； (3)用子集法把它改造成一个等价的DFA。 * 1. ∑={a,b}，为下面所描述的串写正规式： 以ab结尾的所有串 偶数个b但不包含a的所有串 偶数个b、任意个a的所有串 只包含一个a的所有串 包含ab子串的所有串 不包含ab子串的所有串 练 习 (a|b)*ab (bb)* (a*ba*ba*)* b*ab* (a|b)*ab(a|b)* b*a* * 2. ∑={0,1}，请描述下面正规式所定义的串： 0*(100*)*0* (0|1)*(00|11)(0|1)* 1(0|1)*0 答案： 每个1至少有一个0跟在后边的串 所有含两个相继的0或两个相继的1的串 必须以1开头、以0结尾的串 * 3. 给出下列文法所对应的正规式： S?0A|1B A?1S|1 B?0S|0 答案： 解方程组S的解，将A、B代入S得： S=01S|01|10S|1=(01|10)S|(01|10) 所以：S=(01|10)*(01|10) * 4. 构造有穷自动机：