复习例题答案

1、编译原理复习例题一选择题1 编译的各阶段工作都涉及_b。A词法分析B表格管理C语法分析D语义分析2 d型文法也称为正规文法。A 0B 1C2D 33 d文法不是LL(1)的。A递归B 右递归C2 型D含有公共左因子的4 .文法E+E|E*E|i 的句子i*i+i*i 有 c棵不同的语法树。A 1B 3C 5D 75 文法S t aaS|abc定义的语言是cAa2k,bc|k>0kBabc|k>0Ca2k-1bc|k>0k kDa a bc|k>06 若B为非终结符，则A f f.B I ；为 dA移进项目B归约项目C接受项目D待约项目7 .同心集合并可能会产生新的d冲突

2、。A二义B移进/移进C移进/归约D归约/归约8 / 88 代码优化时所依据的是 _cA语法规则B 词法规则C等价变换规则D语义规则的逆波兰表示( 妙单目减)9 .表达式 a-(-b)*cAa-bc* Babc*- Cab- Dabc-*10 .过程的DISPLAY表是用于存取过程的 _A。A非局部变量B嵌套层次C返回地址D入口地址二填空题1 词法分析阶段的任务式从左到右扫描源程序,从而逐个识别单词。2 .对于文法 GE :T|E+T T t F|T*F F PAF|P(E)|i ，句型 T+T*F+i 的句柄是 T。3 .最右推导的逆过程称为最左规约,也称为规范推导。4符号表的每一项是由名字栏

3、和信息栏两个栏目组成。在目标代码生成阶段，符号表是内存分配的依据。三判断题(认为正确的填T”错的填F”【T】1同心集的合并有可能产生“归约 /归约”冲突。【T】2个文法所有句子的集合构成该文法定义的语言。【F 3.非终结符可以有综合属性，但不能有继承属性。【T 4 逆波兰表示法表示表达式时无需使用括号。【F 5个有穷自动机有且只有一个终态。【F 6 .若过程p第k次被调用，则p的DISPLAY表中就有k+1个元素。四解答题1 .给定文法 G和句型(T+F)*i+T,G: E t E+T | T T tT*F | FFt (E) | i(1) 画出句型的语法树；(2) 写出句型的全部短语、简单短

4、语和句柄。解:(略)2 .设有文法 G: St S+S|S*S|i|(S)。(1) 对于输入串i+i*i给出一个最左推导；(2) 该文法是否是二义性文法？请证明你的结论。解：(1) i+i*i的最左推导：S => S+S => i+S => i+S*S => i+i*S => i+i*i(2)该文法是二义性的。因为对于句子i+i*i 可以画出两棵语法树(语法树略)。3 .给出语言a mbmcn|m> 1,n > 0的上下文无关文法(2型)。解： G: S t AB|AATab|abBfB|c4 .给出语言a kbmcn|k, m,n1的正规文法(3型)

5、。解:G: A -aA|aBB-bB|bCC-cC|c5 将文法G改写成等价的正规文法(3型)。解:G: S -dABA-aA|aB-bB|bG:S -dAAraA|aBBbB|b6 .构造一文法产生任意长的a , b串，使得|a| w|b| w 2|a|其中，“|a| ”和“ |b| ”分别表示串中的字符a和b的个数。解：b的个数在a的个数和其2倍之间，串的结构形如aSBS和BSaS,其中B为1或2个b。故得文法G: S pSBS|BSaS| £Bb|bb7 .设有字母表a , b上的正规式 R=(ab|a)*(1 )构造R的相应有限自动机；解：(2 )构造R的相应确定有限自动机；

6、 解：将(1 )所得的非确定有限自动机确定化£ab-01131221+3ab-+013123+12312313+ 13123+(3) 构造R的相应最小确定有限自动机；解：对(2)得到的DFA化简，合并状态 0和2为状态2 :(4 )构造与R等价的正规文法解：令状态1和2分别对应非终结符 B和AG: A t aB|a| &B t aB|bA|a|b| £ 可化简为：G: A t aB| eB t aB|bA| e9 .写出在a,b上，不以a开头，但以aa结尾的字符串集合的 正规式(并构造与之等价的最简DFA)。解:依题意，“不以a开头”，则必以b开头，又要“以aa结尾

7、”,故正规式为：b(a|b)*aa(构造与之等价的最简DFA,此略) 10 .写一个LL(1)文法G,使其语言是L(G)= ambnc2n | m>=0,n>0 并证明文法是LL。解：文法 G (S): St aS | EEbE'E't Ecc | ccSelect(S. aS) HSelect (S. E)=Select(E ' Ecc) A Select (E ' ； cc)= 故文法为LL(1)的11 将文法G改写成等价的LL(1)文法，并构造预测分析表。G : St S*aT|aT|*aTT t +aT|+a(编写递归下降子程序)解：消除左递

8、归后的文法G': S t aTS '|*aTS 'S't*aTS ' | &T t +aT|+a提取左公因子得文法G'':S taTS '|*aTS 'S' t *aTS ' | &Tt +aT 'T't T| &Select(St aTS ' )=aSelect(St *aTS ' )=*Select(StaTS ') A Select(St *aTS ')=Select(S't *aTS ' )=*Select(S&

9、#39;t &=Follow(s')=#Select(S't *aTS ') A Select(S ' t &= Select(Tt +aT ')=+Select(T't T)=First(T) =+Select(T't &=Follow(T')=*,#Select(T't t) A Select(T'T s)=所以该文法是LL(1)文法。 预测分析表：*+a#sS 'Ta, Nt aTS's'S 'Ta, N&, PTT' a, NT'

10、;&, PT, P&, Pa&, N#OK(递归下降子程序，略)12 .对文法 GS: S t aSb | PP t bPc | bQc Q t Qa | a构造简单优先关系表。该文法是否是简单优先文法? 解：简单优先关系矩阵如下：SabPQcS=a=< ><<>b<< >=<P>=Q=c>>由于矩阵中有元素存在多种优先关系，故不是简单优先文法。13.考虑文法G: S t AS | b A sa | a(1) 构造文法的可归前缀图(活前缀的 DFA;(2) 判断文法是否是 LR(O)文法，并说明理由

11、。 解：(1 )可归前缀图A(2 )因为存在冲突，所以不是LR(O)文法。14 .文法G及其LR分析表如下，请给出对串 dada#的分析过程。G: SVdBVeVt£BtaBtBdaBt£状态ACTIONGOTOdea#SBV0r3S3121acc2S43r24r6S5r665r4r46S7r17S88r5r5解：对输入串dada#的分析过程步骤状态栈:符号栈剩余输入符号动作10#dada#用V归约202#Vdada#移进3024#Vdada#移进40245#Vdada#用B归约50246#VdBda#移进602467#VdBda#移进7024678#VdBda#用B t

12、Bda归约80246#VdB#用S tVdB归约901#S#接受15.对传值、程序的输出：传地址和传名3种参数传递方法分别写出下列void p(i nt x, int y, int z) y *= 3;z += x;void mai n() int a=5, b=2;p(a*b,a,a);printf(“ %d n”，a);这些参数传递机制如何实现？解：（1 ）传值5 ；（ 2）传地址25 ；（ 3）传名45（参数传递机制，略）16.将下面程序划分为基本块，并画出其程序流图。b := 1b := 2if w <= x goto L2 e := bgoto L2L1:goto L3L2:c := 3b := 4c := 6L3:if y <= z