发布时间 : 星期六 文章编译原理课后习题答案更新完毕开始阅读50fcfe59a300a6c30c229fdf
第三章
1. 词法分析器的功能是什么？
答：读源程序的字符序列，逐个拼出单词，并构造相应的内部表示TOKEN；同时检查源程序中的词法错误。
2. 试分析分隔符（空格、跳格及回车等）对词法分析的影响。
答：空格、跳格、回车等分隔符号对词法分析不起作用，可以删除。但是回车符号可以用于错误定位，所以在删除回车符号前需要统计回车的个数。 3. 给出识别C语言全部实型常数的自动机。
答：(+|-|?)([1-9][0-9]*|0)(.[0-9][0-9]*|?) (E(+|-|?)[0-9][0-9]*) 4. 写出识别C语言中所有单词的LEX程序。
答： L=[A-Z] | [a-z] D=[0-9] D1=[1-9] %% (L|_)(L|D|_)* {return (1);} D1D* {return (2);} + {return (3);} ……
5
第四章
1. 设有如下文法G[S]:
S?aABbcd | ? A?ASd | ? B?SAh | eC | ? C?Sf | Cg | ?
(1) 求每个产生式的Predict集。 (2) 该文法是否为LL(1)文法？为什么？ 答：(1)
Predict(S?aABbcd)={a} Predict(S? ?)={#,d,f,a,h } Predict(A?ASd)={a,d} Predict(A? ?)={h,a,d,b,e} Predict(B?SAh)={a,d,h} Predict(B? eC)={e} Predict(B? ?)={b} Predict(C?Sf)={a,f} Predict(C? Cg)={a,f,g} Predict(C? ?)={g,b}
(2)由于Predict(A?ASd)? Predict(A? ?)??，所以该文法不是LL(1)文法。 (1) S?(SS’ | ?
S’ ?) | ? (2) S?(S)S | ? (3) S?S(S)S | ? (4) S?(S | S’
S’?(S’) | ?
答：(1)不是，(2)是，(3)不是，(4)不是 3. 已知文法G[E]:
E?E+T | T T?T*F | F F?i | (E)
请按递归下降法构造该文法的语法分析程序。 答：求产生式的predict集合：
2. 下列描述括号匹配的文法中，哪些是LL(1)文法？
predict(E?E+T)={i,(} predict(E?T)={i,(} predict(T?T*F)={i,(} predict(T?F)={i,(}
6
由于文法中非终极符号E和T对应的产生式的predict集合的交集都不为空，所以该文E?TE’ E’?+TE’ | ? T?FT’ T’?*FT’ | ? F?i F?(E)
求新文法的predict集合： Predict(E?TE’)={(,i} Predict(E’?+TE’)={+} Predict(E’??)={#,)} Predict(T?FT’)={i,(} Predict(T’?*FT’)={*} Predict(T’??)={+,),#} Predict(F?i)={i} Predict(F?(E))={(}
由于以上文法中任意非终极符号对应的产生式的predict集合的交集都为空，所以满足Void E()
{ if(token?{(,i}) {T();E’();} else Error();} void E’()
{ if(token?{+}) {Match(‘+’);T();E’();} else if(token?{#,)}) {;} else Error();} void T()
{ if(token?{i,(}) {F();T’();} else Error();} void T’()
{ if(token?{*}) {Match(‘*’);F();T’();} else if(token?{+,),#}) {;} else Error();} void F()
{ if(token?{i}) {Match(‘i’);}
else if(token?{(}) {Match(‘(‘);E();Match(‘)’);} else Error();}
L={? | ?为字母表?上不包括两个相邻的1的非空串}，其中?={0，1}。
法不满足自顶向下分析的条件，现对文法进行等价变换得到如下文法：
自顶向下分析的条件，所以可以写出如下的递归下降语法分析伪代码：
4. 构造一个LL(1)文法G，它能识别语言L: 并证明你所构造的文法是LL(1)文法。
7
答：A?0E | 1F
B?0E | 1F C?0E E?B | ? F?C | ?
Predict(A?0E)={0} Predict(A?1F)={1} Predict(B?0E)={0} Predict(B?1F)={1} Predict(E?B)={0,1} Predict(E??)={#} Predict(F?C)={0} Predict(F??)={#}
对任意非终极符号对应的产生式的predict集合的交集都为空，所以该文法是LL(1)文
法。
5. 已知文法G[A]为：
A?aABe | a B?Bb | d
(1) 试给出与G[A]等价的LL(1)文法G’[A]。
(2) 构造G’[A]的LL(1)分析表并给出输入串aade#的分析过程。 答：(1)所求G’[A]为：
A?aA’ A’?ABe A’? ?
B?dB’ B’?bB’ B’? ?
(1) (2) (3) (4) (5) (6)
Predict(A?aA’)={a} Predict(A’?ABe)={a} Predict(A’??)={#,d} Predict(B?dB’)={d} Predict(B’?bB’)={b} Predict(B’??)={e}
对任意非终极符号对应的产生式的predict集合的交集都为空，所以该文法是LL(1)文(3) 分析表如下： 法。 A A’ a (1) (2) b d (3) e # (3) 8