编译小抄

习题八：1，符号表的组织方式不包括（按标识符名称）方式。包括（按标识符种属，直接，间接）方式。2，分程序结构的高级语言中，编译程序使用（说明标志符的过程或函数的静态层次）来区别标识符的作用域3，在常用的符号表构造和处理方法中，（有序）符号表常把符号表组织成二叉树形式4，在目标代码生成阶段，符号表用于（地址分配）5，错误的局部化是指（当发现错误时，跳过错误所在的语法单位继续分析下去）习题六：1，分配目标程序数据空间的基本策略分为（静态分配和动态分配）2，过程DISPLAY表中记录了（过程的嵌套层次）3，过程P1调用P2时，链接数据不包括（嵌套层次显示表）包括（老SP值，返回地址，全局DISPLATY表地址）4，堆式动态分配申请和释放存储空间遵守（任意）原则5，栈式动态分配与管理在过程返回时应做的工作有（恢复老SP）6，如果活动记录中没有DISPLAY表，则说明（程序中不允许有嵌套定义的过程）习题五：1，优化可生成（运行时间短且占用存储空间小）的目标代码2，下列优化方法中不是针对循环的是（删除多余运算）3，对一个基本块来说，（有一个入口语句和一个出口语句）是正确的4，（无条件转移语句后的下一条语句）不能作为一个基本块的入口5，基本块内的优化为（删除多余运算，删除无用赋值）6，在程序流程图中，称具有（强连接的且只有一个入口结点）的结点序列为一个循环。习题四：1，中间代码的优点（编译结构在逻辑上更为简单明确）2，四元式之间的联系是通过（临时变量）实现的3，间接三元式表示法的优点为（采用间接码表，便于优化处理）4，表达式(-|AVB)N(CVD)的逆波兰表达式为（A-|BVCDVN）5，后缀式（ab@c*-）对应得中缀表达式是a-（-b）*c6，后缀式ab+cd+/可用中缀表达式（(a+b)/(c+d)）来表示7，表达式（a+b）*c的后缀表达式为（ab+c*）8，中间代码生成时所依据的是（语义规则）9，四元表达式的优点为（便于优化处理也便于表的变更）10，（重点）有一语法制导翻译如下所示，若输入序列为b(((aa)a)a)b.......(34242421)习题三：1，程序语言的语义需要用（上下有关文法）来描述2，2型文法对应（下推自动机）3，下述结论中，（均不成立）是正确的4，有限状态自动机能识别（正规文法）5，（重点）文法G[S]:S-xSx|y所识别的语言是（x^nyx^n(n=0)）6，只含有单层分枝的子树称为“简单子树”，则句柄的直接解释是（最左简单子树的末端结点组成的符号串）7，下面对语法书说法错误的描述是（内部结点可以是非终结符）8，由文法开始符S经过零步或者多步推导出来的符号序列是（句型）9，设文法G[S]:S-SA|AA-a|b则对句子的规范推到是（S-SA-Sa-SAa-Sba-Aba-aba）10，（重点）如果文法G[S]是无二义的，则它的任何句子a其（最左推导和最右推导对应的语法树必定相同）11，一个句型的分析树代表了该句型的（推倒过程）12，规范规约中的“可规约串”由（最左直接短语）定义13，规范规约是指（最右推导的逆过程）14，文法G[S]:S-aAcB|BdA-AaB|cB-bScA|b则句型aAcbBdcc的短语是（Bd）15，文法G[E]:E-E+T|TT-T*p|pp-(E)|i则句型P+T+i的句柄和最左素短语是（P和P+T）16，采用自顶向下分析，必须（消除做递归）17，对文法：G[E]:E-E+S|SS-S*F|FF-(E)|i则FIRST(S)=（{{，i}）18，确定的自顶向下分析要求文法满足（A-C）19，递归下降分析器由一组递归函数组成，且每一个函数对应的文法的（一个非终结符）20，LL（1）分析表需要预先定义和构造两族与文法有关的集合（FIRSR和FOLLOW）21，设a，b，c是文法的终结符且满足优先关系a=bb=c则（A-C都不成立）22，算符优先分析法要求文法（不存在...QR...的句型且任何终结符对(a,b)至多满足a=b,ab,ab三种关系之一）23，任何算符优先文法（可能有若干个）优先函数24，在算符优先分析中，用（最左素短语）来刻画可归约串25，下面最左素短语必须具备的条件中有错误的是（至少包含一个非终结符）26，对文法G[S]:S-b|n|(T)T-T,S|S其FIRSTVT（T）为（{，，b，n，(}）27，（重点）对于文法G[S]:E-E*T|TT-T+i|i句子1+2*8+6归约的值为（42）28，下述FOLLOW集构造方法中错误的是（若有A-aB，则有FOLLOW(B)FOLLOW(A)）29，若对文法G[S]的产生式有...AB...出现，则对A求FOLLOW集正确的是（FIRST(B)\{...}FOLLOW(A)）30，下面（算符优先分析法）是自底向上分析法31，下面（SLR（1）分析法）是采用句柄进行的归约的32，一个（项目）指明了在分析过程中某时刻能看到产生式多大一部分33，若B为非终结符，则A-a·Bp为（待约）项目习题二：1，词法分析所依据的是（构词规则）2，词法分析器的输入是（源程序）3，词法分析器的输出是（单词的种别编码和自身的值）4，状态转化图接受的字符集为（含偶数个0的二进制组成的集合）5，对于任一给定的NFAM，（一定存在）一个DFAM‘使L(M)=L(M’)6，DFA适用于（词法分析）7，下面用正规式描述词法的论述中，不正确的是（正规表达式描述能力强于上下文无关文法）8，与(a|b)*(a|b)等价的正规式是（(a|b)(a|b)*）9，在状态转化图的实现中（含回路的状态结点）一般对应一个循环语句10，已知DFAMd={s0,s1,s2},{ab}...........可以用正规表达式表示为（aa(a|a)*）习题一：1，下列叙述中正确的是（编译程序是将高级语言程序翻译成等价的机器语言程序的程序）2，将编译程序分成若干个“遍”是为了（使编译程序结构更加清晰）3，构造编译程序应掌握（以上三项）4，编译程序绝大多数时间花在（表格管理）上5，编译程序是对（高级语言的翻译）重点例题：例3.7与例3.8合G[E]:E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)∣i构造FIRST集。(1)FIRST(E')={+,ε};FIRST(T')={*,ε};FIRST(F)＝{(,i};(2)由T→F…和E→T…知FIRST(F)属于FIRST(T)属于FIRST(E)，即有FIRST(T)属于FIRST(E)={(,i}构造FOLLOW集：1)FOLLOW(E)={#};2)由E→TE'知,FIRST(E')\{ε}属于FOLLOW(T),即FOLLOW(T)＝{+};由T→FT'知,FIRST(T')\{ε}属于FOLLOW(F),即FOLLOW(F)＝{*};由F→(E)知,FIRST(‘)’)属于FOLLOW(E),即FOLLOW(E)＝{),#};3)由E→TE'知,FOLLOW(E)属于FOLLOW(E'),即FOLLOW(E')＝{),#};由E→TE'且E'→ε知,FOLLOW(E)属于FOLLOW(T),即FOLLOW(T)＝{+,),#};由T→FT'知,FOLLOW(T)属于FOLLOW(T')，即FOLLOW(T')＝{+,),#};由T→FT'且T'→ε知,FOLLOW(T)属于FOLLOW(F),即FOLLOW(F)＝{*,+,),#}；构造LL(1)分析表FIRST(E')={+,ε}FIRST(T')={*,ε}FIRST(F)＝{(,i}FIRST(T)={(,i}FIRST(E)={(,i}FOLLOW(E)＝{),#};FOLLOW(E')＝{),#}FOLLOW(T)＝{+,),#}FOLLOW(T')＝{+,),#}FOLLOW(F)＝{*,+,),#}符号栈当前输入符号输入串#Ei1+i2*i3##E’Ti1+i2*i3##E’T’Fi1+i2*i3##E’T’ii1+i2*i3##E’T’+i2*i3##E’+i2*i3##E’T++i2*i3##E’Ti2*i3##E’T’Fi2*i3##E’T’ii2*i3##E’T’*i3##E’T’F**i3##E’T’Fi3##E’T’ii3##E’T’##E’###例3.17试构造文法G[S]的LR(0)分析表:G[S]:S→BBB→aB∣b解:将文法G[S]拓广为文法G'[S']：G'[S']:(0)S'→S(1)S→BB(2)B→aB(3)B→b该文法的LR(0)项目集规范族为:I0:S‘→·SS→·BBB→·aBB→·bI1:S’→S·I2:S→B·BB→·aBB→·bI3:B→a·BB→·aBB→·bI4:B→b·I5:S→BB·I6:B→aB·例2.8正规式(a|b)*(aa|bb)(a|b)*的NFAM如下:试将其确定化为DFAM'。用子集法将上述NFAM确定化为重命名为:例2.9化简由例2.8得到的DFA。(1)先将状态集S={0,1,2,3,4,5,6}划分为终态集{3,4,5,6}和非终态集{0,1,2}。(2)考察{0,1,2}a:因{0,2,1}a={1,3}不属于{3,4,5,6}和{0,1,2},故将{0,1,2}划分为{0,2}和{1}。(3)考察{0,2}b:因{0,2}b={2,4},不属于已划分出的某个子集,故{0,2}划分为{0}和{2}。(4)考察{3,4,5,6}a：{3,4,5,6}a={3,6},属于{3,4,5,6},故不划分。(5)考察{3,4,5,6}b：{3,4,5,6}b={4,5},属于{3,4,5,6},故不划分。(6)按顺序把状态子集{0},{1},{2},{3,4,5,6}重命名为0,1,2,3,得到化简后的DFAM'':第六章：目标程序运行时存储空间的组织从编译角度看，程序语言关于名字的（作用域）和（生存期）的定义规则决定了分配目标程序数据空间的基本策略。不允许可变体积……叫做静态分配策略允许可变体积的数据……叫做动态策略数据空间动态分配与栈顶……叫做栈式动态分配策略允许用户动态申请释放空间……叫做堆式动态分配策略静态分配条件：1，数组的上下界必须是常数。2，过程不允许递归。3，不允许采用动态的数据结构。嵌套过程语言的栈式实现每进入一个过程后，在建立它的活动记录区的同时建立一张（嵌套层次DISPLAY表），将记录它所有（外层过程最新活动其实地址位置的SP值）都放在这张嵌套层次DISPLAY表中，这样就可直接在本层查到它的任何一个外层过程最新活动记录的起始位置。第五章：代码优化代码优化的含义：对代码进行（等价变化），使得变化后的代码具有更高的（时间效率和空间效率）。代码优化的目的是提高目标程序的质量。优化分为局部优化，循环优化，全局优化。基本块的优化就是全局优化。所谓基本块，是指程序中一（顺序执行）的语句序列，其中只有一个入口和一个出口。循环优化：1，代码外提：循环中的代码要随着循环反复执行，但其中某些运算的结果并不因为循环而改变，对于这种不随循环变化的运算，可以将其外提到循环外。2，强度削弱：强度削弱是指把程序中执行时间较长的运算替换为执行时间较短的运算。3，删除归纳变量：如果循环中对变量I只有唯一的形如I=I+-C的赋值，且其中C为循环不变量，则称I为u循环中的基本归纳变量。第四章：语义分析和中间代码生成如果静态语义正确，则直接生成（中间代码）或（目标代码）静态语义检查实在编译时完成的，涉及以下：1，类型检查。2，控制流程检查（保证控制语句有合法的转向点）。3，一致性检查。语义分析只产生中间代码。由于语义是上下文有关的。用（属性文法）作为描述程序语言语义的工具。（语法制导翻译）为每一个产生式配上一个翻译子程序，并在语法分析的同时执行这些子程序。（语法制导翻译）分为自底向上语法知道翻译和自顶向下（重点）语法制导翻译LR分析栈存放三类信息：分析状态，文法符号，语义值文法符号的属性可分为（继承属性）和（综合属性）三地址代码：X=yopz两个用来存放运