编译原理课后习题答案

第三章

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