编译原理习题集与答案解析(整理后) 下载本文

内容发布更新时间 : 2024/3/29 20:44:25星期一 下面是文章的全部内容请认真阅读。

精品

R→cS

2、在自下而上的语法分析中,语法树与分析树一定相同。 ( ) 3、二义文法不是上下文无关文法。 ( ) 4、语法分析时必须先消除文法中的左递归。 ( ) 5、规范归约和规范推导是互逆的两个过程。 ( ) 6、一个文法所有句型的集合形成该文法所能接受的语言。 ( ) 五、简答题

1、句柄 2、素短语 3、语法树 4、归约 5、推导 六、问答题

1、给出上下文无关文法的定义。 2、文法G[S]:

S→aSPQ|abQ QP→PQ bP→bb bQ→bc cQ→cc

(1)它是Chomsky哪一型文法? (2)它生成的语言是什么? 3、按指定类型,给出语言的文法。

L={aibj|j>i≥1}的上下文无关文法。 4、有文法G:S→aAcB|Bd

A→AaB|c B→bScA|b

(1)试求句型aAaBcbbdcc和aAcbBdcc的句柄; (2)写出句子acabcbbdcc的最左推导过程。 5、对于文法G[S]:

S→(L)|aS|a L→L, S|S

(1)画出句型(S,(a))的语法树。(2)写出上述句型的所有短语、直接短语、句柄和素短语。 6、考虑文法G[T]:

T→T*F|F F→F↑P|P P→(T)|i

证明T*P↑(T*F)是该文法的一个句型,并指出直接短语和句柄。

单选[解答] 1、选c。

2、选a。 3、选c。

4、虽然a与b没有优先关系,但构造优先函数后,a与b就一定存在优先关系了。所以,由f(a)>g)(b)或f(a)

5、如果文法G无二义性,则最左推导是先生长右边的枝叶:对于d,如果有两个不同的是了

E E + F 感谢下载载

精品

左推导,则必然有二义性。故选a。

6、选c。

7、由图2-8-1的语法树和优先关系可以看出应选b。

8、规范推导是最左推导,故选d。

9、由T→T,…和T→(… 得FIRSTVT(T))={(,,)};

