《编译原理》练习题.doc

编译原理练习题一 一、填空题（每空1分）1设GS是一个文法，我们把能由文法的 （1） 推导出来的符号串称为G的一个句型。当句型仅由 （2） 组成时 (即VT*)，则将它称为G产生的句子。 2从某一给定的状态q出发，仅经过若干条 (3) 的矢线所能达到的状态所组成的集合称为-CLOSURE(q)。3设G=(VN,VT,P,S)是一文法，我们说G中的一个符号XVNVT是有用的，是指X至少出现在 （4） 的推导过程中，否则，就说X是无用的。我们将不含形如AA的产生式和不含无用符号及无用产生式的文法称为 （5） 。4我们常采用形如 (class, value)的二元式作为一个单词的 (6) 。其中,class是一个整数，用来指示该单词的 (7) ，value则是单词之值。5一个文法GS可表示成形如 （8） 的四元式。其中VN,VT,P均为非空的有限集，分别称为非终结符号集、终结符号集和产生式集， SVN为文法的开始符号。此外，将出现在各产生式左部和右部的一切符号所组成的集合称为 （9） ，记作V。显然，V=VNVT,VNVT=。 6通常，可通过两种途径来构造词法分析程序。其一是根据对语言中各类单词的某种描述或定义，用 (10) 构造词法分析程序；另外一种途径是所谓词法分析程序的 (11) 。7设G为一文法，A是G的一个产生式，如果具有A的形式，其中，不同时为，则称产生式A是 （12） 。若存在推导，则称产生式A是 （13） 。 8设M=(K,f,S0,Z)为一DFA，并设s和t是M的两个不同状态，我们说状态s,t为某一输入串w (14) ，是指从s,t中之一出发，当扫视完w之后到达M的终态，但从其中的另一个状态出发，当扫视完同一个w后而进入 (15) 。9把最右推导称为 （16） ，而把右句型称为 （17） 。10如果从状态转换图的初态出发，分别沿着一切可能的路径到达 (18) ，并将每条路径各矢线上的 (19) 依次连接起来，便得到状态转换图所能识别的全部字符串，这些字符串所组成的集合也就是该状态转换图所识别的语言。二、选择题（每空2分） 1. 下列文法中， 不是产生语言 abnan1 的文法。 AAaBa BbbB BAaB BbabB CAaB BbabBaDAaB BbC CbCa2. 设有文法GS： SaAB AbAc BbBAe则经消去-产生式后与G等价的文法G1S为 。ASaAaBaABa AbcbAc BbBAebeBSaAB AbAc BbBAe CSaAaB Abc BbeDSaAaBa AbcbAc BbBAebe3. 文法 G 产生的 的全体是该文法描述的语言。 A 句型 B. 终结符集 C. 非终结符集 D. 句子4. 设M为一确定有限自动机，并设s 和t是M的两个不同状态。如果s和t ，则称s和t等价。 A不可区分 B可划分 C可区分 D待区分5. 设有文法GS： SaSWU Ua VbVac WaW则经化简后与G等价的文法G1S为 。ASaSW VbVac WaWBSaSU Ua CSaSWU Ua WaWDSaS VbVac 6. 若文法 G 定义的语言是无限集，则文法G必然是 。 A前后文无关的 B递归的 C二义性的 D无二义性的 7. 下列说法中正确的是 。 A一个确定的有限自动机实际上是相应的状态转换图的一种形式描述。 B一个状态转换图是由一组矢线连接的有限个结点所组成的无回路有向图。 C所谓一个DFA M状态数的最小化，是指构造一个与之等价的DFA M，使它们有相同的接受集。 D对于有同一接受集的FA，与之等价的DFA在同构意义下是唯一的。8. 下列文法中， 不是产生语言 的文法。 AAaBa BaaBa BAaB BaaBaa CAaAA AaDAaBB BaaBB9. 如下的表示形式中，不能表示程序语言中单词结构的是 。 A左线性文法 B形如（Class，Value）的二元式 C正规式 D正规文法三、证明题1试证明文法 SaBbA AaSbAAa BaBBbSb 为二义性文法。 （10分）2 试证明文法: SaAB AaAa BaBb 为二义性文法。 （10分）四、简答题1试构造一文法，使其描述如下语言： （15分）L(G)= anbmcmdnm,n1 2消除下列文法中的单产生式。 （10分）SAbBA AABcaBB BAab3对正规式(ab) *ab*)b ，构造与其相应的状态转换图。 （15分）4消除下列文法中的-产生式。 （10分）SABba AaBcaB BaAb5试描述由下列文法所产生的语言。 （10分）SaAd AaAdbBc BbBce6 消除下列文法中的单产生式。 （10分）SaFbMF FMabc MabFc7化简下列文法： （10分）SBabcC BbSb CDa DCbCDa8 对正规式(aab)*ab* ，构造与其相应的状态转换图。 （15分）9试构造一正规文法，使其描述如下语言： （10分）L(G)= abmcbnam1, n0 10试描述由下列文法所产生的语言。 （15分）SaAbB AAab BaAaC CcCd 五、应用题 1对于如下的状态转换矩阵(1) 分别画出相应的状态转换图；（10分）(2) 写出相应的3型文法。 （10分）2 将如图所示的NFA确定化。 （20分）3 将如图所示的具有动作的NFA确定化。 （20分）4 将如图所示的DFA最小化。 （20分）5将如图所示的DFA最小化。 （25分）6对于如下的状态转换矩阵(1) 画出相应的状态转换图；（10分）(2) 写出相应的3型文法。 （10分）7设有如下正规文法GS：SaAaB AbBb BbBbC CbCa （1）构造与文法GS相应的状态转换图； （10分） （2）将所得的NFA确定化。 （15分）8将如图所示的NFA确定化。 （15分）编译原理练习题二一、填空题（每空1分，共10分） 1所谓递归下降法，是指对文法的每一非终结符号，都根据相应产生式各候选式的结构，为其编写一个 (1) ，用来识别该非终结符号所表示的 (2) 。2在每一LR(0)项目A中放置一个 (3) a，使之成为A,a的形式，我们将此种项目称为一个 (4) 。3所谓 (5) ，就是对文法中的 (6) 都附加一个语义动作或语义子程序，且在语法分析过程中，每当需要使用一个产生式进行推导或归约时，语法分析程序除执行相应的 (7) 外，还要执行相应的语义动作或调用相应的语义子程序。 4LL(1)分析表可用一个 (8) 表示，它的每一行与文法的一个非终结符号相关联，而其每一列则与文法的一个终结符号或 (9) 相关联。5若在一个文法G中，不含有形如 (10) 的产生式，其中A,BVN，则称G为算符文法。 6将每一运算符都置于其 (11) 的表达式称为后缀表示，也称为逆波兰表示。 7把流程图中具有如下性质的一组结点称为程序中的一个循环：() 在这组结点中，有惟一的 (12) ，使得从循环外到循环内任何结点的所有通路，都必通过此结点；() 这一组结点是 (13) 。 8语法分析的基本任务是：根据语言的语法规则 (即根据描述该语言的前后文无关文法)，分析源程序的 (14) ，即分析如何由这些单词组成各种语法范畴，并在分析过程中，对源程序进行 (15) 。 9所谓句型的素短语，是指一个句型中具有这样性质的短语：短语中至少含有一个 (16) ，且除它自身外，不再包含其它的 (17) 。10一个文法符号X的 (18) 我们称之为语义属性或简称为属性，用形如X.ATTR的记号来表示文法符号X的相关语义属性。 11表示流程图中各结点间控制关系的一种直观而有效的方法是用树形结构，称之为 (19) 。 12目前，已存在许多语法分析方面的方法。但就产生语法树的方向而言，可大致把它们分为 (20) 和 (21) 两大类。 13将形如AX的项目称为AX的 (22) 。14记录和一个数组有关的信息，如维数n、各维的上、下界lk和uk的数据结构称为数组的 (23) 。 15基本块是程序中具有下述性质的 (24) ：它有惟一的入口和惟一的出口，它们分别是块中的第1个操作和最末一个操作，且块中的各个操作按顺序执行，不出现 (25) 。 16若一文法G的任何两个符号之间 (26) 一种优先关系，且任意两个不同的产生式均无 (27) ，则称G为简单优先文法。 17把在数据区给变量分配的存储单元地址称为 (28) ，而把在目标程序运行时存放在相应单元中的值称为 (29) 。18如果从流程图的首结点到流程图中某一结点n的所有通路都要经过结点d，我们就说结点d控制了结点n，或者把d称为n的 (30) ，记作 (31) 。二、选择题（每空2分） 1. 下列文法中， 是LL(1)文法。 ASbBSa SaBS ASa BAcBSbSbAb AaAaCEE+TT TT*FF F(E)i DSbBS SaBS ASa BAc2. 下列文法中， 是简单优先文法。 AEE+TT TT*FF F(E)iBSA/ AaAAS/CEE+EE*E(E)i DEE1 E1E1+T1T1 T1T TT*FF F(E)i3. 当扫视到数组说明进行语义处理时，必须把一个数组的如维数、各维的上、下界等记录下来。为了便于引用，通常是把上述内容存放于数组相应的 之中。 A信息向量 B内情向量 C地址向量 D指针向量4. 下列说法中正确的是 。A. 所谓递归下降法，是指只能对具有左递归性的文法进行分析的一种语法分析方法。B. 如果一个文法具有二义性，则它必然不是LL(1)文法。C. 对于文法G，当进行自顶向下的语法分析时，不会出现回溯的主要条件是，对于G中的每个AVN，A产生式的所有不同候选式均能推导出以同一终结符号开始的符号串。D. 对任意非LL(1)文法而言，通过消除左递归和反复提取左因子，都能将其改造为LL(1)文法。5. 简单优先分析每次归约的是 。 A. 最左直接短语 B.直接短语 C.最左素短语 D.控制结点6. 下列表示中， 是与f(e+(ad+c)/d)相应的逆波兰式。 Afeadc+d/+ Bfe+ad+c/d Cfad+c/d+e Dadc+d/e+f7. 下列文法中， 是LL（1）文法。 ASaSaA AbAac BSASb ASAa CEE+EE*E(E)i DSaSbA AbAac8. 所谓相容，是指在一个项目集中，不出现这样的情况， 和归约项目并存，或多个归约项目并存。 A移进项目 B基本项目 C待约项目 D后继项目9. 下列表示中， 不是目前经常使用的中间语言的形式。 A逆波兰式 B四元式 C五元式 D树形表示10. 如果从流程图的首结点到流程图中某一结点n的所有通路都要经过结点d，我们就说结点d控制了结点n，或者把d称为n的必经结点，记作 。 Ad DFA n Bd DOM n Cd DAG n Dd DAM n11. 下列说法中错误的是 。 A. 任何LL(1)文法都是无二义性的。B. 左递归文法必然不是LL(1)文法。C. 对于任意一个前后文无关文法G，都能为其构造一个无多重定义的预测分析表。D. 如果文法是左递归的，则自顶向下的分析过程将不能正常地进行。12. 如下的语法分析方法中， 要求文法中不含-产生式。 A预测分析法 BLR（1）分析法 C递归下降分析法 D算符优先分析法13. 如下四元式中正确的是 。 A（jnz， ， ，p） B（j，A1，A2，p）C（jJ goto L2 J:=J+1I:=Ngoto L1 L3: X:=J*A试将它划分为基本块，并作控制流程图。 （10分）3 消除下列文法的左递归性。 （10分） SaAc ABba BAdc 4 将下列中缀式改写为逆波兰式。 （10分）A+B*(C-D)/(E+F) 5将下列语句翻译成四元式序列。 （10分）IF ab c0 THEN b:=b+2 ELSE a:=a-2 6 将下列语句翻译成四元式序列。 （10分）while A0 do C:=C+B*D 7设有文法GZ： ZZAcBa AAba BBdc将其改写为LL(1)文法。 （15分）8对于如下的程序，试对其中的循环进行削弱运算强度的优化。 （10分）9对于如下文法，求各候选式的FIRST集和各非终结符号的FOLLOW集。 （共15分）SACAB|bA| AaAd|e BbB|c CcC|10将下面的逆波兰式改写为中缀式。 （8分） ABCD/-*EF*+11设有如下的三地址码（四元式）序列： I:=1 read L,ML1 ： if I10 goto L2A:=L*MB:=L*I C:=M*A D:=M+B I:=I+1 goto L1L2 ： halt(1) 将它划分为基本块，并作控制流程图； （6分）(2) 对其中的循环进行循环不变运算外提的优化。 （6分）12将下列语句翻译成四元式序列。 （10分）IF ad THEN b:=c+d*3 ELSE a:=a-c/d 13将下列语句翻译成四元式序列。 （10分）IF ab c0 THEN BEGIN b:=b+2；c:=c-1 END ELSE WHILE a=d DO BEGIN a=a-2； d:=d+1 END14将下列逆波兰式改写为中缀式。 （10分）AB+C*DEF*-/15 将下列语句翻译成四元式序列。 （10分）while A0 do X:=A+B*C16对于如下的程序，试对其中的循环进行削弱运算强度的优化。（10分）17设有二维PASCAL数组A110, 120, 130，将下列语句翻译成四元式序列。（10分）X := AI+1,J*2,I * B+C18对于如下的基本块，若变量G，L，M在基本块出口之后被引用： A:=B*C D:=5 E:=C/D F:=2*D G:=C/D H:=B*C L:=H*E M:=L(1) 构造相应的DAG； （5分） (2) 重建经优化后的四元式序列。 （5分）四、应用题 1设有文法GS： SaABb AAcdd BBcee(1) 将其改写为LL(1)文法； （10分）(2) 构造改写后文法的LL(1)分析表。 （10分）2设有文法GE： EE+T|T TT*F|F F(E)|i 其相应的算符优先矩阵如图所示，试给出对符号串i*i+i进行算符优先分析的过程。（20分）(i*+)#(i*+)#文法GE的算符优先矩阵3设有文法GS： SaAB AbAa BcBb （1）构造此文法的LR(0)项目集及状态转换图； （15分）（2）构造LR(0)分析表。 （10分）4对于如图所示的控制流程图：(1) 求出各个结点的必经结点集； （5分）(2) 求出各个回边，并找出流程图的全部循环。 （5分）5 设有文法GS： SaBcbAB AaAbb Bb(1) 构造该文法的LL(1)分析表； （10分）(2) 分析符号串baabbb是否为该文法的句子。（15分）6设有文法GE：EE1 E1E1+T1|T1 T1T TT*F|F F(E)|i 其相应的简单优先矩阵如下图所示，试给出对符号串i+i进行简单优先分析的过程。（20分）7对于如下的基本块，若变量G,M在基本块出口之后被引用： A:=B+C D:=3 E:=6 F:=D*E G:=B+C H:=A+D L:=H*F M:=L(1) 构造相应的DAG； （5分） (2) 重建经优化后的四元式序列。 （5分）8设有文法GS： SABAC AaD Bb Cd Dc（1）构造此文法的LR(0)项目集及状态转换图； （15分）（2）构造SLR(1)分析表。 （10分）9已知文法GS： SaAB AbAa BcBb 的LR(0)项目集及状态转换图如下：(1) 构造LR(0)分析表； （10分）(2) 给出对输入符号串abacb的LR分析过程。 （15分）10 消除下列文法的左递归性。 （15分） ZAaB ABba BZdc11设有文法GE：EE1 E1E1+T1|T1 T1T TT*F|F F(E)|i 其相应的简单优先矩阵如图所示，试给出对符号串i*i进行简单优先分析的过程。（20分）12对于如图所示的控制流程图： （共10分）(1) 求出各个结点的必经结点集；(2) 求出各个回边，并找出流程图的全部循环。13设有文法GS： SaAbDad ABSDb BcD DSac(1) 构造该文法的LL(1)分析表； （10分）(2) 分析