三章词法分析.pptVIP

中南大学软件学院 陈志刚 第三章 词法分析 3.1 词法分析概述 3.2 词法分析程序的设计 3.3 正规式与有限自动机 3.4 词法分析程序的实现 3.5 词法分析器的自动生成 3.1 词法分析概述 词法分析程序 词法分析是编译过程中的一个阶段，在语法分析前进行 ，也可以和语法分析结合在一起作为一遍。 输入：源程序字符串 输出：等价的属性字序列（内部表示形式） 3.1 词法分析概述 一、词法分析程序的任务 从左至右逐个字符地扫描源程序，产生一 个个单词符号。把作为字符的源程序改造为 单词符号串组成的中间程序，执行词法分析 任务的程序称为词法分析器或称扫描器。 二、词法分析程序的功能 词法分析程序主要执行以下功能： 读入源程序字符串，识别开具有独立含义的最小语法单位——单词（符号）； 把单词变换成长度统一的且为定长的属性字； 其他功能： 滤掉空格，跳过注释、换行符 某些预加工处理 三、词法分析程序的安排 常常把词法分析程序作为独立的一遍或作为被语法分析程序所调用的子程序。 1、作为独立的一遍： 语法分析前进行词法分析，把单词符号串形成中间文件存贮。 三、词法分析程序的安排 2、作为被语法分析器词用的子程序： 四、词法分析程序的实现方式 相对独立方式：把词法分析程序作为语法分析程序的一个独立子程序。语法分析程序需要新符号时调用这个子程序。 完全独立方式：词法分析程序作为单独一趟来实现。词法分析程序读入整个源程序，它的输出作为语法分析程序的输入。 相对独立方式 当采用递归下降分析等技术实现一趟编译程序时常采用这种方式。 完全独立方式 采用词法分析工作完全独立的原因： 简化设计，降低语法分析的复杂性 提高编译效率 增加编译系统的可移植性 五、词法分析程序的输出形式 单词--是程序语言的基本语法符号。 如：基本字、标识符、常数、运算符、界符等。 词法分析器中单词的输出形式： （单词类别、单词内部码值） 五、词法分析程序的输出形式 词法分析程序输出的单词符号通常用二元式表示：（单词种别，单词自身的值） 单词种别：表示单词种类，常用整数编码，它是语法分析需要的 单词自身的值：是编译中其他阶段所需要的信息 如果一个种别只含一个单词符号，那么该单词符号的种别编码就完全代表它自身的值。 如果一个种别含有多个单词符号，那么还应给出该单词符号的自身值：标识符自身值是标识符自身的字符串；常数自身值是常数的二进制数值。 语言的单词符号 单词符号是程序语言的基本语法单位，一般分为下面5种： 关键字（基本字）：（个数确定，可全体编为一类，也可一字一类) 标识符：（个数不确定，作为一类） 常数：各种类型的常数 。(个数不确定，按类型分类) 运算符：如+、-、*、/、等。(个数确定，一符一类) 界符：如，、；、（、）、: 等。(个数确定,一符一类) 注意：一种语言的单词如何分类、怎样编码，主要取决于技术上的方便。 例：若分类表为： 试分析输入串：IF a10 THEN b1:=c1*d1 ELSE b1:=5 经词法分析后的输出。 解：输出的单词串为： 一、状态转换图 状态转换图是一张有限方向图。用结点代表状态，状态之间用箭弧连接，箭弧上的标记（字符）代表在射出结状态下可能出现的输入字符或字符类。 一个状态转换图只包含有限个状态，有一个初态，终态用双圈表示。一个状态转换图可识别一定的字符串。 一、状态转换图 二、状态转换图的实现 方法：每个结点对应一段程序，前面状态结的程序调用其后继结点的程序。 例1： 二、状态转换图的实现 为了描述方便，引入一些标准过程（函数）与变量: 1.全程字符变量Char：存放必威体育精装版读入的源程序字符； 2.字符串TOKEN：存放构成单词符号的字符串； 3.过程GETChar：读入一个源程序字符，放入Char中，有哪些信誉好的足球投注网站指针前移； 4.过程GETNBC：反复调用 GETChar，直接读入的 Char ’ ’ 为止； 5.过程CONCAT：把Char中字符连到TOKEN末尾去； 6.函数Letter/digit：判别Char中是否为字母/数字； 7.过程Return (c, val ); 8.过程Retract：有哪些信誉好的足球投注网站器指针回拔一个字符。 例2： 三、为正则文法构造状态转换图 什么是正则文法？（U::=T 或U::=WT） 步骤如下： 以S为开始状态作结点； 把文法中的每一个非终结符号作为状态结点； 对于形如Q::=T的每个规则，引一条开始状态S到状态Q的弧，弧上标记为T；对于形如Q::=RT的规则引一条从状态R到Q的弧，弧上标记为T，其中R为非终结符号，T为终结符号。 以识别符号为终止状态。 构造状态转换图举例 例如：对于正则文法G[Z]： Z::=Z