编译原理答疑题

1、编译原理答疑题1 .编译程序的结构是什么 ？答：编译过程的六个阶段的任务，再加上表格管理和出错处理的工作可分别由几个模块或程序完成，它们分别称作词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、 代码优化程序、目标代码生成程序、表格管理程序和出错处理程序。2 . PL/0编译程序的结构是什么？答：由PL/0的EBNF可知，PL/0语言可看成是 PASCAL语言的子集，它的编译程序是 一个编译解释执行系统。PL/0的目标程序为假想栈式计算机的汇编语言，与具体计算机无关。PL/0的编译程序和目标程序的解释执行程序都是用PASCAL语言书写的，因此 PL/0语言可在配备PASCAL语言的任

2、何机器上实现。其编译过程采用一趟扫描方式，以语法分析程序为核心，词法分析程序和代码生成程序都作为一个独立的过程，当语法分析需要读单词时就调用词法分析程序，而当语法分析正确需生成相应的目标代码时，则调用代码生成程序。此外，用表格管理程序建立变量、常量和过程标识符的说明与引用之间的信息联系。用出错处理程序对词法和语法分析遇到的错误给出在源程序中出错的位置和错误性质。当源程序编译正确时，PL/0编译程序自动调用解释执行程序，对目标代码进行解释执行，并按用户程序要求输入数据和输出运行结果。3 .关系有哪些基本性质？答：自反的 在集合X上的关系R,如对任意xCX,均有(x, x) C R,则称关系R是自

3、 反的。非自反的在集合X上的关系R,如对任意xCX,均有(x, x)任IR,则称关系R是非自反。对称的 在集合X上的关系R,如果合(x, y) C R,便必有(y, x) C R,则称关系R 是对 称的。非对称的在集合X上的关系R,如果有(x, y) CR丛xwy,便必有(y, x)任I R,则称关系R是非对称的。传递的 在集合X上的关系R,如果合(x, y) eR且(y, z) CR,必有(x, z) C R,则 称关系R是传递的。4 .设有文法GI:I->I1/I0/Ia/Ic/a/b/c判断下面符号串中哪些是该文法的句子.ab0 (2)a0c01 (3)aaa (4)bc10 (5

4、)aabc (6)bbca 答：错误(2)正确(3)正确 (4)正确 错误 (6)错误错误5 .给定文法G = (VN , VT , P, S),对于G的任何句型都能构造与之关联的语法树(推导树)。这棵树应满足那些条件？答：给定文法 G = (VN, VT, P, S),对于G的任何句型都能构造与之关联的语法树(推导机)。这棵树满足下列 4个条件：1 .树中每个结点都有一个标记，此标记为VNUVT中的一个符号2 .根的标记为文法的开始符3 .若一结点n至少有一个它自己除外的子孙，并且有标记为A,则A 一定是非终结符4 .如果结点n的直接子孙，从左到右的次序是句a，界上，且分支结点的标记分别为B

