Chapter03--词法分析

LIWensheng,SCS,BUPT第3章词法分析基础知识：PASCAL、C语言、正规表达式正规文法、有限自动机知识点：词法分析器的作用、地位记号、模式词法分析器的状态转换图WenshengLiBUPT2词法分析简介3.1词法分析程序与语法分析程序的关系3.2词法分析程序的输入与输出3.3记号的描述和识别3.4词法分析程序的设计与实现3.5软件工具LEX小结WenshengLiBUPT3简介任务：把构成源程序的字符串转换成语义上关联的记号序列编译程序是在单词的级别上来分析和翻译源程序，因此，词法分析是编译的基础本章内容安排讨论手工设计并实现词法分析程序的方法和步骤词法分析程序的作用词法分析程序的地位源程序的输入与词法分析程序的输出单词符号的描述及识别词法分析程序的设计与实现词法分析程序自动生成工具LEX简介WenshengLiBUPT4词法分析程序的作用源程序由单词组成，单词是最小的语义单位词法分析程序的作用：扫描源程序字符流按照源语言的词法规则识别出各类单词符号产生用于语法分析的记号序列词法检查创建符号表(需要的话)把识别出来的标识符插入符号表中与用户接口的一些任务：–跳过源程序中的注释和空白–把错误信息和源程序联系起来WenshengLiBUPT3.1词法分析程序与语法分析程序的关系词法分析程序与语法分析程序之间的三种关系词法分析程序作为独立的一遍词法分析程序作为语法分析程序的子程序词法分析程序与语法分析程序作为协同程序分离词法分析程序的好处词法分析的一些难点5WenshengLiBUPT6词法分析程序作为独立的一遍输出放入一个中间文件磁盘文件内存文件字符串源程序字符词法分析程序记号记号流源程序WenshengLiBUPT7词法分析程序作为语法分析程序的子程序避免了中间文件省去了取送符号的工作有利于提高编译程序的效率语法分析器词法分析器取下一记号字符串源程序字符记号符号表WenshengLiBUPT8词法分析程序与语法分析程序作为协同程序协同程序：如果两个或两个以上的程序，它们之间交叉地执行，这些程序称为协同程序。词法分析程序与语法分析程序在同一遍中，以生产者和消费者的关系同步运行。P1P2唤醒P2唤醒P1唤醒P2唤醒P1WenshengLiBUPT9分离词法分析程序的好处可以简化设计词法程序很容易识别并去除空格、注释，使语法分析程序致力于语法分析，结构清晰，易于实现。可以改进编译程序的效率利用专门的读字符和处理记号的技术构造更有效的词法分析程序。可以加强编译程序的可移植性在词法分析程序中处理特殊的或非标准的符号。WenshengLiBUPT10词法分析的一些难点位置对准Fortran要求某些结构出现在输入行的固定位置空白不作为分隔符Fortran中空格是无意义的，可以随便加入DO5I=1.25（赋值语句，DO5I是标识符）DO5I=1,25（循环语句，DO是关键字）关键字不保留PL/I语言的关键字不保留IFTHENTHENTHEN=ELSE;ELSEELSE=THENWenshengLiBUPT113.2词法分析程序的输入与输出一、词法分析程序的实现方法二、设置缓冲区的必要性三、配对缓冲区四、词法分析程序的输出WenshengLiBUPT12一、词法分析程序的实现方法利用词法分析程序自动生成器从基于正规表达式的规范说明自动生成词法分析程序。生成器提供用于源程序字符流读入和缓冲的若干子程序利用传统的系统程序设计语言来编写利用该语言所具有的输入/输出能力来处理读入操作利用汇编语言来编写直接管理源程序字符流的读入WenshengLiBUPT13二、设置缓冲区的必要性超前搜索：为了得到某一个单词符号的确切性质，需要超前扫描若干个字符。例：有合法的FORTRAN语句：DO99K=1,10和DO99K=1.10为了区别这两个语句，必须超前扫描到等号后的第一个分界符处。例：Pascal语言中：do99、、:=、（*例：C语言中：==、/*、//、++、for_loop方便实现读字符和退字符操作，提高词法分析器的效率WenshengLiBUPT14三、配对缓冲区原因：不论缓冲器多大都不能保证单词不被它的边界打断把一个缓冲器分为相同的两半，每半各含N个字符，一般N=1KB或4KB。基本方法开始指针向前指针……ifx=ythenj:=j+2;eof…WenshengLiBUPT15测试指针的过程(1)IF(向前指针在左半区的终点){读入字符串，填充右半区;向前指针前移一个位置;}ELSEIF(向前指针在右半区的终点){读入字符串，填充左半区;向前指针移到缓冲区的开始位置;}ELSE向前指针前移一个位置;WenshengLiBUPT16每半区带有结束标记的缓冲器开始指针向前指针…ifx=ytheofenj:=j+2;eofeof基本方法的缺点：更新向前指针时要做二次测试改进：每半区带有结束标记的缓冲器更新向前指针时只要做一次测试WenshengLiBUPT17测试指针的过程(2)向前指针前移一个位置；IF(向前指针指向eof){IF(向前指针在左半区的终点){读入字符串，填充右半区;向前指针前移一个位置;};ELSEIF(向前指针在右半区的终点){读入字符串，填充左半区;向前指针指向缓冲区的开始位置;};ELSE终止词法分析;}WenshengLiBUPT18四、词法分析程序的输出——记号记号、模式和单词记号：是指某一类单词符号的种别编码，如标识符的记号为id，数的记号为num等。模式：是指某一类单词符号的构词规则，如标识符的模式是“由字母开头的字母数字串”。单词：是指某一类单词符号的一个特例，如position是标识符。机内表示外部表示构词规则1.关键字记号的种类2.标识符3.常数4.运算符5.分界符WenshengLiBUPT19记号的属性词法分析程序在识别出一个记号后，要把与之有关的信息作为它的属性保留下来。记号影响语法分析的决策，属性影响记号的翻译。在词法分析阶段，对记号只能确定一种属性标识符：单词在符号表中入口的指针常数：它所表示的值关键字：（一符一种、或一类一种）运算符：（一符一种、或一类一种）分界符：（一符一种、或一类一种）记号的属性是指记号的特征或特性，反映特征或特性的值是属性值一种一符则种别值可以认为是属性值，一种多符则需给出属性值WenshengLiBUPT20total:=total+rate*4的词法分析结果id，指向标识符total在符号表中的入口的指针assign_op，-id，指向标识符total在符号表中的入口的指针plus_op，-id，指向标识符rate在符号表中的入口的指针mul_op，-num，整数值4WenshengLiBUPT213.3记号的描述和识别识别单词是按照记号的模式进行的，一种记号的模式匹配一类单词的集合。为设计词法程序，对模式要给出规范、系统的描述。正规表达式和正规文法是描述模式的重要工具。二者具有同等表达能力正规表达式：清晰、简洁正规文法：便于识别一、词法与正规文法二、记号的文法三、状态转换图与记号的识别WenshengLiBUPT22一、词法与正规文法把源语言的文法G分解为若干子文法：G0、G1、G2、…、Gn——正规文法——上下文无关文法语法词法词法：描述语言的标识符、常数、运算符和标点符号等记号的文法语法：借助于记号来描述语言的结构的文法WenshengLiBUPT23二、记号的文法标识符常数整数无符号数运算符分界符关键字WenshengLiBUPT24标识符假设标识符定义为“由字母打头的、由字母或数字组成的符号串”描述标识符集合的正规表达式：letter(letter|digit)*表示标识符集合的正规定义式：letterA|B|…|Z|a|b|…|zdigit0|1|…|9idletter(letter|digit)*WenshengLiBUPT25把正规定义式转换为相应的正规文法(letter|digit)*=|(letter|digit)+=|(letter|digit)(letter|digit)*=|letter(letter|digit)*|digit(letter|digit)*=|(A|…|Z|a|…|z)(letter|digit)*|(0|…|9)(letter|digit)*=|A(letter|digit)*|…|Z(letter|digit)*|a(letter|digit)*|…|z(letter|digit)*|0(letter|digit)*|…|9(letter|digit)*WenshengLiBUPT26标识符的正规文法idArid|…|Zrid|arid|…|zridrid|Arid|Brid|…|Zrid|arid|brid|…|zrid|0rid|1rid|…|9rid一般写作：idletterridrid|letterrid|digitridWenshengLiBUPT27常数——整数描述整数结构的正规表达式为：(digit)+对此正规表达式进行等价变换：(digit)+=digit(digit)*(digit)*=|digit(digit)*整数的正规文法：digitsdigitremainderremainder|digitremainderWenshengLiBUPT28常数——无符号数无符号数的正规表达式为：(digit)+(.(digit)+)?(E(+|-)?(digit)+)?正规定义式为digit0|1|…|9digitsdigit+optional_fraction(.digits)?optional_exponent(E(+|-)?digits)?numdigitsoptional_fractionoptional_exponentWenshengLiBUPT29把正规定义式转换为正规文法(digit)+(.(digit)+)?(E(+|-)?(digit)+)?=(digit)+(.(digit)+|)(E(+|-|)(digit)+|)=digit(digit)*(.digit(digit)*|)(E(+|-|)digit(digit)*|)num1表示无符号数的第一个数字之后的部分num2表示小数点以后的部分num3表示小数点后第一个数字以后的部分num4表示E之后的部分num5表示(digit)*digits表示(digit)+WenshengLiBUPT30无符号数分析图digit(digit)*(.digit(digit)*|)(E(+|-|)digit(digit)*|)num3num2num1num4numnumdigitnum1num1digitnum1|.num2|Enum4|num2digitnum3num3digitnum3|Enum4|num4+digits|-digits|digitnum5digitsdigitnum5num5digitnum5|digits表示(digit)+num5表示(digit)*WenshengLiBUPT31无符号数的正规文法numdigitnum1num1digitnum1|.num2|Enum4|num2digitnum3num3digitnum3|Enum4|num4+digits|-digits|digitnum5digitsdigitnum5num5digitnum5|WenshengLiBUPT32无符号数4.6E-8的分析树numdigitnum1.num2digitnum3Enum4-digitsdigitnum5468WenshengLiBUPT33运算符关系运算符的正规表达式为：|=|=||=|正规定