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

第三章词法分析 第三章词法分析 主要章节3 1词法分析与词法分析程序3 2词法分析程序的设计与实现3 3词法分析程序的自动生成 3 1词法分析程序的功能 词法分析的功能从左至右逐个字符地对源程序进行扫描 产生一个个单词符号 再转换成词标流的过程 3 4 while i j if i j i i j elsej j i while i j if i j i i j else j j i 3 1词法分析程序的功能 3 2词法分析器的设计与实现 3 2 1单词与属性字1 单词单词是语言中具有独立意义的最小语法单位 要素独立的意义最小的语法单位 5 例 A B 单词是 A 和 B intint1 单词是 int 和 int1 A B 单词是 A 和 B 复习 流行语言词法规则的表示 BNF或EBNF 3型文法 正规式例 int float for include char V 6 1 关键字 保留字或基本字 关键字一般是语言系统本身定义的 通常是由字母组成的字符串 7 2 标识符 用来表示各种名字如 变量名 数组名 结构名 函数名 文件名等 3 2 1单词与属性字 3 常数 256 3 14 true abc 4 运算符 如 等等5 分界符 如逗号 分号 括号 单双引号等 8 3 2 1单词与属性字 3 2 1单词与属性字 注意 1 同一个字符开头 后续字符 跨多个单词类 9 2 非单词成分和预处理成分 例 源程序注释 预处理指令 define include 3 2 1单词与属性字 2 属性字对所识别的单词的数据结构表示 L1 T C 属性字 10 刻画单词类别 单词性质 如 标识符 运算符 单词的内码值 可空 TokenCode 说明 11 单词类别通常用整数编码单词类别提供给语法分析程序使用单词符号属性信息记录单词符号的特征或特性单词的属性值提供给语义分析程序使用编码形式 一类一种 关键字 标识符 常数 运算符 界符一字一种 关键字 运算符 分界符各一码 例题 一类一种 intx 10 y 12 注 通常将标识符的属性放在符号表中 因此常把指向存放标识符有关信息的符号表入口的指针作为标识符的属性值 13 源程序经词法分析器的输出 while id 指向i的符号表入口的指针 relational op id 指向j的符号表入口的指针 do if id 指向i的符号表入口的指针 id 指向j的符号表入口的指针 while i j do if i j then i i j else j j i 例题 一字一种 3 2 2源程序的输入与预处理 1 输入缓冲区成对且对半互补的输入缓冲区模式 即将一个缓冲区分为两个半区 每个半区长度为n n一般为磁盘块或簇长的整倍数 其结构如图所示 14 n 取2的整次幂 每个半区的末尾设置标志 eof 表示读入该半区的源程序的结束 B 单词w开始指针 F 扫描w的指针 两半区互补功能算法 if F 前 eof 重新分配 装入后半区 F elseif F 后 eof 重新分配 装入前半区 F 1 elseF 15 2 两个缓冲区的输入模式 控制线数据线X 固定长度的存储空间 16 预处理程序 作用 1 减少内存空间占用 2 减轻扫描器实质性处理的负担 预处理程序主要任务 1 滤掉源程序中的非单词成分 如无用空格 换行符等 2 实际的预处理工作 17 滤掉注释 宏替换 文件包含的嵌入 条件编译的嵌入 设计工具 FA作为扫描器的状态转换图的构造 step1 对语言的各类单词分别构造状态图 step2 将各类状态图合并 构成一个能识别该语言所有单词的状态图 18 1 将各类单词的状态图的初态合并为一个惟一初态 2 调整冲突编号 例3 2设某语言由标识符和无符号正整数两类单词构成 标识符和无符号正整数的词法规则 L a b z A B ZD 0 1 9 L L D DD 19 step1 对语言的各类单词分别构造状态图 20 其中 other表示非L D 字符 其中 other表示非D字符 step1 step2 将各类状态图合并 构成一个能识别该语言所有单词的状态图 21 其中 other表示非L D 字符 其中 other表示非D字符 step2 4 5 词法分析方法 直接分析法 例 设C语言子集由下列单词符号构成 以正规式的形式表示 关键字 int if for标识符 字母 字母 数字 无符号整常数 数字 数字 运算符或分界符 22 23 24 25 26 语言词法规则状态转换图 FA 可行的扫描器存储和激活问题 数据中心法程序中心法 状态转换图的实现之一 数据中心法将状态转换图看成一种数据结构 状态矩阵表 用总控程序控制输入的源程序串在其上运行 27 状态矩阵二级目录表主表 数据项 状态 分表地址或子程序入口状态 终态时 分表地址为子程序入口状态 非终态时 为分表入口2 分表 数据项 当前输入字符 转换状态 主表分表 28 状态转换图的实现之二 程序中心法 将状态转换图看成一个流程图 从初态开始对它的每个节点 状态 编写一函数或直接跟踪状态图从初态开始的转换完成所有分支的跟踪来编写程序 例3 5设单一小写字母或单一数字或 为合法单词 表示它们的状态转换图如图所示 29 charchar1 char1 nextchar if state i switch char1 case a z J chartype char1 break case 0 9 K chartype char1 break case L chartype char1 break default error 其中 J K L为状态j k l所对应的函数 nextchar 为一函数 功能是从当前扫描的源程序读取下一个字符 状态转换图的实现 intstate 0 enumlettet a z enumnumber 0 9 charchar1 while 1 char1 nextchar switch state case0 switch char1 case a z state 1 break 0 9 state 3 break casecase state 5 break case state 6 break case state 7 break case state 11 break case state 12 break default state 13 break 31 状态转换图的实现 case1 while char1 letter number char1 nextchar state 2 break case2 untread return 02 value orreturn 01 value break 函数untread 功能是回退一个已读进的字符 属性01表示关键字 属性02表示标识符 case3 while char1 number char1 nextchar state 4 break case4 untread return 03 value break 属性03表示无符号整常数 case5 return 04 break 属性04表示 case6 return 05 break 属性05表示 32 状态转换图的实现 case7 char1 nextchar if char1 state 9 elseif char1 state 10 elsestate 8 break case8 untread return 08 break 属性08表示 case9 return 09 break 属性09表示 case10 return 12 break 属性12表示 case11 return 10 break 属性10表示 case12 return 11 break 属性11表示 case13 error error是语法错处理函数 33 一 自动生成思想 一个词法分析程序产生器它接收用正规式表示的定义在某语言字母表 上的单词 然后从此正规式出发 1 构造能识别正规式描述的单词集 正规集 的非确定有限自动机NFAM 此步构造算法定义为X 2 用子集法 子集法实现算法命名为Y 将M 确定化 得到与其等价的DFAM 3 用划分算法 命名为Z 对M化简 得到DFAM 则这个DFAM 即是理论上的扫描器 34 LEX运行与应用过程 35 二 用LEX建立词法分析程序的过程 LEX编译器 LEX源程序lex 1 语言x的词法分析器 LEX编译器接收LEX源程序 由LEX编译器处理LEX源程序 产生一个词法分析器作为输出 在UNIX环境中 LEX编译器的输出是一个具有标准文件lex yy c的C程序 经过C编译器的编译产生a out文件 a out是一个实际可以运行的词法分析器 练习 例 设有识别C语言 的NFA如下 36 例 设有识别C语言 的NFA如下 37 0123