5、1、B2,，Bn,则 A-B1B2Bn一定是 P中的一个产生式。6.自下而上分析算法的基本思想是什么？答：从所给符号串x开始，在其中寻找与文法的某条规则右部相匹配的子串，并用该规则的左部取代此子串(即归约)，重复此过程，步步向上归约，最后试图将符号串x归约到文法的识别符号Z。如归约成功，则符号串 x是文法的句子。7设有文法G:s:=Qc|c Q:kRb|b R:=Sa|a 试求 HARD(S),HARD(Q),HARD(R). 答：HARD(S尸S,Q,R,a,b,cHARD(Q尸S,Q,R,a,b,c HARD(R尸S,Q,R,a,b,c 8.用扩充的BNF范式表布下述文法以消去e规则：S:

6、=aABb|ab A:=Aab| e B:=Aa|a 解：S:=aABb|abA:=ab B:=Aa|a9.将词法分析做为一个独立的阶段，把编译过程的分析工作划分成词法分析和语法分析两个阶段主要的考虑因素是什么？答：1.使整个编译程序的结构更简洁、清晰和条理化。词法分析比语法分析简单的多，但 是由于源程序结构上的一些细节，常使得识别单词的工作甚为曲折和费时。例如，空白和注释的处理；再比如对于FORTRAN那种受书写格式限制的语言，需在识别单词时进行特殊处理等等。如果统统合在语法分析时一并考虑，显然会使得分析程序的结构复杂得多。2 .编译程序的效率会改进。大部分编译时间是花费在扫描字符以把单词符

7、号分离出来。把词法分析独立出来， 采用专门的读字符和分离单词的技术可大大加快编译速度。另外，由于单词的结构可用有效的方法和工具进行描述和识别，进而可建立词法分析程序的自动构造工具。3 .增强编译程序的可移植性。在同一个语言的不同实现中，或多或少地会涉及到与设备有关的特征，比如采用ASCII还是EBCDIC字符编码。另外语言的字符集的特殊性的处理，一些专用符号，如PASCAL中的"T”的表示等等，都可置于词法分析程序中解决而不影响编译程序其它成分的设计。10 .转换图容易用程序实现，最简单的办法是让每个状态结点对应一小段程序。引进一组全 局变量和过程，将它们作为实现转换图的基本成分，这

8、些变量和过程是什么？ 答：(1)ch字符变量，存放最新读进的源程序字符。(2)strToken字符数组，存放构成单词符号的字符串。(3)GetChar子程序过程，将下一输入字符读到ch中，搜索指示器前移一字符位置。(4)GetBC 子程序过程，检查 ch中的字符是否为空白。若是，则调用 GetChar直至ch 中进人一个非空白字符。(5)Concat子程序过程，将ch中的字符连接到 strToken之后。例如，假定strToken原来的值为"AB",而ch中存放着'C',经调用 Concat后，strToken的值就变为"ABC"。(6)

9、IsLetter和IsDigit布尔函数过程，它们分别判断ch中的字符是否为字母和数字。(7)Reserve整型函数过程，对strToken中的字符串查找保留字表，若它是一个保留字则返回它的编码，否则返回0值(假定0不是保留字的编码)。(8)Retract子程序过程，将搜索指示器回调一个字符位置，将 ch置为空白字符。(9)InsertId整型函数过程，将 strToken中的标识符插入符号表，返回符号表指针。(10)InsertConst整型函数过程，将 strToken中的常数插入常数表，返回常数表指针。这些函数和子程序过程都不难编制。使用它们能够方便地构造状态转换图的对应程序。一般来说，

10、可让每个状态结点对应一程序段。11 .什么是正规式，正规式的递归定义是什么？答：正规式也称正则表达式，也是表示正规集的工具。也是我们用以描述单词符号的方便工 具。下面是正规式和它所表示的正规集的递归定义。设字母表为汇，辅助字母表为汇'=，£,|,*,(,)(1) . £和都是汇上的正规式，它们所表示的正规集分别为&和中(2) .任意aC!2, a是汇上的一个正规式，它所表示的正规集为a(3) .若e1, e2都是汇上的一个正规式，它们所表示的正规集分别为 L(e1)和L(e2),那么e1|e2, e1 e2和厘，(e1)也都是正规式，它们所表示的正规集分别为

11、L(e1) U L(e2),L(e1) L(e2)和 口),L(e1)(4) .仅由有限次使用上述三步骤而定义的表达式才是汇上的正规式，仅由这些正规式所表示的字集才是汇上正规集。12 .什么是有穷自动机？什么是确定的有穷自动机？答：有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规 文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。有穷自动机分为两类：确定的有穷自动机(Deterministic Finite Automata)和不确定的有穷自动机(Nondeterministic Finite Auto

12、mata),下面我们分别给出确定有穷自动机和不确定的有 穷自动机的定义，有关概念及不确定的有穷自动机的确定化，确定的有穷自动机的化简等算法。确定的有穷自动机(DFA)一个确定的有穷自动机(DFA)是一个五元组：M= (K,汇，f, S, Z),其中(1) K是一个有穷集，它的每个元素称为一个状态；(2)汇是一个有穷字母表，它的每个元素称为一个输入字符，所以也称汇为输入符号字母 表；f是转换函数，是在 KX汇一 K上映像，即，如f (耳，a)=幻(L CK,0ck), 就意味着，当前状态为 国，输入字符为a时，将转换到下一状态 比，我们把处称作耳的 一个后继状态；(4) S C K是唯一的一个初

13、态；(5)2仁玄，是终态集，终态也称可接受状态或结束状态。13 .正规式的构造步骤是什么？答：我们把状态转换图的概念拓广，令每条弧可用一个正规式作标记。 构造步骤：第一步 在M的状态转换图上加进两个状态，一个为 x, 一个为y。从x状态出发，用 £弧连接到M的所有初始态；从 M的所有终止态出发，用 £弧连接到y状态。形成一个与 M等价的M'。第二步 逐步消去M'中的所有状态，直至只剩下 x和y状态。在消结过程中，逐步用正 规式来标记弧。消结的规则如下：最后x和y结点间的弧上的标记则为所求的正规式Ro14 .举例说明判断LL(1)文法的步骤。答：S 一 ABS

14、 f bCA- £AfbB 一 £BfaDC f ADC f bD 一 aSD-c判别步骤：1 . 求出能推出£的非终结符首先建立一个以文法的非终结符个数为上界的一维数组，其数组元素为非终结符，对应每一个非终结符有一标志位，用来记录能否推出8 ,其值有三种情况"未定"，"是"，"否"。例1所对应数组X的内容如表一所示。表一非终结符能否推出空的表计算能推出£的非终结符步骤如下:(1)将数组X中对应每一个非终结符的标记置初值为"未定”(2)扫描文法中的产生式 删除所有右部含有终结符的产生式

15、，若这使得以某一非终结符为左部的所有产生式都被删除，则将数组中对应该非终结符的标记值改为"否"，说明该非终结符不能推出£ o若某一非终结符的某一产生式右部为£ ,则将数组中对应该非终结符的标志置为”是”,并从文法中删除该非终结符的所有产生式。例中对应非终结符A、B的标志改为"是"。(3)扫描产生式右部的每一符号 若所扫描到的非终结符在数组中对应的标志是"是"，则删去该非终结符， 若这使产生式右部为空，则对产生式左部的非终结符在数组中对应的标志改为"是"，并删除该非终结符为左部的所有产生式。 若所

16、扫描到的非终结符在数组中对应的标志是"否"，则删去该产生式，若这使产生式左部非终结符的有关的产生式都被删去，则把在数组中该非终结符对应的标志改成"否"。(4)重复(3),直到扫描完一遍文法的产生式，数组中非终结符对应的特征再没有改变 为止。由2)中得知例中对应非终结符 D的标志改为"否"。经过上述2)中(a)、(b)两步后文法中的产生式只剩下：S-AB C-AD也就是只剩下右部全是非终结符串的产生式。再由3)中的(a)步扫描到产生式 S-AB时，在数组中A、B对应的标志都为"是"，删去后 S的右部变为空，所以 S对

