北京工业大学编译原理考试一纸开卷【期末复习总结】

1、简要解释编译程序中的遍（趟)的含义.就是对源程序或者源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果和目标程序.通常,每遍的工作有外存上获得的前一遍的中间结果开始,完成它所含的有关工作之后，再把结果记录于外存。.也可以把一个阶段的工作分为若干遍。2、何为“标识符”？何为“名字"？两者的区别是什么？在程序设计语言中,标识符是一个最基本的概念，其定义为:凡以（有限个字符)识符以确切的含义时,这个标识符就叫做名字.程序语言中各种名字都是用标识符表示的，只是标识符是一个没有意义的字符序列,而名字却有着确切的意义和属性。3文法?这是由于在自顶向下的语法分析技术中，要解决的问题是根据当前输入符号判断将栈顶（最左）的非终结符号替换成哪条规则的右部，若文法具有左递归，则在分析过程中，无法判断出替换的规则,造成无穷递归求解的过程.4、简述编译程序的工作过程分解,识别出一个个的单词;②语法分析,根据语言的语法规则，把即对各类语法单位,,把中间代码变换成特定机器上的低级语言指令形式。5、什么是语法制导翻译？,翻译。由于使用属性文法时把语法规则和语义规则分开，但在使用语法规则进行推导或归约的同时又使用这些语义规则来指导翻译与最终产生目标代码，所以称为语法制导翻译.6、请简要阐述高级程序设计语言参数传递的常用方式1、传值：计算实参并将其右值传递给被调用过程2、传地址：调用过程将实参地址传递给被调用过程3、传值结果：将传值和传地址两种方式结合4、传名：只有在被调用过程中用到形参时才动态的建立起它与实参的联系7、什么是自展?什么是交叉编译？自展过程就是用低级语言先实现一个简单的编译器,然后用这个编译器的语言再去编写一个更高级的编译器—这个新编译器是旧编译器的扩展——的过程.编译器的运行环境与产生程序的运行环境不同的编译过程叫做交叉编译8是什么？解释和编译。解释不生成目标代码。9示？

主要需要解决回溯与左递归。回溯：匹配多个候选式无法快速匹配；左递归:推导过程无休止。解决:提取公共左因子、消除直接及间接左递归.翻译程序：能够把某种语言转换成另一种语言，而后者与前者在逻辑上是等价的。语义分析与中间代码产生：对语义分析所识别出的各类语法范畴，分析其含义并进行初步翻译（产生中间代码）编译程序结构:表格管理、出错处理编译前端:括词法分析、语义分析、语义分析与中间代码产生。后端:编译程序中与目标语言有关那些部分，优化与目标代码生成。后端不依赖于源语言而仅仅依赖于中间语言。词法规则是指单词符号的形成规则.语言的语法规则规定了如何从单词符号形成更大的结构（位。二义性：如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。LL（1)的含义：第一个L表示从左到右扫描输入串，第二个L表示最左推导,1表示分析时每一步只需向前查看一个符号限循环②回溯浪费分析时间③某一非终结符用某一候选式匹配成功时，可能是暂时的④分析不成功时，难以找到出错位置自下而上分析的问题：怎样判断栈顶的符号串的可归约性，以及如何归约。一个句型的最左直接短语称为该句型的句柄.在形式语言中最右推导常被称为规范推导（最右推导的逆过程必是规范归约(最左归约）输入串-———-语法树-——————依赖图-—-—--—-语义规则计算次序最左规约=规范规约：A最右推导=规范推导：B短语：子树的末端结点形成的符号串．短语相对的句型：整个树的末端结点．简单子树：只有一层分支的子树简单短语（直接短语）:简单子树的末端结点形成的符号串．句柄：最左直接短语,外不再含任何更小的素短语例题1、构造下面文法的LL(1）分析表。D→TL T→int｜real L→idR R→,idR｜εFIRST(D）=FIRST(T）={int，real｝FIRST(L）=｛id｝FOLLOW（T）=｛id}FIRST(R）=｛,,ε}FOLLOW（R）=｛＃｝注意当FIRST(X）含ε还需要看FOLLOW（X)非终结符 输入符号int real id ， #

S→(L）｜a L→L,S|S试写出一个语法制导定义,它输出配对括号个数为S、L引入属性h,代表配对括号个.语法制导定义如下产生式 语义规则S→(L） S.h：=L。h+1S→ a S.h：=0L→L1S L.h:=L1.h+S。hL→S L.h:=S.hS’→S print(Sh)例题4、S→aS|bS｜a(1）构造该文法的LR（0）项目集规范族（2）构造识别该文法所产生的活前缀的DFA.(3）SLRSLR（1）1G(SG(：DD→TLD→TLS’→S S→aS S→bS S→aTLRT→intT→realL→idRR→,idRR→ε例题2、已知文法：A→aAa｜ε（1）该文法是LL（1）文法吗？为什么？（2)若采用LL(1）分析表？若输入符号串“a.1、不是,→aA|εFOLLOW（A)={#｝∪FIRST(a)=｛a,#}造成 FIRST(A）∩FOLLOW(A）=｛A, ε}∩｛a，2、修改文法为A→aaA｜εFOLLO（）={#}∪FOLLOW(A)=＃，因而FIRST（A)∩FOLLOW（A)=｛a, 3、步骤 分析栈 输入串 产生式动作#A aaaa# A→aaA#Aaa aaaa# 匹配＃Aa aaa＃ 匹配＃A aa＃ A→aaA#Aaa aa# 匹配#Aa a# 匹配#A ＃ →ε＃ # 接受例题3、例7文法G的产生式如下：

23I1存在“移进—归纳”冲突，计算S的FOLLOW合：FOLLOW(S）={#}可以采用SLR冲突消解法，得到表5.1所列的SLR分析表。从分析表可以看出,表中没有冲突项，所以该文法是SLR(1)文法。移进归约冲突的解决以I1为例：可移进S—〉a