编译原理_第1~5章习题课答案

编译原理chapter1~5习题chapter11、何谓源程序、目标程序、翻译程序、编译程序和解释程序？它们之间可能有何种关系？源程序：用源语言编写的程序。目标程序：源程序经翻译程序过加工处理后生成的程序。翻译程序：将源程序转换为与其逻辑上等价的目标程序。编译程序：源语言为高级语言，目标语言为汇编语言或机器语言的翻译程序。解释程序：源语言程序作为输入，但不产生目标程序，而是边解释边执行源程序本身。①先翻译后执行①边解释边执行②执行速度快②有利于程序的调试③多次运算③1次运算编译原理chapter1~5习题2、一个典型的编译系统通常由有哪些部分组成？各部分的主要功能是什么？chapter1编译系统编译程序语法分析语义分析与中间代码生成优化目标代码生成运行系统词法分析编译原理chapter1~5习题②语法分析(SyntaxAnalysis)：在词法分析的基础上将单词序列分解成各类语法短语，如“程序”，“语句”，“表达式”等等。③语义分析(SyntacticAnalysis)：语义分析是在语法分析程序确定出语法短语后，审查有无语义错误，并为代码生成阶段收集类型信息。chapter1①词法分析(LexicalAnalysis)：从左到右一个字符一个字符的读入源程序，对构成源程序的字符串进行扫描和分解，从而识别出一个个单词（也称单词符号或简称符号）。编译原理chapter1~5习题chapter1⑤代码优化(Optimizationofcode)：为了使生成的目标代码更为高效，可以对产生的中间代码进行变换或进行改造，这就是代码的优化。⑥代码生成(Generationofcode)：目标代码生成是编译器的最后一个阶段。在生成目标代码时要考虑以下几个问题：计算机的系统结构、指令系统、寄存器的分配以及内存的组织等。④中间代码生成(Generationofintermediatecode)：完成语法分析和语义处理工作后，编译程序将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或称中间代码，它是一种结构简单、含义明确的记号系统。编译原理chapter1~5习题chapter21.写出C语言和Java语言的输入字母表。C语言：0~9数字，大小写英文字母，键盘上可见的字符Java语言：Unicode可以包括的所有字符。6.文法G6为:N→D|NDD→0|1|2|3|4|5|6|7|8|9（1）G6的语言是什么?G6的语言是：0~9的数字组成的任意非空串L(G6)={x|x∈{0,1,2,3,4,5,6,7,8,9}+}（2）给出句子0127、34和568的最左和最右推导。编译原理chapter1~5习题7、写一文法，使其语言是奇数集。要求：不以0打头。复杂的情况:分三部分末尾：以1|3|5|7|9结尾(一位):D→1|3|5|7|9开头：除了0的任意数字中间部分：空或者任意数字串D→1|3|5|7|9C→CA|εA→0|B所以题目要求的文法G[N]可以写成：N→BCD|DD→1|3|5|7|9B→2|4|6|8|DC→CA|εA→0|BB→2|4|6|8|D编译原理chapter1~5习题9、证明文法:S→iSeS|iS|i是二义的。二义性的含义:如果文法存在某个句子对应两棵以上不同的语法树，或者两种以上不同的最左/右推导，则称这个文法是二义的。首先：找到此文法对应的一个句子iiiei其次：构造与之对应的两棵语法树SiSeSiSiiSiSiSeSii结论：因为该文法存在句子iiiei对应两棵不同的语法树，因而该文法是二义的。编译原理chapter1~5习题11、给出下面语言的相应文法L1={anbnci|n≥1,i≥0}G1(S):S→ABA→aAb|abB→cB|ε从n，i的不同取值来把L1分成两部分：A→aAb|ab前半部分是anbn：后半部分是ci：B→Bc|ε所以整个文法G1[S]可以写为：编译原理chapter1~5习题L2={aibncn|n≥1,i≥0}G2(S):S→ABA→aA|εB→bBc|bcL3={anbnambm|m,n≥0}G3(S):S→ABA→aAb|εB→aBb|ε编译原理chapter1~5习题L4={1n0m1m0n|n,m≥0}可以看成是两部分：剩下两边的部分就是：S→1S0中间部分是0m1m：A→0A1|ε所以G4[S]可以写为：S→1S0|AA→0A1|ε|A编译原理chapter1~5习题chapter37.构造下列正规式相应的DFA。步骤:①.根据正规式画出对应的状态转换图;②.根据状态转换图画出对应的状态转换矩阵;③.根据状态转换矩阵得到重命名后的状态转换矩阵;④.根据重命名后的状态转换矩阵得出最后的DFA.问题：将状态转换图与DFA混淆。编译原理chapter1~5习题1(0|1)*101①.状态转换图abadb1(0|1)*101a1(0|1)*101dcef1εε01101ggg编译原理chapter1~5习题②.状态转换矩阵II0I1{a}Φ{b,c,d}{b,c,d}{c,d}{c,d,e}{c,d}{c,d}{c,d,e}{c,d,e}{c,d,f}{c,d,e}{c,d,f}{c,d}{c,d,e,g}{c,d,e,g}{c,d,f}{c,d,e}1abdcef1εε0101g编译原理chapter1~5习题II0I1{a}Φ{b,c,d}{b,c,d}{c,d}{c,d,e}{c,d}{c,d}{c,d,e}{c,d,e}{c,d,f}{c,d,e}{c,d,f}{c,d}{c,d,e,g}{c,d,e,g}{c,d,f}{c,d,e}③.重命名后的状态转换矩阵S01A(始态)ΦBBCDCCDDEDECF(终态)F(终态)EDAB10C1D010E10101F④.DFA编译原理chapter1~5习题1(1010*|1(010)*1)*0abdc1εε0e0101fghiεε01110jklmnεε①.状态转换图编译原理chapter1~5习题②.状态转换矩阵II0I1{0}Φ{1,2,3}{1,2,3}{4}{5,9,10,11}{5,9,10,11}{6,12}{2,3}{6,12}Φ{2,3,7,8,13}{2,3}{4}{5,9,10,11}{2,3,7,8,13}{2,3,4,8,10,11}{5,9,10,11}{2,3,4,8,10,11}{2,3,4,8,12}{2,3,5,9,10,11}{2,3,4,8,12}{2,3,4,8}{5,9,10,11,13}{2,3,5,9,10,11}{4,6,12}{2,3,5,9,10,11}{2,3,4,8}{2,3,4,8}{5,9,10,11}{5,9,10,11,13}{6,10,11,12}{2,3}{4,6,12}Φ{2,3,7,8,13}{6,10,11,12}{12}{2,3,7,8,13}{12}Φ{13}{13}{10,11}Φ{10,11}{12}{2,3}编译原理chapter1~5习题③.重命名后的状态转换矩阵II0I11Φ22344565Φ7634784891091112101310111141214613Φ71415715Φ161617Φ17156④.DFA编译原理chapter1~5习题8、给出下面正规表达式（1）以01结尾的二进制数串。(0|1)*01（2）能被5整除的十进制数。0|5(0|5)|(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*（4）英文字母组成的所有符号串，要求符号串中的字母按字典序排列。(A|a)*(B|b)*(C|c)*…(Z|z)*（3）包含奇數個1或奇數個0的二進制串0*1(0|10*1)*|1*0(0|10*1)*编译原理chapter1~5习题（5）沒有重複出現的數字的數字符號串的全體令ri=i|,i=0,1,2...9R0|R1|R2|...|R9記為∑Rii(0,1,2...,9)P（0,1,2...,9)表示0,1,2...,9的全排列∑ri0ri1...ri9ri0ri1...ri9P(0,1,2...,9)8、给出下面正规表达式（6）最多有一個重複出現的數字的數字符號串的全體∑i∑ri0ri1...ri9i(0,1,2...,9)ri0ri1...ri9P(0,1,2...,9)（7）不包含字串abb的由a和b組成的符號串的全體b*(a*|(ba)*)*编译原理chapter1~5习题9、对下面情况给出DFA及正规表达式：（1）{0,1}上的含有子串010的所有串。正规式：(0|1)*010(0|1)*DFA做法同第7题。（2）{0,1}上不含子串010的所有串。正规式：1*(0|11*1)*1*0*1*(0|11)*(0|1)1*(0|11)*1*编译原理chapter1~5习题12、将图3.18的(a)和(b)分别确定化和最少化。(a)aaa,b10①.状态转换矩阵IIaIb{0}{0,1}{1}{1}{0,1}{0,1}{1}{0}φ②.重命名后的状态转换矩阵IIaIb01221120φ0a2baba③.DFA④.最小化Π0=({0,1},{2})1{0,1}a={1}{0,1}b={2}因此，不能再分02baa编译原理chapter1~5习题023145aaaabbbbbbaa(b)这道题实质上已经是确定化了的，所以我们只需最小化Π：{2，3，4，5}{0，1}{2，3，4，5}a={0，1，3，5}分属两区，所以分为{2，4}{3，5}{0，1}a={1}{0，1}b={2，4}所以0，1等价{2，4}a={0，1}{2，4}b={3，5}所以2，4等价{3，5}a={3，5}{3，5}b={2，4}所以3，5等价所以分为{0，1}{2，4}{3，5}023aabbba编译原理chapter1~5习题14、构造一个DFA，它接受Σ={0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。思路：先写出满足条件的正规式，由正规式构造NFA，再把NFA确定化和最小化。满足条件的正规式：(0|10)*0110yx(0|10)*xy12100编译原理chapter1~5习题xy12100确定化：01{X,1,Y}{1,Y}{2}{1,Y}{1,Y}{2}{2}{1,Y}φ给状态编号：0101211221φ编译原理chapter1~5习题02101100最小化：{0,1}，{2}{0,1}0={1}{0,1}1={2}{2}0={0}，{2}1=∅⊆{2}或{0,1}所以{0,1}不可分，用狀態0代表它們02100编译原理chapter1~5习题15、给定右线性文法G：求一个与G等价的左线性文法。S→0S|1S|1A|0BA→1C|1B→0C|0C→0C|1C|0|1SABCZ001110001101G[Z]:Z→Z0|Z1|B0|A1B→A0|0A→B1|1确定化、最小化后的DFA为：SB0A110Z010,1编译原理chapter1~5习题补充：构造一右线性文法，使它与如下文法等价：S→ABA→UTU→a|aUT→b|bTB→c|cB并根据所得右线性文法，构造出相应的状态转换图。思路：先写出原文法所描述的语言L(G)={ambnck|m,n,k≥1}G[S]:S→aS|aBB→bB|bCC→cC|caSaCbcBbcT编译原理chapter1~5习题chapter44.1、考虑下面文法G1：S→a|∧|（T）T→T，S|S（1）消去G1的左递归；S→a|∧|（T）T→ST’T’→，ST’|ε（2）经改写后的文法是否是LL(1)文法，给出预测分析表。经改写后的文法满足3个条件，所以是LL(1)的编译原理chapter1~5习题预测分析表构造算法:1.对文法中的每个产生式A→α执行第二步和第三步;FIRST(S)={a,∧,(}FIRST(T)={a,∧,(}FIRST(T’)={,,ε}FOLLOW(S)={),,,#}FOLLOW(T)={