编译原理复习题及参考标准答案教学文案Word格式.docx

1、32.每条指令的执行代价定义为 。33.算符优先分析法每次都是对 进行归约。三、名词解释：1.局部优化2.二义性文法3.DISPLAY表4.词法分析器5.最左推导6.语法7.文法8.基本块9.语法制导翻译10.短语11.待用信息12.规范句型13.扫描器14.超前搜索15.句柄16.语法制导翻译17.规范句型18.素短语19.语法20.待用信息21.语义四、简答题：1.写一个文法G,使其语言为不以0开头的偶数集。2.已知文法G（S）及相应翻译方案 SaAb print “1”Sa print “2”AAS print “3”Ac print “4”输入acab,输出是什么？3.已知文法G（S）

2、SbAaA（B | aBAa）写出句子b（aa）b的规范归约过程。4.考虑下面的程序： Procedure p（x, y, z）； beginy:=x+y;z:=z*z; endA:=2;B:=A*2;P（A, A, B）;Print A, B end.试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出A,B的值是什么？5.文法GSSdABAaA| a BBb| 描述的语言是什么？6.证明文法GS SSaS| 是二义性的。7.已知文法GS SBA ABS| d BaA| bS | c 的预测分析表如下 a b c d # SSBA AABSAd BBaA BbS Bc给出句子 adc

3、cd 的分析过程。8.写一个文法G, 使其语言为 L（G）=albmclanbn| l=0, m=1, n=2 9.已知文法G（S）:Sa| （T）TT,S|S的优先关系表如下：关系a（）,-.0为奇数， m0为偶数22.写出表达式a:=（b+c）*e+（b+c）/f的逆波兰式和三元序列。23.一个文法G别是LL（1）文法的充要条件是什么？24.已知文法GSSS*aF | aF | *aFF+aF | +a消除文法左递归和提公共左因子。25.符号表的作用是什么？符号表查找和整理技术有哪几种？五、计算题：1.设文法GS: S | a | （T） TT,S | S 消除左递归； 构造相应的FIRS

4、T和FOLLOW集合； 构造预测分析表 2.语句 if E then S（1）改写文法，使之适合语法制导翻译；（2）写出改写后产生式的语义动作。3.设文法GS：S（T） | aTT+S | S（1）计算FIRSTVT 和LASTVT；（2）构造优先关系表。4.设某语言的for语句的形式为for i:E（1） to E（2） do S其语义解释为 i:E（1） LIMIT:E（2）again: if iLIMIT thenBeginS;i:i1goto againEnd;（1）写出适合语法制导翻译的产生式；（2）写出每个产生式对应的语义动作。5.把语句 while a0 then a:=a+1

5、else a:=a*3-1;翻译成四元式序列。6.设有基本块D:=A-CE:=A*CF:=D*ES:=2T:Q:G:=2*SJ:=T*QK:=G*5L:=K+JM:=L假设基本块出口时只有M还被引用，请写出优化后的四元序列。7.已知文法G（S）Sa | | （T）TT,S | S（1）给出句子（a,（a,a）的最左推导； （2）给出句型（T,S）,a）的短语, 直接短语，句柄。8.对于C语言do S while E语句9.已知文法GS: SaAcBe AAb| b Bd （1）给出句子abbcde的最左推导及画出语法树； （2）给出句型aAbcde的短语、素短语。10.设文法GS: S（T）

6、| aS | a 消除左递归和提公共左因子； 构造相应的FIRST和FOLLOW集合； 构造预测分析表。11.把语句if X0 Y0 do X:=A*3 else Y:=B+3;12.已知文法GS: EE+T | T TT*F| F F（E）| i （1）给出句型（i+i）*i+i的最左推导及画出语法树； （2）给出句型（E+T）*i+F 的短语，素短语和最左素短语。13.设文法GS： ST | ST TU |TU Ui |-U参考答案1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 1.

