编译原理与实现03第3章词法分析.ppt

《编译原理与实现03第3章词法分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章词法分析词法分析程序又称词法分析器或扫描器，是编译过程的第一步，是下一步进行语法分析的基础。3.1词法分析的功能3.2程序语言的单词符号种类及词法分析输出3.3正则文法及状态图3.4词法分析程序的设计与实现3.1词法分析的功能扫描源程序字符流，按照源语言的词法规则识别出各类单词符号，并产生用于语法分析的符号序列，即将字符串源程序转换成符号串源程序。程序设计语言的保留字或关键字、标识符、常数、各种运算符等都是单词符号的例子。词法分析程序要做的工作是：从源程序的第一个字符开始，顺序读字符，一次读一个，根据所读进的字符识别各类单词，同时去掉源程序中的空

2、白和注释。词法分析检查的错误主要是挑出源程序中出现的非法符号。所谓非法符号是指不是程序设计语言中允许出现的符号，就像自然语句中的错字。词法分析与语法分析之间的关系通常有两种形式：1.词法分析作为独立的一遍词法分析可作为单独一遍来实现。这种词法分析的输出存入一个中间文件供语法分析使用。这样通过词法分析，就可以将字符串源程序转换成符号串源程序，如图3.1。字符串源程序词法分析符号串源程序图3.1词法分析单独作为一遍3.1词法分析的功能2.词法分析程序作为语法分析程序的子程序有些编译程序将词法分析和语法分析安排在同一遍中，此时词法分析作为语法分析程序的一个子

3、程序。每当语法分析需要一个新的符号时，就调用词法分析子程序，词法分析子程序从字符串源程序中识别出一个具有独立意义的单词，将其符号返给语法分析。这种方法避免了中间文件，省去了送取符号工作，有利于提高编译程序的效率，如图3.2。字符串源程序词法分析器语法分析器图3.2词法分析作为语法分析子程序取符号送符号3.2程序语言的单词符号种类及词法分析输出词法分析的功能是为识别出的具有独立意义的单词，而输出的就是这些单词的符号。在程序设计语言中，单词符号是最基本的语法单位，具有确定的语法意义。通常程序语言的单词符号有：保留字：如if、while、for等等。这些保留

4、字在程序语言中具有固定的意义，是编译程序识别各类语法成分的依据，用户不能用它们作标识符。标识符：由用户定义，用来表示各种名字，如变量名、函数名、数组名等等。无符号数：如125、0.788、15.2分界符：如+、-、*、/、；、（、）等单分界符，还有>=、<=、!=、++等双分界符.词法分析的输出常采用二元式，如图3.3所示。单词类别单词值图3.3词法分析程序的输出形式3.2程序语言的单词符号种类及词法分析输出单词类别通常用一个整数类码或单词记号表示，单词记号比整数码含义明确。例如，保留字FOR，可直接用同样的字符串FOR作为单词记号来表示，而如果用整数

5、类码，含义就不直观。用汇编编写词法分析程序，单词类别常用整数表示，因为用单词记号处理起来比较麻烦。而如果用高级语言编写词法分析程序，那么采用单词记号则更自然些，因为高级语言提供了字符串处理函数，处理助记符号不再烦琐。一个语言的单词类别如何分类、分成几类、怎样编码，主要取决于技术处理上的方便。标识符一般归为一类，常数则按类型（整数、实数等）分类。保留字即可将全体定为一类，也可一字一类。分界符可单独作为一类，也可采用一符一类的分法。采用一字一类或采用一符一类的分法实现处理起来更方便一些。因为，如果一个类别只含一个单词符号，那么，对于这个单词符号，类别编码就

6、完全代表它自身的值，词法分析就不必输出其值了。3.3正则文法及状态图程序设计语言的单词符号可用3型文法来描述，3型文法也称为正则文法。对于正则文法所描述的语言可以用一种有穷自动机来识别。我们的目的是实现词法分析程序，所以为了简化问题，我们直接介绍这种自动机的非形式表示，即状态图。3.3.1状态图所谓“状态图”就是一张有穷的有向图。图中的结点代表状态，用圆圈表示，状态间用有向弧线连接，连接弧上标记有符号，表示在弧线射出端的状态下，读入弧线上标记的符号可转换到弧线指向的状态。状态图只有有穷个状态，其中有一个是开始状态，至少有一个状态是结束状态，结束状态常用

7、双圈表示。3.3.1状态图正则文法形式为：U→a或U∷=Wa，其中：U，W∈Vn（非终结符号集），a∈Vt（终结符号集）正则文法的状态图画法如下：文法中的每个非终结符号对应状态图中的一个结点，即图中的每个结点代表一个非终结符号。增设一个结点代表开始状态S，而文法中的开始符号对应的结点为终结状态对于文法中的每一条形如U→a的规则，画一条从结点S指向结点U的弧线，并在弧上标记a。对于文法中每一条形如U∷=Wa的规则，画一条从结点W指向结点U的弧线，并在弧上标记a。3.3.1状态图例3.1，设有正则文法G[Z]：Z→U0

8、V1U→Z1

9、1V→Z0

10、0画出该文

11、法对应的状态图。解：根据状态图的画法，首先确定状态图的结点。文法中有三个非终结符号Z、U、V，