《编译原理》期中及期末习题

3.5.36 语言L是所有由偶数个0和偶数个1组成的句子的集合,给出定义L的正规文法。

3.5.37 已知文法G[S]:S→ABS|AB

AB→BA A→0 B→1

该文法是几型的?该文法所产生的语言是什么?(用自然语言描述)写出与该文法等价的CFG文法。

3.5.8 写一个上下文无关文法G,使得L(G)={anbmcmdn|n≥0,m≥1}。

3.5.39 写一个文法G,使其语言为L(G)={ anbm|n≥m≥1}。

3.5.40 生成语言1={albmclanbn|1>=O,m>=1,n>=2}的文法是什么?它是Chomsky那一型文法?

3.5.41文法G[P]:P→aPQR|abR

RQ→QR bQ→bb bR→be cR→cc

它是Chomsky哪一型文法?请证aaabbbccc是G[P]的一个句子。

3.5.42文法G[S]:S→aSPQ|abQ

QP→PQ bP→bb bQ→be cQ→cc

(1)它是Chomsky哪一型文法? (2)它生成的语言是什么?

3.5.43 给定文法G[S]:S→(S)S|ε,给出句子(()())()()的规范推导,并指出每步推导所得句型的句柄,画出该句子的语法推导树,指出所有的短语和直接短语。

3.5.44 设文法G[S]:S→(A)|a

A→A+S|S

(1)构造各非终结符的FIRSTVT和LASTVT集合。 (2)构造优先关系表。

3.5.45已知文法G[S]:S→dAB

A→aA|a B→Bb|ε

(1)试问G[S]是否为正规文法,为什么? (2)G[S]所产生的语言是什么?

(3) G[S]能否改写为等价的正规文法?

3.5.46 选择题

有文法G[S]:S→aA|a|bC,A→aS|bB,B→aC|bA|b,C→aB|bS,则_____为L(G) 中句子。

a. aloob5oabloo b. alooob5ooaba

c. a500b60aab2a d. a l00 b4oab10 aa

3.5.47 对文法G[S‘]:S‘→#S#

S→fstS S→i=E E→E+T|T T→P↑T|P P→(E)|i

