编译原理第三章习题答案

编译原理电子教案第三章词法分析（lexicalanalysis）谢强计算机科学与技术学院13851481944[e-mail]上一页下一页2本章的主要内容词法分析器的设计要求状态转换图正规表达式有限自动机正规式、正规文法、有限自动机的等价性确定有限自动机的化简词法分析器的自动产生（了解）上一页下一页3本章要求知识点：词法分析程序的功能及构造方法，正规表达式与正规集，正规表达式与正规文法，状态转换图与基本符号的识别，有限自动机。深刻理解：正规表达式，有限自动机，正规文法以及三者之间的等价性；确定的有限自动机和非确定的有限自动机之间的等价性。熟练掌握：（1）对于某一正规集，写出其正规表达式，构造其非确定的有限自动机、确定的有限自动机，并将其最小化；（2）对于某一正规集，写出正规表达式，构造自动机，然后构造正规文法。上一页下一页4本章教学线索1词法分析程序的设计1.1词法分析程序的功能1.2词法分析程序作为一个独立子程序2词法分析器的设计3状态转换图4正规表达式与有限自动机5确定有限自动机的化简6词法分析程序的自动构造工具LEX简介上一页下一页51.1词法分析程序的功能词法分析的任务：从左到右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。词法分析器源程序单词符号上一页下一页6单词符号关键字、标识符、常数、（运）算符、界符；词法分析器输出单词符号的表示（单词种别，单词符号的属性值）单词种别通常用整数编码。词类编码提供给语法分析程序使用；单词自身的属性值提供给语义分析程序使用。具体的分类设计以方便语法分析程序使用为原则。单词分种策略标识符一般统规为一种；常数则宜按类型（整、实、布尔等）分种；关键字可以将全体视为一种，也可以一字一种；运算符可采用一字一种，也可将具有共性的运算符视为一种。界符一般采用一字一种。上一页下一页71.2词法分析程序作为一个独立子程序（1）语法分析程序的子程序；（2）组织成一遍扫描。（为什么？）复杂问题分解，模块化设计，使得整个编译程序的结构更简洁、清晰。由于词法分析程序相对于语法分析程序来说要简单得多，如果把词法分析和语法分析合在一起将会导致语法分析程序变得非常复杂，并且使编译程序的执行效率变得很低。上一页下一页8词法分析语法分析语义分析和中间代码生成源程序中间代码符号表管理错误的诊查处理上一页下一页9whilei＜＞jdoifi＞jtheni:＝i-jelsej:=j-i‘while’，‘i’，‘＜＞’，‘j’，‘do’，‘if’，‘i’，‘＞’，‘j’,‘then’,'i',':=’,'i',’-’,'j','else','j',':=','j','-',‘i'词法分析器〈while，——〉〈id，指向i的符号表入口的指针〉〈relational－op，NE〉〈id，指向j的符号表入口的指针〉〈do，——〉〈if，——〉〈id，指向i的符号表入口的指针〉〈id，指向j的符号表入口的指针〉例子：上一页下一页10本章教学线索1词法分析程序的设计2词法分析器的设计2.1输入、输出预处理2.2单词符号的识别（P40—41）3状态转换图4正规表达式与有限自动机5确定有限自动机的化简6词法分析程序的自动构造工具LEX简介上一页下一页112.1输入、输出预处理（1）去除掉空白符、跳格符、回车符和换行符等编辑性字符；（2）去除程序中的注释符；（3）扫描缓冲区上一页下一页122.2单词符号的识别（P40—41）超前搜索问题关键字的识别标识符的识别常数的识别算符和界符的识别上一页下一页13本章教学线索1词法分析程序的设计2词法分析器的设计3状态转换图3.1状态转换图的概念3.2构造识别一种简单语言的单词符号的转换图4正规表达式与有限自动机5确定有限自动机的化简6词法分析程序的自动构造工具LEX简介上一页下一页143.1状态转换图的概念状态转换图是一张有限方向图，在状态转换图中，结点代表状态，用圆圈表示。状态之间用箭弧连结。箭弧上的标记（字符、正规式）代表在射出结点（即箭符始结点）状态下可能出现的输入字符或字符类。一张状态转换图只包含有限个状态（即有限个结点），其中含有一个初态（用双线箭头指示）和若干个终态（用双圈表示），而且实际上至少要有一个终态，初态表示分析的开始，终态表示分析的结束。一个状态转换图可用于识别（或接受）一定的字符串。上一页下一页15012*字母其它字母或数字图A—识别标识符的转换图012*数字其它图B—识别整数的转换图数字017*其它图C—识别Fortran实型常数的转换图23456数字数字数字其它+或-E或D数字E或D··数字数字数字上一页下一页163.2构造识别一种简单语言的单词符号的转换图限制条件：（1）所有关键字都是“保留字”，用户不得使用它们作为自己定义的标识符。（2）关键字作为一类特殊的标识符来处理，不再专门设置对应的转换图，把它们预先安排在一张表格中，当转换图识别出一个标识符，就去查询这张表，确定是否为一个关键字。（3）如果关键字、标识符和常数之间没有确定的运算符或界符作间隔，则必须至少用一个空白符作间隔。上一页下一页17019105674*2**38*121311非*空白字母非字母与数字字母或数字数字数字非数字=+*...，（）其它上一页下一页18获取一个字符输入缓冲区是否为空格Y读入一个字符是否是字母是否是数字是否是=是否是+是否是*是否为字母或数字Y退回一个字符判断获取的字符串是否为保留字N返回保留字插入符号表、返回标志符类型及在符号表中的指针NYYYNNNNN读入一个字符是否为数字退回一个字符插入常数表返回整数数据类型及在常数表中的指针YN...NERROR读入一个字符是否为*返回**退回一个字符返回*NN返回=返回+源程序YYY循环和分支方法实现简单语言词法分析器的程序流程示意图Y上一页下一页19本章教学线索1词法分析程序的设计2词法分析器的设计3状态转换图4正规表达式与有限自动机4.1正规式与正规集4.2确定有限自动机（DFA）4.3非确定有限自动机NFA4.4DFAM和NFAM的等价性4.5正规文法与有限自动机的等价性4.6正规式与有限自动机的等价性5确定有限自动机的化简6词法分析程序的自动构造工具LEX简介上一页下一页204.1正规式与正规集4.1.1正规式与正规集的定义（概念）（1）ε、Φ都是∑上的正规式，它们所表示的正规集分别为{ε}和Φ；（2）任何a∈∑，a是∑上的一个正规式，它所表示的正规集为{a}；（3）如果U、V都是∑上的正规式，它们所表示的正规集分别记为L（U）和L（V），那么，（U|V）、（U*V）和（U）*也是正规式，它们所表示的正规集分别为L（U）∪L（V）、L（U）L（V）和（L（U））*；仅由有限次使用上述步骤而得到的表达式才是∑上的正规式；仅由这些正规式所表示的字集才是∑上的正规集。上一页下一页21例子：令∑={a，b}，下面是∑上的正规式和相应的正规集正规式正规集ba*∑上所有以b为首后跟任意多个a的字a(a|b)*∑上所有以a为首的字（a|b）*(aa|bb)(a|b)*∑上所有含有两个相继的a或两个相继的b的字上一页下一页224.1.2正规式的数学运算交换律：U|V=V|U；结合律：U|（V|W）=（U|V）|W、U（VM）=（UV）W；分配律：U（V|W）=UV|UW（V|W）U=VU|WUε连接：εU=Uε=U上一页下一页23另外一种定义方法：定义正规表达式（regularexpression）是以下的一种：基本（basic）正规表达式由一个单字符a（其中a在字母表∑中），以及元字符ε或元字符Φ组成。在第1种情况下，L(a)={a}；在第2种情况下，L(ε)={ε}；在第3种情况下，L(Φ)={}。r|s格式的表达式：其中r和s均是正规式。在这种情况下，L（r|s）=L（r）∪L（s）。rs格式的表达式：其中r和s是正规式。在这种情况下，L（rs）=L(r)L（s）。r*格式的表达式：其中r是正规表达式。在这种情况下，L（r*）=L（r）*。（r）格式的表达式：其中r是正规式。在这种情况下，L（（r））=L（r），因此，括号并不改变语言，它们只调整运算的优先权。上一页下一页24需要注意：｜的优先权最低，连结次之，*则最高。另外还注意到在这个定义中，5个符号|、*、*、（和）都有了元字符的含义。正规式的连接一般不满足交换律上一页下一页254.2确定有限自动机（DFA）4.2.1确定有限自动机的定义一个确定有限自动机（DFA）M是一个五元式：M=（S，∑，δ，s0，F），其中：S是一个有限集，它的每个元素称为一个状态；∑是一个有穷字母表，它的每个元素称为一个输入字符；δ是一个从Sx∑至S的单值部分映射。δ（s，a）=s′，意味着：当现行状态为s、输入为字符a时，将状态转换到下一个状态s′。我们称s′为s的一个后继状态。s0∈S，是唯一的初态。FS，是一个终态集（可空）。上一页下一页264.2.2DFA的矩阵表示及状态转换图表示行表示状态列表示输入字符矩阵元素表示δ（s，a）的值。这个矩阵称为状态转换矩阵。例子：M=（{0，1，2，3}，{a，b}，δ，0，{3}）其中δ为：δ(0，a)=1δ(0，b)=2δ(1，a)=3δ(1，b)=2δ(2，a)=1δ(2，b)=3δ(3，a)=3δ(3，b)=3上一页下一页27对应的状态转换矩阵：状态ab012132213333一个DFA也可以表示成一张（确定的）状态转换图：δ(0，a)=1δ(0，b)=2δ(1，a)=3δ(1，b)=2δ(2，a)=1δ(2，b)=3δ(3，a)=3δ(3，b)=31023ababa，bab上一页下一页28确定有限自动机（DFA）的三种表示形式1）状态转换函数2）状态转换矩阵3）状态转换图开始状态一般状态终态•状态转换图节点的三种形式上一页下一页294.2.3有限自动机DFAM接受的语言从状态转换函数来看：如果对所有α∈Σ*，以下述方式递归扩张δ的定义：δ（s，ε）＝s，δ(s，aα）＝δ（δ（s，a），α）（ａ∈Σ，s∈S），则有Ｌ（Ｍ）＝｛α｜α∈Σ*，若存在s∈Ｆ，使δ（s0，α）＝s｝对上例的DFAM和w=baa，δ（0，baa）=δ（2，aa）=δ(1，a）=3（注意：其中0代表0态，1表示1态，2表示2态，3表示3态）上一页下一页30从状态转换图来看：对于Σ*上的任何字α，如果存在一条从初态结点到某一终态结点的通路，且这条通路上所有弧的标记符连接成的字等于α，则称α可为DFAM所识别（读出或接受），如果M的初态结点同时又是终态结点，则空字ε可为DFAM所识别。DFAM所能识别的字的全体记为L(M)。上一页下一页314.2.4DFA的程序模拟DFAM=（K，Σ，f，S，Z）的行为的模拟程序K=S；c=getchar;whileceofdo{K=f(K,c);c=getchar;};ifKisinZthenreturn(‘yes’)Elsereturn(‘no’)上一页下一页324.3非确定有限自动机NFA一个非确定有限自动机NFAM是一个五元式：M=(S，Σ，δ，S0，F)其中：S是一个有限集，它的每个元素称为一个状态；∑是一个有穷字母表，它的每个元素称为一个输入字符；δ是一个从Sx∑*至S的子集的映射，即δ：Sx∑*→2s（S集合的幂集/S的所有子集的集合）S0S，是一个非空初态集。FS,是一个终态集（可空）。上一页下一页33对于∑*中的任何一个字α，若存在一条从某一初态结点到某一终态结点的通路，且这条通路上所有弧的标记字依序连接成的字（忽略那些标记为ε的弧）等于α，则称α可为NFAM所识别（读出或接受）。若M的某些结点既是初态结点又是终态结点，或者存在一条从初态结点到某一终态结点的ε通路，那么，空字ε可为M所接受。例子：识别所有含有相继两个a或相继两