7、（最右推导）2.（词法分析），（语法分析），（中间代码生成），（代码优化），（目标代码生成）3.（二义性的）4.（执行性），（说明性）5.（单词符号），（语法单位）。6.（源程序），（单词符号）7.（类型、种属、所占单元大小、地址）8.（现行活动记录地址和所有外层最新活动记录的地址）9.（句柄）10.（栈式），（堆式）11.（类型），（作用域）12.（传地址），（传值），（传名）13.（局部优化），（循环优化），（全局优化）14.（自上而下），（自下而上）15.（分析表），（符号栈）16.（传地址），（传值），（传名）17.（初），（终）18.9局部优化），（循环优化），（全局优化）19.（语

8、法），（语义）20.（句柄）21.（LL（1） 文法）22.（静态），（动态）23.（二义性文法）24.（规范推导），（规范）25.（自上而下），（自下而上）26.（句子）27.（从开始符号出发，向下推导，推出句子）28.（单词符号），（语法单位）29.（局部优化）30.（分析表），（符号栈）31.（上下文无关文法），（正规）32.（指令访问主存次数加1）33.（最左素短语）1.局部优化：局限于基本块范围的优化称。2.二义性文法：如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义性文法。3.DISPLAY表：过程的嵌套层次显示表，记录该过程的各外层过程的最新活动记录的起始地址。4

9、.词法分析器：执行词法分析的程序。5.最左推导：任何一步=都是对中的最右非终结符替换。6.语法：一组规则，用它可形成和产生一组合式的程序。7.文法：描述语言的语法结构的形式规则。8.基本块：指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就是其中的第一个语句，出口就是其中的最后一个语句。9.语法制导翻译：在语法分析过程中，根据每个产生式所对应的语义子程序进行翻译的办法叫做语法制导翻译。10.短语：令G是一个文法，S划文法的开始符号，假定是文法G的一个句型，如果有SA且A，则称是句型相对非终结符A的短语。11.待用信息：如果在一个基本块中，四元式i对A定值，四元式j要引用A值，而从

10、i到j之间没有A的其它定值，则称j是四元式i的变量A的待用信息。12.规范句型：由规范推导所得到的句型。13.扫描器：14.超前搜索：在词法分析过程中，有时为了确定词性，需超前扫描若干个字符。15.句柄：一个句型的最左直接短语。16.语法制导翻译：在语法分析过程中，根据每个产生式所对应的语义程序进行翻译的方法 叫做语法制导翻译。17.规范句型：18.素短语：素短语是指这样一个短语，至少含有一个终结符，并且，除它自身外不再含任何更小的素短语。19.语法：是组规则，用它可形成和产生一个合式的程序。20.待用信息：21.语义：定义程序的意义的一组规则。1.所求文法是GS:SAB |B A0AAD |

11、CB2 |4 |6 |8C1 |3 |5 |7 |9 |BD0 |C2.输出是42313.句子b（aa）b的规范归约过程：步骤符号栈输入串动作#b（aa）b#预备1#b（aa）b#移进2#b（aa）b#3#b（aa）b#4#b（A归约5#b（Mab）b#6#b（Ma）b#7#b（B8#bA9#bAb10#S接受4.传地址 A=6, B=16传值 A=2, B=45.L（G）=danbm |n0, m06.证明：因为文法GS存在句子aa有两个不同的最左推导，所以文法GS是是二义性的。S=SaS=SaSaS=aSaS=aaS=aa S=aS=7.句子 adccd 的分析过程：产生式adccd#AB

12、#AAa#AAdccd#Ad#Accd#SB#Scccd# Bccd#Acd#11#A 12#d13 # 8.所求文法是GS: SAB AaAc | D DbD | bBaBb | aabb9.函数fg10.优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。三种级别：局部优化、循环优化、全局优化11.目标代码通常采用三种形式：机器语言，汇编语言，待装配机器语言模块。应着重考虑的问题：（1）如何使生成的目标代码较短；（2）如何充分利用寄存器，以减少访问内存次数；（3）如何充分利用指令系统的特点。12.正规式 a （ a | b ）*。13.删除多余运算，代码外提，强度

