编译原理第三章_词法分析

第三章词法分析(LexicalAnalysis)Lexical:oforrelatingtowordsorthevocabularyofalanguageasdistinguishedfromitsgrammarandconstruction词法分析在编译程序中的逻辑位置表处理错误处理目标代码生成中间代码优化中间代码生成语义分析语法分析词法分析目标程序源程序主要内容：词法分析程序的功能;单词分类及内部表示;词法分析程序的设计与实现步骤。3.1词法分析介绍例某程序片段如下：VARsum,first,count:real;BEGINsum:=first+count*10END.VAR□sum,first,count:real;BEGINsum:=first+count*10END.源程序一般表现为字符序列的形式;例某程序片段如下：VARsum,first,count:real;BEGINsum:=first+count*10END.:=first+count;sum,count:realVARsum,first.*10ENDBEGIN期望的源程序表示形式:=:END3.1.1词法分析程序的功能单词是字符的序列,是指语言中那些具有独立含义的最小语义单位。单词不是程序设计语言中的语法概念，是编译程序中引进的一个概念。编译程序的翻译工作为提高效率，编译应该在单词一级上进行;词法分析的主要任务:词法分析是编译的第一阶段，它的的主要任务是按语言的词法规则，从左至右逐个字符地对原程序进行扫描，从源程序中识别出每个单词，并把每个单词转换成它们的内部表示，即所谓的TOKEN，同时进行词法检查。词法分析程序：执行词法分析的程序称为词法分析程序,有时也称为词法分析器(LexicalAnalyzer)或者扫描器(Scanner)。3.1.2词法分析程序的接口词法分析程序与语法分析程序的接口有两种形式:1.词法分析程序作为编译器的独立一遍遍（Pass）：所谓“遍”就是对源程序或源程序的中间表示形式从头到尾扫描一次，并作加工处理，生成新的中间结果或目标程序。词法分析程序作为独立的一遍：读入源程序字符序列，识别出每一个单词并将其转换成相应的内部表示，形成一个TOKEN序列，这个TOKEN序列将作为语法分析程序的输入；2.词法分析程序作为语法分析程序的一个子程序语法分析程序每调用一次词法分析程序,词法分析程序就从源程序的字符序列中拼出一个单词，并将其TOKEN值返回给语法分析程序。这种方式的好处是，它不需要存储源程序的内部表示。词法分析器的接口CharList独立词法分析器语法分析TokenList附属词法分析器语法分析callTokenCharList3.2词法分析程序的设计3.2.1单词分类一般常用程序设计语言的单词可以分为以下几类：保留字：保留字一般是由语言系统自身定义的，通常是由字母组成的字符串。如C语言中的int,if,for,do等等。这些字在语言中具有固定的意义，是编译程序识别各类语法成分的依据。标识符：用来标识程序中各个对象的名称。它们由用户定义，用来表示变量名、常量名、数组名和函数名等。常量：主要包括整数常数、实数常数、字符常量、字符串常量等。特殊符号：包括运算符和界限符。运算符表示程序中算术运算、逻辑运算、字符运算、赋值运算的确定的字符或字符串。如各类语言通用的+、-、*、/、、=、=等。界限符在语言中是作为语法上的分界符号使用的。如逗号、分号、单引号等。3.2.1单词分类（续）3.2.2单词的内部表示TOKEN结构图单词的内部表示TOKEN的结构一般由两部分组成：单词类别和语义信息。单词类别，又称词法信息，用来区分单词的不同种类，通常可以用整数编码来表示。单词的语义信息，应该是唯一确定其本身内容的编码。词法信息语义信息一、标识符和常量的TOKEN结构给出标识符和常量类别编码;给出标识符和常量的语义信息。关于语义信息可以有两种处理方法：一种是在其TOKEN的语义信息部分直接存储这些值；另外一种是设置标识符表和常量表来存储其值，这时TOKEN的语义信息部分就是一个指向相应表项的一个指针。第一种方法处理起来比较简单，但是TOKEN的空间大小不好确定，可能造成空间浪费。因此，我们采取第二种策略。标识符种类编码语义信息常量种类编码语义信息二、保留字、界限符和运算符的处理可以有两种处理方法：一种是保留字、界限符和运算符分别算作一类，除了要给出其类别外，还需在其TOKEN的语义信息部分直接存储这些值的串或整数编码；如：另外一种是保留字、界限符和运算符采用一符一类的方法，不输出单词的值（其TOKEN的语义信息部分为空），只输出其类别码即可。如：保留字种类编码if‘+’的编码单词名称类别编码(词法信息)类别编码的助记符标识符1$id无符号整数2$int，30$comma；31$semi:=32$assi+33$plus.34$stop：35$colon*36$mult\n37$returnvar15$varreal20$realbegin23$beginend24$end单词名称类别编码(词法信息)类别编码的助记符标识符1$id无符号整数2$int，30$comma；31$semi:=32$assi+33$plus.34$stop：35$colon*36$mult\n37$returnvar15$varreal20$realbegin23$beginend24$end例1某程序片段如下：VARsum,first,count:real;BEGINsum:=first+count*10END.不设置标识符表和常量表，词法分析程序扫描该程序段的字符序列，生成下列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$mult\n37$returnvar15$varreal20$realbegin23$beginend24$end例1某程序片段如下：VARsum,first,count:real;BEGINsum:=first+count*10END.不设置标识符表和常量表，词法分析程序扫描该程序段的字符序列，生成下列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,)设置标识符表和常量表,词法分析程序扫描该程序段的字符序列，生成下列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某程序片段如下：VARsum,first,count:real;BEGINsum:=first+count*10END.sum2.($id,p1)firstcount104.($id,p2)6.($id,p3)19.($int,p4)例某程序片段如下：VARsum,first,count:real;BEGINsum:=first+count*10END.(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单词的形式描述描述程序设计语言中单词的工具主要有：正则表达式、自动机和正则文法。设计一个语言的词法分析器，通常是首先用正则表达式描述各类单词的组成，然后将其转换为确定有限自动机，最后根据这个自动机来构造词法分析器。基于正则表达式的单词的形式化描述一般的程序设计语言，各类单词的正则表达式可描述如下：1）标识符：L(L|D)*其中：L=[a-z,A-Z],D=[0-9]2）正整数：D1D*其中：D1=[1-9]，D=[0-9]3）特殊符号：+|；|：|:=||=|…4）保留字：begin|end|while|…基于有限自动机的单词的形式化描述构造识别单词的有限自动机的方法与步骤如下：1.根据构成规则对程序语言的单词按类构造出相应的状态转换图，或将各类单词的正则表达式转换成相应的有限自动机。2.合并各类单词的状态转换图，构成一个能识别语言所有单词的DFA。合并方法为：（1）将各类单词的状态转换图的初始状态合并为一个唯一的初始状态；（2）化简调整状态冲突和对冲突状态重新编号；（3）如果有必要，增加出错状态。例：标识符D1D无符号整数+界限符、运算符：=图3.4各类单词的自动机；：=LL|D合并后的DFA01LL|D2D1D：=653+4；=97807106otherother3.2.4自动机的实现自动机实现的状态转换矩阵法（又称数据中心法）把自动机看作一种数据结构（状态转换矩阵），由控制程序控制字符在其上运行，从而完成词法分析。转换矩阵法的优点是程序短，但占存储空间多。State:=InitState;Read(CurrentChar);whileT(State,CurrentChar)error&CurrentCharEofdobeginState:=T(State,CurrentChar);Read(CurrentChar);end;ifStateFinalStatesthenAcceptelseError;自动机实现的直接转向法（又称状态转换图方法、程序中心法、）1.每个状态对应一个带标号的switch语句2.转向边对应goto语句特点：程序长，但占用存储空间少b①非终止状态对应的switch语句ijkaLi:switch(CurrentChar){case‘a’：gotoLj;case‘b’:gotoLk;default:Error();}②终止状态对应的switch语句jikabLi:seitch(CurrentChar){case‘a’：gotoLj;case‘b’:gotoLk;case‘Eof’:Accept;default:Error();}3.3词法分析程序的实现3.3.1实现词法分析程序应注意的问题一般语言中常见的一些问题。1.保留字识别保留字的实现方法可分为两大类：一类是设置保留字表，另一类是用自动机单独来识别。设置保留字表方法的主要思想是事先构造好所谓的保留字表，在进行词法分析时，把保留字也当作一般标识符来识别，然后查保留字表，若有，则把它作为保留字来处理；若没有，则按一般标识符来处理。用自动机单独来识别保留字的主要思想是在自动机中加入识别各个保留字的状