由T→S得FIRSTVT(S)?FIRSTVT(T),而FIRSTVT(S)={b,∧,(};即

FIRSTVT(T)={b,∧,(,,}; 因此选c。

10、d 11、c 12、b 13、b 14、b

多选解答 1、e、a、c 2、a、c、e 3、b、c、d 4、a、c 5、b、c 6、a、b、c、d、e 填空解答 1、空集 终结符 右 2、最左

3、自上而上 自下而上 4、自上而上

5、语法 分析 6、移进 接受

7、4 2 型 3型 上下文无关语言 正规语言 下推自动机 有限 判断解答 1、对 2、错 3、错 4、错 5、错 6、错

简答[解答]

1、句柄:一个句型的最左直接短语称为该句型的句柄。

2、素短语:至少含有一个终结符的素短语,并且除它自身之外不再含任何更小的素短语。 3、语法树:满足下面4个条件的树称之为文法G[S]的一棵语法树。 ①每一终结均有一标记,此标记为VN∪VT中的一个符号;

②树的根结点以文法G[S]的开始符S标记;

③若一结点至少有一个直接后继,则此结点上的标记为VN中的一个符号;

④若一个以A为标记的结点有K个直接后继,且按从左至右的顺序,这些结点的标记分别为X1,X2,…,XK,则A→X1,X2,…,XK,必然是G的一个产生式。

4、归约:我们称αγβ直接归约出αAβ,仅当A→γ 是一个产生式,且α、β∈(VN∪VT)*。归约过程就是从输入串开始,反复用产生式右部的符号替换成产生式左部符号,直至文法开始符。

5、推导:我们称αAβ直接推出αγβ,即αAβ?αγβ,仅当A→ γ 是一个产生式,且α、β∈(VN∪VT)*。如果α1?α2?…?αn,则我们称这个序列是从α1至α2的一个推导。若存在一个从α1αn的推导,则称α1可推导出αn。推导是归约的逆过程。

感谢下载载

精品

问答1[解答]

一个上下文无关文法G是一个四元式(VT,VN,S, P),其中: ●VT是一个非空有限集,它的每个元素称为终结符号;

●VN是一个非空有限集,它的每个元素称为非终结符号,VT∩VN=Φ; ●S是一个非终结符号,称为开始符号; ●P是一个产生式集合(有限),每个产生式的形式是P→α,其中,P∈VN, α∈(VT∪VN)*。开始符号S至少必须在某个产生式的左部出现一次。

2[解答] (1)由于产生式左部存在终结符号,且所有产生式左部符号的长度均小于等于产生式右部的符号长度,所以文法G[S]是Chomsky1型文法,即上下文有关文法。

(2)按产生式出现的顺序规定优先级由高到低(否则无法推出句子),我们可以得到: S?abQ?abc

S?aSPQ?aabQPQ?aabPQQ?aabbQQ?aabbcQ?aabbcc

S?aSPQ?aaSPQPQ?aaabQPQPQ?aaabPQQPQ?aaabPQPQQ?aaaPPQQQ? aaabbPqqq?aaabbQQQ?aaabbbcQQ?aaabbbccQ?aaabbbccc ……

于是得到文法G[S]生成的语言L={anbncn|n≥1} 3【解答】

(1)由L={aibj|j>i≥1}知,所求该语言对应的上下文无关文法首先应有S→aSb型产生式,以保证b的个数不少于a的个数;其次,还需有S→Sb或S→bS型的产生式,用以保证b的个数多于a的个数;也即所求上下文无关文法G[S]为:

G[S]:S→aSb|Sb|b 4【解答】(1)分别画出对应两句型的语法树,如图2-8-2所示 句柄:AaB Bd

B d c b (a)

A a B b S c A a A c B S a A c B B S c A B d c (b) S 感谢下载载

精品

图2-8-2 语法树

(2)句子acabcbbdcc的最左推导如下:

S?aAcB?aAaBcB?acaBcB?acabcB?acabcbScA?acabcbBdcA ?acabcbbdcA?acabcbbdcc 5【解答】

S ( L ) (1)句型(S,(a))的语法树如图2-8-3所示 L , S

S ( L ) S a

图2-8-3 句型(S,(a))的语法树

(2)由图2-8-3可知:

①短语:S、a、(a)、S,(a)、(S,(a)); ②直接短语:a、S; ③句柄:S;

④素短语:素短语可由图2-8-3中相邻终结符之间的优先关系求得,即;

# ·(·, ·( ·a· )· )· # 因此素短语为a。 6【解答】

首先构造T*P↑(T*F)的语法树如图2-8-4所示。

由图2-8-4可知,T*P↑(T*F)是文法G[T]的一个句型。 直接短语有两个,即P和T*F;句柄为P。

T * F T * F 图2-8-4 句型T*P↑(T*F)的语法树 F ↑ P P ( T ) T 感谢下载载

精品

第三章

一、单项选择题

1、词法分析所依据的是 。

a. 语义规则 b. 构词规则 c. 语法规则 d. 等价变换规则 2、词法分析器的输出结果是 。

a. 单词的种别编码 b. 单词在符号表中的位置 c. 单词的种别编码和自身值 d. 单词自身值 3、正规式M1和M2等价是指 。

a. M1和M2的状态数相等 b. M1和M2的有向弧条数相等

c. M1和M2所识别的语言集相等 d. M1和M2状态数和有向弧条数相等 4、状态转换图(见图3-6-1)接受的字集为 。

a. 以 0开头的二进制数组成的集合 b. 以0结尾的二进制数组成的集合 c. 含奇数个0的二进制数组成的集合 d. 含偶数个0的二进制数组成的集合 5、词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确,因此, 。 a. 词法分析器应作为独立的一遍 b. 词法分析器作为子程序较好

c. 词法分析器分解为多个过程,由语法分析器选择使用 d. 词法分析器并不作为一个独立的阶段 二、多项选择题

1、在词法分析中,能识别出 。 a. 基本字 b. 四元式 c. 运算符 d. 逆波兰式 e. 常数

2、令∑={a,b},则∑上所有以b开头,后跟若干个ab的字的全体对应的正规式为 。 a. b(ab)* b. b(ab)+ c.(ba)*b

+d. (ba)b e. b(a|b)

三、填空题

1、确定有限自动机DFA是 的一个特例。

2、若二个正规式所表示的 相同,则认为二者是等价的。 3、一个字集是正规的,当且仅当它可由 所 。 四、判断题

1、一个有限状态自动机中,有且仅有一个唯一终态。 ( ) 2、设r和s分别是正规式,则有L(r|s)=L(r)|L(s)。 ( ) 3、自动机M和M′的状态数不同,则二者必不等价。 ( ) 4、确定的自动机以及不确定的自动机都能正确地识别正规集。 ( ) 5、对任意一个右线性文法G,都存在一个NFA M,满足L(G)=L(M)。 ( ) 6、对任意一个右线性文法G,都存在一个DFA M,满足L(G)=L(M)。 ( ) 7、对任何正规表达式e,都存在一个NFA M,满足L(G)=L(e)。 ( )

0 X 1 Y 0 图3-6-1 感谢下载载