作业一1.已知文法G[A]，写出它定义的语言描述如：G[A]:A → 0B|1CB → 1|1A|0BBC → 0|0A|1CC2. 给出生成下述语言的上下文无关文法：（1）{ a n b n a m b m| n，m>=0}(2) { 1n0m 1m0n| n，m>=0}3. 给出生成下述语言的三型文法：(1){ a n b m|n,m>=1 }(2){a n b m c k|n,m,k>=0 }4、文法G[E]为：E→E+T|TT→T*F|FF→(E)|i试给出句型(E+F)*i的短语，简单(直接)短语,句柄。

第3章练习题一、判断题:1、编译程序中的词法分析程序以字符形式的源程序作为输入，输出的单词符号常采用二元组的形式。

2、正规式的运算符“|”读作“或“。

3、若两个正规式所表示的正规集相同，则认为二者是等价的。

4、用l代表字母，d代表数字，Σ={l，d}，则正规式r=dd*定义了无符号整数单词。

5、一个确定的有穷自动机DFA M的转换函数f是一个从KⅹΣ到K 的子集的映像。

6、一个非确定的有穷自动机NFA N 的转换函数f是一个从KⅹΣ*到K 的映像。

7、一张状态转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。

8、终态与非终态是可区别的。

9、对任意一个右线性文法G，都存在一个NFA M，满足L（G）=L（M）。

10、对任意一个右线性文法G，都存在一个DFA M，满足L（M）=L（R）。

二、构造正规式1(0|1)*101相应的DFA.练习题2一、判断题：1、空符号串的集合{ε}={}=ф。

2、设A是符号串的集合，则A0=ε。

3、设G是一个文法，S是开始符号，如果S => x且x∈V T*,则称x是文法G[S]的句型。

4、在形式语言中，最右推导的逆过程也称为规范归约。

5、一个语言的文法是唯一的。

6、若一个语言是无穷集合，则定义该语言的文法一定是递归的。

7、一个句型中出现某个产生式的右部，则此右部一定是此句型的句柄。

8、每个直接短语都是某规则的右部。

9、用二义性文法定义的语言也是二义性的。

10、文法的二义性与语言的二义性是两个不同的概念。

11、任何正规文法都是上下文无关文法。

12、正规文法对规则的限制比上下文无关文法对规则的限制要多一些。

二、选择题（从各题的4个答案中选出一个或多个正确的答案写在横线上）（1）一般程序设计语言的描述都涉及（）3个方面。

A 语法B 语用C 语义D 基本符号的确定（2）为了使编译程序能对程序设计语言进行正确的翻译，必须采用（）方法定义程序设计语言。

Ａ非形式化Ｂ自然语言描述问题Ｃ形式化 D自然语言和符号体系相结合（3）设x是符号串的幂运算 x0=（）。

A 1B xC εD Φ（4）设A是符号串的集合，则A*=（）。

A A1∪A2∪…∪A N∪…B A0∪A1∪A2∪…∪A N∪…C {ε}∪A+D A0∪A+（5）字母表中的元素可以是（）A 字母 B字母和数字 C 数字D字母、数字和其他符号（6）文法用来描述语言的语法结构，它由如下4个部分组成：（）和文法开始符号。

A文法终结符集合B 文法规则的集合C 文法非终结符集合D字母数字串（7）在规则中，符号“→”（：：=）表示（）。

A 恒等于B 等于C 取决于D 定义为（8）在规则中，符号“|”表示（）。

A 与B 或C 非D 定引导开关参数（9）设文法G[E]的规则如下：A→A1|A0|Aa|Ac|a|b|c ,该文法的句子是下列符号串（）A ab0B a0c01C aaaD bc10(10) 如果在推导过程中的任何一步α=>β,都是对α中的最右非终结符进行替换，则称这种推导为（）。

A．直接推导 B.最右推导 C. 最左推导 D.规范推导（11）描述语言L={a m b n|n≥m≥1}的文法为（）。

A.S→ABbB.S→ABbA→aA|a A→aA|aB→bB|b B→aBb | bC. S→Sb |AD.S→aAbA→aAb |ab A→Ab|aAb|ε(12) 设有文法G[S]=（{S，B} {b}, {S→bB |b ,B→bS}, S）,该文法描述的语言是（）。

A.L(G[S])={b n|n ≥0}B.L(G[S])={b2n |n ≥0}C.L(G[S])={b2n+1|n ≥0}D. L(G[S])={ b2n+1|n ≥1}(13) 一个句型最左边的（）称为该句型的句柄。

A．短语 B.素短语 C. 直接短语 D.规范短语(14)设有文法G[S]：E→E+T | E-T |TT→T*F |T/F|FF→(E) |i该文法的句型E+T*F的句柄是下列符号串（）。

A EB E+TC T*FD E+T*F(15) 设有文法G[T]：T→T*F |FF→F^P | PP→(T) |a该文法的句型T*P^(T*F)的直接短语是下列符号串（）。

A. PB. (T*F)C. T*FD. P^(T*F)(16) 若一个文法满足（），则称该文法是二义文法。

A.文法的某一个句子存在两棵（包括两棵）以上的语法树。

B.文法的某一个句子，它有两个（包括两个）以上的最右（最左）推导。

C.文法的某一个句子，它有两个（包括两个）以上的最右（最左）归约。

D.文法的某一个句子存在一棵（包括一棵）以上的语法树。

