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