编译原理 第3章VIP免费

第3章词法分析词法分析程序又称扫描器，是编译过程的第一步，是下一步进行语法分析的基础。词法分析的任务:1.从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位“单词”，并将其转化为内部编码形式。2.删除无用的空白字符和回车字符以及其他非实质性字符。3.删除注释。4.进行词法检查,报告所发现的错误。3.1设计扫描器时应考虑的几个问题3.1.1词法分析阶段的必要性对于一个程序设计语言来说，关键字、标志符、常数、运算符及分隔符都是单词。它们的单词结构(即词法)也是用相应文法中的若干个产生式来描述的。词法分析与语法分析之间的关系通常有两种形式：1.词法分析作为独立的一遍(完全独立模式)词法分析可作为单独一遍来实现。这种词法分析的输出存入一个中间文件供语法分析使用。这样通过词法分析，就可以将字符串源程序转换成符号串源程序。字符串源程序词法分析符号串源程序图3.1词法分析单独作为一遍2.词法分析程序作为语法分析程序的子程序（相对独立模式）将词法分析和语法分析安排在同一遍中，此时词法分析作为语法分析程序的一个子程序。每当语法分析需要一个新的符号时，就调用词法分析子程序，词法分析子程序从字符串源程序中识别出一个具有独立意义的单词，将其返给语法分析。如图3.2。字符串源程序词法分析器语法分析器图3.2词法分析作为语法分析子程序取符号送符号•完全独立模式的好处：改进编译程序的效率、增强编译程序的可移植性、结构清晰、简化设计。•相对独立模式的好处：词法分析器和语法分析器被设计在同一趟，省去了存放单词的终结文件词法分析过程•逐个读入源程序字符，然后按照构词规则切分成一列单词，再转换成单词序列。单词是语言中具有独立意义的最小单位。•词标(token）是单词的机内表示，其格式由实现系统规定。•实现词法分析程序时，首先需要描述单词，其次需要执行某些相关操作识别单词。•描述程序设计语言的词法的机制是3型文法和正规式，识别机制是有穷状态自动机（FA）。•在词法分析过程中，与语法分析无关的单词应处理时可掠过，无需产生相应词标。3.1.2单词符号的内部表示词法分析的功能是识别出的具有独立意义的单词，并转化为相应的内部表示。词法分析的输出常采用二元式(class，value),如图3.3所示。class为以整数码或助记符,value则是该单词的值(如变量名在符号表中的序号,常数的二进制表示,以及运算符和分隔符的编码,等等)class单词类别value单词值图3.3词法分析程序的输出形式单词的分类–单词符号一般可分为下列五种：–基本字，关键字；–标识符；–常数（量）；–运算符；–分隔符•关键字,运算符和分隔符每字为一类。标识符统一为一类,而常数一般按数据类型进行分类。•至于单词的值,一字一类的符号的类别号已能完全表示相应的符号,故不须再给出单词的值;但一个类别中含有多个单词,则除了类别号,还须按某种编码给出单词的值。3.1.3识别标识符的若干约定和策略定义标识符的语法规则为<标识符>→<字母><∣标识符><字母><∣标识符><数字>从语法上来说,标识符的长度似乎可以任意。然而,考虑实现技术,许多语言都对标识符的最大允许长度作了限制。设计扫描器时,按如下原则行事:1.如果一个标识符中的字符个数超过最大允许长度,则把尾部多出的字符截去;2.对于字符个数不超过最大允许长度的标识符,则按“尽可能长”的策略来识别标识符。3.一般而言,当一个语言的两种单词有相同的前缀时,其扫描器都应当考虑采用超前搜索和多字符回退操作。3.1.4源程序的输入及预处理•为了提高读盘的效率和便于扫描器工作,通常采用缓冲输入的方案,即在内存设置一个适当大小的输入缓冲区,让操作系统直接将磁盘上的源程序字符串分批送入次缓冲区,供扫描器处理。•实现源程序输入的一组函数(子程序)作为编译系统的最底层,称为输入系统。•输入系统除了完成上述读盘任务外,还应支持超前搜索和多字符回退操作以及扫描器中依赖于系统的大部分操作。•预处理工作包括将源程序中的注释、回车、换行、制表、空格、空白字符以及其他非实质性符号予以删除。3.2正规文法和状态转换图程序设计语言中的单词是基本语法符号，单词符号的语法可用有效...