五、计算题：
　　
　　 1、写一个文法，使其语言是奇数集，且每个奇数不以0开头。(5分)
　　
　　 解：文法G(N)：
　　 　　　　　 　N→AB|B
　　 　　　　　 　A→AC|D
　　 　　　　　 　B→1|3|5|7|9
　　 　　　　　 　D→B|2|4|6|8
　　 　　　　　 　C→0|D　　　　　(5分)
　　
　　 2、设文法G(S)：
　　 　　S→(L)|a S|a
　　 　　L→L，S|S
　　 　　(1) 消除左递归和回溯；
　　 　　(2) 计算每个非终结符的FIRST和FOLLOW；
　　 　　(3) 构造预测分析表。
　　
　　 解： (1)
　　 　　　　　　　S→(L)|aS’
　　 　　　　　　　S’→S|ε
　　 　　　　　　　L→SL’
　　 　　　　　　　L’→SL’|ε
　　 　　　　评分细则：消除左递归2分，提公共因子2分。
　　
　　 　　(2)
　　 　　　　　　　FIRST)S)＝{(，a}　　　　FOLLOW(S)＝{#，，，)}
　　 　　　　　　　FIRST(S’)＝{，a,ε}　　FOLLOW(S’)＝{#，，，)}
　　 　　　　　　　FIRST(L)＝{(，a}　　　　FOLLOW(L)＝{ )}
　　 　　　　　　　FIRST(L’)＝{，，ε}　　FOLLOW(L’〕＝{ )}
　　
　　 3、While　a＞0 ∨ b＜0　do
　　 　　Begin
　　 　　　　X：＝X＋1；
　　 　　　　if a＞0 then a：＝a－1
　　 　　　　　　　　else b：＝b＋1
　　 　　End；
　　 　　翻译成四元式序列。(7分)
　　
　　 解：
　　 　　　(1) (j＞，a，0，5)
　　 　　　(2) (j，－，－，3)
　　 　　　(3) (j＜，b，0，5)
　　 　　　(4) (j，－，－，15)
　　 　　　(5) (＋，×，1，T1)
　　 　　　(6) (：＝，T1，－，×)
　　 　　　(7) (j≥，a，0，9)
　　 　　　(8) (j，－，－，12)
　　 　　　(9) (－，a，1，T2)
　　 　　　(10) (：＝，T2，－，a)
　　 　　　(11) (j，－，－，1)
　　 　　　(12) (＋，b，1， T3)
　　 　　　(13) (：＝，T3，－，b)
　　 　　　(14) (j，－，－，1)
　　 　　　(15)
　　 　　评分细则：控制结构4分，其它3分。
　　
　　 4、已知文法G(E)
　　 　　E→T|E＋T
　　 　　T→F|T * F
　　 　　F→(E)|i
　　 　　(1) 给出句型(T * F＋i)的最右推导及画出语法树；
　　 　　(2) 给出句型(T * F＋i)的短语、素短语。(7分)
　　
　　 解：(1) 最右推导：
　　 　　　　　ETF(E)(E＋T)(E＋F)(E＋i)
　　 　　　 　(T＋i)(T*F＋i)
　　 　　　　　 (2) 短语：(T*F＋i)，T*F＋i，T*F，i　　　　(2分)
　　 　　　　　　　 素短语：T*F,i 　　　　　　　　　　　　(1分)
　　
　　 5、设布尔表达式的文法为
　　 　　E → E(1)∨E(2)
　　 　　E → E(1)∧ E(2)
　　 　　E → i
　　 　　假定它们将用于条件控制语句中，请
　　 　　(1) 改写文法，使之适合进行语法制导翻译和实现回填；
　　 　　(2) 写出改写后的短个产生式的语义动作。(6分)
　　
　　 解：(1) E0→E(1)
　　 　　　　　　　 E→E0E(2)
　　 　　　　　　　 EA→E(1)
　　 　　　　　　　 E→EAE(2)
　　 　　　　　　　 E→i　　　　　　　　　　　　　　　　　　(3分)
　　 　 (2) E→E(1)
　　 　　　　　　　 {BACKPATCH(E(1)·FC，NXQ)；
　　 　　　　　　 　　　E0·TC：＝E(1)·TC}
　　 　　　　　 　　E→E0E(2)
　　 　　　　　　　 {E·FC：＝E(2)·FC；
　　 　　　　　　 　　　E·TC：＝MERG(E0·TC，E(2)·TC)}
　　 　　　　　　 　EA→E(1)
　　 　　　　　　 　 {BACKPATCH(E(1)·TC，NXQ)；
　　 　　　　　　　 　　E0·FC：＝E(1)·FC}
　　 　　　　　　　 E→EAE(2)
　　 　　　　　　　 {E·TC：＝E(2)·TC；
　　 　　　　　　　 　　E·FC：＝MERG(EA·FC，E(2)·FC}
　　 　　　　　　 　E→i
　　 　　　　　　　 {E·TC：＝NXQ；E·FC：＝NXQ＋1；
　　 　　　　　　　 　　GEN(jn2，entry(i)，－0)；
　　 　　　　　　　　 　GEN(j，－，－，0)　　　　　　　　　(3分)
　　 6、设有基本块
　　 　　T1：＝2
　　 　　T2：＝10/T
　　 　　T3：＝S－R
　　 　　T4：＝S＋R
　　 　　A：＝T2 * T4
　　 　　B：A
　　 　　T5：＝S＋R
　　 　　T6：＝T3 * T5
　　 　　B：＝T6
　　 　　(1) 画出DAG图；
　　 　　(2) 假设基本块出口时只有A，B还被引用，请写出优化后的四元序列。(6分)
　　
　　 解：(1)DAG：
　　 (2) 优化后的四元式
　　 　　　　　 　　T3：＝S－R
　　 　　　　　 　　T4：＝S＋R
　　 　　　　　 　　A：＝5*T4
　　 　　　　　 　　B：＝T3＋T4　　　　　　　　　　　　(3分)