哈工大编译原理3-1.ppt

第三章词法分析 2 编译器的各个阶段 编译器是分阶段执行的 每个阶段将源程序从一种表示转换成另一种表示 源程序 词法分析器 错误处理器 符号管理表 语法分析器 语义分析器 中间代码生成器 代码优化器 代码生成器 编译的各个阶段 3 3 2词法分析器的手工构造 用DFA能识别 3 3词法分析程序自动构造工具LEX简介 3 1词法分析程序的设计 词法分析器的功能 输出 把它组织成单独程序 4 8 0 0 1 3 4 2 5 6 e n i L 字母 字母 字母 字母 数字 数字 数字 0 1 2 4 5 6 3 L i n e 8 0 id 25 Line 36 num 27 80 45 数字 字母 字母 1 1 0 0 0 3 1 输入 输出 有穷控制器 单词的词类和属性 词类符号 单词的属性 5 3 1词法分析程序的设计 二 扫描器的任务 一 词法分析程序的功能源程序单词序列 词法分析器 1 组织源程序的输入 2 转换成机内表示形式 3 删除注释行 空格及无用符号 4 查填符号表 5 检查词法错误 6 ifi jtheni 0elsej 1 词法分析 ifI JThenI 0elsej 1 7 三 词类和属性 2 标识符 用来表示各种名字 3 字面常数 256 3 14 true abc 4 运算符 如 等等 5 分界符 如逗号 分号 冒号等 程序语言单词的分类 1 关键字 保留字或基本字 begin end 8 界符和运算符 词法分析器的输出 词类编码 单词自身的属性值 关键字可分成一类 也可以一个关键字分成一类 常数可统归一类 也可按类型 整型 实型 布尔型等 每个类型的常数划分成一类 所有的标识符分为一类 词类编码原则 一字一码 一类型一码 一类一码 一字一码 9 表3 1单词词类编码 10 对于关键字 界符 运算符来说 它们的词类编码就可以表示其完整的信息 故对于这类单词 其单词自身的属性值通常为空 而对于标识符 词类编码所反映的信息不够充分 标识符的具体特性还要通过单词自身的属性进行互相区分 标识符的单词自身的属性常用其在符号表中的入口指针来表示 11 对于常数 其单词自身的属性常用其在常数表中的入口指针来表示 12 以语句子a b c d为例 假设按表3 1为单词编码 词法分析后的结果为 Token字 符号表 a b c d a25 B25 C25 D25 13 四 词法分析的设计形式 1 设计成一个独立程序 完成词法分析的任务 结果以文件的形式组织 做为语法分析的输入 源程序 词法分析 符号表 TOKEN字 错误信息 14 词法分析 语法分析 语义分析和中间代码生成 源程序 中间代码 符号表管理 错误的诊查处理 2 作为语法分析和语义分析的子程序 15 五 词法分析程序的设计框图 SCANNER OUTPUT sort 字母 RECOGID 数字 RECOGDIG HANDLCOM RECOGDEC 界符 RECOGSTR LOOKUP 16 3 2词法分析器的手工构造 为了构造词法分析器 要研究构词法 每种词类的结构模式以及识别它的数学模型 有穷自动机 它的模拟程序可以作为词法分析器的控制程序 3 2 1确定的有限自动机 DFA 3 2 2构造识别单词的DFA3 2 3编写词法分析程序 17 分析程序的设计框图 SCANNER OUTPUT sort 字母 RECOGID 数字 RECOGDIG HANDLCOM RECOGDEC 界符 RECOGSTR LOOKUP 18 一 手工构造识别单词的DFAm根椐DFA识别单词的定义 在研究给定程序语言单词结构的基础上 能直接构造出识别它的DFAm 例如 对于C语言 整数 非空数字串 无符号实数 用d表示数字 a d d d dE d d d dE d d c d d d d 0 1e 14 12e 4 3 141592 d dd dd 1000 19 I B T T a a d 其它 例 C语言的标识符 标识符 字母开始的字母数字串 20 例 C语言实常数的文法描述 0 1 2 3 4 5 6 7 d d d E d E d d d 1000 3 1415 12e 4 0 1e 14 21 在识别标识符的过程中 要拼写出来 并和保留字区别开来 识别出的标识符要填入符号表中 二 编写词法分析程序 根据画出的状态转换图 识别单词的 构造词法分析程序 每个状态对应一段程序 完成到达此状态的工作 在识别常数的过程中 要把它转换成机器表示以作为属性值 记录到常数表中 词法分析程序的控制程序模拟状态转换图的状态转换 22 programSCANNER Begininitiate符号表 字符串表 行 列计数器 Open源文件 TOKEN文件 打印机文件 RepeatFIRSTCH CH ifCH EOLthencallSORT CH elseRDLINE untilCH EOF 把符号表 字符串表做成文件 close源文件 TOKEN文件 callOUTPUTR 模块0 扫描器主控 23 单词分类模块 SORT 输入 CH内含单词首符 procedureSORT CH caseCHof 字母 字母 callRECOGID CH TOKEN callHANDLECOM CH TOKEN 数字 callRECOGDIG CH TOKEN callRECOGSTR CH TOKEN otherwisecallRECOGDEL CH TOKEN endcase writeTOKENintoTOKEN文件 Return 24 procedureRECOGID CH TOKEN WORD WORD WORD CH Repeat callGETCH CH ifCH是字母或数字thenWORD WORD CH untilCH 字母或数字 ifCH是非法字符thencallPRINTERR 非法字符 else列计数 1 ifWORD是关键字thenTOKEN 关键字种别码 else callLOOPUP WORD 标识符 ENTRY TOKEN 标识符种别码 ENTRY Return 识别标识符 输入 CH中含标识符的首字母 输出 TOKEN 二元式形式 25 procedureHANDLECOM TOKEN callGETCH CH ifCH then 列计数 1 TOKEN 的识别码 return TOKEN 1 GETCH CH while列计数 行长 1do CH1 CH callGETCH CH ifCH1 andCH thenTOKEN ifTOKEN thencallPRINTERR 注解未完 TOKEN return 处理注解 HANDLECOM 输入 进入该模块之前已扫描了一个字符 输出 的TOKEN字或空TOKEN字 26 识别界限符 RECOGDEL 输入 CH内含单界限符 输出 各种界符的TOKEN字 procedureRECOGDEL CH TOKEN caseCHof TOKEN 的种别码 TOKEN 的种别码 thenTOKEN 的种别码 else 列计数 1 TOKEN 的种别码 endcase return 27 3 3词法分析程序的自动构造工具LEX简介一 原理单词的结构用正规式描述正规式 NFA DFA minDFA LEX编译器 LEX源程序lex 1 Lex yy c 二 用LEX建立词法分析程序的过程 28 C编译器 Lex yy c a out a out 输入流 单词序列 三 lex源程序lex源程序由三部分组成 29 声明 翻译规则 辅助过程 30 声明包括变量 符号常量和正规定