编译原理 第3章课件.docVIP

第三章 词法分析 本章将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。 教学要求１.掌握：正规式，DFA的概念，NFA的概念 ２.理解：将 NFA转换为DFA ,正规式、正规文法与有穷自动机间的转换 目录3.1 词法分析程序的设计 3.2 单词的描述工具 3.3 有穷自动机 3.4 正规式与有穷自动机的等价性 3.5 正规文法和有穷自动机的等价性 3.6 词法分析程序的自动构造工具 小结? 3.1.词法分析（lexical analysis） 程序的设计 回顾： 1、词法分析的任务：逐个读入源程序字符并按照构词规则切分成一系列单词。 2、词法分析程序：实现词法分析的程序。 一.词法与语法分析程序的接口方式 1、作为独立的一遍 词法分析是编译过程中的一个阶段，在语法分析前进行，把字符流的源程序变为单词序列，输出在一个中间文件上。 2、与语法分析结合在一起作为一遍 一般、把词法分析程序设计成一个子程序，由语法分析程序调用词法分析程序来获得当前单词，供语法分析使用。 词法分析程序和语法分析程序的关系 词法分析程序的主要任务：读源程序，产生单词符号 词法分析程序的其他任务：滤掉空格，跳过注释、换行符 追踪换行标 志，复制出错源程序，宏展开， …… 二、词法分析程序的输出 输出是单词符号。单词是语言中具有独立意义的最小单位。 单词包括： 保留字 标识符 常量 运算符 界符（标点符号） 词法分析程序所输出的单词符号常常采用以下二元式表示：(单词种别，单 词自身的值)。 单词的种别是语法分析需要的信息，而单词自身的值则是编译其它阶段需要 的信息。 对某些单词来说，不仅仅需要它的值，还需要其它一些信息以便编译的进行， 那么可以将单词的二元式表示设计成如下形式： (标识符，指向该标识符所在符号表中位置的指针) 单词的种别可以用整数编码表示，假如标识符编码为1，常数为2，保留字为 3，运算符为4，界符为5 例如：程序段 if i=5 then x∶=y； 在经词法分析器扫描后输出的单词符号和它们的表示如下：　 - 保留字if(3，if)　 - 标识符i(1，指向i的符号表入口)　 - 等号=(4，=)　 - 常数5(2，5)　 - 保留字then(3，then)　 - 标识符x(1，指向x的符号表入口)　 - 赋值号∶=(4，∶=) 　 - 标识符 y(1，指向y的符号表入口)　 - 分号；(5，；) 　 三、词法分析工作从语法分析工作独立出来的原因： 简化设计 改进编译效率 增加编译系统的可移植性 3.2 单词的描述工具 程序设计语言中的单词是基本语法成分.单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，实现词法分析程序的自动构造. 描述工具：正规文法和正规式 识别工具：有穷自动机 一．正规文法 多数程序设计语言的单词的语法能用正规文法来描述。正规文法所描述的是VT* 上的正规集。几类单词的规则如下： 标识符→l|l字母数字 字母数字→ l|d|l字母数字|d 字母数字 无符号整数→d|d 无符号整数 运算符 →+|-|*|/|等号|等号|…… 等号 →= 界符 →，|；|（|）|…… 二．正规式（regular expression） 描述单词符号最方便的工具。 正规式也称正则表达式,是说明单词的模式(pattern)的一种重要的表示法（记号），是定义正规集的数学工具。 下面是正规式和它所表示的正规集的递归定义。 定义（正规式和它所表示的正规集）： 设字母表为?，辅助字母表?`={?，?，?，，?，?，?}。 1 ?和?都是?上的正规式，2 它们所表示的正规集分别为{?}和? ； 2 任何a? ?，a是?上的一个正规式，它所表示的正规集为{a}； 3 假定e1和e2都是?上的正规式，它们所 表示的正规集分别为L(e1)和L(e2)， 那么，(e1), e1? e2, e1?e2, e1?也都是正规式,它们所表示的正规集分别为L(e1), L(e1)?L(e2), L(e1)L(e2)和(L(e1))?。 4 仅由有限次使用上述三步骤而定义的表达式才是?上的正规式，仅由这些正规式所表示的集合才是?上的正规集 正规式中的符号说明 “?”读为“或” ； “? ”读为“连接”； “?”读为“闭包”（即，任意有限次的自重复连接）。 在不致混淆时，括号可省去，但规定算符的优先顺序为“?”、“? ”、“?” 。 连接符“? ”一般可省略不写。 “?”、“?