第2章词法分析分解.ppt

第二章 词法分析 本章主要讨论词法分析程序的设计原则，单词的描述技术、识别机制及词法分析程序的自动构造原理。 1.词法分析的功能 2.程序语言的单词符号种类及词法分析输出 3.词法分析程序的设计与实现 4.正规表达式与有穷自动机 5.词法分析程序的自动生成 本章重点 单词的描述工具 单词的识别系统 设计和实现词法分析程序 首先需要描述和刻画程序设计语言中的原子单位——单词，其次需要识别单词和执行某些相关的动作。 描述程序设计语言的词法的机制是正规表达式，识别机制是有穷自动机。 词法分析程序 词法分析是编译过程中的一个阶段，在语法分析前进行。可以作为一个独立的子程序。 优势表现为： 简化设计 改进编译效率 增加编译系统的可移植性 可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。 单词符号 是程序设计语言中具有独立意义的最小单位，程序设计语言基本组成成分。 五类： 关键字（保留字/基本字）:if while … 标识符：常量名 变量名 常数：34 56.78 运算符：+ - / AND… 界限符：， ； （ ）… 词法分析器的输出：Token串 机内表示形式： 单词类别有多种编码方式： 标识符一般统一为一种：一个编号 常数按类型分别编码：整数、实数、布尔、字符 关键字一般一字一种 运算符一般一符一种 界符一般一符一种 各种常数和标识符一般放在一个符号表中，在输出的token文件中的单词属性值则存放单词在符号表中的指针 例子 　 　a=10＋c*20 识别各种单词符号 标识符的识别：字母+(字母/数字) 关键字的识别：与标识符相同，最后查表 常数的识别: 界符和算符的识别: 扫描程序的设计－预处理 预处理：删除无用的空格； 删除跳格； 删除回车和换行等编辑性字符； 删除注解部分。 每一次对一串定长的输入字符串进行预处理，并装入一个指定的缓冲区。 扫描缓冲区 一分为二，互补使用。 有哪些信誉好的足球投注网站指针从单词起点开始有哪些信誉好的足球投注网站，如果遇到半区域的边界，但尚未到达单词的终点时，则可将后续的输入字符装入该缓冲区的另一半。 必须对标识符和常数单词符号的长度加以限制。 单词的构成规则用状态转换图表示 示例语言的单词符号 标识符： name， aaa 基本字： if，else，for，while，do，int，read，write 无符号整数：100，256 算符及界符： 单分界符：如+，-，*，/，（，），；，‘，!等 双字符分界符：=，=，!=，==等。 注释符：用/*….*/括起 示例语言各类单词的状态图 示例语言单词符号的状态图 示例语言词法分析程序的算法 首先读入一个字符，若为空字符，则继续读，直到读进一个非空字符。当这个字符是： 字母：继续读，直到遇见空格、或单字符分界符、或文件尾。组合字符串，查保留字表。若为保留字，输出相应类码。若无，输出标识符的单词记号及单词值（标识符）； 数字：继续读，直到非数字字符出现或文件尾。输出无符号整数的单词记号及数字串； =、＜、＞、！：读下一个字符，判断是否为双字符分界符，若是，组成双字符分界符，输出类码；若不是，输出单分界符记号； 非=、＜、＞、/等与双分界符首字符不同的单分界字符：输出相应单词记号及单分界符。 /：读下一个。若不是，输出/的类码；若是*，进行注释处理。词法分析不输出“/*”，并要跳过整个注释内容直到遇到“*/”为止，然后返回开始状态，继续识别下一个单词符号。 非法字符：如果读进的字符不属于上面任意情况，则说明词法分析程序从源程序读入了一个不合法的字符，进行错误处理，报告错误信息，跳过这个字符，然后转入开始状态，继续识别下一个单词符号。 正规表达式与有限自动机 要求 正规式与正规集的定义 有穷自动机的定义及表示 NFA确定化为DFA 掌握DFA的化简 掌握用正规式构造DFA 掌握正规文法与有穷自动机间的转换 字母表和符号串的基本概念 字母表：元素的非空有穷集合。记为∑。  字母表包含了语言中所允许出现的一切符号。 例如： ∑= {0，1} 符号串(字)：字母表中的符号所组成的有穷序列。 一个语言的句子总是它的字母表的符号串。这个符号串的组成必须是按照文法规则组合而成的。 语法分析的一个重要任务就是：判断一个符号串的组成是否满足某个文法的规定。 字母表和符号串的基本概念(续) 空串：不包含任何符号的串，记为ε。 Σ*：表示Σ上所有符号串的全体。 空集：φ，不