编译原理(王力红著)习题答案

习题11-1说明解释程序和编译程序的区别。答：通常，翻译程序可分为解释程序、汇编程序和编译程序。所谓解释程序是一种将源程序按动态顺序逐句进行分析解释编译，边解释边执行、不产生目标程序的一种翻译程序。这种翻译程序结构简单、占用内存较少，易于在执行过程中对源程序进行修改，但工作效率低，只适合一些规模较小的语言，如解释BASIC等。而编译程序（也称编译器）是源语言为某种高级语言，目标语言为相应于某一计算机的汇编语言或机器语言的一种翻译程序。这种编译程序将源程序翻译成执行时可完全独立于源程序的经优化的目标语言代码，因而运行效率高。更为重要的是，它使工作于高级语言环境下的程序设计人员，不必考虑与机器有关的繁琐细节，却能完成机器语言所能完成的绝大多数工作。在解释方式下，并不生成目标代码，而是直接执行源程序本身。这是编译方式与解释方式的根本区别。1-2简述高级语言程序按编译方式的执行过程。答：高级语言程序按编译方式的执行过程一般可分为两个阶段：编译阶段和运行阶段。其中，编译阶段完成由源程序到目标程序的翻译，若目标程序是汇编语言程序，还需再通过汇编程序进一步翻译成机器语言程序。而运行阶段的任务是在目标计算机上执行编译阶段所得到的目标程序。但目标程序往往不能由计算机直接执行，一般还应有运行系统进行配合，这个运行系统包括链接程序和由这样一些子程序组成的系统库，如标准函数计算子程序、数组动态存储子程序等。由链接程序将目标程序和系统库连接在一起，最终形成一个可执行程序，在计算机上直接执行。1-3什么是编译系统？答：通常将编译程序、链接程序、系统库、源程序编辑程序等软件组成的系统称为编译系统。1-4编译过程通常有哪几个阶段？简述各阶段的主要任务。答：程序设计语言的编译过程一般可以分为词法分析、语法分析、语义分析和中间代码生成、代码优化、目标代码生成5个阶段。词法分析是编译过程的第一个阶段。该阶段的主要任务是从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位——单词，并指出其属性。语法分析阶段的主要任务是在词法分析的基础上，根据相应程序设计语言的语法规定进行语法分析，在源程序的单词串中识别出各种语法成分，如“程序”、“语句”、“表达式”等，并确定整个输入串是否构成一个语法上正确的程序，检查出语法错误。语义分析和中间代码生成阶段的主要任务有两个，其一是进行相应的语义检查，以保证源程序在语义上的正确性，其二是确定各语法成分的含义、用途，收集类型信息，确定应进行的运算和操作，并将其转换为某种内部表示形式，即生成中间代码。代码优化阶段是编译过程的最后阶段。这一阶段的任务是对上一阶段产生的中间代码进行变换和改造，以期获得高质量的目标代码。目标代码生成阶段的任务是把优化后的中间代码转换成特定机器上的绝对指令代码，或可重定位的指令代码，或汇编指令代码。由于这种转换工作与具体的目标计算机的系统结构及其指令系统有关，涉及各种变量的存储空间分配、寄存器的调度、各种硬件功能部件的使用等，因此工作比较复杂。1-5什么是编译程序的遍？对编译程序来说，遍多和遍少各有什么优缺点？所谓一遍（pass）或一趟，是指在编译过程中对源程序或与之等价的中间程序从头到尾扫描一遍，并将其转换成下一个中间程序的整个过程。答：编译程序按其扫描次数可分为单遍（趟）扫描和多遍（趟）扫描。采用多遍扫描方式，各遍的工作分工明确，便于多人合作开发，缩短开发周期，同时节省运行时的内存空间，易于提高目标程序的质量。但各遍之间的重复工作多，编译效率低。而单遍（趟）扫描的编译程序，编译速度快、效率高，但运行时占用空间大，目标程序质量低。1-6一个最简单的编译程序至少要包含哪几个组成部分（程序）？答：至少要包含词法分析程序、语法分析程序、目标代码生成程序等3个组成部分（程序）。习题22-3已知算术表达式文法G[E]：E→E+T|TT→T*F|FF→(E)|i求符号串i*i的最左推导、最右推导、最左归约、最右归约。解：最左推导：E=T=T*F=F*F=i*F=i*i最右推导：E=T=T*F=T*i=F*i=i*i最左归约：i*i=F*i=T*i=T*F=T=E最右归约：i*i=i*F=F*F=T*F=T=E2-4设有文法G[A]：A→bA|cc判断符号串bbc，bbbcc，bbA，bbAc是否是G[A]的句型或句子。解答：∵A=bA=bbA=bbbA=bbbcc∴bbA是G[A]的句型,bbbcc是G[A]的句子，bbAc不是G[A]的句型,bbc不是G[A]的句子。2-5分别求下列文法所描述的语言：①G1[S]：S→aaSbb|解答：∵S=aaSbb=aaaaSbbbb=…∴L(G1[S])={a2nb2n|n≥0}②G2[S]：S→10S0|aAA→bA|a基本的求解方法：语言的定义解:∵S=10S0=1010S00=…=(10)mS0m=(10)maA0mA=bA=bbA=…=bnA=bna∴S=…=(10)maA0m=(10)mabna0mL(G2[S])={(10)mabna0m|m≥0,n≥0}③G3[S]：S→SS|1A0A→1A0|基本的求解方法：语言的定义解:∵S=SS=…=SSm=SSm=1A0(1A0)mA=1A0=11A00=…=1mA0m=1mA0m=1m0m∴S=1A0(1A0)m=11m0m0(11m0m0)nL(G2[S])={(1m0m)n|m≥1,n≥1}2-6分别对下列语言构造相应的文法：①可以以0开头的所有正偶数的集合;参考答案：e=(0|1|2|…|9)*(0|2|4|6|8)G[S]:S→(0|1|2|…|9)S|0|2|4|6|8②不以0开头的所有奇数的集合；e=(1|3|5|7|9)|(1|2|3|4|5|6|7|8|9)(0|1|2||3|4|5|6|7|8|9)*(1|3|5|7|9)解：S→BA|CA→DA|CB→1|2|3|4|5|6|7|8|9C→1|3|5|7|9D→0|B③能被5整除的所有整数的集合；e=(0|1|2|…|9)*(0|5)解：S→0S|1S|2S|…|9S|0|5④以a开头、b结尾的∑={a,b}上的任意符号串的集合；e=a(a|b)*b解：S→aAA→aA|bA|b⑤{an#bn|n≥0}∪{cn#dn|n≥0}；解：S→A|BA→aAb|#B→cBd|#⑥{1n0m1m0n|m,n≥0}；解：S→1S0|AA→0A1|⑦{w#wr#|w∈{0,1}*,wr表示将w中的符号按逆序排列所得的符号串}；解：S→A#A→0A0|1A1|#2-7已知算术表达式文法G[E](见题2-3)，根据定义求句型E+i*i的短语、简单短语和句柄。解答：E=E+T=E+T*F=E+F*F=E+i*F=E+i*iE=E+T=E+T*F=E+F*F=E+F*i=E+i*iE=E+T=E+T*F=E+T*i=E+F*i=E+i*i短语：i*i，E+i*i简单短语：i，句柄：i2-8分别写出一个描述如下语言的非左递归文法和非右递归文法：{s;，s;s;，s;s;s;，…}并分别给出句子s;s;的最左推导、最右推导和相应的语法树。解答：非左递归文法：S→s;S|s;最左推导：S=s;S=s;s;最右推导：S=s;S=s;s;相应的语法树：非右递归文法：S→Ss;|s;最左推导：S=Ss;=s;s;最右推导：S=Ss;=s;s;相应的语法树：2-9已知算术表达式文法G[E](见题2-3)，根据语法树求句型E+i*i的短语、简单短语和句柄。解：求语法树：根据语法树：短语：i，i*i，E+i*i简单短语：i句柄：i2-10设有文法G[A]：A→#B#B→B+C|CC→C*a|a①至少采用两种EBNF表示法改写该文法；解答：A→#B#B→(B+|)CC→(C*|)a②用语法图表示该文法。习题33-1画出下列有限自动机的状态转换图，并说明它所识别或接受的语言是什么？①M＝({S，A，B，C}，{0，1}，f，S，{S})，其转换函数为：f(S，0)=Bf(B，0)=Sf(S，1)=Af(B，1)=Cf(A，0)=Cf(C，0)=Af(A，1)=Sf(C，1)=B参考答案：有限自动机的状态转换图它所识别或接受的语言是：L(M)={,00,11,0101,0110,1001,1010,0011,0000,1111,…,}由偶数个0或偶数个1组成的二进制串。②M＝({0，1，2}，{a，b}，f，0，{2})，其状态转移矩阵为：符号状态ab0{1,2}{0}1{0,1}2{0,2}{1}解答：有限自动机M的状态转换图：有限自动机M所识别或接受的语言是：L(M)={a,aaa,abaa,ba,baaa,babaa,…}3-2设计字母表∑={a,b}上的确定有限自动机，使它能识别或接受下列语言：①以aa为首的所有符号串集合；解答：正则式e=aa(a|b)*NFA：DFA：ab0112,3,42,3,43,43,43,43,43,4最小化：ab2333332，3等价，合并。ab0112②以aa结尾的所有符号串集合；e=(a|b)*aaIIaIbXX,AXX,AX,A,YXX,A,YX,A,YX重命名：{X}为0{X,A}为1{X,A,Y}为2ab010120220③含有相继两个a或相继两个b的所有符号串集合。e=(a|b)*(aa|bb)(a|b)*3-3试把下述NFA变换为DFA。解答：最基本的方法是子集法：IIaIb{0}{1}-{1}-{1，2}{1，2}{1}{1，2}重命名：{0}为0，{1}为1，{1，2}为2，包含原终态2的{1，2}为新终态，于是所求DFA为：解：最基本的方法：子集法：IIaIb{0}{1}-{1}-{1，2}{1，2}{0}{1，2}重命名：IIaIb01-1-22023-5试把下列FA确定化(若需要的话)和最小化。参考答案：2,4状态是死状态，应删除。只有一个状态的FA肯定是确定化的和最小化的。此FA是DFA，不需要确定化。最小化：首先按终态与非终态划分：{0，1}，{2，3，4，5}；然后计算：ab012114对于输入a，b，{0，1}后继都属于同一集合，故0，1等价。ab21334055对于输入a，{2，4}后继属于同一集合{0，1}，{3，5}后继属于同一集合{3，5}，故可继续划分为：{2，4}，{3，5}。进一步计算：ab2134052，4等价。ab3325543，5等价。合并等价状态，最小化为：习题44-1假定符号表采用栈结构组织，请给出下列C程序段执行过程中符号表的变化情况。inti,j;intfun(intn){chari,t;{floatj;}{char*j;}}习题55-3请识别下列PASCAL程序段中的单词符号并给出单词的内部编码。functionmax(i:integer;j:integer):integer;(*returnmaximumofintegersiandj*)beginifi＞jthenmax:=ielsemax:=jend;参考答案：function保留字max标识符（分隔符i标识符:分隔符integer标识符;分隔符j标识符:分隔符integer标识符)分隔符:分隔符integer标识符;分隔符begin保留字if保留字＞特殊符then保留字:=特殊符else保留字end保留字习题66-1设有文法G[S]：S→a|^|(T)T→T,S|S①求符号串S和T,S的FIRST集；②求非终结符S和T的FOLLOW集；③求各产生式的SELECT集；④求非终结符S和T的FIRSTVT集和LASTVT集。参考答案：非终结符号的FIRST集合：FIRST(S)={a,^,(}FIRST(T)={a,^,(}①符号串的FIRST集：FIRST(S)={a,^,(}FIRST(T,S)=FIRST(T)={a,^,(}②非终结符号的FOLLOW集