(1)求各非终结符的FIRSTVT和LASTVT集合。 (2)构造该文法的优先关系表。(请将终结符以=+、↑、(、i, f, t,)、#的顺序构造优先关系表)

3.5.48 有文法R::=i|(T),T::=T,R|R,完成表3.21所示的算符优先关系表(填写第一、第二行)。

3.5.49 文法G[M]是否LL(1)的,说明理由。 G[M]:M→TB T→Ba|ε B→Db|eT|ε D→d|ε

3.5.50 将文法G[E]改写为等价的LL(I)文法,并给出相应的预测分析表。 G[E]:E→[T T→F]|TE F→i|Fi 3.5.51 已知文法G[S]: S→S*aP|aP|*aP P→+aP|+a

(1)将文法G[S]改写为LL(1)文法G‘[S]。 (2)写出文法G' [S]的预测分析表。

5

※<习题四>

第四章

典型例题: 单项选择题

语法分析器的自动构造

4.1.1.若a为终结符,则A→a·aβ为_____项目。 a.归约 b.移进 c.接受 d.待约

4.1.2.两个LR(1)项目集如果除去______后是相同的,则称这两个LR(1)项目同心。 a.项目 b.活前缀 c.搜索符 d.前缀 4.1.3.同心集合并不会产生—冲突。

a.二义 b.移进/移进 c.移进/归约 d.归约/归约 4.1.4.左结合意味着_____。

a.打断联系实行移进 b.打断联系实行归约 c.建立联系实行移进 d.建立联系实行归约 4.1. 5.若项目集Ik含有A→a·,则在状态k时,仅当面临的输入符号a∈FOLLOW(A) 时,才采取“A→a·”动作的一定是_____。

a. LALR文法 b. LR(0)文法 c. LR(1)文法 d. SLR(1)文法 4.1.6.就文法的描述能力来说,有_____。 a. SLR(1)cLR(0) b. LR(1)cLR(0) c. SLR(1)cLR(1) d.无二义文法cLR(1)

4.1. 7.在LR(0)的ACTION子表中,如果某一行中存在标记为\”的栏,则____。 a.该行必定填满ri b.该行未填满ri

c.其他行也有ri d. goto子表中也有ri

4.1.8.一个____指明了在分析过程中的某时刻所能看到产生式多大一部分。 a.活前缀 b.前缀 c.项目 d.项目集 4.1.9.若B为非终结符,则A→a·Bβ为____项目。 a.接受 b.归约 c.移进 d.待约 4.1.10.同心集合并有可能产生新的_冲突。

a.归约 b.移进/移进 c.移进/归约 d.归约/归约 4.1.11.右结合意味着_。

a.打断联系实行归约 b.建立联系实行归约 c.建立联系实行移进 d.打断联系实行移进 4.1.12.若项目集Ik含有A→a·,则在状态K时,无论面临什么输入符号都采取“A→α 归约”的动作一定是_。

a. LR(1)文法 b. LALR(1)文法 c. LR(0)文法 d. SLR(1)文法 4.1.13.就文法的描述能力来说,有_。

a.无二义文法cSLR(1) b. LR(0) cLR(1) c.无二义文法cLR(0) d. LR(1) cLR(0)

多项选择题:

4.2.1.一个LR分析器包括____。

a.一个总控程序 b.一个项目集。 c.一个活前缀 d.一张分析表 e.一个分析栈

4.2.2 .LR分析器核心部分是一张分析表,该表包括_____等子表。 a. LL(1)分析 b.优先关系 c. GOTO d. LR e. ACTION

4.2.3.每一项ACTION[S,a]所规定的动作包括______。

a.移进 b.比较 c.接受 d.归约 e.报错

4.2.4.对LR分析表的构造,有可能存在_____动作冲突。

a.移进 b.归约 c.移进/归约 d.移进/移进e .归约/归约 4.2.5.就文法的描述能力来说,有____。

a. SLR(1)c LR(1) b. LR(0) c SLR(1)c. LR(0) c LR(1) d. LR(1)c无二义文法 e. SLR(1)c无二义文法 4.2.6.对LR分析器来说,存在____等分析表的构造方法。

a. LALR b. LR(0) c. SLR(1) d. SLR(0) e. LR(1) 4.2.7.自上而下的语法分析方法有___。

a.算符优先分析法 b. LL(1)分析法 c. SLR(1)分析法 d. LR(0)分析法 e. LALR(1)分析法

填空题:

4.3.1.对于一个文法,如果能够构造___,使得它的____均是唯一确定的,则称该文法 为LR文法。

4.3.2.字的前缀是指该字的____。

4.3.3.活前缀是指_____的一个前缀,这种前缀不含_____之后的任何符号。

4.3.4.在LR分析过程中,只要_的已扫描部分保持可归约成一个____,则扫描过的 部分正确。

4.3.5.将识别____的NFA确定化,使其成为以_____为状态的DFA,这个DFA就是建 立的基础。

4.3.6. A→a·称为_____项目;对文法开始符S',称S'→a·为___项目;若a为

终结符,则称A→a·aβ为___项目;若B为非终结符,则称A→a·Bβ为_____项目。 4.3.7. LR(0)分析法的名字中“L”表示,“R”表示,\”表示______。 4.3.8.一个LR分析器包括两部分:________和_______.

4.3.9.两个LR(1)项目集如果除去______后是相同的,则称这两个LR(1)项目集_____。 4.3.10.构成识别一个文法____的DFA的项目集全体,称为这个文法的LR(0) _____.

4..3.11.一个活前缀γ的____,就是从识别文法活前缀DFA的初态出发,经读出γ后所到达的那个

4.3.12.左结合意味着打断联系实行____,右结合意味着打断联系实行_____。 4.3.13.同心集合并不会产生—冲突,但可能产生____冲突。

判断题:

4.4.1. LR分析法在自左至右扫描输入串时就能发现错误,但不能准确地指出出错地点。 ()

联系客服:779662525#qq.com(#替换为@)