《编译原理引论教学资料》简答题

《《编译原理引论教学资料》简答题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1.编译程序在逻辑上由哪几部分组成？请简述每部分的功能。编译程序和解释程序有哪些区别？词法分析器，又称扫描器，输入源程序，进行词法分析，输出单词符号。语法分析器，简称分析器，对单词符号串进行语法分析（根据语法规则进行推导或归约），识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序”。语义分析和中间代码产生器，按照语义规则对于法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中加代码。优化器，对中间代码进行优化处理目标代码生成器，把中间代码翻译成目标程序。表格管理：编译程序

2、在工作过程屮需要保持一系列的表格，以登记源程序的各类信息和编译各结点的进展状况。一个编译程序不仅应能对书写正确的程序进行翻译，而且应能对出现在源程序中的错误进行恢复。如果源程序有错误，编译程序应设法发现错误，把有关错误信息报告给用户，这就是由错误处理程序完成的。编译程序和解释程序的区别：编译程序以一个可执行程序的描述作为输入，以另一个等价的可执行程序的描述作为输出。以某种语言（源语言程序）转变成为另外一种语言程序（目标语言程序），而后者与前者在逻辑上是等价的。解释程序以一个可执行程序的描述作为输入，但是

3、不产生目标程序，而是边解释边执行，以执行这一可执行程序描述的结果作为输出。2.简述为什么自顶向下的语法分析技术不能处理具有左递归的文法。答：在自顶向下的语法分析技术中，要解决的问题是根据当前输入符号判断将识别符号以及非终结符号替换成哪条规则的右部，若文法具有左递归，则在分析过程中，无法判断替换的规则，造成无穷递归求解过程。3・简要叙述语法分析的基本功能是什么？对于同一个文法，LALR（l）和SLR（l）的分析表状态个数相同，为什么前者的分析能力要比后者强？答：语法分析的基本功能是：a）语法分析处于词法分

4、析和语义分析之间，它的输入是词法分析的输出，它的输出是语义分析的输入。（1分）b）词法分析对输入的字符串进行分析，判断是否一个合法的输入。其中合法是指输入的字符串是否符合程序设计语言的语法规定（或者文法的规定）。（3分）c）对于不符合语法的字符串要设计错误处理机制。其分析方法包括自顶向下和自底向上分析两种。（1分）LALR(l)比SLR(l)分析能力强的原因：在构造分析表时，SLR(l)中的规约项填写的是全体FOLLOW(A)集合中的符号，这样就增加了移动■规约冲突的可能性。(2分)而对于LALR(l)

5、,虽然分析表状态和SLR(l)同样多，但是它釆用了向前搜索符技术，使得规约项填写的只是FOLLOW(A)集合的子集，而且大部分时间下是真子集，这就使得产生移动■规约冲突的可能性减少，因此更加精确,所以分析能力更强。(3分)4.通过合并LR(1)文法中的同心状态得到的LALR(l)文法可能会产生哪些冲突？一定不会产生哪些冲突？为什么？答：可能会产生归约■归约冲突，一定不会产生移进■归约冲突。因为在对LR(1)合并同心集合时，有可能将原本没有冲突的同心集的项目集合并后造成一些归约项目向前搜索符集合的交集不是

6、空，产生归约■归约冲突。但是由于文法木身已经是LR(1)文法，因此可知，在项目集中一定不存在移进・归约冲突，也就是移进项目要求输入的终结符和任意归约项目的向前搜索符集合的交集都是空集。这样，在将同心集合并之后，移进项冃要求输入的终结符和归约项目的向前搜索符集合的交集也述是空集。5.何谓二义性文法？试举一例说明。答：若文法G的一个句子对应有两棵或两棵以上不同的推导树，则称该句子是二义性的。产生二义性句子的文法称为二义性文法，否则该文法是无二义性的。例子：E・・・i

7、E+E

8、E*Ei*i+i的推导6.设€1

9、=(Vn，Vt,P,)是上下文无关文法，产生式集合P中任意一个产生式应具有什么样的形式？若G是正则文法呢？答：上下文无关文法的产牛式形式为：A->a,其中，AWVn，ae(VNUVT)*正则文法产生式形式为：A—aB,或A->a(右线性文法)其中，A,BWVn，aGVTA->Ba,或A->a(左线性文法)其中，A,B^Vn，aevT7.试简单描述LL(1),LR(1),SLR(l)和LALR⑴的定义。并说明它们是怎么解决分析表中的冲突的。LL(1)定义：一个文法G是LL(1)的，当且仅当对于G的每

10、一个非终结符A的任何两个不同产生式A—>a

11、卩，下面的条件成立：SELECT(A->a)ASELECT(A->卩戶，其中，a

12、卩不能同时8oSLR(l)定义：满足下面两个条件的文法是SLR(l)文法a.对于在s屮的任何项目AtolX

13、3,当X是一个终结符，且X在Follow(B)屮时,s中没有完整的项目B->r.b.对于在s中的任何两个完整项目A->(x.和B->p.,Follow(A)nFollow(B)为空。LL(1)就是向前只搜索1个