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