计算机科学系 2010春季学期
3. 写出一个新的文法，要求新文法无二义且和上述文法产生相同的语言.
答案一： S ? aSb | T
T ? aT | ? 答案二： S ? TS’ T ? aT | ? S’ ? aS’b | ?
~\\(≧▽≦)/~ ~\\(≧▽≦)/~ ~\\(≧▽≦)/~ ~\\(≧▽≦)/~ ~\\(≧▽≦)/~ ~\\(≧▽≦)/~ ~\\(≧▽≦)/~
《编译原理》第五次作业参考答案
一、 考虑以下文法：
S ? aTUV | bV T ? U | UU
U ? ? | bV V ? ? | cV
写出每个非终端符号的FIRST集和FOLLOW集.
FIRST(S)={a, b} FIRST(T)={?, b} FIRST(U)={ ?, b} FIRST(V)={?, c}
FOLLOW(S)={$} FOLLOW(T)={ b, c, $} FOLLOW(U)={ b, c, $} FOLLOW(V)={b, c , $}
二、 考虑以下文法：
S ? (L) | a L ? L, S | S
1. 消除文法的左递归.
S ? (L) | a L ? SL’ L’ ? ,SL’ | ?
2. 构造文法的LL(1)分析表.
FIRST(S) = {‘(‘, ‘a’} FIRST(L) = {‘(‘, ‘a’} FIRST(L’) = {‘,’, ?}
FOLLOW(S) = {‘$’, ‘,’, ‘)’} FOLLOW(L) = {‘)’ } FOLLOW(L’) = {‘)’}
NON-TERMINAL ( S L L’ S ? (L) L ? SL’ ) L’ ? ? INPUT SYMBOL a S ? a L ? SL’ , L’ ? ,SL’ $ 3. 对于句子(a, (a, a))，给出语法分析的详细过程（参照课本228页的图4.21）. MATCHED ( ( ( (a (a STACK S$ (L)$ L)$ SL’)$ aL’)$ L’)$ ,SL’)$ 6
INPUT ACTION (a, (a, a))$ (a, (a, a))$ output S ? (L) a, (a, a))$ a, (a, a))$ output L ? SL’ a, (a, a))$ output S ? a , (a, a))$ , (a, a))$ output L’ ? ,SL’
计算机科学系 2010春季学期
(a, (a, (a,( (a,( (a,( (a,(a (a,(a (a,(a, (a,(a, (a,(a,a (a,(a,a (a,(a,a) (a,(a,a) (a,(a,a)) SL’)$ (L)L’)$ L)L’)$ SL’)L’)$ aL’)L’)$ L’)L’)$ ,SL’)L’)$ SL’)L’)$ aL’)L’)$ L’)L’)$ )L’)$ L’)$ )$ $ (a, a))$ (a, a))$ output S ? (L) a, a))$ a, a))$ output L ? SL’ a, a))$ output S ? a , a))$ , a))$ output L’ ? ,SL’ a))$ a))$ output S ? a ))$ ))$ output L’ ? ? )$ )$ output L’ ? ? $
三、 考虑以下文法：
S ? aSbS | bSaS | ?
这一文法是否是LL(1)文法？给出理由.
这一文法不是LL(1)文法，因为S有产生式S ? ?，但FIRST(S) = {a, b, ?}， FOLLOW(S) = {a, b}，因而FIRST(S)∩FOLLOW(S)≠?. 根据LL(1)文法的定义知这一文法不是LL(1)文法.
~\\(≧▽≦)/~ ~\\(≧▽≦)/~ ~\\(≧▽≦)/~ ~\\(≧▽≦)/~ ~\\(≧▽≦)/~ ~\\(≧▽≦)/~ ~\\(≧▽≦)/~ ~\\(≧▽≦)/~
《编译原理》第六次作业参考答案
一、 考虑以下文法：
(0) E’ ? E (1) E ? E+T (2) E ? T (3) T ? TF (4) T ? F (5) F ? F* (6) F ? a (7) F ? b
1. 写出每个非终端符号的FIRST集和FOLLOW集. FIRST(E’)= FIRST(E)= FIRST(T)= FIRST(F)={a, b} FOLLOW(E’)={$} FOLLOW(E)={+, $} FOLLOW(T)={+, $, a, b} FOLLOW(F)= {+, *, $, a, b}
2. 构造识别这一文法所有活前缀（viable prefixes）的LR(0) 自动机（参照课本4.6.2节图4.31）.
7
计算机科学系 2010春季学期
3. 构造这一文法的SLR分析表（参照课本4.6.3节图4.37）. STATE ACTION a 0 1 2 3 4 5 6 7 8 9 s4 s4 r4 r6 r7 s4 r3 r5 s4 b s5 s5 r4 r6 r7 s5 r3 r5 s5 + s6 r2 r4 r6 r7 r3 r5 r1 * s8 r6 r7 s8 r5 $ accept r2 r4 r6 r7 r3 r5 r1 E 1 GOTO T 2 9 F 3 7 3 7 4. 给出SLR分析器识别输入串a+ab*的过程（参照课本4.6.4节图4.38） STACK SYMBOLS INPUT (1) (2) (3) (4) (5) (6) 0 04 03 02 01 016 a F T E E+ 8
ACTION a+ab*$ shift +ab*$ reduce by F?a +ab*$ reduce by T?F +ab*$ reduce by E?T +ab*$ shift ab*$ shift
计算机科学系 2010春季学期
(7) (8) (9) (10) (11) (12) (13) (14) (15) 0164 0163 0169 01695 01697 016978 01697 0169 01 E+a E+F E+T E+Tb E+TF E+TF* E+TF E+T E b*$ reduce by F?a b*$ reduce by T?F b*$ shift *$ reduce by F?b *$ shift $ reduce by F?F* $ reduce by T?TF $ reduce by E?E+T $ accept
~\\(≧▽≦)/~ ~\\(≧▽≦)/~ ~\\(≧▽≦)/~ ~\\(≧▽≦)/~ ~\\(≧▽≦)/~ ~\\(≧▽≦)/~ ~\\(≧▽≦)/~ ~\\(≧▽≦)/~
《编译原理》第八次作业参考答案
一、 考虑以下语法制导定义（Syntax Directed Definition）：
语法规则 S ? ABCD A ? gBa B ? B1b B ? b C ? C1c C ? c D ? d 语义规则 S.val = A.val + B.val + C.val + D.val A.val = B.val * 5 B.val = B1.val * 2 B.val = 2 C.val = C1.val * 3 C.val = 3 D.val = 1 对于输入串gbbabbccd构造带注释的分析树（annotated parse tree）. 最终答案：34 二、 以下文法定义了二进制浮点数常量的语法规则：
S ? L.L | L L ? LB | B B ? 0 | 1
试给出一个S属性的语法制导定义，其作用是求出该二进制浮点数的十进制值，并存放在开始符号S相关联的一个综合属性value中。例如，对于输入串101.101，S的value属性值结果应该是5.625。要求在编写语法制导定义时，不得改写文法！ 参见05级期末考答案.
9
计算机科学系 2010春季学期
三、 选做课本Exercise 5.3.2和Exercise 5.3.3中的一题.
Exercise 5.3.2 产生式 E?E1+T E?T T?T1*F 语义规则 E.expr = E1.expr + ‘+’ + T.expr E.op = ‘+’ E.expr = T.expr E.op = T.op if (T1.op == ‘+’) if (F.op == ‘+’) T.expr = ‘(‘ + T1.expr + ‘)’ +’ *’ + ‘(‘ + F.expr + ‘)’ else T.expr = ‘(‘ + T1.expr + ‘)’ +’ *’ + F.expr else if (F.op == ‘+’) T.expr = T1.expr +’ *’ + ‘(‘ + F.expr + ‘)’ T.op = ’*’ T.expr = F.expr 10
T->F 计算机科学系 2010春季学期
T.op = F.op F ?(E) F?letter
Exercise 5.3.3 产生式 E?E1+T E?T T?T1*F T->F F ?(E) F?id F?x
语义规则 E.expr = E1.expr + ‘+’ + T.expr E.deri = E1.deri + ‘+’ + T.deri E.expr = T.expr E.deri = T.deri T.expr = T1.expr +’*’ +F.expr T.deri = ‘(’ + T1.expr +’*’ +F.deri + ‘+’ + T1.deri + ‘*’ + F.expr + ‘)’ T.expr = F.expr T.deri = F.deri F.expr = E.expr F.deri = ‘(‘ + E.deri + ‘)’ F.expr = id F.deri = ‘0’ F.expr = x.val F.deri = ‘1’ F.expr = E.expr F.op = E.op F.expr = letter.lexval F.op = ‘n’ 11