(17) 在下列描述含+，*算术表达式的文法中，属于二义性文法的是（）。

A．E→E+E|E*E|(E)|i B.E→EAE|(E)|iA→+|*C. E→E+T |TD.E→EAE|TT→T*F | F T→TBF|FF→(E) |I F→(E)|iA→+B→*(18)乔姆斯基把文法分成4种类型，即0型、1型、2型和3型。

2型文法也称为（）、3型文法也称为（）。

A.上下文无关文法B.正规文法C. 上下文有关文法 B.无限制文法1、如下程序流图(图11.18)中，B3中的i∶=2是循环不变量，可以将其提到前置结点吗?你还能举出一些例子说明循环不变量外移的条件吗?图11.182、2、对图11.19的流图：(1) 求出流图中各结点n的必经结点集D(n)；(2) 求出流图中的回边；(3) 求出流图中的循环。

图11.19语法分析部分一、判断题：1、LL（1）文法是无左递归、无二义性文法。

2、无左递归的文法是LL（1）文法。

3、在高级语言编译程序常用的语法分析方法中，预测分析法属于自上而下的语法分析方法。

4、在高级语言编译程序常用的语法分析方法中，算符优先分析法属于自上而下的语法分析方法。

5、算符优先分析法是一种规范规约分析法。

6、算符优先分析法是最适合于分析算术表达式。

7、设有一个LR（0）项目集I={X->α.Bβ,A->α.},该项目集含有“移进—归约”冲突。

8、LR分析法是一种规范规约分析法。

9、设有一个LR（1）项目集I={[X->α.bβ, α],[A->α. ，α]},该项目集含有“移进—归约”冲突。

10、SLR（1）文法是二义性文法。

二、选择题（从四个答案中选择一个或多个正确答案写在横线上）1、编译程序中语法分析常用的方法__________________.A. 自上而下分析法B.自下而上分析法C．自左向右分析法 D.自右向左分析法2、编译程序的语法分析器接受以_________________为单位的输入，并产生有关信息供以后各阶段使用。

A. 表达式B.字符串C．单词 D.语句3、在高级语言编译程序常用的语法分析方法中，递归下降分析法属于_____________分析法。

A. 自左向右分析法B.自上而下分析法C．自下而上分析法 D.自右向左分析法4、递归分析法和预测分析法要求描述的文法是_____________。

A. 正规文法B. LR（1）文法C. LL（1）文法D. 右线性文法5、设有文法G[E]：E–>TE’E’–> +TE’| εT –> FT’T‟–> *FT‟ | εF –> (E)|idFIRST(T‟)=__________________, FOLLOW(F)=______________________.A. {(, id )B. {*,ε}C. {*,+,},#}D. {+,),#}6、自下而上语法分析法的原理是__________________.A. “移进-推导法”B. “移进-归约法” C．“最左推导法” D. “推导-归约法”7、设有文法G，如果文法G中没有形如A->…BC…的规则，其中A，B，C为非终结符，则称文法G为_____________.A. 算符优先文法B. LL（1）文法C. LR（1）文法D. 算符文法9、设有文法G[E]:E->E+T|TT->T*F|FF->(E)|a句型T+T*F+a的素短语是_______________.A. aB. T*FC.TD.T+T*F10、设有文法G[S]：S->a|∧|(T)T->T,S|S其中FIRSTVT(T)=______________________, LASTVT(T)=_________________________. A. {a ,(,)} B. {a ,(, ∧)C. {a ,(,‟,‟)D. {a ,(,‟,‟, ∧)E. {$,}}F. {$,},a}G.{a,},‟,‟} H. {…,‟,）,a, ∧}11、LR（0）项目集规范族的项目类型可分为__________________.A. 移进项目B. 归约项目C 待约项目 D. 接受项目12、LR（0）分析器的核心部分是一张分析表，这张分析表包括两部分，它们是_________.A.LL(1)分析表B. 分析动作表C 状态转换表 D. 移进分析表13、设有LR（0）项目集I={X->α. bβ, A->α.,B->α.},该项目集含有冲突项目，它们是__________________. A、“移进—归约”冲突 B.“移进—接受”冲突C “移进—待约”冲突D. “归约—归约”冲突第五章自测练习题判断题：1、对任何一个编译程序来说，产生中间代码是不可缺少的一部分。

2、目前多数编译程序进行语义分析的方法采用语法制导翻译法，这是因为语法制导翻译法是一种形式化系统。

3、一个属性文法包括一个上下文无关文法和一系列规则。

4、文法符号的属性有两种，一种称为继承属性，另一种称为综合属性。

5、自下而上语法制导翻译法的特点是语法分析栈与语义分析栈不需同时操作。

6、自下而上语法制导翻译法的特点是在栈顶形成句柄，在归约之前执行相应的语义动作。

7、逆波兰表达式ab+cd+*所代表的中缀形式的表达式是a+b*c+d.8、赋值语句A=A+B*C^(D/E)/F的逆波兰表示是AABCDE/^*F/+=9、表达式-(a+b)*(c+d)-(a+b+c)的四元式表示是：（1）(T1=a+b)（2）(T2=-T1)（3）(T3=c+d)（4）(T4=T2*T3)（5）(T5=a+b)（6）(T6=T5+c)（7）(T7=T4-T6)选择题：（1）编译程序的语义处理有两个任务：一个是（），另一个是（）。