17、应标志置为"是"。最后由3)中的(b)扫描到产生式 C-AD时，其中，A对应的标志为"是"，D对应的标志是" 否"，删去该产生式后，再无左部为C的产生式，所以 C的对应标志改成"否"。15 .如何计算FIRST集答：根据定义计算由 FIRST 集定义 FIRST ( a )=a| a => * a 3 , a V? ,”， 3CV*若 a => * s ,则规定 s FIRST( “)。对每一文法符号 XCV,计算FIRST(X)(a)若 XC Vt ,则 FIRST(X)=X(b)若 X C VN ,

18、且有产生式 X - a,aC VT ,则 aC FIRST(X)(C)若 XC VN ,且有产生式 X- e ,则 e C FIRST(X)(d)若 XC %, yi 丫2,YiC Vn ,而有产生式 X-Y1Y2Yn。当 Y1Y2 丫/ 者 B=> 'e 时，(其中 IWiWn),则 FIRST(Y1)- £ , FIRST(Y2)- £ ,FIRST 工-1 )- £ , FIRST(Yi)都包含在 FIRST(X)中。(e)当(d)中所有 Yi=> * e(i=1, 2, .n),则FIRST(X)= FIRST(Y1) U FIRST(

19、Y2) UU FIRST(Yn) U £反复使用(a)-(e)步，直到每个符号的 FIRST集合不再增大为止16 . PL/ 0编译程序对语法错误的处理采用哪两种办法？答：(1)对于一些易于校正的错误，如丢了逗号、分号等，则指出出错位置，并加以校正。校正的方式就是补上逗号或分号。(2)对某些错误，编译程序难于确定校正的措施，为了使当前的错误不致影响整个程序的 崩溃，把错误尽量局限在一个局部的语法单位中。这样就需跳过一些后面输入的单词符号， 直到读入一个能使编译程序恢复正常语法分析工作的单词为止。17 .解释说明下列指令 LIT、LOD、STO、CAL、INT、JMP、JPC、OPR?

20、答：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,其句型的素短语是一个短语，它至少包含一个终结符

21、，并除自身外不 包含其他素短语。最左边的素短语称最左素短语。20 .简述LR(1)项目集族的构造？答:(1)构造LR(1湮目集的闭包函薮.a)若I的任何项目都属于CLOSUREDb)有项目AfQ. A 6，a属于CLOSURED)，BY是文法中的产生式，0三¥*,b三FIRST。a)则Bf ¥.b也属于CLOSURE(；】)中.c)重复垃直到CLO£URE( I)不再增大为止.(2)转换函数的构造LR(1)转换函数的构造与 LR(0)的相似，GO(I , X) = CLOSURE( J )其中I是LR(1)的项目集，X是文法符号：J= 任何形如A-aX. 3, a

22、的项目 | A-a.X3,a CI对文法G'的LR(1)项目集族的构造仍以S'一. S, #为初态集的初始项目，然后对其求闭 包和转换函数，直到项目集不再增大。也就是对状态I经过符号X后转向状态J,求出J的核后，对核求闭包即为 CLOSURE(J)。21 . L-属性文法的定义是什么？答：一个属性文法称为 L-属性文法，如果对于每个产生式A-X1X2Xn,其每个语义规则中的每个属性或者是综合属性，或者是 Xj(1 wjwn)的一个继承属性且这个继承属性仅依赖 于：(1)产生式Xj的左边符号X1, X2,，Xj-1的属性；(2)A的继承属性。22 .要提高访问符号表的效率和节省存储空间，要考虑哪些问题？答：首先，要考虑程序设计语言的性质， 它包含哪些语法成分， 应该进行哪些语义真缺性检 查等等；其次，不能离开支撑环境，如目标机器的性能怎样， 将借助符号表产生怎样的目标 代码，编译程序所依赖的操作，系统能提供哪些存储、管理方式等等。23 .常见的符号表的结构有哪些？答：常见的符号表结构有：无序符号表：是按标识符出现的顺序建立符号表有序符号表：建表时，各标识符名按字典顺序排列于符号表中栈符号表：对于分析程序(或过程)嵌套结构型程序设计语言，将其符号表设计为栈式符号表。总是从栈顶加入；而查找则从栈顶向底检查)。24 .什么是静态存储分配？答：在