编译原理
一、回答下列问题：30分1．什么是S属性文法？什么是L属性文法？它们之间有什么关系？解答：S属性文法是只含有综合属性的属性文法。（2分）L属性文法要求对于每个产生式AX1X2…X
，其每个语义规则中的每个属性或者是综合属性，或者是Xj的一个继承属性，且该属性仅依赖于：（1）产生式Xj的左边符号X1X2…Xj1的属性；（2）A的继承属性。（2分）S属性文法是L属性文法的特例。（2分）2．什么是句柄？什么是素短语？一个句型的最左直接短语称为该句型的句柄。分）素短语是这样的一个短语，（3它至少包含一个终结符并且不包含更小的素短语。分）（33．划分程序的基本块时，确定基本块的入口语句的条件是什么？解答：（1）程序第一个语句，或（2）能由条件转移语句或无条件转移语句转移到的语句，或（3）紧跟在条件转移语句后面的语句。4．6分运行时的DISPLAY表的内容是什么？它的作用是什么？答：DISPLAY表是嵌套层次显示表。每当进入一个过程后，在建立它的活动记录区的同时建立一张嵌套层次显示表diaplay假定现在进入的过程层次为i，则它的diaplay表含有i1个单元，自顶向下每个单元依次存放着现行层、直接外层、…、直至最外层主程序，0层等每层过程的最新活动记录的起始地址。通过DISPLAY表可以访问其外层过程的变量。5．6分对下列四元式序列生成目标代码：ABCDEFGADHG2其中，H是基本块出口的活跃变量，R0和R1是可用寄存器答：LDR0，BMULR0，CLDR1，EADDR1，F
fADDR0，R1MULR0，2STR0，H二、设0，1上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。8分答：构造相应的正规式：011013分NFA2分11
0


1


2
1
3
4
0确定化：3分I012121231241234
I0
0
I1
1212124121240
12312312341231234
10
01
1
2
0
3
0
4
01
11
三、写一个文法使其语言为LGa
bmamb
m
≥1。6分答：文法GSSaSbBBbBaba
四、对于文法GE8分
ETETTFTFFEi1写出句型TFi的最右推导并画出语法树。
E
T
f2写出上述句型的短语，直接短语、句柄和素短语。
答：14分ETFEETEFEiTiTFi24分短语：TFiTFiTFi直接短语：TFi句柄：TF素短语：TFi
五、设文法GS：12分
SSiAAAABBBA
1．构造各非终结符的FIRSTVT和LASTVT集合；2．构造优先关系表和r