《编译原理第四章 词法分析》由会员分享，可在线阅读，更多相关《编译原理第四章 词法分析（33页珍藏版）》请在金锄头文库上搜索。
1、第 4 章 词法分析第四章第四章 词法分析词法分析课前索引课前索引【课前思考】 词法分析程序的功能是什么？ PL/0 词法分析程序识别哪几种单词？ 画出 PL/0 词法分析程序的流程图。 C 语言，PASCAL 语言的标识符和数的表示分别有什么规定？ 编写一个程序（C 的，或 PASCAL 的）识别 C+语言的标识符。 【学习目标】 明确词法分析在编译过程所处的阶段和作用。 掌握词法分析程序的手工实现方法。 理解通常的单词分类和构词规则。 会使用单词的描述和识别机制。 掌握词法分析程序的自动构造原理。 【学习指南】词法分析程序是编译程序的一个构成成分，它的主要任务是扫描源程序，按构词规则 识别
2、单词，并报告发现的词法错误。词法分析也是语法分析的一部分，把词法分析从语法 分析中独立出来是为了使编译程序结构清晰，也是为了便于使用自动构造工具，提高编译 效率。 本章首先介绍词法分析程序的功能和设计原则，然后引入正规式和其对单词的描述， 接着讲述有穷自动机理论，最后给出词法分析程序的自动构造原理。 【难重点】 如何设计和实现词法分析程序 正规式的定义-如何用作单词的描述工具 有穷自动机的定义和分类-如何用作单词的识别系统 正规式到有穷自动机的转换算法-词法分析程序的自动构造原理 第 4 章 词法分析【知识结构】第 4 章 词法分析词法分析是编译的第一个阶段，它的主要任务是从左至右逐个字符地对
3、源程序进行扫 描，产生一个个单词序列，用以语法分析。执行词法分析的程序称为词法分析程序或扫描 程序。本章我们将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析 程序的自动构造原理。 词法分析程序的主要任务：词法分析程序的主要任务：- 读源程序，产生单词符号词法分析程序的其他任务：词法分析程序的其他任务：- 滤掉空格，跳过注释、换行符- 追踪换行标志，复制出错源程序，- 宏展开， 本章要点：本章要点：- 告诉你掌握词法分析程序的设计和实现的办法- 首先需要描述和刻画程序设计语言中的原子单位-单词，其次需要识别单词和执行某 些相关的动作。- 描述程序设计语言的词法的机制是正则表达式，
4、识别机制是有穷状态自动机。4.1 词法分析程序词法分析程序首先讨论词法分析程序与语法分析程序的接口方式词法分析程序完成的是编译第一阶段的工作。词法分析工作可以是独立的一遍，把字 符流的源程序变为单词序列，输出在一个中间文件上，这个文件做为语法分析程序的输入 而继续编译过程。然而，更一般的情况，是将词法分析程序设计成一个子程序，每当语法 分析程序需要一个单词时，则调用该子程序。词法分析程序每得到一次调用，便从源程序 文件中读入一些字符，直到识别出一个单词，或说直到下一单词的第一个字符为止。这种 设计方案中，词法分析程序和语法分析程序是放在同一遍里，而省掉了中间文件，象第 2 章介绍的 PL/0
5、编译程序那样.也是大多数编译程序采用的方案。 实现词法分析（实现词法分析（lexical analysis）的程序）的程序逐个读入源程序字符并按照构词规则切分成一系列单词。 单词是语言中具有独立意义 的最小单位，包括保留字、标识符、运算符、标点符号和常量等。 词法分析是编译过程中 的一个阶段，在语法分析前进行 。也可以和语法分析结合在一起作为一遍，由语法分析程 序调用词法分析程序来获得当前单词供语法分析使用。 词法分析程序和语法分析程序的关系 f4-1-1.swf 词法分析程序的主要功能是从字符流的源程序中识别单词，它要从左至右逐个字符地 扫描源程序，因此它还可完成其它一些任务。比如，滤掉源程
6、序中的注释和空白(由空格， 制表或回车换行字符引起的空白)；又比如，为了使编译程序能将发现的错误信息与源程序 的出错位置联系起来，词法分析程序负责记录新读入的字符行的行号，以便行号与出错信 息相联；再有，在支持宏处理功能的源语言中，可以由词法分析程序完成其预处理等等。 接着讨论词法分析程序的输出接着讨论词法分析程序的输出词法分析程序的功能是读入源程序，输出单词符号。单词符号是一个程序设计语言的 基本语法符号。程序设计语言的单词符号一般可分成下列 5 种： 保留字，也称关键字，如 PASCAL 语言中的 begin,end,if,while 和 var 等。第 4 章 词法分析 标识符，用来表示
7、各种名字，如常量名、变量名和过程名等。 常数，各种类型的常数，如 25，3.1415，TRUE 和“ABC“等。 运算符，如+，*，0) 符号串集合：若集合 A 中的一切元素都是某字母表 上的符号串，则称 A 为字母表 上的符号串集合。两个符号串集合 A 和 B 的乘积定义如下：AB=xy|xA 且 yB，即 AB 是满足 x 属于 A，y 属于 B 的所有符号串 xy 所组成的集合。例如，若 A=a,b,B=c,d,则 集合 AB=ac,ad,bc,bd。因为对任意符号串 x 有 x=x=x，所以有A=A=A。指定字母表 之后，使用 * 表示 上的一切符号串（包括 ）组成的集合。* 称为 的
8、闭包。 上的除 外的所有符号串组成的集合记为 +。 + 称为 的正闭包。+ =* -=* =23* =2例：=a,b* =,a,b,aa,ab,ba,bb,aaa,aab,+ =a,b,aa,ab,ba,bb,aaa,aab, 我们用以描述单词符号的工具是正规式。正规表达式（regular expression）是说明单词的模式(pattern)的一种重要的表示法（记 号） ，是定义正规集的工具。 正规式也称正则表达式，也是表示正规集的数学工具。下面是正规式和它所表示的正 规集的递归定义。定义（正规式和它所表示的正规集）：设字母表为 ，辅助字母表 =，|，*，(， 。 和 都是 上的正规式，它
9、们所表示的正规集分别为和 ； 任何 a，a 是 上的一个正规式，它所表示的正规集为a； 假定 e1和 e2都是 上的正规式，它们所表示的正规集分别为 L(e1)和 L(e2)，那么， (e1), e1|e2, e1e2, e1*也都是正规式,它们所表示的正规集分别为 L(e1), L(e1)L(e2), L(e1)L(e2)和 (L(e1)*。 仅由有限次使用上述三步骤而定义的表达式才是 上的正规式，仅由这些正规式 所表示的字集才是 上的正规集。 正规式定义中的“|”读为“或”（也有使用“+”代替 “|” 的） ；“”读为“连接”；“*”读为“闭 包”（即，任意有限次的自重复连接） 。在不致混
10、淆时，括号可省去，但规定算符的优先顺 序为“(”、 “)”、 “*”、 “”、 “|” 。连接符“”一般可省略不写。 “*”、 “”和“|” 都是左结合的。令=a，b， 上的正规式和相应的正规集的例子有：正规式 正规集a aa|b a,bab ab(a|b)(a|b) aa,ab,ba,bba* ,a,a, 任意个 a 的串(a|b)* ,a,b,aa,ab 所有由 a 和 b 组成的串(a|b)*(aa|bb)(a|b)* *上所有含有两个相继的 a 或两个相继的 b 组成的串若两个正规式 e1和 e2所表示的正规集相同，则说 e1和 e2等价，写作 e1=e2。例如： e1= (a|b)，
11、 e2 = b|a又如： e1= b(ab)* ，e2 =(ba)* b 再如： e1= (a|b)* ，e2 =(a* |b* )* 设 r,s,t 为正规式，正规式服从的代数规律有：第 4 章 词法分析 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 是“连接“的恒等元素零一律 r|r=r r*=|r|rr| “或“的抽取律 程序设计语言的单词都能用正规式来定义。请看下面两个例子：例 4.1 令 =l，d，则 上的正规式 r=l(
12、l|d)* 定义的正规集为：l,ll,ld,ldd,，其 中 l 代表字母，d 代表数字，正规式，即是字母(字母|数字)*，它表示的正规集中的每 个元素的模式是“字母打头的字母数字串”，就是 Pascal 和多数程序设计语言允许的的 标识符的词法规则。例 4.2=d，+，-,则 上的正规式 d*(dd* |)( (+| -|)dd* |)表示的是无符号数 的集合。其中 d 为 09 的数字。 外文教材中常常遇到的术语 - Token 单词,词标，符号- lexeme 词素，词位- pattern 模式，式样这段话帮你理解外文教材中常常遇到的术语 In general，there is a se
13、t of strings in the input for which the same token is produced as output. This set of strings is described by a rule called a pattern associated with the token. The pattern is said to match each string in the set. A lexeme is a sequence of characters in the source program that is matched by the patt
14、ern for a token. 例如：源程序语句 Const pi=3.14159，x1=10；中的 pi 和 x1 是 token “identifier”的 lexeme，其 pattern 为字母开头，后面跟有字母和/或数字的字符序列。第 4 章 词法分析4.3 有穷自动机有穷自动机有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正 规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析 程序的自动构造寻找特殊的方法和工具。 有穷自动机分为两类有穷自动机分为两类：确定的有穷自动机(Deterministic Finite Automat
15、a)和不确定的有 穷自动机(Nondeterministic Finite Automata)，下面我们分别给出确定有穷自动机和不确定的 有穷自动机的定义，有关概念及不确定的有穷自动机的确定化，确定的有穷自动机的化简 等算法。关于有穷自动机我们将讨论如下题目- 确定的有穷自动机 DFA- 不确定的有穷自动机 NFA- NFA 的确定化- DFA 的最小化 4.3.1 确定的有穷自动机确定的有穷自动机 DFADFA 定义：-一个确定的有穷自动机（DFA）M 是一个五元组： M=（K，f，S，Z）其中 K 是一个有穷集，它的每个元素称为一个状态； 是一个有穷字母表，它的每个元素称为一个输入符号，所以也称 为输入符号字 母表； f 是转换函数，是 KK 上的映射，即，如 f（ki，a）=kj， （kiK，kjK）就意 味着，当前状态为 ki，输入符为 a 时，将转换为下一个状态 kj，我们把 kj 称作 ki 的一个 后继状态； S K 是唯一的一个初态； Z K 是一个终态集，终态也称可接受状态或结束状态。 举一个 DFA 的例子：DFA M=（S，U，V，Q，a，b，
