编译原理答疑题.doc

编译原理答疑题1 编译程序的结构是什么?答：编译过程的六个阶段的任务，再加上表格管理和出错处理的工作可分别由几个模块或程序完成，它们分别称作词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、表格管理程序和出错处理程序。2 PL0编译程序的结构是什么？答：由PL0的EBNF可知，PL0语言可看成是PASCAL语言的子集，它的编译程序是一个编译解释执行系统。PL0的目标程序为假想栈式计算机的汇编语言，与具体计算机无关。PL0的编译程序和目标程序的解释执行程序都是用PASCAL语言书写的，因此PL0语言可在配备PASCAL语言的任何机器上实现。其编译过程采用一趟扫描方式，以语法分 析程序为核心，词法分析程序和代码生成程序都作为一个独立的过程，当语法分析需要读单词时就调用词法分析程序，而当语法分析正确需生成相应的目标代码时，则调用代码生成程序。此外，用表格管理程序建立变量、常量和过程标识符的说明与引用之间的信息联系。用出错处理程序对词法和语法分析遇到的错误给出在源程序中出错的位置和错误性质。当源程序编译正确时，PL0编译程序自动调用解释执行程序，对目标代码进行解释执行，并按用户程序要求输入数据和输出运行结果。3关系有哪些基本性质？答：自反的 在集合X上的关系R，如对任意xX，均有(x，x) R，则称关系R是自反的。 非自反的 在集合X上的关系R，如对任意xX，均有(x，x)R，则称关系R是非自反。对称的 在集合X上的关系R，如果合(x，y) R，便必有(y，x) R，则称关系R是对 称的。 非对称的 在集合X上的关系R，如果有(x，y) R丛xy，便必有(y，x)R，则称关系R是非对称的。 传递的 在集合X上的关系R，如果合(x，y) R且(y，z) R，必有(x，z) R，则称关系R是传递的。4设有文法GI: I-I1/I0/Ia/Ic/a/b/c 判断下面符号串中哪些是该文法的句子. (1) ab0 (2)a0c01 (3)aaa (4)bc10 (5)aabc (6)bbca答：(1)错误 (2)正确 (3)正确 (4)正确 (5)错误 (6)错误 (7)错误5. 给定文法G =（VN，VT，P，S），对于G的任何句型都能构造与之关联的语法树(推导树)。这棵树应满足那些条件？答：给定文法G =（VN，VT，P，S），对于G的任何句型都能构造与之关联的语法树(推导树)。这棵树满足下列4个条件：1 树中每个结点都有一个标记，此标记为VNVT中的一个符号2 根的标记为文法的开始符3 若一结点n至少有一个它自己除外的子孙，并且有标记为A，则A一定是非终结符4 如果结点n的直接子孙，从左到右的次序是 ，且分支结点的标记分别为B1、B2,Bn，则AB1B2Bn一定是P中的一个产生式。6. 自下而上分析算法的基本思想是什么？答：从所给符号串x开始，在其中寻找与文法的某条规则右部相匹配的子串，并用该规则的左部取代此子串(即归约)，重复此过程，步步向上归约，最后试图将符号串x归约到文法的识别符号Z。如归约成功，则符号串x是文法的句子。7设有文法G：s:=Qc|cQ:=Rb|bR:=Sa|a试求HARD(S),HARD(Q),HARD(R).答： HARD(S)=S,Q,R,a,b,c HARD(Q)=S,Q,R,a,b,c HARD(R)=S,Q,R,a,b,c8. 用扩充的BNF范式表示下述文法以消去规则： S:=aABb|ab A:=Aab| B:=Aa|a解：S:=aABb|ab A:=ab B:=Aa|a9.将词法分析做为一个独立的阶段，把编译过程的分析工作划分成词法分析和语法分析两个阶段主要的考虑因素是什么？答：1 使整个编译程序的结构更简洁、清晰和条理化。词法分析比语法分析简单的多，但是由于源程序结构上的一些细节，常使得识别单词的工作甚为曲折和费时。例如，空白和注释的处理；再比如对于FORTRAN那种受书写格式限制的语言，需在识别单词时进行特殊处理等等。如果统统合在语法分析时一并考虑，显然会使得分析程序的结构复杂得多。 2 编译程序的效率会改进。大部分编译时间是花费在扫描字符以把单词符号分离出来。把词法分析独立出来，采用专门的读字符和分离单词的技术可大大加快编译速度。另外，由于单词的结构可用有效的方法和工具进行描述和识别，进而可建立词法分析程序的自动构造工具。3 增强编译程序的可移植性。在同一个语言的不同实现中，或多或少地会涉及到与设备有关的特征，比如采用ASCII还是EBCDIC字符编码。另外语言的字符集的特殊性的处理，一些专用符号，如PASCAL中的的表示等等，都可置于词法分析程序中解决而不影响编译程序其它成分的设计。10. 转换图容易用程序实现，最简单的办法是让每个状态结点对应一小段程序。引进一组全局变量和过程，将它们作为实现转换图的基本成分，这些变量和过程是什么？答：(1)ch 字符变量，存放最新读进的源程序字符。(2)strToken 字符数组，存放构成单词符号的字符串。(3)GetChar 子程序过程，将下一输入字符读到ch中，搜索指示器前移一字符位置。(4)GetBC 子程序过程，检查ch中的字符是否为空白。若是，则调用GetChar直至ch中进人一个非空白字符。(5)Concat 子程序过程，将ch中的字符连接到strToken之后。例如，假定strToken原来的值为AB，而ch中存放着C，经调用Concat后，strToken的值就变为ABC。(6)IsLetter和IsDigit 布尔函数过程，它们分别判断ch中的字符是否为字母和数字。(7)Reserve 整型函数过程，对strToken中的字符串查找保留字表，若它是一个保留字则返回它的编码，否则返回0值(假定0不是保留字的编码)。(8)Retract 子程序过程，将搜索指示器回调一个字符位置，将ch置为空白字符。(9)InsertId 整型函数过程，将strToken中的标识符插入符号表，返回符号表指针。(10)InsertConst 整型函数过程，将strToken中的常数插入常数表，返回常数表指针。这些函数和子程序过程都不难编制。使用它们能够方便地构造状态转换图的对应程序。一般来说，可让每个状态结点对应一程序段。11. 什么是正规式，正规式的递归定义是什么？答：正规式也称正则表达式，也是表示正规集的工具。也是我们用以描述单词符号的方便工具。下面是正规式和它所表示的正规集的递归定义。 设字母表为，辅助字母表为=，|，*，(，) (1). 和都是上的正规式，它们所表示的正规集分别为和 (2). 任意a，a是上的一个正规式， 它所表示的正规集为a (3). 若e1，e2都是上的一个正规式， 它们所表示的正规集分别为L(e1)和L(e2)，那么e1|e2，e1e2和，( e1)也都是正规式, 它们所表示的正规集分别为L(e1)L(e2), L(e1) L(e2)和，L(e1) (4). 仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上正规集。12. 什么是有穷自动机？什么是确定的有穷自动机？答：有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。 有穷自动机分为两类：确定的有穷自动机(Deterministic Finite Automata)和不确定的有穷自动机(Nondeterministic Finite Automata)，下面我们分别给出确定有穷自动机和不确定的有穷自动机的定义，有关概念及不确定的有穷自动机的确定化，确定的有穷自动机的化简等算法。确定的有穷自动机（DFA） 一个确定的有穷自动机（DFA）是一个五元组：M=（K，f，S，Z），其中(1) K是一个有穷集，它的每个元素称为一个状态；(2) 是一个有穷字母表，它的每个元素称为一个输入字符，所以也称为输入符号字母表；(3) f是转换函数，是在KK上映像，即，如f（ ，a）=（K，K），就意味着，当前状态为，输入字符为a时，将转换到下一状态，我们把称作的一个后继状态；(4) SK是唯一的一个初态；(5) ，是终态集，终态也称可接受状态或结束状态。13. 正规式的构造步骤是什么？答：我们把状态转换图的概念拓广，令每条弧可用一个正规式作标记。构造步骤： 第一步 在M的状态转换图上加进两个状态，一个为x，一个为y。从x状态出发，用弧连接到M的所有初始态；从M的所有终止态出发，用弧连接到y状态。形成一个与M等价的M。 第二步 逐步消去M中的所有状态，直至只剩下x和y状态。在消结过程中，逐步用正规式来标记弧。消结的规则如下：最后x和y结点间的弧上的标记则为所求的正规式R。14.举例说明判断LL(1)文法的步骤。答：SABSbC AAbBBaDCADCbDaSDc判别步骤：1 求出能推出的非终结符 首先建立一个以文法的非终结符个数为上界的一维数组，其数组元素为非终结符，对应每一个非终结符有一标志位，用来记录能否推出，其值有三种情况未定，是，否。例1所对应数组X 的内容如表一所示。 表一 非终结符能否推出空的表计算能推出的非终结符步骤如下：（1） 将数组X 中对应每一个非终结符的标记置初值为未定 （2） 扫描文法中的产生式 删除所有右部含有终结符的产生式，若这使得以某一非终结符为左部的所有产生式都被删除，则将数组中对应该非终结符的标记值改为否，说明该非终结符不能推出。 若某一非终结符的某一产生式右部为，则将数组中对应该非终结符的标志置为是，并从文法中删除该非终结符的所有产生式。例中对应非终结符A、B的标志改为是。 （3） 扫描产生式右部的每一符号 若所扫描到的非终结符在数组中对应的标志是是，则删去该非终结符，若这使产生式右部为空，则对产生式左部的非终结符在数组中对应的标志改为是，并删除该非终结符为左部的所有产生式。 若所扫描到的非终结符在数组中对应的标志是否，则删去该产生式，若这使产生式左部非终结符的有关的产生式都被删去，则把在数组中该非终结符对应的标志改成否。 （4） 重复（3），直到扫描完一遍文法的产生式，数组中非终结符对应的特征再没有改变为止。 由2)中(a)得知例中对应非终结符D的标志改为否。 经过上述2)中(a)、(b)两步后文法中的产生式只剩下：SAB CAD也就是只剩下右部全是非终结符串的产生式。 再由3)中的(a)步扫描到产生式SAB时，在数组中A、B对应的标志都为是，删去后S的右部变为空，所以S对应标志置为是。最后由3)中的(b)扫描到产生式CAD时，其中，A对应的标志为是，D对应的标志是否，删去该产生式后，再无左部为C的产生式，所以C的对应标志改成否。15.如何计算FIRST集答：根据定义计算由FIRST集定义 FIRST ()=a|=a， a， ， V若=, 则规定FIRST()。 对每一文法符号XV，计算FIRST(X)(a) 若X，则FIRST(X)=X(b) 若X，且有产生式Xa，a，则aFIRST(X)(c) 若X，且有产生式X，则FIRST(X)(d) 若X，Y1，Y2，Yi，而有产生式XY1Y2Yn。当Y1Y2Yi-1都=时，(其中1in)，则FIRST(Y1)-，FIRST(Y2)-，FIRST )-，FIRST(Yi)都包含在FIRST(X)中。(e) 当(d)中所有Yi=(i=1，2，.n),则FIRST(X)= FIRST(Y1)FIRST(Y2)FIRST(Yn) 反复使用(a)-(e)步，直到每个符号的FIRST集合不再增大为止16. PL0编译程序对语法错误的处理采用哪两种办法?答：(1)对于一些易于校正的错误，如丢了逗号、分号等，则指出出错位置，并加以校正。校正的方式就是补上逗号或分号。 (2)对某些错误，编译程序难于确定校正的措施，为了使当前的错误不致影响整个程序的崩溃，把错误尽量局限在一个局部的语法单位中。这样就需跳过一些后面输入的单词符号，直到读入一个能使编译程序恢复正常语法分析工作的单词为止。17.解释说明下列指令LIT、LOD、STO、CAL、INT、JMP、JPC、OPR?答：1.LIT：将常量值取到运行栈顶。2. LOD：将变量放到栈顶。3. STO：将栈顶的内容送入某变量单元中。4. CAL：调用过程的指令。5. INT：为被调用的过程(或主程序)在运行栈中开辟数据区。6. JMP：无条件转移指令。7. JPC：条件转移指令。8. OPR：关系运算和算术运算指令。将栈顶和次栈顶的内容进行运算，结果存放在次栈顶，此外还可以是读写等特殊功能的指令。18. 解释符号串联结?答：设有符号串x和y，把y的符号写在x的符号之后所得的符号串，叫做x与y的联结，记为xy。19. 什么是最左素短语？答：设有文法GS，其句型的素短语是一个短语，它至少包含一个终结符，并除自身外不包含其他素短语。最左边的素短语称最左素短语。20. 简述LR(1)项目集族的构造？答：(2) 转换函数的构造 LR(1)转换函数的构造与LR(0)的相似，GO(I，X)CLOSURE( J ) 其中I是LR(1)的项目集，X是文法符号： J任何形如 AX，a的项目 | AX，a I 对文法G的LR(1)项目集族的构造仍以SS，#为初态集的初始项目，然后对其求闭包和转换函数，直到项目集不再增大。 也就是对状态I经过符号X后转向状态J，求出J的核后，对核求闭包即为CLOSURE(J)。21. L-属性文法的定义是什么？答：一个属性文法称为L-属性文法，如果对于每个产生式AX1X2Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj(1jn)的一个继承属性且这个继承属性仅依赖于： (1)产生式Xj的左边符号X1，X2，Xj-1的属性； (2)A的继承属性。22. 要提高访问符号表的效率和节省存储空间，要考虑哪些问题？答：首先，要考虑程序设计语言的性质，它包含哪些语法成分，应该进行哪些语义真缺性检查等等；其次，不能离开支撑环境，如目标机器的性能怎样，将借助符号表产生怎样的目标代码，编译程序所依赖的操作，系统能提供哪些存储、管理方式等等。23. 常见的符号表的结构有哪些？答：常见的符号表结构有：无序符号表：是按标识符出现的顺序建立符号表有序符号表：建表时，各标识符名按字典顺序排列于符号表中栈符号表：对于分析程序（或过程）嵌套结构型程序设计语言，将其符号表设计为栈式符号表。总是从栈顶加入；而查找则从栈顶向底检查）。24. 什么是静态存储分配?答：在编译阶段对源程序中的量分配以固定的存储单元，运行时始终不变。25.名词解释：以过程为单位进行存储分配：答：以过程调用为单位来设置数据区。26. 优化的目的是什么