第4章-词法分析

武汉理工大学计算机科学系陈天煌第4章词法分析本章将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。4.1对于词法分析程序的要求4.2正规表达式与正规集（正规语言）4.3有穷自动机4.5正规文法与有穷自动机的等价性4.4正规式与有穷自动机的等价性4.6词法分析程序的自动构造武汉理工大学计算机科学系陈天煌本章重点•单词的描述工具•单词的识别系统•设计和实现词法分析程序—首先需要描述和刻画程序设计语言中的原子单位——单词，其次需要识别单词和执行某些相关的动作。—描述程序设计语言的词法的机制是正则表达式，识别机制是有穷状态自动机。武汉理工大学计算机科学系陈天煌词法分析程序实现词法分析（lexicalanalysis）的程序称为词法分析程序（或扫描器）。对构成源程序的字符串从左到右的扫描，逐个字符地读入源程序字符并按照构词规则切分成一个一个具有独立意义的单词。并确定其属性（如保留字、标识符、运算符、界限符和常量等）。再把它们转换成长度统一的标准形式—属性字（TOKEN）。词法分析程序的主要任务：武汉理工大学计算机科学系陈天煌词法分析是编译过程中的第一个阶段，在语法分析前进行。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。源程序词法分析程序语法分析程序Tokengettoken….词法分析程序和语法分析程序的关系武汉理工大学计算机科学系陈天煌词法分析工作从语法分析工作独立出来的原因：•简化设计•改进编译效率•增加编译系统的可移植性武汉理工大学计算机科学系陈天煌§4.1对于词法分析器的要求4.1.1词法分析器的功能和输出形式功能：输入源程序，输出单词符号。单词符号是一个程序语言的基本语法符号。单词的分类（五类）：(1)关键字：由程序语言定义的具有固定意义的标识符。也称为保留字或基本字。(2)标识符：用来表示程序中各种名字的字符串。(3)常数：常数的类型一般有整型、实型、布尔型、文字型。(4)运算符：如+、－、*、/等。(5)界限符：如逗号、分号、括号等。武汉理工大学计算机科学系陈天煌一个程序语言的关键字、运算符、界限符都是固定的，即数量有限及意义明确；而对于标识符和常数通常是不确定的。词法分析器所输出的单词符号常常表示成如下的二元式：（单词种别，单词符号的属性值）单词种别通常用整数编码。一个语言的单词符号如何分种，分成几种，怎样编码，是一个技术性的问题。它主要取决于处理上的方便。标识符一般统归为一种。常数则直按类型（整、实、布尔等）分种。关键字可将其全体视为一种，也可以一字一种。采用一字一种的分法实际处理起来较为方便。运算符可采用一符一种的分法，但也可以把具有一定共性的运算符视为一种。至于界符一般用一符一种的分法。武汉理工大学计算机科学系陈天煌如果一个种别只含一个单词符号，那么，对于这个单词符号，种别编码就完全代表它自身了。若一个种别含有多个单词符号，那么，对于它的每个单词符号，除了给出种别编码之外，还应给出有关单词符号的属性信息。单词符号的属性是指单词符号的特性或特征。属性值则是反应特性或特征的值。例如，对于某个标识符，常将存放它的有关信息的符号表项的指针作为其属性值；对于某个常数，则将存放它的常数表项的指针作为其属性值。武汉理工大学计算机科学系陈天煌在教材中，我们假定关键字、运算符和界限符都是一符一种。对于它们，词法分析器只给出其种别编码，不给出它自身的值。标识符单列一种。常数按类型分种。考虑下述C＋十代码段：while（i＞＝j）i－－；经词法分析器处理后，它将被转换为如下的单词符号序列：＜while，－＞＜（，－＞＜id，指向i的符号表项的指针＞＜＞＝，－＞＜id，指向j的符号表项的指针＞＜），－＞＜id，指向i的符号表项的指针＞＜－－，－＞＜；，－＞武汉理工大学计算机科学系陈天煌4.1.2词法分析器的设计我们将按照词法分析的任务和作为一个独立子程序的要求来考虑词法分析器的设计。一、输入、预处理词法分析器工作的第一步是输入源程序文本。输入串一般是放在一个缓冲区中，这个缓冲区称输入缓冲区。词法分析的工作（单词符号的识别）可以直接在这个缓冲区中进行。但在许多情况下，把输入串预处理一下，对单词符号的识别工作将是比较方便的。武汉理工大学计算机科学系陈天煌•某些跳格符、回车符和换行符等编辑性字符，在别处的任何出现都没有意义，预处理时可以将其剔掉。•注解部分—仅在于改善程序的易读性和易理解性。对于它们，预处理时可以将其剔掉。•空白符（一个或相继数个）用作单词符号之间的间隔，即用作界符。在这种情况下，预处理时可把相继的若干个空白结合成一个。我们可以构造一个预处理子程序，它能够完成上面所述的任务。预处理的主要工作：武汉理工大学计算机科学系陈天煌二、单词符号的识别：超前搜索词法分析器的结构如图4.1所示。图4.1词法分析器武汉理工大学计算机科学系陈天煌三、状态转换图状态转换图是一张有限方向图。在状态转换图中，结点代表状态，用圆圈表示。状态之间用箭弧连结。箭弧上的标记（字符）代表在射出结点（即箭弧始结点）状态下可能出现的输入字符或字符类。例如，图4.2（a）表示：在状态1下，若输入字符为X，则读进X，并转换到状态2。若输入字符为Y，则读进Y，并转换到状态3。一张转换图只包含有限个状态（即有限个结点），其中有一个被认为是初态，而且实际上至少要有一个终态（用双圈表示）。123XY图4.2（a）转换图示例武汉理工大学计算机科学系陈天煌一个状态转换图可用于识别（或接受)一定的字符串。例如，识别标识符的转换图如图4.2（b）所示。图4.2（b）识别标识符的转换图武汉理工大学计算机科学系陈天煌图4.2（c）识别整数的转换图图4.2（d）识别FORTRAN实型常数的转换图武汉理工大学计算机科学系陈天煌§4.2正规表达式与正规集（正规语言）程序设计语言中的单词是基本语法成分。单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，实现词法分析程序的自动构造。正规表达式是典型的词法规则描述工具。武汉理工大学计算机科学系陈天煌正规式定义（正规式和它所表示的正规集）：设字母表为，辅助字母表={，，，，，，}，正规式也称正则表达式。正规表达式（regularexpression）是说明单词的模式(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.仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的集合才是上的正规集。武汉理工大学计算机科学系陈天煌注意:其中“”、“”、“”均为正规式运算符：2.“”读为“连接”；3.“”读为“闭包”（即，任意有限次的自重复连接）。在不致混淆时，括号可省去，但规定算符的优先顺序为“”、“”、“”。连接符“”一般可省略不写。“”、“”和“”都是左结合的。1.“”读为“或”；武汉理工大学计算机科学系陈天煌例子令={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,ab……所有由a和b组成的串}(ab)(aabb)(ab){上所有含有两个相继的a或两个相继的b组成的串}武汉理工大学计算机科学系陈天煌讨论下面两个例子例4.2有={d，.，e，+，-},则上的正规式d(.dd)(e(+-)dd)表示的是无符号数的集合。其中d为0～9的数字。结论：程序设计语言的单词都能用正规式来定义。例4.1令={l，d}，则上的正规式r=l(ld)定义的正规集为:{l,ll,ld,ldd,……},其中l代表字母,d代表数字,正规式即是字母(字母数字),它表示的正规集中的每个元素的模式是“以字母打头的字母数字串”,就是Pascal和多数程序设计语言允许的的标识符的词法规则。武汉理工大学计算机科学系陈天煌正规式的等价性若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。例如：e1=(ab)，e2=ba，e1=e2又如：e1=b(ab),e2=(ba)b，e1=e2e1=(ab),e2=(ab)，e1=e2武汉理工大学计算机科学系陈天煌设U,V,W为正规式，正规式服从的代数规律有：1.UV=VU“或”服从交换律2.U(VW)=(UV)W“或”的可结合律3.(UV)W=U(VW)“连接”的可结合律4.U(VW)=UVUW(VW)U=VUWU分配律5.U=U,U=U是“连接”的恒等元素零一律6.UU=UU=UUU…“或”的抽取律武汉理工大学计算机科学系陈天煌§4.3有穷自动机有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。有穷自动机分为两类：确定的有穷自动机(DeterministicFiniteAutomata)和不确定的有穷自动机(NondeterministicFiniteAutomata)。武汉理工大学计算机科学系陈天煌关于有穷自动机讨论如下内容：•确定的有穷自动机DFA•不确定的有穷自动机NFA•NFA的确定化•DFA的最小化武汉理工大学计算机科学系陈天煌1.K是一个有穷状态集，它的每个元素称为一个状态；§4.3.1确定的有穷自动机DFA一、DFA定义：一个确定的有穷自动机（DFA）M是一个五元组：M=（K，Σ，f，s0，Z）,其中:2.Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号表；3.f是转换函数，是在K×Σ→K上的单值部分映射。即，如果f（ki，a）=kj，（ki∈K，kj∈K）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；5.ZK是一个终态集（可空），终态也称可接受状态或结束状态。4.s0∈K是唯一的一个初态；武汉理工大学计算机科学系陈天煌二、一个DFA的例子：DFAM=（{S，U，V，Q}，{a，b}，f，S，{Q}）其中f定义为：f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q武汉理工大学计算机科学系陈天煌显然，一个DFA可用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，即k行a列的矩阵元素表示f（k，a）的值。这个矩阵称为状态转换矩阵。状态abSUVUQVVUQ-QQQ对于上例，有如下状态转换矩阵注意：在状态矩阵中初态结点的旁边标以；终态结点旁边标—。f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q武汉理工大学计算机科学系陈天煌一个DFA也可表示成一张（确定的）状态转换图。注意：初态结点的旁边标以；终态结点则用双圈表示。假定DFAM含有m个状态和n个输入字符，那么，这个图含有m个状态结点，每个结点顶多有n条箭弧射出和别的结点相连接，每条箭弧用Σ中的一个不同输入字符作标记，整张图含有唯一的一个初态结点和若干个（可以是0个）终态结点。武汉理工大学计算机科学系陈天煌SUQVaabbbaa,