[工学]z第三章 词法分析.ppt

第三章 词法分析 3.1 词法分析的任务 3.2 正则文法与状态转换图 3.3 有限自动机 3.4 正规式和正规集 3.5 扫描器生成 习题三 编译程序首先是在单词级别上来分析和翻译源程序的。 词法分析的任务是：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。因此，词法分析是编译的基础。 执行词法分析的程序称为词法分析器或称扫描器 。 词法分析程序的功能 词法分析程序主要执行以下功能： 读入源程序字符串，识别开具有独立含义的最小语法单位——单词（符号）； 把单词变换成长度统一的且为定长的属性字； 其他功能： 滤掉空格，跳过注释、换行符 某些预加工处理 3.1 词法分析的任务 词法分析程序的任务：读入源程序，输出单词符号。 单词一般分为5类： 1. 基本字，也称关键词。如PASCAL语言中的begin，end，if，while和var等。 2. 标识符。用来表示各种名字，如常量名、变量名、过程名和函数名等。 3. 常数。各种类型的常数，如25，2.71828，a，hello和TRUE等。 4. 算符。如+，-，*，=等。 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,‘;’) 单词类别:通常用整数编码。一个语言的单词符号如何分种，分成几种，怎样编码是一个技术问题。它取决于处理上的方便。 标识符一般统归为一类。 常数则宜按类型（整、实、布尔等）分类。 关键字可视其全体为一类，也可以一字一类。采用一字一类的分法实际处理起来较为方便。 运算符可采用一符一类的分法，但也可以把具有一定共性的运算符视为一类。 至于界符一般一符一类的分法。 词法分析程序的实现方式 完全独立方式：词法分析程序作为单独一趟来实现。词法分析程序读入整个源程序，它的输出作为语法分析程序的输入。 相对独立方式：把词法分析程序作为语法分析程序的一个独立子程序。语法分析程序需要新符号时调用这个子程序。 将词法分析编成一个子程序，该子程序由语法分析程序调用，当语法分析程序需要一个新的单词时，就调用该子程序，每调用一次，则从源程序字符串中，读出一个具有独立意义的单词。 避免了中间文件的生成，可以提高编译程序的效率。 将扫描器分离的考虑 词法是语法的一部分。 分成词法分析和语法分析两个阶段的主要原因： 1. 使整个编译程序的结构更简洁、清晰和条理化。 2. 编译程序的效率会提高。 3. 增强编译程序的可移植性。 第三章 词法分析 3.1 词法分析的任务 3.2 正则文法与状态转换图 3.3 有限自动机 3.4 正规式和正规集 3.5 扫描器生成 习题三 3.2 正则文法与状态转换图 右图表示一个定义在字母表∑={0,1}上的状态转换图 3.2 正则文法与状态转换图 状态转换图 定义在字母表∑上的有向图。 结点代表状态； 状态之间用有向弧连结； 有向弧上的标记（字符）表示在射出结点（有向弧的开始结点）所代表的状态下可能出现的输入符号或符号串（可以是空串）。 用状态转换图可以设计词法分析程序（扫描器）。 状态转换图中只包含有限个状态（结点）。 状态转换图的作用 一个状态转换图可用于接受（或识别）一定的符号串。 在状态转换图中从初始状态到某一终止状态的序列为路。 对于某一符号串β，在状态转换图中，若