《编译原理》练习题

《编译原理》练习题一一、填空题（每空1分）1．设G［S］是一个文法，我们把能由文法的（1）推导出来的符号串α称为G的一个句型。当句型α仅由（2）组成时(即α∈VT*)，则将它称为G产生的句子。2．从某一给定的状态q出发，仅经过若干条(3)的矢线所能达到的状态所组成的集合称为ε-CLOSURE(q)。3．设G=(VN,VT,P,S)是一文法，我们说G中的一个符号X∈VN∪VT是有用的，是指X至少出现在（4）的推导过程中，否则，就说X是无用的。我们将不含形如A→A的产生式和不含无用符号及无用产生式的文法称为（5）。4．我们常采用形如(class,value)的二元式作为一个单词的(6)。其中,class是一个整数，用来指示该单词的(7)，value则是单词之值。5．一个文法G[S]可表示成形如（8）的四元式。其中VN,VT,P均为非空的有限集，分别称为非终结符号集、终结符号集和产生式集，S∈VN为文法的开始符号。此外，将出现在各产生式左部和右部的一切符号所组成的集合称为（9），记作V。显然，V=VN∪VT,VN∩VT=。6．通常，可通过两种途径来构造词法分析程序。其一是根据对语言中各类单词的某种描述或定义，用(10)构造词法分析程序；另外一种途径是所谓词法分析程序的(11)。7．设G为一文法，A→α是G的一个产生式，如果α具有υAδ的形式，其中υ，δ不同时为ε，则称产生式A→α是（12）。若存在推导AA*，则称产生式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.下列文法中，不是产生语言{abna∣n≥1}的文法。A．A→aBaB→b∣bBB．A→aBB→ba∣bBC．A→aBB→ba∣bBaD．A→aBB→bCC→bC∣a2.设有文法G[S]：S→aABA→bAc∣εB→bB∣Ae∣ε则经消去ε-产生式后与G等价的文法G1[S]为。A．S→aA∣aB∣aAB∣aA→bc∣bAcB→bB∣Ae∣b∣eB．S→aABA→bAcB→bB∣AeC．S→aA∣aBA→bcB→b∣eD．S→aA∣aB∣aA→bc∣bAcB→bB∣Ae∣b∣e3.文法G产生的的全体是该文法描述的语言。A．句型B.终结符集C.非终结符集D.句子4.设M为一确定有限自动机，并设s和t是M的两个不同状态。如果s和t，则称s和t等价。A．不可区分B．可划分C．可区分D．待区分5.设有文法G[S]：S→aS∣W∣UU→aV→bV∣acW→aW则经化简后与G等价的文法G1[S]为。A．S→aS∣WV→bV∣acW→aWB．S→aS∣UU→aC．S→aS∣W∣UU→aW→aWD．S→aSV→bV∣ac6.若文法G定义的语言是无限集，则文法G必然是。A．前后文无关的B．递归的C．二义性的D．无二义性的7.下列说法中正确的是。A．一个确定的有限自动机实际上是相应的状态转换图的一种形式描述。B．一个状态转换图是由一组矢线连接的有限个结点所组成的无回路有向图。C．所谓一个DFAM状态数的最小化，是指构造一个与之等价的DFAM′，使它们有相同的接受集。D．对于有同一接受集的FA，与之等价的DFA在同构意义下是唯一的。8.下列文法中，不是产生语言}1{12nan的文法。A．A→aBaB→a∣aBaB．A→aBB→aa∣BaaC．A→aAAA→aD．A→aBBB→a∣aBB9.如下的表示形式中，不能表示程序语言中单词结构的是。A．左线性文法B．形如（Class，Value）的二元式C．正规式D．正规文法三、证明题1．试证明文法S→aB∣bAA→aS∣bAA∣aB→aBB∣bS∣b为二义性文法。（10分）2．试证明文法:S→aABA→aA∣aB→aB∣b为二义性文法。（10分）四、简答题1．试构造一文法，使其描述如下语言：（15分）L(G)={anbmcmdn∣m,n≥1}2．消除下列文法中的单产生式。（10分）S→AbB∣AA→AB∣caB∣BB→Aa∣b3．对正规式((a∣b)*∣ab*)b，构造与其相应的状态转换图。（15分）4．消除下列文法中的ε-产生式。（10分）S→ABb∣aA→aB∣caB∣εB→aA∣b∣ε5．试描述由下列文法所产生的语言。（10分）S→aAdA→aAd∣bBcB→bBc∣e6．消除下列文法中的单产生式。（10分）S→aFbM∣FF→M∣abcM→abF∣c7．化简下列文法：（10分）S→Bab∣cCB→bS∣bC→DaD→Cb∣CDa8．对正规式(a∣ab)*ab*，构造与其相应的状态转换图。（15分）9．试构造一正规文法，使其描述如下语言：（10分）L(G)={abmcbna∣m≥1,n≥0}10．试描述由下列文法所产生的语言。（15分）S→aAbBA→Aab∣εB→aA∣aCC→cC∣d五、应用题1．对于如下的状态转换矩阵(1)分别画出相应的状态转换图；（10分）(2)写出相应的3型文法。（10分）2．将如图所示的NFA确定化。（20分）3．将如图所示的具有ε动作的NFA确定化。（20分）4．将如图所示的DFA最小化。（20分）5．将如图所示的DFA最小化。（25分）6．对于如下的状态转换矩阵abcACBEBDCDDBECED初态:S终态:D(1)画出相应的状态转换图；（10分）(2)写出相应的3型文法。（10分）7．设有如下正规文法G[S]：S→aA∣aBA→bB∣bB→bB∣bCC→bC∣a（1）构造与文法G[S]相应的状态转换图；（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)外，还要执行相应的语义动作或调用相应的语义子程序。4．LL(1)分析表可用一个(8)表示，它的每一行与文法的一个非终结符号相关联，而其每一列则与文法的一个终结符号或(9)相关联。5．若在一个文法G中，不含有形如(10)的产生式，其中A,B∈VN，则称G为算符文法。6．将每一运算符都置于其(11)的表达式称为后缀表示，也称为逆波兰表示。7．把流程图中具有如下性质的一组结点称为程序中的一个循环：(ⅰ)在这组结点中，有惟一的(12)，使得从循环外到循环内任何结点的所有通路，都必通过此结点；(ⅱ)这一组结点是(13)。8．语法分析的基本任务是：根据语言的语法规则(即根据描述该语言的前后文无关文法)，分析源程序的(14)，即分析如何由这些单词组成各种语法范畴，并在分析过程中，对源程序进行(15)。9．所谓句型的素短语，是指一个句型中具有这样性质的短语：短语中至少含有一个(16)，且除它自身外，不再包含其它的(17)。10．一个文法符号X的(18)我们称之为语义属性或简称为属性，用形如X.ATTR的记号来表示文法符号X的相关语义属性。11．表示流程图中各结点间控制关系的一种直观而有效的方法是用树形结构，称之为(19)。12．目前，已存在许多语法分析方面的方法。但就产生语法树的方向而言，可大致把它们分为(20)和(21)两大类。13．将形如A→αX·β的项目称为A→α·Xβ的(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)文法。A．S→bBS′aS′→aBS′∣εA→S∣aB→AcB．S→bS∣bA∣bA→aA∣aC．E→E+T∣TT→T*F∣FF→(E)∣iD．S→bBS′S′→aBS′∣εA→S∣aB→Ac2.下列文法中，是简单优先文法。A．E→E+T∣TT→T*F∣FF→(E)∣iB．S→A/A→aA∣AS∣/C．E→E+E∣E*E∣(E)∣iD．E→E1E1→E1+T1∣T1T1→TT→T*F∣FF→(E)∣i3.当扫视到数组说明进行语义处理时，必须把一个数组的如维数、各维的上、下界等记录下来。为了便于引用，通常是把上述内容存放于数组相应的之中。A．信息向量B．内情向量C．地址向量D．指针向量4.下列说法中正确的是。A.所谓递归下降法，是指只能对具有左递归性的文法进行分析的一种语法分析方法。B.如果一个文法具有二义性，则它必然不是LL(1)文法。C.对于文法G，当进行自顶向下的语法分析时，不会出现回溯的主要条件是，对于G中的每个A∈VN，A产生式的所有不同候选式均能推导出以同一终结符号开始的符号串。D.对任意非LL(1)文法而言，通过消除左递归和反复提取左因子，都能将其改造为LL(1)文法。5.简单优先分析每次归约的是。A.最左直接短语B.直接短语C.最左素短语D.控制结点6.下列表示中，是与f×(e+(a×d+c)/d)相应的逆波兰式。A．fead×c+d/+×B．f×e+a×d+c/dC．fad×+c/d+e×D．ad×c+d/e+f×7.下列文法中，是LL（1）文法。A．S→aS∣aAA→bA∣acB．S→AS∣bA→SA∣aC．E→E+E∣E*E∣(E)∣iD．S→aS∣bAA→bA∣ac8.所谓相容，是指在一个项目集中，不出现这样的情况，和归约项目并存，或多个归约项目并存。A．移进项目B．基本项目C．待约项目D．后继项目9.下列表示中，不是目前经常使用的中间语言的形式。A．逆波兰式B．四元式C．五元式D．树形表示10.如果从流程图的首结点到流程图中某一结点n的所有通路都要经过结点d，我们就说结点d控制了结点n，或者把d称为n的必经结点，记作。A．dDFAnB．dDOMnC．dDAGnD．dDAMn11.下列说法中错误的是。A.任何LL(1)文法都是无二义性的。B.左递归文法必然不是LL(1)文法。C.对于任意一个前后文无关文法G，都能为其构造一个无多重定义的预测分析表。D.如果文法是左递归的，则自顶向下的分析过程将不能正常地进行。12.如下的语法分析方法中，要求文法中不含-产生式。A．预测分析法B．LR（1）分析法C．递归下降分析法D．算符优先分析法13.如下四元式中正确的是。A．（jnz，，，p）B．（j，A1，A2，p）C．（j，A1，A2，p）D．（j，A1，，p）14.如下的语法分析方法中，属于自顶向下的语法分析方法。A．LR（1）分析法B．算符优先分析法C．简单优先分析法D．LL（1）分析法15.下列四元式中，是变址取数四元式的形式。A．（=[]，X，0，T1[T]）B．（=[]，T1[T]，0，X）C．（[]=，T1[T]，X，0）