第7部分习题答案

11.15．若L是正规语言，证明下面21L语言也是正规语言。21L语言的定义是21L={x|y.xyL&|x|=|y|}答案因为L是正规语言，那么存在一个DFAM=(S,,,s,F)，它接受语言L。接受语言21L的DFAM=(S,,,s,F)可如下构造。1．S的每个状态是一个二元组s1,S1，其中s1S，S1S。2．(s1,S1,a)=s2,S2，其中s2=(s1,a)S2={s2|s1S1b(s2,b)=s1}3．s=s,F4．F={s1,S1|s1S1}可以证明这是接受语言21L的DFA，因此21L是正规语言（证明比较复杂，我们在此略去）。分析这个题目超出的编译课程的范围。但是如果理解了这儿的解答，那就掌握了证明正规语言的一种很重要的技巧。下面我们说明，为什么这样定义DFAM。长度为n的串w，若它是语言L的某个句子的前缀，那么从M的开始状态s，经n步转换，到达某个状态sn。该串是否属于21L，取决于是否存在从sn开始到某个接受状态的路径，其长度为n。怎样判断是否存在这样的到某个接受状态的路径呢？我们可以在M的状态转换图上按下面的步骤办。1．首先找出从任意接受状态逆向任意走一步能到达的所有状态，把这个状态集合称做R1。2．再找出从R1的任意状态逆向任意走一步能到达的所有状态，把这个状态集合称做R2。3．这样逆向操作n步后，得到状态集合Rn。4．若sn在Rn中，那么串w属于21L，否则不是。可以看出，上面定义的M是在M上同时跟踪从开始状态出发的正向状态转换和从接受状态集合出发的逆向搜索所有状态。我们再看一下M的定义。1．S的每个状态之所以是一个二元组s1,S1，是因为需要用s1来表示正向的状态转换，用S1来表示逆向搜索。2．再看状态转换的定义(s1,S1,a)=s2,S2，其中s2=(s1,a)表示了M上正向一步转换到达的状态，S2={s2|s1S1b(s2,b)=s1}表示了M上逆向一步搜索到达的状态集合。3．开始状态s=s,F表示在M上的跟踪是从开始状态和接受状态集合这两端启动。4．接受状态F={s1,S1|s1S1}表达的意思是，若在M上从开始状态经n转换到s1，那么一定存在长度为n的从s1到某个接受状态的路径。下面我们以1.4题的正规语言为例。不难理解，该语言的21语言应该是字母表={0,1}2上的所有串。我们用上面的方法来构造接受它的DFA。该DFA的开始状态s0=0,{0}。状态s0:0,{0}(s0,0)=2,{1,2}(s0,1)=1,{1,2}状态s1:2,{1,2}(s1,0)=0,{0,3}(s1,1)=3,{0,3}状态s2:1,{1,2}(s2,0)=3,{0,3}(s2,1)=0,{0,3}状态s3:0,{0,3}(s3,0)=2,{1,2}(s3,1)=1,{1,2}状态s4:3,{0,3}(s4,0)=1,{1,2}(s4,1)=2,{1,2}从s0到s4的这五个状态，每个状态的第一元都在第二元的集合中，因此这五个状态都是接受状态。这个DFA的图形表示见图1.17（图中用状态0,1,2,3和4代替了这里对应的状态）。显然，它能接受字母表={0,1}上所有的串，化简这个DFA可以得到只有一个状态的DFA。1.16保留字、关键字和标准标识符之间的区别是什么？答案保留字是语言预先确定了含义的单词，程序员不可以对这样的单词重新声明它的含义。如PASCAL语言的type和procedure等。词法分析器读到一个符合标识符拼写的单词时，都要和保留字进行比较，以确定该单词是标识符呢还是哪个保留字。很多语言的关键字是保留的，因此和上面的保留字没有区别，如C语言和Java语言。但是FORTRAN语言的关键字不保留，如IF，当它作为语句的第一个单词时，很可能是关键字，但也不排除是用户定义的标识符。这给词法分析带来很大困难，因为识别单词和该单词所处的上下文有关。现在的语言都不会象FORTRAN这样来定义关键字。标准标识符是预先确定了含义的单词，但是程序员可以重新声明它的含义。在这个声明的作用域内，程序员声明的含义起作用，而预先确定的含义消失，如PASCAL语言的integer和true等。词法分析器对标准标识符没有什么特别的处理，由符号表管理来解决这件事。1.17词法分析器能查出源程序中什么样的错误，举例说明。答案词法分析器对源程序采取非常局部的观点，因此象C语言的语句fi(a==f(x))…中，词法分析器把fi当作一个普通的标识符交给编译的后续阶段，而不会把它看成是关键字if的拼写错。PASCAL语言要求作为实型常量的小数点后面必须有数字，如果程序中出现小数点后面没有数字情况，它由词法分析器报错。1.18一个C语言编译器编译下面的函数时，报告parseerrorbefore‘else’。这是因为else的前面少了一个分号。但是如果第一个注释/*thenpart*/误写成111110000start432001图1.17接受={0,1}上所有串的一个DFA3/*thenpart那么该编译器发现不了遗漏分号的错误。这是为什么？longgcd(p,q)longp,q;{if(p%q==0)/*thenpart*/returnqelse/*elsepart*/returngcd(q,p%q);}答案此时编译器认为/*thenpartreturnqelse/*elsepart*/是程序的注释，因此它不可能再发现else前面的语法错误。分析这是注释用配对括号表示时的一个问题。注释是在词法分析时忽略的，而词法分析器对程序采取非常局部的观点。当进入第一个注释后，词法分析器忽略输入符号，一直到出现注释的右括号为止，由于第一个注释缺少右括号，所以词法分析器在读到第二个注释的右括号时，才认为第一个注释处理结束。为克服这个问题，后来的语言一般都不用配对括号来表示注释。例如Ada语言的注释始于双连字符（--），随行的结束而终止。如果用Ada语言的注释格式，那么上面函数应写成longgcd(p,q)longp,q;{if(p%q==0)--thenpartreturnqelse--elsepartreturngcd(q,p%q);}