[精品]编译原理复习材料2

《[精品]编译原理复习材料2》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第三章词法分析1、词法分析的任务编译原理是在单-词的级别上对源程序进行分析和翻译的，而从源程序屮获取单词的工作是曲词法分析程序來完成的。词法分析的任务是从左至右逐个字符地对源程序进行扫描，产生一个个单词符号，把作为字符吊的源程序改造成为单词符号串的屮间程序。。因此，词法分析是编译的基础。执行词法分析的程序称为词法分析器，也叫扫描器。词法分析的功能是输入源程序，输出单词符号。单词符号是一・个程序语言的基本语法符号。一•般冇5类：（1）关键字，是程序语言定义的具冇固定意义的标识符，也叫保留字或基本字

2、，如begin,repeat,while等；（2）标识符，用來表示各种名字，如变量名、数组名和过程名；（3）常数，常数的类型有整型、实型、布尔型、字符型等;（4）运算符,如+,・，*,/等;（5）界符,如逗号、分号、括号、/*,/*等。词法分析程序的输出格式一般为：单词类别单词符号的属性值词法分析程序不仅给出单词符号的值，还同时给出单词符号的类别，这有利于编译程序的后继工作——词法分析的进行。2、状态转换图状态转换图是一张有限方向图，大多数程序语言的单词符号都可以用转换图予以识别。状态转换图由结

3、点和箭弧组成，结点代表状态，用圆圈表示。状态之间用箭弧连结，箭弧上的标记（字符）代表射出结点（即箭弧始结点）状态下可能出现的输入字符或字符类。用标记为X的箭弧连接状态a和b表示：在状态a下，若输入字符为X,则读进X,并转换到状态b。一张转换图只包含冇限个状态（即有限个结点），其中有一个被认为是初态，并且至少耍有一个终态（用双圈来表示）。状态转换图可用于识别（或接受）一定的字符串。数字识別整常数的状态转换图3、正规文法、正规式和正规集正规文法是即Chomsky3型文法，是描述正规集的文法，可用于描

4、述程序设计语言的语法部分。止规集是止规文法产生的语言。止规集是集合，可有穷也可无穷，可通过正规式来形象化表示。正规式和正规集的递归定义：对给定的字母表s(1)8和0都是工上的正规式，它们所表示的正规集为｛£｝和0；(2)任何昵工,a是》上的正规式，它所表示的正规集为｛a｝;(3)假定U和V都是Z上的正规式，它们所表示的正规集为L(U)和L(V),那么(U

5、V)、(U・V)秋U)*也都是正规式，它们所表示的正规集分别为为L(U)uL(V)、L(U)L(V)(连接积)和(L(U))*(闭包)。仅由冇

6、限次使用上述三步骤而定义的表达式才是S上的正规式，仅由这些正规式表示的字集才是z上的正规集。若两个正规式所表示的正规集相同，则认为两者是等价的。两个等价的正规式U和V记为U=Vo例如:b(ab)*=(ba)*bo令U、V和W均为正规式，则有：定理1：(1)U

7、V=V

8、U交换律(2)U

9、(V

10、W)=(U

11、V)

12、W;U(VW)=(UV)W结合律(3)U(V

13、W)=UV

14、UW;(V

15、W)U=VU

16、WU分配律(4)Ue=eU=U(5)(U*)*=U*(6)U*=U++wU'=UU+=U'U(7)(U+V

17、)*=(U*+V*>(U*V*)*定理2：若U、V、W是字母表工上的正规式，JleeL(W),则U=V

18、UW当且仅当u=vw[U=V

19、WU当但仅当u=w*v正规文法转换成相应的正规式，其步骤为：(1)由正规文法G的各个产生式写出对应的正规方程式，得到联立方程组；(2)把方程组中的非终结符当做变元；(3)求此止规式方程组的解，得到关于开始符号S的解，S=W,WGVt*,W就是所求的正规式。例如：已知正规文法G1的产生式，求出它所定义的正规式。产生式为：S—aS

20、aBB->bB

21、bAAtcA

22、c解：

23、(1fS=aS

24、aB-

25、bA.A=cA

26、c(2)根据定理2出S=aS

27、aB得S=a*aB=a*B同理由B=bB

28、bA得B=b+A由A=cA

29、c得A=c代入得B=b1cS=aVc4©故正规式为S=aVc+o4、有限自动机(FA)有限口动机是一种识别装置，它能准确地识别止规集，它为词法分析程序的构造捉供了方法和工具。有限自动机具有离散输入系统的数学模型，它具有有限数目的内部状态，系统可以根据当前所处的状态和面临的输入字符决定系统的后继行为，其当前状态概括了过去输入处理的信息。有限自动机的

30、模型：(1)输入带状态分为初始状态、中间状态和终止状态。终止状态可以为若干个，但是初始状态一般只有一个。读头全部读完，且此时状态为终止状态，则说明此输入串正确。(3)(2)状态：非终态血此时状态不是终止状态，则说明此输入串错误。输入带输入带读头全部读完，5、确定有限自动机(DFA)-个确定的状态转换图可以用一个确定的有限自动机来表示，确定的有限自动机(DFA)定义如下:一个确定的有限自动机M是一个五元式M=(S,Z,f,So,F)其中:(1)S是一个有限集，它的每个元素称为一个状态；(2)Z是一