编译原理张淑艳 compiler-principle03.pptVIP

郑州大学 程序设计语言编译原理 张 淑 艳 zhang_shu_yan@163.com 第三章 词法分析 3.1 对于词法分析器的要求 3.2 词法分析器的设计 3.3 正规表达式与有限自动机 3.4 词法分析器的自动产生 3.1 对于词法分析器的要求 3.1.1 词法分析器的功能和输出形式 功能：输入源程序，输出单词符号 单词符号： 关键字（保留字，基本字） 标识符：变量名，数组名 常数： 整形，实型 运算符：+, -, *, /,… 界符： ; , ( ) … 反映单词符号特性或特征的值 通常用整数编码 输出：二元式形式（单词种别，单词符号的属性值） 全体视为一种或一字一种 统归为一种 按类型分种(整，实，布尔…) 一符一种或具有一定共性的运算符 视为一种 一符一种 3.1 对于词法分析器的要求 单词符号的属性信息： 特征和特性 标识符的属性：存放它的符号表项的指针 常数的属性：存放它的常数表项的指针 如：while(i = j) i- -; 词法分析器的处理结果： while，- ( ， - id，指向i的符号表项的指针 =， - id，指向j的符号表项的指针 )， - id，指向i的符号表项的指针 - -， - ; ， - 符号表 i . . . 1 2 . . . 3.1 对于词法分析器的要求 作为独立的一遍 作为语法分析器的子程序（本书使用的方法） 3.1.2 词法分析器作为一个独立子程序 取下一个单词符号 词 法 分析器 单词符号 源程序 分析树 符号表 语 法 分析器 3.1 对于词法分析器的要求 作为独立的一遍 作为语法分析器的子程序（本书使用的方法） 3.1.2 词法分析器作为一个独立子程序 取下一个单词符号 分析树 词法分析器 单词符号 源程序 符号表 语法分析器 3.2 词法分析器的设计 3.2.1 输入、预处理 注释 词法分析器 单词符号 源程序 输入缓冲区 预处理 子程序 扫描器 输入 列表 单词符号 扫描缓冲区 词法分析器 编辑性字符： int a = b; 3.2 词法分析器的设计 起点指示器：正在扫描单词的开始位置 有哪些信誉好的足球投注网站指示器：用于寻找单词的终点 词法分析器对缓冲区扫描的两个指示器： Together 一分为二的缓冲区： 问题： My name is Li Lei. One of M y friends is Han Meimei. My name is Li Lei. One of M y friends is Han Meimei. 3.2 词法分析器的设计 3.2.2 单词符号的识别：超前有哪些信誉好的足球投注网站 单词符号：关键字、标识符、常数、算符和界符 关键字的识别 特例：关键字不加保护，可做标识符,如FORTRAN DO99K=1,10 DO99K=1.10 IF(5.EQ.M)I=10 IF(5)=55 标识符的识别 以字母开头的“字母|数字”串，其后常跟算符和界符。容易识别 3.2 词法分析器的设计 常数的识别 除个别语言（如FORTRAN），常数的识别很直接 5.EQ.M 5.E08 文字常数 3HABC 算符和界符的识别 多个字符复合成的算符和界符需要超前有哪些信誉好的足球投注网站 ==，--，++，=, =, !=, , , || 了解了词法规则，就可以设计法分析器！！ 练习题（要求使用伪代码给出算法）： 编写一个程序，用于统计文件中单词的总数，不同单词的数目。 eg: I love Zhengzhou and I love ZZU 单词总数：7 不同单词数目：5 Do you know? This is a small lexical analyzer . 3.2 词法分析器的设计 3.2 词法分析器的设计 3.2.3 状态转换图 有限方向图，结点表示状态，状态间用箭弧连接，箭弧上的标记（符号）代表射出结点状态下有可能出现的输入字符或字符类。 0 1 2 X Y 一张状态转换图有： （1）有限个状态 （2）一个初态 （3）一个或多个终态, 用双圈表示 一个状态转换图可用于识别（或接受）一定字符串。 上图为接受X和Y的状态转换图 3.2 词法分析器的设计 3.2.3 状态转换图 有限方向图，结点表示状态，状态间用箭弧连接，箭弧上的标记（符号）代表射出结点状态下有可能出现的输入字符或字符类。 一个状态转换图可用于识别（或接受）一定字符串。 上图为接受X和Y的状态转换图 0 数字 1 2 3 数字 数字 3.2