《编译原理 第三章词法分析.doc》由会员分享，可在线阅读，更多相关《编译原理 第三章词法分析.doc（11页珍藏版）》请在金锄头文库上搜索。
1、第三章 词法分析词法分析是编译的第一个阶段，它的主要任务是从左至右逐个字符地对源程序进行扫描，产生一个个单词序列，用以语法分析。执行词法分析的程序称为词法分析程序或扫描程序。本章我们将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。本章重点：正规式、有限自动机（DFA、NFA）、NFA到DFA的转换、DFA的最小化。第一节 词法分析程序的设计一、词法分析程序的输出词法分析程序的功能是读入源程序，输出单词符号，单词符号是一个程序设计语言的基本语法符号。程序设计语言的单词符号一般可分为下列5种：1、基本字，也称关键字，如PASCAL语言中的begin, end,
2、if, while和var等。2、标识符，用来表示各种名字，如常量名、变量名和过程名等。3、常数，各种类型的常数，如25,3.1415,TRUE和“ABC”等。4、运算符，如+, , =等。5、界符，如逗点，分号，括号等。词法分析程序所输出的单词符号常常采用以下二元式表示：（单词种别，单词自身的值）。单词的种别是语法分析需要的信息，而单词自身的值则是编译其它阶段需要的信息。比如在PASCAL的语句const i=25, yes=1;中的单词25和1的种别都是常数，常数的值25和1，对于代码生成来说，是必不可少的。有时，对某些单词来说，不仅仅需要它的值，还需要其它一些信息以便编译的进行。比如，对
3、于标识符来说，还需要记载它的类别、层次还有其它属性，如果这些属性统统收集在符号表中，那么可以将单词的二元式表示设计成如下形式（标识符，指向该标识符所在符号表中位置的指针），如上述语句中的单词i和yes的表示为：（标识符，指向i的表项的指针）（标识符，指向yes的表项的指针）单词的种别可以用整数编码表示，假如标识符编码为1，常数为2，保留字为3，运算符为4，界符为5，程序段if i=5 then x ：= y；在经词法分析器扫描后输出的单词符号和它们的表示如下： 保留字if (3，if) 标识符i（1，指向i的符号表入口） 等号 =（4，=） 常数5（2，5） 保留字then（3，then） 标
4、识符x（1，指向x的符号表入口） 赋值号 ：=（4：=） 标识符y（1，指向y的符号表入口） 分号；（5，；）第二节 单词的描述工具程序设计语言中的单词是基本语法符号。单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，可以建立分析技术，进而可以建立词法分析程序的自动构造方法。一、正规文法多数程序设计语言的单词的语法都能用正规文法或3型方法来描述。回顾一下3型方法G =（VN，VT，S，P）的特征，即P中的每一条规则都有下述形式：AaB或Aa其中A，BVN，aV。正规文法所描述的是V上的正规集。程序设计语言中的几类单词可用下述规则描述：1|11| d |1 |d d | d + |
5、| | / | | =，| ；|（ | ）| 其中1表示a z中的任何一英文字母，d表示0 9中的任一数字。二、 正规式正规式也称正则表达式，也是表示正规集的工具。也是我们用以描述单词符号的方便工具。下面是正规式和它所表示的正规集的递归定义。设字母表为 ，辅助字母表= ，, |, (,) 。1、和都是上的正规式，它们所表示的正规集分别为和；2、任何a ，a是上的一个正规式，它所表示的正规集为a；3、假定e1和e2都是上的正规式，它们所表示的正规集分别为L (e1),和L (e2)，那么，(e1), e1 |e2, e1e2和e1也都是正规式，它们所表示的正规集为L (e1), L (e1) U
6、L (e2), L (e1) L (e2)和 (L(e1) )。4、仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集。例 1 令 =a, b, 上的正规式和相应的正规集的例子有： 正规式正规集 aa a | ba , b abab (a | b) (a | b)aa, ab, ba, bb a, a, aa,任意个a的串 (a | b), a, b, aa, ab所有a, b组成的串 (a | b) (aa | bb) (a | b) 上所有含有两个相继的a或两个相继的b组成的串。三、 正规文法到正规式一个正规语言可以由正规文法定义，也可以由正规式
7、定义，对任意一个正规文法，存在一个定义同一个语言的正规式；反之，对每个正规式，存在一个生成同一个语言的正规文法，有些正规语言很容易用文法定义，有些语言更容易用正规式定义，本节介绍两者间的转换，从结构上建立它们的等价性。1、将上的一个正规式转换成文法G=（VN，VT，S，P）。令其中的VT= ，确定产生式和VN的元素用如下办法。对任何正规式r，选择一个非终结符S生成产生式Sr，并将S定为G的识别符号。若x和y都是正规式，对形如Axy的产生式，重写成：AxB, By两产生式，其中B是新选择的非终结符，即BVN。对已转换的文法中的形如Axy的产生式，重写为：AxBAyBxBBy 其中B为一新非终结符
8、，对形如Ax | y的产生式，重写为：Ax Ay不断利用上述规则做变换，直到每个产生式最多含有一个终结符为止。例2 将R = a (a | d )转换成相应的正规文法，令S是文法的开始符号，首先形成Sa (a | d),然后形成SaA和A (a | d )，再重写第二条产生式形成SaA,A (a | d )B,A,B (a|d)B和B进而变换为SaA,BaB,AaB,BdBAdB,BA2、将正规文法转换成正规式。基本上是上述过程的逆过程，最后只剩下一个开始符号定义的产生式，并且该产生式的右部不含非终结符。其转换规则列于表4.1表4.1 正规文法到正规式的转换规则文法产生式正规式规则1规则2规则
9、3AxB, ByAxA | yAx AyAxyAx yAx | y例3 文法GSSaASaAaAAdAAaAd先有：S=aA|aA=(aA|dA)|(a|d)再将A的正规式变换为A=(a|d) A|(a|d)，据表中规则2变换为：A=(a|d)*(a|d)，再将A右端代入S的正规式得：S=a(a|d) *(a|d)|a再利用正规式的代数变换可依次得到S=a(a|d) *(a|d)|a 即a(a|d) *为所求。第三节 有穷自动机有穷自动机（也称有限自动机）作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造
10、寻找特殊的方法和工具。有穷自动机分为两类：确定的有穷自动机（Deterministic Finite Automata）和不确定的有穷自动机（Nondeterministic Finite Automata），下面我们分别给出确定有穷自动机和不确定的有穷自动机的定义，有关概念及不确定的有穷自动机的确定化，确定的有穷自动机的化简等算法。一、 确定的有穷自动机（DFA）一个确定的有穷自动机（DFA）M是一个五元组：M =（K, , f, S, Z）其中1、K是一个有穷集，它的每个元素称为一个状态；2、是一个有穷字母表，它的每个元素称为一个输入字符，所以也称为输入符号字母表；3、f是转换函数，是在k
11、 K上的映像，即，如f (ki, a ) = kj (kik, kjk )就意味着，当前状态为Ki，输入字符为a时，将转换到一状态kj，我们把kj称作ki的一个后继状态；4、SK是唯一的一个初态；5、ZK，是一个终态集，终态也称可接受状态或结束状态。例 3 DFA M=（S,U,V,Q,a, b,f, S,Q）其中f定义为：f (S, a) = Uf ( V, a ) = Uf (S, b) = Vf ( V, b ) = Qf (U, a) = Qf ( Q, a ) = Qf (U, b) =Vf ( Q, b) = Q一个DFA可以表示成一个状态图（或称状态转换图）。假定DFA有m个状态
12、，n个输入字符，那么这个状态图含有m个结点，每个结点最多有n个弧射出，整个图含有唯一一个初态结点和若干个终态结点，初态结点冠以“”或标以“”，终态结点用双圈表示或标以“+”，若f (ki, a) = kj，则从状态结点ki到状态结点kj，画标记为a的弧；例3中的DFA的状态图表如图3-3-1。 a.baaa b a b b图3-3-1 状态图表示UQFQQQSV a.baaa b a b b图3-3-1 状态图表示UQQQQSV 字符状态abSUV0UQV0VUQ0QQQ1图3-3-2 矩阵表示 一个DFA还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字
13、符列下的新状态，即k行a列为f (k, a)的值。用“”标明初态；否则第一行即是初态，相应终态行在表的右端标以1，非终态标以0。例3中的DFA的矩阵表示如图3-3-2对于中的任何字符串t,若存在一条从初态结到某一终态结的道路，且这条路上所有弧的标记符连接成的字符串等于t,则称t可为DFA M所接受，若M的初态结同时又是终态结，则空字可为M所识别（接受）。DFA M所能接受的字符串的全体（字的全体）记为L（M）。结论： 上一个符号串集V*是正规的，当且仅当存在一个上的确定有穷自动机M，使得V=L(M)。DFA的确定性表现在转换函数f：KK是一个单值函数，也就是说，对任何状态kK，和输入符号a，f（k，a）唯一地确定了下一个状态。从状态转换图来看，若字母表含有n个输入字符，那末任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。二、不确定的有穷自动机（NFA）一个不确定的有穷自动机（NFA）M是一个五元组，M=
