《编译原理》练习题

《《编译原理》练习题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《编译原理》练习题一一、填空题（每空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．我们常采用

2、形如(class,value)的二元式作为一个单词的(6)。其中,class是一个整数，用来指示该单词的(7)，value则是单词之值。5．一个文法G[S]可表示成形如（8）的四元式。其中VN,VT,P均为非空的有限集，分别称为非终结符号集、终结符号集和产生式集，S∈VN为文法的开始符号。此外，将出现在各产生式左部和右部的一切符号所组成的集合称为（9），记作V。显然，V=VN∪VT,VN∩VT=Æ。6．通常，可通过两种途径来构造词法分析程序。其一是根据对语言中各类单词的某种描述或定义，用(10)构造词法分析程序；另外一种途径

3、是所谓词法分析程序的(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．如果从状态转换图的初态出发，分别沿着一切可能的路径到达(1

4、8)，并将每条路径各矢线上的(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→

5、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．

6、S→aSV→bV∣ac6.若文法G定义的语言是无限集，则文法G必然是。A．前后文无关的B．递归的C．二义性的D．无二义性的7.下列说法中正确的是。A．一个确定的有限自动机实际上是相应的状态转换图的一种形式描述。B．一个状态转换图是由一组矢线连接的有限个结点所组成的无回路有向图。C．所谓一个DFAM状态数的最小化，是指构造一个与之等价的DFAM′，使它们有相同的接受集。D．对于有同一接受集的FA，与之等价的DFA在同构意义下是唯一的。8.下列文法中，不是产生语言的文法。A．A→aBaB→a∣aBaB．A→aBB→aa∣BaaC

7、．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→

8、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．消除下列文法中的单产生式