03第3章 词法分析.ppt

第3章词法分析 词法分析程序又称词法分析器或扫描器 是编译过程的第一步 是下一步进行语法分析的基础 3 1词法分析的功能3 2程序语言的单词符号种类及词法分析输出3 3正则文法及状态图3 4词法分析程序的设计与实现 3 1词法分析的功能 扫描源程序字符流 按照源语言的词法规则识别出各类单词符号 并产生用于语法分析的符号序列 即将字符串源程序转换成符号串源程序 程序设计语言的保留字或关键字 标识符 常数 各种运算符等都是单词符号的例子 词法分析程序要做的工作是 从源程序的第一个字符开始 顺序读字符 一次读一个 根据所读进的字符识别各类单词 同时去掉源程序中的空白和注释 词法分析检查的错误主要是挑出源程序中出现的非法符号 所谓非法符号是指不是程序设计语言中允许出现的符号 就像自然语句中的错字 词法分析与语法分析之间的关系通常有两种形式 1 词法分析作为独立的一遍词法分析可作为单独一遍来实现 这种词法分析的输出存入一个中间文件供语法分析使用 这样通过词法分析 就可以将字符串源程序转换成符号串源程序 如图3 1 字符串源程序 词法分析 符号串源程序 图3 1词法分析单独作为一遍 3 1词法分析的功能 2 词法分析程序作为语法分析程序的子程序有些编译程序将词法分析和语法分析安排在同一遍中 此时词法分析作为语法分析程序的一个子程序 每当语法分析需要一个新的符号时 就调用词法分析子程序 词法分析子程序从字符串源程序中识别出一个具有独立意义的单词 将其符号返给语法分析 这种方法避免了中间文件 省去了送取符号工作 有利于提高编译程序的效率 如图3 2 3 2程序语言的单词符号种类及词法分析输出 词法分析的功能是为识别出的具有独立意义的单词 而输出的就是这些单词的符号 在程序设计语言中 单词符号是最基本的语法单位 具有确定的语法意义 通常程序语言的单词符号有 保留字 如if while for等等 这些保留字在程序语言中具有固定的意义 是编译程序识别各类语法成分的依据 用户不能用它们作标识符 标识符 由用户定义 用来表示各种名字 如变量名 函数名 数组名等等 无符号数 如125 0 788 15 2分界符 如 等单分界符 还有 等双分界符 词法分析的输出常采用二元式 如图3 3所示 图3 3词法分析程序的输出形式 3 2程序语言的单词符号种类及词法分析输出 单词类别通常用一个整数类码或单词记号表示 单词记号比整数码含义明确 例如 保留字FOR 可直接用同样的字符串FOR作为单词记号来表示 而如果用整数类码 含义就不直观 用汇编编写词法分析程序 单词类别常用整数表示 因为用单词记号处理起来比较麻烦 而如果用高级语言编写词法分析程序 那么采用单词记号则更自然些 因为高级语言提供了字符串处理函数 处理助记符号不再烦琐 一个语言的单词类别如何分类 分成几类 怎样编码 主要取决于技术处理上的方便 标识符一般归为一类 常数则按类型 整数 实数等 分类 保留字即可将全体定为一类 也可一字一类 分界符可单独作为一类 也可采用一符一类的分法 采用一字一类或采用一符一类的分法实现处理起来更方便一些 因为 如果一个类别只含一个单词符号 那么 对于这个单词符号 类别编码就完全代表它自身的值 词法分析就不必输出其值了 3 3正则文法及状态图 程序设计语言的单词符号可用3型文法来描述 3型文法也称为正则文法 对于正则文法所描述的语言可以用一种有穷自动机来识别 我们的目的是实现词法分析程序 所以为了简化问题 我们直接介绍这种自动机的非形式表示 即状态图 3 3 1状态图所谓 状态图 就是一张有穷的有向图 图中的结点代表状态 用圆圈表示 状态间用有向弧线连接 连接弧上标记有符号 表示在弧线射出端的状态下 读入弧线上标记的符号可转换到弧线指向的状态 状态图只有有穷个状态 其中有一个是开始状态 至少有一个状态是结束状态 结束状态常用双圈表示 3 3 1状态图 正则文法形式为 U a或U Wa 其中 U W Vn 非终结符号集 a Vt 终结符号集 正则文法的状态图画法如下 文法中的每个非终结符号对应状态图中的一个结点 即图中的每个结点代表一个非终结符号 增设一个结点代表开始状态S 而文法中的开始符号对应的结点为终结状态对于文法中的每一条形如U a的规则 画一条从结点S指向结点U的弧线 并在弧上标记a 对于文法中每一条形如U Wa的规则 画一条从结点W指向结点U的弧线 并在弧上标记a 3 3 1状态图 例3 1 设有正则文法G Z Z U0 V1U Z1 1V Z0 0画出该文法对应的状态图 解 根据状态图的画法 首先确定状态图的结点 文法中有三个非终结符号Z U V 加上代表开始状态S的结点 因此共有四个结点 其中S结点为开始状态 Z结点为终结状态 对于规则Z U1 V1 则分别从结点U和结点V画指向结点Z的弧线 并分别在弧线上标记0和1 对于规则U Z1 1 从Z画指向U的弧线 从S画指向U的弧线 并分别在弧线上标记为1 对于规则V Z0 0 分别从Z和S画指向V画弧线 并分别在弧线上标记0 最终 我们可以画出该文法的状态图 如图3 4所示 图3 4状态图 3 3 2状态图的用法 状态图画好后 就可以利用状态图来分析和识别字符串 其方法如下 1 首先设置初始状态S为当前状态 从输入串的最左字符开始重复步骤2 直到到达输入串的右端为止 2 扫描输入串的下一个字符 在当前状态所射出的弧中 找出标记有该字符的弧 并沿此弧前进 过渡到下一个状态 如果找不到标记有该字符的弧 则说明输入串不是合法的句子 分析过程失败结束 如果我们扫描输入串的最后一个字符 并从当前状态出发沿着标记有该字符的弧到达终结状态 则表示输入串是该文法的合法句子 识别过程成功结束 如果扫描输入串的最后一个符号后到达的状态不是状态图的终结状态 则表示输入串不是该文法的合法句子 识别过程失败结束 利用状态图识别句子的方法是一种自底向上的分析方法 开始时 处于开始状态 此时句柄是随后扫描的字符 即输入串的的第一个符号 所要归约的符号就是从开始状态经过标记有句柄符号的弧到达的下一个状态的名字 以后每一步 除第一步外 的句柄是当前状态的名字和随后扫描的字符 而句柄所要归约的符号就是下一个状态的名字 3 3 2状态图的用法 例3 2 对句子0110进行的分析 解 根据上面介绍的状态图使用方法 我们在图3 5 a 列出分析的每一步 由于这些规则很简单 所以分析也非常简单 首先 在开始状态S下扫描的第一个符号是0 转到状态V 表示0是句柄 归约到V 接下来 在状态V扫描1 转到状态Z 此时句柄为V1 归约成Z 再往下扫描1 由状态Z转到状态U 表示句柄为Z1归约为U 最后 扫描0 转到状态Z 此时句柄为U0 归约为Z 从而形成图3 5 b 所示的语法树 3 5 a 输入串0110分析过程 图3 5 b 输入串0110的语法树 3 3 2状态图的用法 从上例的分析过程可看出 因为非终结符号仅作为规则右部第一个符号出现 所以 第一步总是把句子的第一个符号作为句柄归约成一个非终结符号 其后各步总是应用形式为U Wa的规则 把句型Wat的头两个符号归约成一个非终结符号U 在执行这个规约时 当前状态的名字是W 扫描的字符是a 下一个状态是U 因为每个右部是唯一的 所以规约的符号也是唯一的 3 4词法分析程序的设计与实现 3 4 1TEST语言的词法规则及状态图TEST语言是本书中专门设计的一种程序语言 它在语法上与C语言类似 但要比C语言简单的多 它的所有变量都是整型变量 它具有IF WHILE FOR等控制语句 注释用 和 括起来 但注释不能嵌套 TEST的表达式局限于布尔表达式和算术表达式 TEST语言的单词符号有 标识符 name aaa保留字 它是标识符的子集 if else for while do int read write无符号整数 100 256分界符 如 等单分界符 还有双字符分界符 等 注释符 用 括起或从 到行尾词法分析程序并不输出注释 在词法分析阶段 注释的内容将被删掉 为了从源程序字符流中正确识别出各类单词符号 相邻的标识符 整数或保留字之间至少要用一个空格分开 TEST语言的各类单词符号的正则文法规则如下 ID ID NUM a b z A B Z 1 2 9 0 上述规则中 标识符 无符号整数 双字符分界符以及注释规则表面看不是正则文法 但只要一转换可变成正则文法 如将标识符规则中的字母分别用实际字母代入 就是正则文法 如下所示 TEST语言的各类单词符号的正则文法规则如下 ID a b z ID符 a ID z ID 0 ID 9 NUM 0 1 9 NUM 0 NUM 9 doubleword 上述部分各条词法规则的状态图如图3 6所示 注意 由于部分单分界符与双分界符或注释的头符号相同 如 和 所以这些单分界符要在双分界符或注释中处理 TEST语言的各类单词符号的正则文法规则如下 图3 6各条词法规则的状态图 TEST语言的各类单词符号的正则文法规则如下 图3 7单词符号的状态图 3 4 2TEST语言词法分析程序的构造 有了状态图后 根据分析的相应动作就可以画出词法分析程序的算法流程图 如图3 8 在程序开始时 首先读入一个字符 若为空字符 则继续读 直到读进一个非空字符 然后根据读进的字符进行不同的处理 当这个字符是 1 字母 继续读 直到遇见空格 或单字符分界符 或文件尾 组合字符串 查保留字表 若为保留字 输出相应类码 若无 输出标识符的单词记号及单词值 标识符 2 数字 继续读 直到非数字字符出现或文件尾 输出无符号整数的单词记号及数字串 3 读下一个字符 判断是否为双字符分界符 若是 组成双字符分界符 输出类码 若不是 输出单分界符记号 4 非 等与双分界符首字符不同的单分界字符 输出相应单词记号及单分界符 5 读下一个 若不是 输出 的类码 若是 进行注释处理 词法分析不输出 并要跳过整个注释内容直到遇到 为止 然后返回开始状态 继续识别下一个单词符号 6 非法字符 如果读进的字符不属于上面任意情况 则说明词法分析程序从源程序读入了一个不合法的字符 即该字符不属于程序语言所定义的所有单词符号的首字符集合 词法分析程序在遇到不合法字符时要进行错误处理 报告错误信息 跳过这个字符 然后转入开始状态 继续识别下一个单词符号 3 4 2TEST语言词法分析程序的构造 在设计词法分析程序时要注意 为了识别标识符 无符号整数及与双分界符首字符相同的单分界符时 我们需要向前多读一个字符 因此 在具体实现词法分析程序时 遇到这种情况在返回开始状态识别下一个单词符号时 需要回退一个字符 如果不回退 也可约定 识别出一个单词符号后返回开始状态时 已将下一个字符读进 这时就要在识别那些不需要超前读字符就可识别的单词符号后 要再读一个字符 以保证每次返回开始状态识别下一个单词时 已经读进了下一个字符 本节介绍的程序就采用这种方式 因此 在纯单分符处理分支 双分符处理分支后都添加了读字符 同样 在处理了注释后 也要注意将下一个字符读进来 3 4 2TEST语言词法分析程序的构造 图3 8词法分析程序框图 3 4 3TEST语言的词法分析程序实现 1 输出形式为了使词法分析的输出含义明确 易于理解 本程序对识别出的每个单词符号输出两项内容 一是单词记号 二是单词值 对于保留字 分界符直接输出相同的字符串作为单词记号 此时 单词记号与单词值相同 为了统一输出形式 两者一同输出 对于标识符 其单词记号用ID表示 单词值是实际标识符 对于无符号整数 单词记号用NUM表示 具体的无符号整数以数字字符串形式作为单词值输出 2 该词法分析程序采用C语言编制 程序中的变量及有关过程均在程序注释中说明 在这个词法分析程序中 为了简化程序设计 使初学者能尽快掌握词法分析的设计 所以程序中使用的语句 设计思想及实现方法都比较简单 极容易实现 程序中将保留字保存在一个指针数组中 可随时增加和修改 分界符有单分界符和双分界符之分 对于那些和双分界符或其它符号没有冲突的单分界符连接起来作为一个字符串并保存在字符数组danfenfu中 这样 通过判断读入的字符是否是danfenfu中的字符 就可识别出单分界符 双分界符需要单独处理 本程序处理的双分界符第二个字符都相同 所以可将所有双分界符的第一个符号连接成字符串并保存在字符数组shuangfenfu中 当判断字符是shuangfenfu中的字符时 要再读入一个字符 如果这个字符是 则识别出双分界符 如果不是则输出相应的单分界符 对于注释和单分界符 要特别处理 当读入的字符是 时 要读入下一个字符 如果不是 则输出单分界符 如果是 则进行注释处理 处理方法是 设立一个新变量ch1 ch保存前一个字符 ch1为新读入的字符 如果ch是 且ch1是 则遇到注释尾 否则令ch ch1 ch1则读如下一个字符 再判断 直到遇到注释尾 这样就可将注释去掉 如果还想加入其它的双分界符甚至三分界符 就需要单独处理 不过掌握了处理双分界符的方法 处理其它形式的分界符应该不是难事 本词法分析程序处理的保留字不区分大小写 但标识符区分 如果想不区分大小写 可在组合标识符结束后 统