第三章-词法分析及词法分析程序-课后答案【khdaw-lxywyl】

    课后答案网，用心为你服务！  大学答案---中学答案---考研答案---考试答案 最全最多的课后习题参考答案，尽在课后答案网（）！Khdaw团队一直秉承用心为大家服务的宗旨，以关注学生的学习生活为出发点，旨在为广大学生朋友的自主学习提供一个分享和交流的平台。 爱校园（）课后答案网（）淘答案（） 第三章词法分析及词法分析程序1试用某种高级语言编写一个FORTRAN源程序的预处理子程序，其功能是：每调用它一次，即把源程序中的一个完整语句送入扫描缓冲区。要求删去语句中的注释行；删去续行标记字符，把语句中的各行连接起来，并在语句的末端加上语句结束符。此外，还要求此程序具有组织源程序列表输出的功能。2画出用来识别如下三个关键字的状态转移图。STEPSTRINGSWITCH3假定有一个猎人带着一只狼、一头山羊和一棵白菜来到一条河的左岸，拟摆渡过河，而岸边只有一条小船，其大小仅能装载人和其余三件东西中的一件，也就是说，每一次猎人只能将随行者中的一件带到彼岸。若猎人将狼和山羊留在同一岸上而无人照管，那么，狼就会将羊吃掉；如果猎人把山羊和白菜留在同一岸，山羊也会把白菜吃掉。现在，请你用状态转换图作为工具，描述猎人可能采取的种种摆渡方案，并从中找出可将上述三件东西安全地带到右岸的方案来。4设已给文法G=(VN,VT,P,S)，其中，P仅含形如A→αBA→αα∈V*T，B∈VN的产生式，试证明：由此种文法所产生的语言是一正规语言。5试证明：任何有限个符号串所组成的集合L={x1,x3,…,xn}xi∈Σ+都是3型语言。6试构造一右线性文法，使得它与如下的文法等价S→ABA→UTU→a|aUT→b|bTB→c|cB并根据所得的右线性文法，构造出相应的状态转换图。7对于如题图37所示的状态转换图(1)写出相应的右线性文法；(2)指出它接受的昀短输入串；(3)任意列出它接受的另外四个输入串；(4)任意列出它拒绝接受的四个输入串。8对于有限自动机M=(K,Σ,f,S0,Z)其中，K={S0,S1,S2,S3,S4,S5},Σ={a,b},Z={S1,S4,S5}。f由如下的状态转移矩阵给出：[]a[]bS0[]S2[]S1S1[]S3[]S1S2[]S0[]S4S3[]S0[]S0S4[]S5[]S4S5[]S4[]S0试找出一个长度昀小的输入串，使得：(1)在识别此输入串的过程中，每一状态至少经历一次；(2)每一状态转换至少经历一次。9对于下列的状态转换矩阵：[]a[]bS[]A[]SA[]A[]BB[]B[]B(i)初态：S终态：B[][][]a[]bS[]A[]BA[]B[]AB[]B[]B(ii)初态：S终态：A[]a[]bS[]A[]BA[]C[]AB[]B[]CC[]C[]C(iii)初态：S终态：A,C[][][]a[]bS[]A[]SA[]C[]BB[]B[]CC[]C[]C(iv)初态：S终态：C(1)分别画出相应的状态转换图；(2)写出相应的3型文法；(3)用自然语言分别描述它们所识别的输入串的特征。10对于下面所给的文法：G1=({S,A,B,C,D},{a,b,c,d},P1,S)P1由如下产生式组成：S→aAS→BA→abSA→bBB→bB→cCC→DD→dD→bB以及G2=({S,A,B,C,D},{a,b,c,d},P2,S)P2由如下产生式组成：S→AaS→BA→CcA→BbB→BbB→aC→DC→BabD→d(1)试分别对G1和G2构造相应的状态转换图(提示：对于右线性文法，可将形如C→D的产生式视为C→εD；而对左线性文法，则可将它视为C→Dε)。(2)对于G1，构造一等价的左线性文法G1′；对于G2构造一等价的右线性文法G2′。(3)对于G1和G1′，分别给出如下符号串的推导序列：abbaababbbcdcbb对于G2和G2′分别给出如下符号串的推导序列：aabaaabcadca(4)试给出若干个不能由G1或G2产生的符号串，并验证它们同样不能用G1′和G2′产生。11分别构造将左线性文法转换为右线性文法以及将右线性文法转换为左线性文法的算法。12将如题图312所示的NFA确定化和昀小化。13将如题图313所示的具有ε动作的NFA确定化。14将如题图314所示的有限自动机昀小化。15试用一种高级语言分别写出将NFA确定化以及将DFA昀小化的算法。16构造一产生FORTRAN语言COMMON语句的3型文法(假定分别用λ和μ代表标识符和整常数，它们都是终结符号，且假定数组的维数不加限定)，构造相应的DFA，并写出描述COMMON语句的正规式。17设r,s等为任意的正规式，试证明下列的关系式成立：(1)r*=(ε|r)*=ε|rr*=(r*)*(2)(rs)*r=r(sr)*(3)(r|s)*=(r*s*)*=(r*|s*)*18对于解习题36所得的文法，试用正规式描述它所产生的语言。[]a[]bS0[]S1[]S5S1[]S2[]S7S2[]S3[]S5S3[]S5[]S7S4[]S5[]S5S5[]S3[]S1S6[]S3[]S0S7[]S0[]S1S8[]S3[]S8(1)初态：S0终态：S1，S2，S6，S7[][][]a[]bS0[]S5[]S2S1[]S6[]S2S2[]S0[]S4S3[]S3[]S5S4[]S6[]S2S5[]S3[]S0S6[]S3[]S1(2)初态：S0终态：S4,S5,S6题图31419对于习题310所给的文法G1和G2，试分别用正规式描述它们所产生的语言。20设有如下的文法G［〈标号说明〉］：〈标号说明〉→′LABEL′〈标号表〉〈标号表〉→d〈标号段〉〈标号段〉→d〈标号段〉|,〈标号〉|；〈标号〉→d〈标号段〉其中′LABEL′,′d′,′,′,′;′等为终结符号。(1)试求出描述此文法所产生语言的正规式；(2)构造识别此语言的具有昀少状态的DFA。21求出描述习题37所给有限自动机所识别语言的正规式。22分别构造识别如下正规语言的DFA：(1)((0*|1)(1*0))*(2)(b|a(aa*b)*b)*(3)a(abab*|a(bab)*a)*b(4)(b|aa|ac|aaa|aac)*(5)a(a|b)*b(a|b)*a(a|b)*b(a|b)*23试设计一个识别器，它识别由下列英语单词：ONE,TWO,THREE,…，NINE，TEN，ELEVEN，TWELVE，THIRTEEN，…，NINETEEN，TWENTY，THIRTY，FORTY，…，NINETY，HUNDRED所表示的从1到999间的任何整数(各单词间用空格分隔，如THREEHUNDREDFIFTYSIX)，并将它们翻译为相应的阿拉伯数字(如356)作为输出。24设有辅助定义式D0=a|bD1=D0D0D2=D1D1…Dn=Dn-1Dn-1试回答如下问题：(1)由Dn所表述的正规集是什么?(2)如果将Dn中所出现的Dn-1用前面已定义的辅助定义式反复进行替换，则可昀终将Dn化为Σ={a,b}上的正规式，此正规式有多长?(3)用来识别Dn的DFA至多需要几个状态?25试将LEX中的“动作子程序”Ai的功能加以扩充，使之可用来生成文本编辑程序。26指出下列LEX正规式所匹配的字符串：(1){［^{］*}(2)^［^a-z］［A-Z］［0-9］$(3)［^0-9］|［＼r＼n］(4)＼′(［^′＼n］|＼′＼′)+＼′(5)＼(［^＼n］|＼＼［＼n］)*＼27写出一个LEX正规式，它能匹配C语言的所有无符号整数(例如：OX89ab，0123，45，′Z′,′＼t′,′＼xab′,′＼012′,等等)。28写出一个LEX正规式，它能匹配C语言的标识符。29编写一个LEX源程序，它将一个正文文件中的全部小写字母均换为大写字母，并将其中的制表字符、空白字符序列均用单个空格字符进行替换(提示：在语义动作中使用全程变量yytext)。30编写一个LEX源程序，它能统计一个PASCAL程序中所含用户定义之标识符个数，并能找出昀长标识符中的字符个数(提示：使用全程变量yytext及yyleng)。上机实习题对于如下文法所定义的PASCAL语言子集，试编写并上机调试一个词法分析程序：〈程序〉→〈变量说明〉BEGIN〈语句表〉END.〈变量说明〉→VAR〈变量表〉：〈类型〉；|〈空〉〈变量表〉→〈变量表〉，〈变量〉|〈变量〉〈类型〉→INTEGER〈语句表〉→〈语句表〉；〈语句〉|〈语句〉〈语句〉→〈赋值语句〉|〈条件语句〉|〈WHILE语句〉|〈复合语句〉|〈过程定义〉〈赋值语句〉→〈变量〉∶=〈算术表达式〉〈条件语句〉→IF〈关系表达式〉THEN〈语句〉ELSE〈语句〉〈WHILE语句〉→WHILE〈关系表达式〉DO〈语句〉〈复合语句〉→BEGIN〈语句表〉END〈过程定义〉→PROCEDURE〈标识符〉〈参数表〉；BEGIN〈语句表〉END〈参数表〉→(〈标识符表〉)|〈空〉〈标识符表〉→〈标识符表〉，〈标识符〉|〈标识符〉〈算术表达式〉→〈算术表达式〉+〈项〉|〈项〉〈项〉→〈项〉*〈初等量〉|〈初等量〉〈初等量〉→(〈算术表达式〉)|〈变量〉|〈无符号数〉〈关系表达式〉→〈算术表达式〉〈关系符〉〈算术表达式〉〈变量〉→〈标识符〉〈标识符〉→〈标识符〉〈字母〉|〈标识符〉〈数学〉|〈字母〉〈无符号数〉→〈无符号数〉〈数字〉|〈数字〉〈关系符〉→=|＜|＜=|＞|＞=|＜＞〈字母〉→A|B|C|…|X|Y|Z〈数字〉→0|1|2|…|8|9〈空〉→要求和提示：(1)单词的分类。可将所有标识符归为一类；将常数归为另一类；保留字和分隔符则可采取一词一类。(2)符号表的建立。可事先建立一保留字表，以备在识别保留字时进行查询。变量名表及常数表则在词法分析过程中建立。(3)单词串的输出形式。所输出的每一单词，均按形如(CLASS，VALUE)的二元式编码。对于变量标识符和常数，CLASS字段为相应的类别码，VALUE字段则是该标识符、常数在其符号表中登记项的序号(要求在变量名表登记项中存放该标识符的字符串，其昀大长度为四个字符；常数表登记项中则存放该整数的二进制形式)。对于保留字和分隔号，由于采用一词一类的编码方式，所以仅需在二元式的CLASS字段上放置相应的单词的类别码，VALUE字段则为“空”。不过，为便于查看由词法分析程序所输出的单词串，也可以在CLASS字段上直接放置单词符号串本身。(4)可以仿照程序34的结构来编写上述词法分析程序，但其中的若干语义过程有待于具体编写。(5)写出它的LEX源程序，并上机进行处理。第三章习题解答1．从略2．3假设W:表示载狐狸过河，G:表示载山羊过河，C:表示载白菜过河用到的状态1：狐狸和山羊在左岸2：狐狸和白菜载左岸3:羊和白菜在左岸4:狐狸和山羊在右岸5:狐狸和白菜在右岸6:山羊和白菜在右岸F:全在右岸4证明：只须证明文法G:A→αB或A→α（A,B∈VN,α∈VT+）等价于G1:A→aB或A→a(a∈VT+)G1的产生式中A→aB,则B也有B→bC,C→cD….所以有A→abc…B’,a,b,c…∈VT,B’∈VN所以与G等价。2）G的产生式A→αB，α∈VT+，因为α是字符串，所以肯定存在着一个终结符a，使A→aB可见两者等价，所以由此文法产生的语言是正规语言。56根据文法知其产生的语言是L={ambnci|m,n,i≧1}可以构造如下的文法VN={S,A,B,C},VT={a,b,c}P={S→aA,A→aA,A→bB,B→bB,B→cC,C→cC,C→c}其状态转换图如下:7(1)其对应的右线性文法是:A→0D,B→0A,B→1C,C→1|1F,C→1|0A,F→0|0E|1A,D→0B|1C,E→1C|0B(2)昀短输入串011(3)任意接受的四个串011,0110,0011,000011(4)任意以1打头的串.8从略。9（2）相应的3型文