编译原理及实现技术 教学课件 作者 刘磊 第03章 词法分析.ppt

《编译原理及实现技术 教学课件 作者 刘磊 第03章 词法分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章词法分析主要内容：词法分析概述词法分析器的设计词法分析器的实现词法分析器自动生成词法分析器功能功能读源程序的字符序列,逐个拼出单词,并构造相应的内部表示TOKEN.同时检查源程序中的词法错误.单词所谓单词是指语言中具有独立含义的最小的语义单位。Token单词的内部表示。编译程序总是用某种程序语言书写的程序，语言的操作对象只能是该语言规定的各种数据。而编译程序的操作对象是程序中的各种语法单位，因此，必须把它们表示成某种数据结构形式。词法分析器的接口CharList独立词法分析器语法分析TokenList附属词法分析器语法分析callTokenCharL

2、ist一般程序设计语言的单词可以分为：1)保留字：保留字一般是由语言系统自身定义的，通常是由字母组成的字符串。2)标识符：标识符一般是由字母开头，字母、数字或其它符号的任意组合构成的。3)常量：用来表示各种常量。主要包括整数常数、实数常数、字符串常量等。4)特殊符号：包括运算符和界限符。运算符表示程序中算术运算、逻辑运算、字符运算、赋值运算的确定的字符或字符串。设计与实现--单词分类1)标识符：L(L

3、D)*其中L=[a-z,A-Z],D=[0-9]2)整数：D1D*

4、0,其中D1=[1-9]3)特殊符号：+

5、；

6、：

7、:=

8、<

9、<=

10、…4)保留字：if

11、e

12、lse

13、…设计与实现--正则表达式描述1.按类构造出相应的状态转换图。2.合并各类单词的状态转换图，构成一个能识别语言所有单词的状态转换图。1)将各类单词的状态转换图的初始状态合并为一个唯一的初始状态；2)化简调整状态冲突和对冲突状态重新编号；3)如果有必要，增加出错状态。设计与实现--有限自动机描述状态转换矩阵法把自动机看作一种数据结构（状态转换矩阵），由控制程序控制字符在其上运行，从而完成词法分析。转换矩阵法的优点是程序短，但占存储空间多。State:=InitState;Read(CurrentChar);whileT(State,CurrentCh

14、ar)error&CurrentCharEofdobeginState:=T(State,CurrentChar);Read(CurrentChar);end;ifStateFinalStatesthenAcceptelseError;特点程序短小，但占用存储空间多。设计与实现--自动机实现状态转换图的形式：每个状态对应一个带标号的case语句转向边对应goto语句特点：程序长，但占用存储空间少ijkabLi:caseCurrentCharofa：gotoLjb:gotoLkother:Error()设计与实现--自动机实现保留字的识别1）设置保留字

15、表事先构造好所谓的保留字表，在进行词法分析时，把保留字也当作一般标识符来识别，然后查保留字表，若有，则把它作为保留字来处理；若没有，则按一般标识符来处理。2）自动机单独识别在自动机中加入识别各个保留字的状态，即把保留字和一般标识符分开来识别而不统一识别。几个问题和处理方法复合单词的识别在程序设计语言中，有一类单词是由两个或者两个以上的符号组成的，这类单词的前缀部分也可以是一个独立的单词。在处理这类单词时要特别加以注意。数的转换词法分析程序应该把字符串转换成数，如“123”应该转换成123。向前看若干个字符的处理在有些语言里，为了识别出一个单词需要向前看好几

16、个字符。几个问题和处理方法控制字符的处理1.无用的空格符和制表符要删掉；2.字符串内的空格不能删；3.换行符不能直接删除。用于错误定位注释的处理源程序中的注释没有任何语法和语义上的意义，因此在进行词法分析时可以直接将注释删除，而不必生成其TOKEN。几个问题和处理方法标识符表和常量表直接在语义信息部分存储语义信息的长度有限制时，可直接将标识符或常量本身存储于其TOKEN中的语义信息部分。设置标识符表和常量表标识符和常量没有长度限制时，构造标识符或常量表，语义信息中为其在表中的地址（节省存贮空间）。构造词法分析器步骤确定词法分析器的接口，即确定词法分析器是作

17、为语法分析的一个子程序还是作为独立一遍。确定单词分类和Token结构。构造每一类单词的描述正则表达式NFADFA。设计算法实现DFA。