东北大学秦皇岛分校编译原理课件第四章.ppt

第四章 词法分析 本章将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。 4.1 词法分析程序 4.2 正规表达式与正规集（正规语言） 4.3 有穷自动机 4.4 词法分析程序的自动构造 本章重点 单词的描述工具 单词的识别系统 设计和实现词法分析程序 首先需要描述和刻画程序设计语言中的原子单位——单词，其次需要识别单词和执行某些相关的动作。 描述程序设计语言的词法的机制是正则表达式，识别机制是有穷状态自动机。 回顾 什麽是词法分析程序 实现词法分析（lexical analysis）的程序 逐个读入源程序字符并按照构词规则切分成一系列单词。 单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。 词法分析是编译过程中的一个阶段，在语法分析前进行 。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。 词法分析程序的任务 词法分析是编译的第一个阶段。 词法分析所做的工作也叫“扫描处理”，因此，词法分析程序也常被叫做“扫描器”。 词法分析的任务是识别单词，为语法分析提供语法单位序列。 单词的形式一般为： 词法分析程序的输入是源程序，输出是一定形式的单词序列。 词法分析程序和语法分析程序的关系 词法分析程序的要求 词法分析程序必须按照一定的分类标准将源程序中的单词进行识别并进行预加工处理。 常见的单词分类形式有两种： 1、一字一类型 2、按下列方式将单词分为5种类型 关键字：也叫保留字、基本字，是由程序语言定义的具有固定意义的标识符。 标识符：开发人员自己定义的用来表示变量、数组等名称的。 常数：包括整型、实型、布尔型、字符及字符串型等。 运算符：包括+、–、*、/、〉、〈 以及布尔运算等。 界符：逗号、分号、括号、回车、换行等将语法单位分隔开的符号。 词法分析程序的工作阶段 词法分析工作可以分成两个工作阶段： 1、输入、预处理阶段：预处理子程序。 2、识别单词符号：超前有哪些信誉好的足球投注网站法。所谓超前有哪些信誉好的足球投注网站法，是指想要识别出某个字符串是否是一个单词，必须超前扫描一个或多个字符，直到能够肯定某个字符序列是一个单词为止。 编译程序的“遍数”影响词法分析的设计。 词法分析工作从语法分析工作独立出来的原因： 简化设计 改进编译效率 增加编译系统的可移植性 正规文法和正规式 多数程序设计语言的单词的词法规则都能用正规文法来描述。 正规文法所描述的式文法的字符表Vt*上的正规集。 正规式也称正则表达式，也是表示正规集的工具 正规式服从的代数规律： r|s=s|r r|(s|t)=(r|s)|t (rs)t=r(st) r(s|t)=rs|rt (s|t)r=sr|tr ?r=r r?=r 正规式 正规式也称正则表达式,正规表达式（regular expression）是说明单词的模式(pattern)的一种重要的表示法（记号），是定义正规集的数学工具。我们用以描述单词符号。下面是正规式和它所表示的正规集的递归定义。 定义（正规式和它所表示的正规集）： 设字母表为?，辅助字母表?`={?，?，?，?，?，?，?}。 1。 ?和?都是?上的正规式，它们所表示的正规集分别为{?}和{ }； 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。仅由有限次使用上述三步骤而定义的表达式才是?上的正规式，仅由这些正规式所表示的集合才是?上的正规集。 正规式中的符号 其中的“?”读为“或”（也有使用“+”代替 “?” 的）；“? ”读为“连接”；“?”读为“闭包”（即，任意有限次的自重复连接）。在不致混淆时，括号可省去，但规定算符的优先顺序为“?”、“? ”、“?” 。连接符“? ”一般可省略不写。“?”、“? ”和“?” 都是左结合的。 例子 令?={a，b}， ?上的正规式和相应的正规集的例子有： 正规式 正规集 a {a} a?b {a,b} ab {ab} (a?b)(a?b) {aa,ab,ba,bb} a ? {? ,a,a, ……任意个a的 串} 正规式 正规集 (a?b)? {? ,a,b,aa,a