编译原理第三章 词法分析222.ppt

第三章 词法分析 3.1 词法分析的任务 3.2 正则文法与状态转换图 3.3 有限自动机 3.4 正规式和正规集 3.5 扫描器生成 习题三 词法分析程序 词法分析是编译过程中的一个阶段，在语法分析前进行 ，也可以和语法分析结合在一起作为一遍。 输入：源程序字符串 输出：等价的属性字序列（内部表示形式） 词法分析程序的功能 词法分析程序主要执行以下功能： 读入源程序字符串，识别开具有独立含义的最小语法单位——单词（符号）； 把单词变换成长度统一的且为定长的属性字； 其他功能： 某些预加工处理----滤掉空格，跳过注释、换行符 单词表示形式： 常表示成二元式形式： (单词类别, 单词的值) 单词的类别是语法分析需要的信息， 单词自身的值则是编译其它阶段需要的信息,简称单词值。 如：语句const i=25,yes=1中的单词25和1的类别都是常数，其值分别为25和1； 对于标识符来说，还需要记载它的类别、所在层次等其它属性，这些属性一般都收集在符号表中，所以标识符的二元式形式相应地表示成： (标识符, 指针) 指针:指向该标识符在符号表的位置 单词类别:通常用整数编码。 一个语言的单词符号如何分类，分成几类，怎样编码取决于处理上的方便。 标识符一般统归为一类。 常数则宜按类型（整、实、布尔等）分类。 关键字可视其全体为一类，也可以一字一类。采用一字一类的分法实际处理起来较为方便。 运算符可采用一符一类的分法，也可以把具有一定共性的运算符视为一类。 至于界符一般一符一类的分法。 若是一符一类，单词自身值就不需要了。否则，要查符号表。 例如程序段 if i=5 then x:= y； 在经过词法分析单词可表示如下： 保留字if (3,‘if’) 标识符i (1, 指向i的符号表入口) 等号= (4,‘=’) 常数5 (2,‘5’的二进制表示) 保留字then (3,‘then’) 标识符x (1, 指向x的符号表入口) 赋值号:= (4,‘:= ’) 标识符y (1, 指向y的符号表入口) 分号; (5,‘;’) 标识符的识别 多数语言的标识符是字母开头的“字母/数字”串，而且在程序中标识符的出现后都跟着算符或界符。因此，不难识别。 常数的识别 对于某些语言的常数的识别也需要使用超前有哪些信誉好的足球投注网站。 算符和界符的识别 对于诸如C++语言中的“+ +”、“- -”，这种复合成的算符，需要超前有哪些信誉好的足球投注网站。 词法分析程序的实现方式 完全独立方式：词法分析程序作为单独一遍来实现。词法分析程序读入整个源程序，它的输出作为语法分析程序的输入。 相对独立方式：把词法分析程序作为语法分析程序的一个独立子程序。语法分析程序需要新符号时调用这个子程序。 相对独立方式 当采用递归下降分析等技术常采用这种方式。 用于实现程序一遍编译。 将扫描器分离的考虑 词法是语法的一部分。 编译程序分成词法分析和语法分析两阶段的原因： 1. 使整个编译程序的结构更简洁、清晰和条理化。识别单词的工作比较曲折和费时，如果合在一起考虑，会使分析程序的结构复杂得多。 2. 编译程序的效率会提高。 采用专门的读字符和分离单词技术可大大加快编译速度 ；进而可建立词法分析程序的自动构造工具。 3. 增强编译程序的可移植性。 比如解决编码问题等等。 右图表示一个定义在字母表∑={0,1}上的状态转换图 状态转换图的作用 作用:一个状态转换图可用于接受（或识别）一定的符号串。 路:在状态转换图中从初始状态到某一终止状态的弧上的标记序列。 对于某一符号串β，在状态转换图中，若存在一条路产生β，则称状态转换图接受（或识别）该符号串β，否则称符号串β不能被接受。 能被状态转换图TG接受的符号串的集合记为L(TG)，我们称它为状态转换图所能识别的语言。 由状态转换图3-3可见，字母表∑上的符号串 L(TG)={ 0，1，00，01，11，001，010，…} 字母表∑={a,b}上的一个转换图 L(TG)={ a，b，ab，ba，aaa，bbb，aab，bba，…} 状态转换图的实现 转换图比较容易用程序实现。 最简单的方法是让每个状态结点对应一小段程序（3.5 详细介绍）。 3.2.2正则文法的