13、削弱，变换循环控制条件，合并已知量，复写传播和删除无用赋值。14.文法GS:S aB | a Bbc |bBc15.传值 a=2 传地址 a=1516.逆波兰式: abcd-*e/+三元序列: op arg1 arg2 （1） - c d （2） * b （1） （3） / （2） e （4） + a （3）17.证明：因为文法GS存在句子 （） 有两个不同的最左推导，所以文法GS是是二义性的。A=AA=（A）A=（）A=（） A=（A）=18.（a*b|b*a）=a,b,ab,ba,aab,bba19.Display表: 嵌套层次显示表由于过程嵌套允许内层过程引用外层过程定义的数据，因此，当

14、一个过程运行时必须跟踪它的所有外层过程的最新活动记录起始地址， display表就是用于登记每个外层过程的最新活动记录起始地址。20.传地址 a=12传值 a=521.所求文法是GS: SAC AaaAbb | ab CccC | cc22.逆波兰式 abc+e*bc+f/+:=三元序列 op arg1 arg2 （1） + b c （2） * （1） e （3） + b c （4） / （3） f （5） + （2） （4） （6） := a （5） 23.一个文法G别是LL（1）文法的充要条件是: （1） FIRST（） FIRST（）= （2） 如果 =*, FIRST（） FOLLOW

15、（A）= 24.消除左递归SaFS | *aFSS*aFS | 提公共左因子,文法 GS F+aFFF |25.作用：登记源程序中出现的各种名字及其信息，以及了解各阶段的进展状况。主要技术：线性表，对折查找，杂奏技术。1（1）消除左递，文法变为GS：S | a | （T）TST | ST,ST |此文法无左公共左因子。（2）构造相应的FIRST和FOLLOW集合：FIRST（S）=a, , （， FOLLOW（S）=#, , ）FIRST（T）=a, , （ ，FOLLOW（T）=FIRST（T）=, ，FOLLOW（F）=）（3） 构造预测分析表：SSaSS（T）TTSTTTT,ST2. （

16、1）Cif E thenSCS（1） （2） Cif E then BACK（E.TC, NXQ）; C.chain:=E.FC SCS（1） S.chain:=MERG（C.Chain, S（1）. Chain）3. （1） FIRSTVT（S）=a, （ FIRSTVT（T）=+, aa, （ LASTVT（S）=a, ） LASTVT（T）=+, a, ） + （ ） .+ 4. （1） Ffor i:=E（1） to E（2） do SFS（1）（2）Ffor i:GEN（:=, E（1）.place, _, entry（i）;F.place:=entry（i）;LIMIT:=Newt

17、emp;GEN（:=, E（2）.place, _, LIMIT）;=NXQ;F.QUAD:=q;GEN（j, entry（i）, LIMIT, q+2）F.chain:GEN（j, _, _, 0）SFS（1）BACKPATCH（S（1）.chain, NXQ）; GEN（+, F.place, 1, F.place）; GEN（j, _, _, F.QUAD）; S.chain:=F.chain5.（1） （j, c, 0, （5）（4）（j, _, _, （8）（5）（+, a, 1, T1）（6）（:=, T1, _, a）（7）（j, _, _, （1）（8）（*, a, 13, T2）（9）（-, T2, 1, T3）（10）（:=, T3, _, a）（11）（j, _, _, （1）（12）6.优化后的四元序列=F+207.最左推导S=（T）=（T,S）=（S,S）=（a,S）=（a,（T）=（a,（T,S）=（a,（S,S）=（a,（a,S）=（a,（a,a）短语 （T,S）,a） （T,S）,a （T,S） T,S直接短语句柄8.（1）Sdo M1 S1 while M2 EMM M.quad=nestq