杭电编译原理试卷三及复习资料

试卷（三一、选择下面说正确的是A一个正规文法也一定是二型文法一个二型文法也一定能有一个等价的正规文法文法G[A]A→bA→ABB→AbB→a是A)二型文法正规文法下面说正确的()lex一个词法分析器yacc一个语法分析器的生成器一个LR（）文法合并同心集后如果不是LALR(1)法必定存在(B)移进--归约冲突归约--归约冲突PL/0语言编程序使用递归子程序法进行语法分析，他的文法必须满(A)ALL（1）文法BSLR(1)文法二、问答问答第（6分试对repeatx:=buntilor(b<aandb=d)的四元式序列给出第四区段应回填的指令地址，并指出真假出口链和链头及回填的次序。应回填的值回的次序x:=bifb>a()()()()ifb<a()()()()ifgoto()()()()解：

真链头E.true=真出口链()真出口链()假链头假出口链()应回填的值

回填的次序

真链头E.true=x:=bifb>a(8(6)(4)(ifgoto(6)(2)(1)(if((5)(1)(

真出口链()假链头E.false=7假出口链()/9问答第2题分)某语言的拓广文法为(0)S→SSDd|εB→Ba|证明G不文法而是SLR(1)文法，请给出分析表。解：拓广文法G'增加产生式S'在项目集I0：有移进项目D→·d归约项目D和B存在移进归约和归约-约冲突，所以G不是文法。若产生式排序为：(0)S'SSDdDεB→BaB→G的LR(0)项目集族及识别活前缀DFA如图：识别G活缀的DFA/9由产生式知：Follow(S)={#}Follow(D)={b}Follow(B)=,#}在中Follow(D)∩{d}={b}∩{d}=Follow(B)∩{d}={,#}∩{d}=Follow(D)∩Follow(B)={b}∩{a,#}=在中Follow(S)所以在I0中移进归约和归归约冲突可以由Follow集决,以G是文,构造的分析表如下表。分析表问答第3题分给出文法G[S]的LR(1)目集规范族中I0项目集的全体项目。为：VA→b(S)|εI0:/9解：I0:问答第4题分文法及其分表如下，请给出对串的分析过程。G[M]:1)S→VdB2)→e3)ε4)B→a5)→Bda6)B→解：对串dada#分析过程如下表对输入串dada#分析过程步骤

状态文符剩输入栈号栈符

动作0dada#0240245#Vdada#0246#VdB02467#VdBd

用Vε归约移进移进用→a归移进移进/9024678#VdB0246#S

用→Bda归用S→VdB归约接受问答第5题分(1)给出下列示意程序中当程序执到D过调用A过程执A过体时）的栈式存储分配布局和用显表时A过最新活记录的内容。说表全局的用。示意程序为：varx;A;varbegin(*A*)(*A*);B;n=7;vare,g;D;varbegin(*D*)callA;;(*D*)begin(*B*)callD;;(*B*)begin(*main*)read(x);callB;end.(*main*)解）示意程序中当程序执行到过调A程后（即执行A程体时）的栈式存储分配布局和用Display显表时栈中过程最新活动记录的内容如下图。栈式存储分配布局和栈中过程最新活动记录的内容/9（2）表全局Display的用是：·Display表作用是对嵌套过程语言实现对非局部变量的引用而设置的依存放着包围它的外过程的最新活动记录的基地址值由于，嵌套层次为i+1程中的非局部变量可能在i局变量的引用是通它的Display表素d[i]d[i-1]d[0]而得包围它的外过程的最新活动记录的基地址SP，再加上变量在该过程（第i层的偏移量。如若非局部变量a是第i层那么引用，首先从当前栈顶过程的表中元素d[i]中出存放的第i层新活动记录基地址值后加上所在过第i）的偏移量，就得到的存放地址。全存放本过程表起始地址，其作用是把Display地作连接数据之一，如过程P1调过程时，这时先从的局到的Display表始地址，然后从P1的Display中自底向上地抄录I2个单元（I2为的层数）再添上进入P2后新建立的P2的sp值就构成了的Display表问答第分给出问答第题PL/0示程序编译到过体时表内。其中TABLE表的格式可为下表。表格式：levelvaladr解：问答第5题PL/0示意程序编译到D过体时的内容如下表。表内容/9由于A并列过程，当编译到B过时A程体已经编译结束A所义的标识符不会再被使用，所以由B过定的标识符覆盖。问答第7题（6）按指定类型给出下列语言的文法。L1={candbm|n}用规文法。L2={1nbmcm|n>0m用型文法（1解：描述L1语言的正规文法如下：S→cA→dDD→bD|ε（2解：描述L2语言的二型文法如下：S→AB→0A1|0a1→bBc|ε问答第8题（5）文法G[S]：→SdTT→T<G|GG→(S)|试给出句型(SdG)<a短语、简单直)语、句柄和最左素短语。解：句型(SdG)<a短语：）、SdG、G、简单直接短语G、句柄：G最左素短语：问答第9题（5）给出正规式R＝（aba*）等的NFA/9abab问答第1题分将下图的确化为。解：用子集法确定化如下表II

I

状态{X,0,1,3}{2,3,Y}{2,3,Y}{2,3,Y}{1,3}{Y}{1,3}{2,Y}{2,Y}{1,3}{Y}{Y}确定化后如下图

XY问答第题分将文法G[S]改为等价的G'[S]，使不含左递归和左公共因子。：S→B]|AS解：文法改写为等价的不含左递归和左公共因子G'[S]为：S→[AA→B]A→SA′|→aBB问答第1题分)判下面文法是否为LL(1)文法，若是，请构造相的LL(1)分表。S→aDD→STe|εT→bMM→bH/9H→M|ε解：文法的集FOLLOW非终结符集{a}D，ε}

FOLLOW集{#，b}{#，b}