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

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分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。 （）

4.4.2.构造LR分析器的任务就是产生LR分析表。 （） 4.4.3 .LR文法肯定是无二义的，一个无二义文法决不会是LR文法。 （） 4.4.4.在任何时候，分析栈的活前缀X1X2...Xm的有效项目集就是栈顶状态Sm所在的那个 项目集。 （） 4.4.5．同心集的合并有可能产生新的“移进”／“归约”冲突。 （） 4.4.6.由于LR(0)分析表构造简单，所以它的描述能力强、适用面宽；LR(1)分析表因构造复杂而描述能力弱、适用面窄。 （） 4.4.7．所有LR分析器的总控程序都是一样的，只是分析表各有不同。 （） 4.4.8. LR分析技术无法适用二义文法。 （） 4.4.9.项目A→β1·β2对活前缀αβ1是有效的，其条件是存在规范推导S'*=>aAW=> a β

1β2ω。 （）

4.4.10. SLR(1)文法的特点是：当符号栈中的符号串为βα，而面临的输入符号为α则存在 把α归约为A的规范句型的前缀β Aα时，方可把a归约为A。 （ ）

综合题

4.5.1请指出图4.2中的LR分析表（a）、（b）、（c）分属LR（0）、SLR和LR（1）中的那一 种，并说明理由。

4.5.2文法G的产生式如下：

S→BB B～aB|b

请分别构造该文法的（1) LR (0）分析表；(2）SLR分析表；(3）规范LR分析表（即 LR（1）分析表）；（4）LALR分析表。

4.5.3什么是规范句型的活前缀？引进它的意义何在？

4.5.4对于文法G[S］：S→AS|b A→SA|a (1)列出所有LR (0)项目。

(2)根据列出的项目构造识别文法活前缀的NFA并确定化为DFAo （3)证明DFA的所有状态全体构成文法LR（0)规范族。

4.5.5 LR分析器与优先关系分析器在识别句柄时的主要异同是什么？

4.5.6 LR（0）、SLR(1), LR（1)及LALR有何共同特征？它们的本质区别是什么？试论述之。 4.5.7 为二义文法G构造一个LR分析表（详细说明构造方法）。其中终结符“，”满足右结

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《编译原理》期中及期末习题(5)在线全文阅读。