编译原理第三章词法分析.ppt

第三章第三章 词法分析词法分析 (Lexical Analysis)Lexical:of or relating to words or the vocabulary of a language as distinguished from its grammar and construction 词法分析在编译程序中的逻辑位置词法分析在编译程序中的逻辑位置表表 处处 理理 错错 误误 处处 理理 目目标标代代码码生生成成中中间间代代码码优优化化中中间间代代码码生生成成语语义义分分析析语语法法分分析析词词词词法法法法分分分分析析析析目目标标程程序序源源程程序序主要内容：主要内容：l词法分析程序的功能词法分析程序的功能;l单词分类及内部表示单词分类及内部表示;l词法分析程序的设计与实现步骤。词法分析程序的设计与实现步骤。3.1 3.1 词法分析介绍词法分析介绍例例 某程序片段如下：某程序片段如下：VAR sum,first,count:real;BEGIN sum:=first+count*10 END.VARsum,first,count:real;BEGINsum:=first+count*10END.l源程序源程序一般表现为字符序列的形式一般表现为字符序列的形式;例例 某程序片段如下：某程序片段如下：VAR sum,first,count:real;BEGIN sum:=first+count*10 END.:=first+count;sum,count:realVARsum,first.*10ENDBEGINl期望的源程序表示形式期望的源程序表示形式:=:END3.1.1 3.1.1 词法分析程序的功能词法分析程序的功能l单词单词是字符的序列是字符的序列,是指语言中那些具有独立是指语言中那些具有独立含义的最小语义单位。含义的最小语义单位。l单词不是程序设计语言中的语法概念，是编单词不是程序设计语言中的语法概念，是编译程序中引进的一个概念。译程序中引进的一个概念。l编译程序的翻译工作编译程序的翻译工作 为提高效率，编译为提高效率，编译应该应该在单词一级上进行在单词一级上进行;l词法分析的主要任务词法分析的主要任务:词法分析是编译的第一词法分析是编译的第一阶段，它的的主要任务是按语言的词法规则，从阶段，它的的主要任务是按语言的词法规则，从左至右逐个字符地对原程序进行扫描，从源程序左至右逐个字符地对原程序进行扫描，从源程序中识别出每个单词，并把每个单词转换成它们的中识别出每个单词，并把每个单词转换成它们的内部表示，即所谓的内部表示，即所谓的TOKENTOKEN，同时进行词法检查。，同时进行词法检查。l词法分析程序：词法分析程序：执行词法分析的程序称为词法执行词法分析的程序称为词法分析程序分析程序,有时也称为词法分析器有时也称为词法分析器(Lexical Analyzer)或者扫描器或者扫描器(Scanner)(Scanner)。3.1.2 词法分析程序的接口词法分析程序的接口 l词法分析程序与语法分析程序的接口有两种形式词法分析程序与语法分析程序的接口有两种形式:1.1.词法分析程序作为编译器的独立一遍词法分析程序作为编译器的独立一遍 遍（遍（PassPass）：所谓）：所谓“遍遍”就是对源程序或源程序就是对源程序或源程序的中间表示形式从头到尾扫描一次，并作加工处的中间表示形式从头到尾扫描一次，并作加工处理，生成新的中间结果或目标程序。理，生成新的中间结果或目标程序。词法分析程序作为独立的一遍：读入源程序字符词法分析程序作为独立的一遍：读入源程序字符序列，识别出每一个单词并将其转换成相应的内序列，识别出每一个单词并将其转换成相应的内部表示，形成一个部表示，形成一个TOKENTOKEN序列，这个序列，这个TOKENTOKEN序列将序列将作为语法分析程序的输入；作为语法分析程序的输入；2.2.词法分析程序作为语法分析程序的一个子程序词法分析程序作为语法分析程序的一个子程序 语法分析程序每调用一次词法分析程序语法分析程序每调用一次词法分析程序,词词法分析程序就从源程序的字符序列中拼出一个法分析程序就从源程序的字符序列中拼出一个单词，并将其单词，并将其TOKENTOKEN值返回给语法分析程序。值返回给语法分析程序。这种方式的好处是，它不需要存储源程序这种方式的好处是，它不需要存储源程序的内部表示。的内部表示。词法分析器的接口词法分析器的接口CharList 独独 立立词法分析器词法分析器语法分析语法分析TokenList 附附 属属词法分析器词法分析器语法分析语法分析callTokenCharList 3.2 3.2 词法分析程序的设计词法分析程序的设计3.2.1 单词分类单词分类一般常用程序设计语言的单词可以分为以下几类：一般常用程序设计语言的单词可以分为以下几类：l保留字：保留字：保留字一般是由语言系统自身定义的保留字一般是由语言系统自身定义的，通常是由字母组成的字符串。如通常是由字母组成的字符串。如C C语言中的语言中的int,if,for,doint,if,for,do等等。这些字在语言中具有等等。这些字在语言中具有固定的意义，是编译程序识别各类语法成分的固定的意义，是编译程序识别各类语法成分的依据。依据。l标识符：标识符：用来标识程序中各个对象的名称。它用来标识程序中各个对象的名称。它们由用户定义，用来表示变量名、常量名、数们由用户定义，用来表示变量名、常量名、数组名和函数名等。组名和函数名等。l常量：常量：主要包括整数常数、实数常数、字符常量、主要包括整数常数、实数常数、字符常量、字符串常量等。字符串常量等。l特殊符号特殊符号：包括运算符和界限符。包括运算符和界限符。运算符表示程序中算术运算、逻辑运算、运算符表示程序中算术运算、逻辑运算、字符运算、赋值运算的确定的字符或字符串。字符运算、赋值运算的确定的字符或字符串。如各类语言通用的如各类语言通用的+、-、*、/、=、=等。等。界限符在语言中是作为语法上的分界符号使用的。界限符在语言中是作为语法上的分界符号使用的。如逗号、分号、单引号等。如逗号、分号、单引号等。3.2.1 单词分类（续）单词分类（续）3.2.2 3.2.2 单词的内部表示单词的内部表示lTOKEN结构图结构图 l单词的内部表示单词的内部表示TOKEN的结构一般由两部分组成：的结构一般由两部分组成：单词类别和语义信息。单词类别和语义信息。l单词类别，又称词法信息，用来区分单词的不同单词类别，又称词法信息，用来区分单词的不同种类，通常可以用整数编码来表示。种类，通常可以用整数编码来表示。l单词的语义信息，应该是唯一确定其本身内容的单词的语义信息，应该是唯一确定其本身内容的编码。编码。词法信息词法信息语义信息语义信息一、标识符和常量的一、标识符和常量的TOKENTOKEN结构结构 l给出标识符和常量类别编码给出标识符和常量类别编码;l给出标识符和常量的给出标识符和常量的语义信息。语义信息。关于语义信息可以有两种处理方法：关于语义信息可以有两种处理方法：一种是在其一种是在其TOKENTOKEN的语义信息部分直接存储这些值；的语义信息部分直接存储这些值；另外一种是设置标识符表和常量表来存储其值，这时另外一种是设置标识符表和常量表来存储其值，这时TOKENTOKEN的的语义信息部分就是一个指向相应表项的一个指针。语义信息部分就是一个指向相应表项的一个指针。第一种方法处理起来比较简单，但是第一种方法处理起来比较简单，但是TOKENTOKEN的空间大小不好确的空间大小不好确定，可能造成空间浪费。因此，我们采取第二种策略。定，可能造成空间浪费。因此，我们采取第二种策略。标识符种类编码标识符种类编码语义信息语义信息常量种类编码常量种类编码语义信息语义信息二、保留字、界限符和运算符的处理二、保留字、界限符和运算符的处理l可以有两种处理方法：可以有两种处理方法：一种是保留字、界限符和运算符分别算作一类，除了要给出一种是保留字、界限符和运算符分别算作一类，除了要给出其类别外，还需在其其类别外，还需在其TOKENTOKEN的语义信息部分直接存储这些值的的语义信息部分直接存储这些值的串或整数编码；如：串或整数编码；如：另外一种是保留字、界限符和运算符采用一符一类的方法，另外一种是保留字、界限符和运算符采用一符一类的方法，不输出单词的值（其不输出单词的值（其TOKENTOKEN的语义信息部分为空），只输出其的语义信息部分为空），只输出其类别码即可。如：类别码即可。如：保留字种类编码保留字种类编码if+的的 编码编码单词名称 类别编码(词法信息)类别编码的助记符标识符 1$id无符号整数2$int，30$comma；31$semi:=32$assi+33$plus.34$stop：35$colon*36$multn37$returnvar15$varreal20$realbegin23$beginend24$end单词名称 类别编码(词法信息)类别编码的助记符标识符 1$id无符号整数2$int，30$comma；31$semi:=32$assi+33$plus.34$stop：35$colon*36$multn37$returnvar15$varreal20$realbegin23$beginend24$end例例1 某程序片段如下：某程序片段如下：VAR sum,first,count:real;BEGIN sum:=first+count*10 END.不设置标识符表和常量表，词法分不设置标识符表和常量表，词法分析程序扫描该程序段的字符序析程序扫描该程序段的字符序列，生成下列列，生成下列TOKEN序列：序列：1.(15,)2.(1,sum)3.(30,)4.(1,first)5.(30,)6.(1,count)7.(35,)8.(20,)9.(31,)10.(37,)11.(23,)12.(37,)13.(1,sum)14.(32,)15.(1,first)16.(33,)17.(1,count)18.(36,)19.(2,10 )20.(37,)21.(24,)22.(34,)单词名称 类别编码(词法信息)类别编码的助记符标识符 1$id无符号整数2$int，30$comma；31$semi:=32$assi+33$plus.34$stop；35$colon*36$multn37$returnvar15$varreal20$realbegin23$beginend24$end例例1 某程序片段如下：某程序片段如下：VAR sum,first,count:real;BEGIN sum:=first+count*10 END.不设置标识符表和常量表，词法分不设置标识符表和常量表，词法分析程序扫描该程序段的字符序析程序扫描该程序段的字符序列，生成下列列，生成下列TOKEN序列：序列：1.($var,)2.($id,sum)3.($comma,)4.($id,first)5.($comma,)6.($id,count)7.($colon,)8.($real,)9.($semi,)10.($return,)11.($begin,)12.($return,)13.($id,sum)14.($assi,)15.($id,first)16.($plus,)17.($id,count)18.($mult,)19.($int,10 )20.($return,)21.($end,)22.($stop,)u设置标识符表和常量表设置标识符表和常量表,词法分析程序扫描该程序段的字符序词法分析程序扫描该程序段的字符序列，生成下列列，生成下列TOKEN序列：序列：1.($var,)3.($comma,)5.($comma,)7.($colon,)8.($real,)9.($semi,)10.($return,)11.($begin,)12.($return,)13.($id,p1)14.($assi,)15.($id,p2)16.($plus,)17.($id,p3)18.($mult,)20.($return,)21.($end,)22.($stop,)p2p1p3p4标识符表标识符表常量表常量表例例1 某程序片段如下：某程序片段如下：VAR sum,first,count:real;BEGIN sum:=first+count*10 END.sum2.($id,p1)firstcount104.($id,p2)6.($id,p3)19.($int,p4 )例例 某程序片段如下：某程序片段如下：VAR sum,first,count:real;BEGIN sum:=first+count*10 END.(30,)(1,p3)(35,)(34,)(15,)(1,p1)(30,)(1,p2)(37,)(1,p1)(32,)(20,)(31,)(37,)(23,)(2,10)(37,)(24,)(1,p2)(33,)(1,p3)(36,)曾期望的形式曾期望的形式曾期望的形式曾期望的形式源程序源程序源程序源程序词法分析的结果词法分析的结果词法分析的结果词法分析的结果3.2.3 单词的形式描述单词的形式描述l描述程序设计语言中单词的工具主要有：正则表达描述程序设计语言中单词的工具主要有：正则表达式、自动机和正则文法。式、自动机和正则文法。l设计一个语言的词法分析器，通常是首先用正则表设计一个语言的词法分析器，通常是首先用正则表达式描述各类单词的组成，然后将其转换为确定有达式描述各类单词的组成，然后将其转换为确定有限自动机，最后根据这个自动机来构造词法分析器限自动机，最后根据这个自动机来构造词法分析器 。l基于正则表达式的单词的形式化描述基于正则表达式的单词的形式化描述一般的程序设计语言，各类单词的正则表达式可描述一般的程序设计语言，各类单词的正则表达式可描述如下如下 ：1 1）标识符标识符：L(L|D)L(L|D)*其中：其中：L=a-z,A-Z,D=0-9L=a-z,A-Z,D=0-92 2）正整数正整数：D D1 1D D*其中：其中：D D1 1=1-9=1-9，D=0-9 D=0-9 3 3）特殊符号特殊符号：+|+|；|：|:=|=|:=|=|4 4）保留字保留字：begin|end|while|begin|end|while|l基于有限自动机的单词的形式化描述基于有限自动机的单词的形式化描述构造识别单词的有限自动机的方法与步骤如下：构造识别单词的有限自动机的方法与步骤如下：1.1.根据构成规则对程序语言的单词按类构造出相根据构成规则对程序语言的单词按类构造出相应的状态转换图，或将各类单词的正则表达式应的状态转换图，或将各类单词的正则表达式转换成相应的有限自动机。转换成相应的有限自动机。2.2.合并各类单词的状态转换图，构成一个能识别合并各类单词的状态转换图，构成一个能识别语言所有单词的语言所有单词的DFADFA。合并方法为：。合并方法为：（1 1）将各类单词的状态转换图的初始状态合并）将各类单词的状态转换图的初始状态合并为一个唯一的初始状态；为一个唯一的初始状态；（2 2）化简调整状态冲突和对冲突状态重新编号；）化简调整状态冲突和对冲突状态重新编号；（3 3）如果有必要，增加出错状态。）如果有必要，增加出错状态。l例：标识符D1D无符号整数+界限符、运算符：=图3.4 各类单词的自动机；：=LL|Dl合并后的DFA 01LL|D2D1D：=653+4；=9780 7106otherother3.2.4 自动机的实现自动机的实现l自动机实现的状态转换矩阵法（又称数据中心法自动机实现的状态转换矩阵法（又称数据中心法 ）把自动机看作一种数据结构（状态转换矩阵），由控把自动机看作一种数据结构（状态转换矩阵），由控制程序控制字符在其上运行，从而完成词法分析。转换制程序控制字符在其上运行，从而完成词法分析。转换矩阵法的优点是程序短，但占存储空间多。矩阵法的优点是程序短，但占存储空间多。State:=InitState;Read(CurrentChar);while T(State,CurrentChar)error&CurrentChar Eof dobegin State:=T(State,CurrentChar);Read(CurrentChar);end;if State FinalStates then Accept else Error;l自动机实现的直接转向法自动机实现的直接转向法 （又称状态转换图（又称状态转换图方法、程序中心法方法、程序中心法 、）、）1.1.每个状态对应一个带标号的每个状态对应一个带标号的switchswitch语句语句2.2.转向边对应转向边对应gotogoto语句语句 特点：特点：程序长，但占用存储空间少程序长，但占用存储空间少b非终止状态对应的非终止状态对应的switchswitch语句语句ijkaLi:switch(CurrentChar)case a：goto Lj;case b:goto Lk;default :Error();终止状态对应的终止状态对应的switchswitch语句语句 jikabLi:seitch(CurrentChar)case a ：goto Lj;case b :goto Lk;case Eof:Accept;default :Error();3.3 3.3 词法分析程序的实现词法分析程序的实现3.3.1 3.3.1 实现词法分析程序应注意的问题实现词法分析程序应注意的问题一般语言中常见的一些问题。一般语言中常见的一些问题。1.1.保留字保留字l识别保留字的实现方法可分为两大类：一类是设识别保留字的实现方法可分为两大类：一类是设置保留字表，另一类是用自动机单独来识别。置保留字表，另一类是用自动机单独来识别。l设置保留字表方法的主要思想是事先构造好所谓设置保留字表方法的主要思想是事先构造好所谓的保留字表，在进行词法分析时，把保留字也当的保留字表，在进行词法分析时，把保留字也当作一般标识符来识别，然后查保留字表，若有，作一般标识符来识别，然后查保留字表，若有，则把它作为保留字来处理；若没有，则按一般标则把它作为保留字来处理；若没有，则按一般标识符来处理。识符来处理。l用自动机单独来识别保留字的主要思想是在自动机用自动机单独来识别保留字的主要思想是在自动机中加入识别各个保留字的状态，即把保留字和一般中加入识别各个保留字的状态，即把保留字和一般标识符分开来识别而不统一识别。标识符分开来识别而不统一识别。beginendNot(e)Not(g)Not(i)Notn)Not(n)Not(d)Not(b,e)l两种方式的比较：不用保留字表的优点是能两种方式的比较：不用保留字表的优点是能提高速度，但它使得自动机的状态数随着保提高速度，但它使得自动机的状态数随着保留字个数的增多而急剧变大。留字个数的增多而急剧变大。2.复合单词的识别复合单词的识别 在程序设计语言中，有一类单词是由两个或在程序设计语言中，有一类单词是由两个或者两个以上的符号组成的，这类单词的前缀部分也者两个以上的符号组成的，这类单词的前缀部分也可以是一个独立的单词，如可以是一个独立的单词，如“:=”:=”，在处理到，在处理到“:”:”时，还不能断定这个单词是时，还不能断定这个单词是“:”:”，还是，还是“:=”:=”的前缀，这取决于的前缀，这取决于“:”:”的下一个字符，如的下一个字符，如果下一个字符是果下一个字符是“=”=”，则该单词为，则该单词为“:=”:=”，否则，否则为为“:”:”。在处理这类单词时要特别加以注意。在处理这类单词时要特别加以注意。3.数的转换数的转换 词法分析程序应该把数字字符串转换成数，词法分析程序应该把数字字符串转换成数，如如“123”123”应该转换成应该转换成123123。4.4.向前看若干个字符的处理向前看若干个字符的处理 在有些语言里，为了识别出一个单词需要向在有些语言里，为了识别出一个单词需要向前看好几个字符。前看好几个字符。5.控制字符的处理控制字符的处理 控制字符，如空格、控制字符，如空格、TabTab和回车换行等。这些字和回车换行等。这些字符将占用很大的空间，而且一般来说，它们只有词符将占用很大的空间，而且一般来说，它们只有词法意义而没有语法和语义上的意义（字符串内的控法意义而没有语法和语义上的意义（字符串内的控制字符例外）。制字符例外）。若若TabTab和空格符用来分隔源程序中不同的单词，则直和空格符用来分隔源程序中不同的单词，则直接将它们删除。接将它们删除。回车换行本身并没有实际意义，但是对于错误处理回车换行本身并没有实际意义，但是对于错误处理起着重要的作用，因此回车换行不能直接删除。起着重要的作用，因此回车换行不能直接删除。需要注意的是不能删除掉字符串内的需要注意的是不能删除掉字符串内的TabTab和空格符，和空格符，因为它们任何时候都是有意义的符号。因为它们任何时候都是有意义的符号。在处理在处理TabTab和空格符时，可以设置一个标志变量，和空格符时，可以设置一个标志变量，每当进入字符串内部时令其为真，这样就可以根据每当进入字符串内部时令其为真，这样就可以根据此变量的值来判断是否在字符串内部，如果不是在此变量的值来判断是否在字符串内部，如果不是在字符串内部，可以直接将它们删除。字符串内部，可以直接将它们删除。6.注释的处理注释的处理 源程序中的注释没有任何语法和语义上的意义，源程序中的注释没有任何语法和语义上的意义，因此在进行词法分析时可以直接将注释删除，而不因此在进行词法分析时可以直接将注释删除，而不必生成其必生成其TOKENTOKEN。3.3.4 实现算法实现算法l首先给出词法分析程序中用到的一些基本操作。Append(string,char)：拼单词。KeyWord(string)：查保留字表，看string是否为保留字。若此函数返回0，则表示string是一个标识符，否则为保留字编码。AddTable(table,string)：入表操作，检查string在table中有没有出现，若有则返回其位置指针，若没有则将其插入到table的末尾，并返回该位置的指针。BACK：源程序文件指针回退一个字符。PROCEDURE Scanner();BEGIN LS0:string:=“”;ReadChar(CurrentChar);case CurrentChar of A.Z|a.z：goto LS1；0.9：goto LS2;+：goto LS3;：goto LS4;:：goto LS5;：goto LS8;end;01LL|D2D1D：=653+4；=97other10other8LS1:string:=Append(string,CurrentChar);ReadChar(CurrentChar);case CurrentChar of A.Z，a.z，0.9：goto LS1;other：BEGIN BACK;c:=KeyWord(string);if(c!=0)then return(c,“”);else beginpID:=AddTable(IdTable,string);return($id,pID);end;END end;01LL|D2D1D：=653+4；=97other10other8 LS2:string:=Append(string,CurrentChar);ReadChar(CurrentChar);case CurrentChar of 0.9:goto LS2;other:BEGIN BACK;pNB:=AddTable(NbTable,string);return($int,pNB);ENDend;01LL|D2D1D：=653+4；=97other10other8LS3:return($plus,“”);LS4:return($semi,“”);LS5:ReadChar(CurrentChar);case CurrentChar of=:goto LS6;other:goto LS7;end;LS6:return($assi,“”);LS7:BACK;return($colon,“”);LS8:ReadChar(CurrentChar);case CurrentChar of =:goto LS9;other:goto LS10;end;LS9:return($le,“”);LS10:BACK;return($lt,“”);END01LL|D2D1D：=653+4；=97other10other83.4 词法分析程序自动生成词法分析程序自动生成一个数的二进制表示后面加一个“0”得到的数相当于该数乘以2；一个数的二进制表示后面加一个“1”得到的数相当于该数乘2加1。练习题：用练习题：用正则表达式表示能被正则表达式表示能被3整除整除的二进制数的集合。的二进制数的集合。结果：结果：1(10*1|01*0)*10*|01start00100101 2final110111010011211152346 93 186 372 745 1491 1start00100101 2final101*001*0|10*1 10*1S S1(01*0|10*1)*11(01*0|10*1)*10*1(01*0|10*1)*1|0