态层次D标识符的行号
三、填空题每空1分，共10分1．计算机执行用高级语言编写的程序主要有两种途径：___解释__和__编译___。2．扫描器是__词法分析器___，它接受输入的__源程序___，对源程序进行___词法分析__并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。3．自上而下分析法采用___移进__、归约、错误处理、___接受__等四种操作。4．一个LR分析器包括两部分：一个总控程序和___一张分析表__。5．后缀式abc所代表的表达式是___abc__。6．局部优化是在__基本块___范围内进行的一种优化。四、简答题（20分）1简要说明语义分析的基本功能。答：语义分析的基本功能包括确定类型、类型检查、语义处理和某些静态语义检查。
2考虑文法GS
S→TaSaT→TSS消除文法的左递归及提取公共左因子。解：消除文法GS的左递归：S→TaSa
fT→ST′T′→ST′ε提取公共左因子：S→TaS′S′→SεT→ST′T′→ST′ε
3试为表达式wabcde108写出相应的逆波兰表示。
解：wabcde108
4按照三种基本控制结构文法将下面的语句翻译成四元式序列：
whileAC∧BD
ifA≥1CC1
elsewhileA≤D
AA2
。
解：该语句的四元式序列如下其中E1、E2和E3分别对应A＜C∧B＜D、A≥1和A≤D，并且关系运算符优先级高：100jAC102101j__113102jBD104103j__113104jA1106105j__108106C1C107j__112108j≤AD110109j__112110A2A111j__108112j__100113
f5已知文法GS为S→aSbSbb，试证明文法GS为二义文法。证明：
由文法GS：S→aSbSbb，对句子aabbbb对应的两棵语法树为：
因此，文法GS为二义文法。
五计算题（10分）已知文法
AaAdaAbε
判断该文法是否是SLR1文法，若是构造相应分析表，并对输入串ab给出分析过程。解：增加一个非终结符S后，产生原文法的增广文法有：
SAAaAdaAbε下面构造它的
LR0项目集规范族为：
f从上表可看出状态I0和I2存在移进归约冲突，该文法不是LR0文法。对于I0来说有：FOLLOWA∩abd∩aΦ，所以在I0状态下面临输入符号为a时移进，为bd时归约，为其他时报错。对于I2来说有也有与I0完全相同的结论。这就是说，以上的移进归约冲突是可以解决的，因此该文法是SLR1文法。其SLR1分析表为：
对输入串ab给出分析过程为：
f一、是非题：
1一个上下文无关文法的开始符，可以是终结符或非终结符。
2一个句型的直接短语是唯r