篇一：编译原理复习题
一、填空题：（10分，第1小题每2个1分，其余每空1分）
1、编译程序一般含有八部分，分别是、 、
2、编译程序与解释程序的根本区别是
3、一个上下文无关文法G包括四个组成部分依次为：一组_____、一个_____、一组_____、一组______。
4、设G是一个文法，S是文法的开始符号，如果S?* X，则称X是。
二、选择题（本大题共15小题，每小题1分，共15分）
1、编译程序生成的目标程序是机器语言程序。
A、一定 B、 不一定
2、设有文法G[S]=（{b},{S,B},S,{S→b|bB, B→bS}）,该文法描述的语言是 。
A、bi | i≥0B、b2i | i≥0 C、b2i+1 | i≥0 D、b2i+1 | i≥1
3、设有文法G[S]： S→S*S|S+S|（S）|a
该文法 二义性文法
A、是 B、不是C、无法判断
4、汇编程序是将______翻译成______；编译程序是将_______翻译成__________。
A、汇编语言程序B、机器语言程序
C、高级语言程序 D、汇编语言或机器语言程序
5、给定文法A→bA|cc, 下面符号串中，为该文法句子的是① cc ② bcbc ③ bcbcc ④ bccbcc ⑤bbbcc
A、① B、①③④⑤C、①⑤ D、①④⑤E、①②③④⑤
6、语法分析的常用方法是。
①自顶向下 ②自底向上 ③ 自左向右④自右向左
A、①②③④B、①② C、③④D、①②③
7、已知语言L={anbbn|n≥1}，则下述文法中， 可以产生语言L
A、Z→aZb|aAb|bA→aAb|bB、A→aAb A→b
C、Z→AbB A→aA|a B→bB|b D、Z→aAb A→aAb|b
8、下列正规表达式中________与(a|b)*(c|d)等价。
A、（a*|b*）(c|d) B、（a*|b*）*(c|d) C、(ab)*(d|c) D、（a*b*）(cd)
9、算符优先分析法每次都是对进行归约。
A、最左短语 B、直接短语 C、句柄 D、素短语E、最左素短语
10、简单优先分析法每次都是对进行归约
A、最左短语 B、直接短语 C、句柄 D、素短语E、最左素短语
11、下列文法G[S] ]：S→AA A→Aa|a不是LR（1）文法，理由是
A.、FIRST(S)∩FIRST（A）≠? B、FIRST（A）∩FOLLOW（A）≠?
C、FIRST（Aa）∩FIRST（a）≠?D、都不是
12、设有文法G[E]：E→E*E|E+E|（E）|a 该文法LR（1）文法
A、是 B、不是 C、无法判断
13、对于文法G[A]：A→aABe|BaB→dB|?
有人说，因为FIRST（aABe）∩FOLLOW（A）≠? 并且FIRST（Ba）∩FOLLOW
（A）≠?，所以文法G[A]不是LL（1）文法。这种说法
A、正确 B、不正确
14、素短语是指_______的短语。
①至少包含一个符号
②至少包含一个非终结符号
③至少包含一个终结符号
④除自身外不再包含其它终结符号
⑤除自身外不再包含其它非终结符号
⑥除自身外不再包含其它短语
⑦除自身外不再包含其它素短语
可选项有：
A、①④ B、①⑤C、①⑥D、②④E、③⑤F、③⑦ G、②⑦
15、表达式A*（B-C*（C/D））的逆波兰式为
A、 ABC-CD/** B、 ABCCD/*-*
C、 ABC-*CD/* D、都不正确
三、简答题（共35分）
1、 (10分)现有文法G[E]:
E→E+T|E-T|TT→T*F|T/F|F F→(E)|i
画出句型E+F*（E+i）的语法树,找出它的短语，直接短语，句柄和素短语
2、 (5分)对下面的文法G[S]构造状态转换图,并说明符号串aaba是否是该文法接受的句子： S→aA S→B A→abS A→bB B→b B→cC C→D D→d D→bB
3、 (10分)将下面具有?的NFA确定化
4、 (5分)求出下列文法所产生语言对应的正规式。S→aAA→bA|aB|bB→aA。
(5分)构造识别下面正规式的NFA （a|b）*ba。
二、选择题（本大题共20小题，每小题1分，共20分）
1、汇编程序是将______翻译成______；编译程序是将_______翻译成__________。 a、汇编语言程序b、机器语言程序 c、高级语言程序 d汇编语言或机器语言程序
2、描述一个语言的文法是___________。
a、唯一的 b、不唯一的 c、个数有限的
3、生成非0开头的正偶数集的文法是______________。
a、Z::=ABC c、Z::=ABC|2|4|6|8
C::=0|2|4|6|8C::=0|2|4|6|8
B::=BA|B0|ε B::=BA|B0|0
A::=1|2|3|4|5|6|7|8|9 A::=1|2|3|4|5|6|7|8|9
b、Z::=ABC d、Z::=ABC|2|4|6|8
C::=0|2|4|6|8C::=0|2|4|6|8
B::=BA|B0|0B::=BA|B0|ε
A::=1|2|3|4|5|6|7|8|9A::=1|2|3|4|5|6|7|8|9
4、设有文法G[I]：
I→I0|I1|I a|Ic|a|b|c
下列符号串中是该文法的句子的有___________________。
①ab0 ②a0c01 ③aaa ④bc10
可选项有
a、① b、②③④ c、③④ d、①②③④
5、现有前缀表示的表达式文法G1：
E::=-EEE::=-E E::=a|b|c
则文法的句子—a-bc的所有可能语法树有______棵。
a、1b、2 c、3 d、4
6、一个上下文无关文法G包括四个组成部分依次为：一组_____、一个_____、一组_____、一组______。
a、字符串b、字母数字串 c、产生式 d、结束符号e、开始符号 f、文法 g、非终结符号 h、终结符号
7、语法分析的常用方法是_________：
①自顶向下 ②自底向上 ③自左向右 ④自右向左
可选项有：
a、①②③④ b、①② c、③④ d、①②③
8、下列文法__________二义文法
E::=EiT|T T::=T+F|iF|F F::=E*|(
可选项有： a、是 b、不是 c、无法判断。
9、素短语是指_______的短语。
①至少包含一个符号
②至少包含一个非终结符号
③至少包含一个终结符号
④除自身外不再包含其它终结符号
⑤除自身外不再包含其它非终结符号
⑥除自身外不再包含其它短语
⑦除自身外不再包含其它素短语
可选项有：
a、①④ b、①⑤ c、①⑥ d、②④ e、③⑤ f、③⑦g、②⑦
10、LR（K）文法是_________。
a、从左到右分析，共经过K步的一种编译方法。
b、从左到右分析，每次向前预测K步的一种编译方法。
c、从左到右分析，每次向貌似句柄的符号串后看K个输入符号的一种编译方法。 d、从左到右分析，每次走K步的一种编译方法。
11、在编译中产生语法树是为了____________。
a、语法分析 b、语义分析 c、词法分析 d、产生目标代码
12、文法的二义性和语言的二义性是两个____________概念。
a、不同 b、相同c、无法判断
13、下述正规表达式中________与(a*+b)*(c+d)等价。
① a*（c+d）+b（c+d）
② a*（c+d）*+b（c+d）*
③ a*（c+d）+b*（c+d）
⑤ （a*+b）*c+（a*+b）*d
可选项有:a、① b、② c、③ d、④ e、⑤ f、④⑤ g、③④⑤
14、_______这样的语言，他们能被确定的有限自动机识别，但不能用正规表达式表示： a、存在 b、不存在 c、无法判定是否存在
15、LL（K）文法________二义性的。
a、都是 b、都不是 c、不一定都是
16、下面的文法是__________。S::=aAa|aBb|bAb|bBa A::=x B::=x
可选项有：a、LR（1）文法 b、LALR（1）文法 c、都不是 d、a和b
17、编译过程中，比较常见的中间语言有___________。
①波兰表示
②逆波兰表示
③三元式
④四元式
⑤树形表示
可选项有：a、①③④ b、②③④c、③④①⑤d、②③④⑤
18、-a-（b*c/（c-d）+（-b）*a）的逆波兰表示是___________。
a、abc*cd-b-a*+/-- b、a-bc*cd-b-a*+/-
c、a-bc*cd-/b-a*+- d、a-bc*/cd-b-a*+-
19、在编译程序中安排中间代码生成的目的是_______________。
①便于进行存储空间的组织
②利于目标代码优化
③利于编译程序的移植
④利于目标代码的移植
⑤利于提高目标代码的质量
可选项有：
a、②④ b、①②③c、③④①d、②③④⑤
20、代码优化的主要目标是_____________。
①如何提高目标程序的运行速度
②如何减少目标程序运行所需的空间。
③如何协调①和②
④如何使生成的目标代码尽可能简短
可选项有：
a、②④ b、①②③c、③④① d、②③④
三、简答题：（每小题5分，共35分）
1、 证明下面文法是二义性的。S::=ibtSeS|ibtS|a
2、 现有文法S::=SaA|AA::=AbB|B B::=cSd|e
请证实是文法的一个句型，并写出该句型的所有短语、素短语以及句柄。
3、 求出下列文法所产生语言对应的正规式。
S::=bS|aAA::=aA|bBB::=aA|bC|bC::=bS|aA
4、 将表达式((a*d+c)/d+e)*f+g分别表示三元式、四元式、逆波兰式序列
5、 消除下列文法的左递归。
S::=SaP|Sf|P P::=QbP|QQ::=cSd|e
6、 给出与下图的NFA等价的正规文法。
7、对基本块P画出DAG图
B:=3
D:=A+C
E::=A*C
F:=E+D
G:=B*F
H:=A+C
I:=A*C
J:=H+I
K:=B*5
L:=K+J
M:=L
假定只有L在基本块出口之后活跃，写出优化后的四元式序列。
1、 文法G1：P→ aPQR| abR，RQ→ QR，BQ→ bb，bR→ bc，cR→ cc，它是chomsky哪一型文法？
A、0型B、1型 C、2型 D、3型
2、编译程序必须完成的工作有
①词法分析 ②语法分析 ③语义分析 ④代码生成 ⑤中间代码生成 ⑥代码优化
①②③④ B、①②③④⑤ C、①②③④⑥ D、①②③④⑤⑥
3、LR（K）文法________二义性的。
A、都是 B、都不是 C、不一定都是
4、语法分析的常用方法是________。
①自顶向下 ②自底向上 ③ 自左向右④自右向左
篇二：编译原理(选择、填空、简答)题
一、是非题(下列各题，你认为正确的，请在题干的括号内打“√”，错的打“×”。每题1分,共5分)
1、算符优先关系表不一定存在对应的优先函数。 √
2、数组元素的地址计算与数组的存储方式有关。√
3、仅考虑一个基本块，不能确定一个赋值是否真是无用的。√
4、每个文法都能改写为LL(1)文法。×
5、对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。×
6、一个LL(1)文法一定是无二义的。
7、逆波兰法表示的表达式亦称前缀式。
8、目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。
9、正规文法产生的语言都可以用上下文无关文法来描述。
10、一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态 。
二、选择题：
1.编译原理是对（ c ）。
A、机器语言的执行 B、汇编语言的翻译
C、高级语言的翻译 D、高级语言程序的解释执行
2.词法分析器的输出结果是（ d ）。
A、单词自身值 B、单词在符号表中的位置
C、单词的种别编码 D、单词的种别编码和自身值
3. 若文法G定义的语言是无限集，则文法必然是（ c ）
A.前后文无关文法 B.正规文法C.二义性文法D.递归文法
4.文法：G：S→xSx | y所识别的语言是（ d ）。
nm*** A、xyxB、(xyx)C、xyxD、xnyxn（n≥0）
1 ．文法 G 产生的 ⑴ 的全体是该文法描述的语言。 d
A ．句型 B. 终结符集 C. 非终结符集 D. 句子
2 ．若文法 G 定义的语言是无限集，则文法必然是 ⑵ ： a
A ．递归的 B 前后文无关的 C 二义性的 D 无二义性的
3 ． Chomsky 定义的四种形式语言文法中， 0 型文法又称为 ⑶ 文法； 1 型文法又称为 ⑷ 文法； 2 型语言可由 ⑸ 识别。
A ．短语结构文法 B 前后文无关文法 C 前后文有关文法 D 正规文法
E 图灵机 F 有限自动机 G 下推自动机
4 ．一个文法所描述的语言是 ⑹ ；描述一个语言的文法是 ⑺ 。
A ．唯一的 B 不唯一的 C 可能唯一，好可能不唯一
5 ． 数组的内情向量中肯定不含有数组的 ⑻ 的信息
A．维数 B.类型 C.维上下界 D.各维的界差
6 ．在下述的编译方法中，自底向上的方法有 ⑼ ，自顶向下的分析方法有 ⑽ 。 ①简单优先分析 ②算符优先分析 ③递归下降分析 ④预测分析技术 ⑤LR（K）分析 ⑥ SLR（k）分析 ⑦ LL（k）分析 ⑧LALR（K）分析
A.③④⑦ B. ③④⑧ C.①②⑧ D.③④⑤⑥⑦
E.①②⑤⑥⑦ F. ①②⑤⑥⑧
⑴ D ⑵ A ⑶ A ⑷ C ⑸ G. ⑹ A ⑺ B ⑻ A ⑼ F ⑽ A
1、 编写一个计算机高级语言的源程序后，到正式上机运行之前，一般要经过__B____这几
步
①编辑 ② 编译 ③ 连接 ④运行
A、①②③④ B、①②③C、①③ D、①④
2、 使用高级语言进行编程时，首先可以通过编译程序发现源程序的所有___A__错误和部
分___B__错误
A、语法B、语义C、语用D 运行
3、 乔姆斯基定义的四种形式语言文法分别为：__（1）_文法（又称_（2）___文法）、（3）
___文法（又称_（4）___文法）、__（5）_文法（又称_（6）___文法）、_（7）__文法（又称__（8）__文法）
（1）0型 （2）短语文法 （3）1型 （4）上下文有关文法 （5）2型 （6）上下文无关文法 （7）3型 （8）正则
4、 巴科斯—诺尔范式（即BNF）是一种广泛采用的__C__工具
A、描述规则 B、描述语言C、描述文法D、描述句子
给定文法A ?bA|cc,下面的符号串为该文法句子的是①cc②bcbc③bcbcc④ bccbcc ⑤bbbcc
A、①⑤ B、①③④⑤ C、①④ D、①②③④⑤
5、 上下文无关文法__A____产生语言L={anbnci|i>=1,n>=1}
A、可以 B、不可以
6、 文法的二义性与语法的二义性是两个__A___的概念
A、不同 B、相同 C、无法判断
7、 一个语言的文法是___B____
A、唯一的 B、不唯一的C、个数有限的
8、 二义文法是指__D___
A、 对应有两棵不同语法树的文法
B、 对应两面三刀种不同推导的文法
C、 文法中的任何一个非终结符，都存在以它为左部的两面个不同的产生式
D、 以上说法都是错误的
9、 关于短语与句柄，正确的论述是：B
A、 短语就是句柄
B、 直接短语才可能是句柄
C、 左短语一定是句柄
D、 最右短语一定是句柄
10、 词法分析器的另一个名称为__B_____
A、 分析器具
B、 扫描器
C、 划分处理器
D、 词法探索器
11、 递归下降分析方法属于————B
A、 自左至右
B、 自顶向下
C、 自底向上
D、 自右向左
12、 算符优先文法是一种自底向上的分析方法，它是以_B__作为每一步归约的对象
A、 最左直接短语
B、 最左素短语
C、 最左直接短语
D、 句柄
13、 赋值语句X:=-(a+b)/(c-d)-(a+b*c)的逆波兰表示为 C
A、 Xab+cd-/-bc*a+-:=
B、 Xab+/cd-bc*a+--:=
C、 Xab+-cd-/abc*+-:=
D、 Xab+cd-/abc*+--:=
14、 在编译过程中，比较常见的中间语言有 D
①波兰表示②逆波兰表示③三元式④ 四元式 ⑤树型表示
A、①③④ B、②③④C、①③④⑤D、②③④⑤
15、 运行阶段存储组织与管理的目的是C
① 提高编译程序的运行速度
②提高目标程序的运行速度
③为运行阶段存储分配作准备
A、①②B、①③C、②③D、①②③
16、 编译方法中，动态存储分配的含义是A
A、 在运行阶段对源程序中的量进行分配
B、 在编译阶段对源程序中的量进行分配
C、 在编译阶段对源程序中的量进行分配，在运行时这些量的地址可以根据需要改变
D、 以上都不正确
17、 FOTRAN编译中存储分配是_A_____。
A 静态存储分配B 动态存储分配
18、 与PASCAL语言存储分配方式相似的语言是___A___。
AC语言BBASIC语言 C FOTRAN-77
19、 局部优化是局限于______范围内的一种优化。
可选项有：
A 程序的一个基本块 B 一个函数或一个过程
C 一个基本的流程语句结构 D 程序的任何一个局部
20、 合并表达式中常量运算的目的________。
① 尽可能合并常量，使用统一的常量标识符替代表达式中的常量
② 在表达式尽可能去掉重复的常量表达，只留下一个，使表达式尽可能简洁
③ 将可在编译时刻计算的常量运算在编译时刻就算出来，用计算结果替换表达式
中出的所有这种常量运算，使生成的代码指令尽可能少
可选项有：
A ①B② C③ D①②③
三、填空题(每题2分，共20分)
1、从功能上说，程序语言的语句大体可分为_执行性_语句和_说明性_语句两大类。
2、扫描器的任务是从_源程序_中识别出一个个_单词符号_。
3、所谓最右推导是指：_任何一步α?β都是对α中最右非终结符进行替换的_。
4、语法分析最常用的两类方法是_自上而下_和_自下而上_分析法。
5、一个上下文无关文法所含四个组成部分是 一组终结符、一组非终结符、一个开始符号、一组产生式_。
6、所谓语法制导翻译方法是__为每个产生式配上一个翻译子程序，并在语法分析的同时执行这些子程序__。
7、符号表中的信息栏中登记了每个名字的有关的性质，如址_等等。
8、一个过程相应的DISPLAY表的内容为 现行的活动记录的地址和所有外出最新活动的记录地址 。
9、常用的两种动态存贮分配办法是动态分配和动态分配。
10、产生式是用于定义的一种书写规则。
11、一般程序语言的语法单位有： 表达式 、 语句 、 分程序 、和 函数、过程、程序 等等。
12、语法分析器的任务是 在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则 。
13、若源语言用高级语言编写的，目标程序是，则其翻译程序称为 编译程序 。
14、高级语言经过编译生成的目标程序一般是或
15、一个高级语言的源程序在编写形成后到正式运行前，一般要经过 编辑 、编译、连接 这三个阶段
16、假设G是一个文法，S是文法的开始符号，如果S?*X，则称X是
17、乔姆斯基定义的四种形式语言文法分别为：__（1）_文法（又称_（2）___文法）、（3）___文法（又称_（4）___文法）、__（5）_文法（又称_（6）___文法）、_（7）__文法（又称__（8）__文法）
（1）0型 （2）短语文法 （3）1型 （4）上下文有关文法 （5）2型 （6）上下文无关文法 （7）3型 （8）正则
8、确定的有穷自动机是一个（五元组），通常表示为（(S, Σ,δ,s0, F)）
19、单词的描述工具有有穷自动机、（正规式）与（正规文法）
20、单词的三种描述工具互相方间存在（等价性）
21、符号表的内容包括两面部分：__和__
11、在编译中，各个阶段均广泛应用于的数据结构是（表），它记录着不同阶段时的信息，以便查询和修改，其中使用期最长的是（符号表）
22、在PASCAL中，由于允许用户动态申请与释放内存间，所以必须采用（堆）存储分配技术
23、过程与过程引用中信息交换的方法是（参数传递）与（全局变量）
四、名词解释(每题2分，共10分)
1、遍 :指编译程序对源程序或中间代码程序从头到尾扫描一次。
2．无环路有向图(DAG):如果有向图中任一通路都不是环路，则称有向图为无环路有向图，简称DAG。
3．语法分析:按文法的产生式识别输入的符号串是否为一个句子的分析过程。
4．短语:令G是一个文法。S划文法的开始符号，假定αβδ是文法G的一个句型，如果有SαAδ且AB，则称β是句型αβ相对非终结符A的短语。
5．后缀式:种把运算量写在前面，把算符写在后面的表示表达式的方法。
6．词法分析器:指执行词法分析的程序。
7．语法:组规则，用它可以形成和产生一个合式的程序
8．最右推导:指对于一个推导序列中的每一步直接推导，被替换的总是当前符号串中的最右非终结符号。
9．语法制导翻译:在语法分析过程中，根据每个产生式所对应的语义子程序进行翻译的办法叫做语法制导翻译。
10．基本块:指程序中一个顺序执行的语句序列，其中只有一个入口，一个出口，入口即第一个语句。出口即最后一个语句。
五、简述题(每题4分，共24分)
1、何谓优化？按所涉及的程序范围可分为哪几级优化？
2、目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？
3、符号表的作用是什么？符号表的查找的整理技术有哪几种?
4、所谓DISPLAY表？其作用是什么?
5、LL （ 1 ）分析法对文法有哪些要求？
6、常见的存储分配策略有几种？它们都适合于什么性质的语言？
7、常见循环优化都有哪些项目？
8、什么是活动记录？它主要由哪些内容构成？
1、 答：优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。 (2分)
三种级别：局部优化、循环优化、全局优化。 (2分)
2、 答：目标代码通常采用三种形式：机器语言，汇编语言，待装配机器语言模块。(2分 应着重考虑的问题：
(1)如何使生成的目标代码较短；
(2)如何充分利用寄存器，以减少访问内存次数；
(3)如何充分利用指仅系统的的特点。(2分)
3、答：
作用：登记源程序中出现的各种名字及其信息，以及编译各阶段的进展状况。(2分) 主要技术：线性表，对折查找与二叉树，杂凑技术。(2 分)
4、 答： display表是层次显示表。
由于过程嵌套允许内层过程引用外层过程定义的数据，因此，当一个过程运行时必须跟踪它的所有外层过程的最新活动记录起始地址，而display表就是用于登记每个外层过程的最新活动记录起始地址。
5、答：对于 G 中的每个产生式 A →γ 1 | γ 2 | ? | γ m ，其各候选式均应满足：
（1）不同的候选式不能推出以同一终结符号打头的符号串，即
FIRST( γ i ) ∩ FIRST( γ j )= φ（ 1 ≤ i ， j ≤ m ； i ≠ j ）
（2）若有γ j ε，则其余候选式γ i 所能推出的符号串不能以 FOLLOW(A) 中的终结符号开始，即有
FIRST( γ i ) ∩ FOLLOW(A)= φ（ i ≤ 1,2, ? ,m ； i ≠ j ）
6、答：有三种分配存储空间的方式：
篇三：编译原理习题解答
第二章：习题2-4Table表
var x,y; procedure p; var a;
procedure q; var b; beginb:=10; end; procedure s; var c,d; procedure r; var e,f; begin call q; end; begin call r; end; begin call s; end;
begin call p; end
根据：Page289，变量table:array[0..txmax] of record 结构体以及block函数得到下表，而表中各部分的含义，
第三章 文法和语言
5. 写一文法，使其语言是偶正整数的集合 要求：
(1) 允许0打头 (2) 不允许0打头 解：
(1) G[S]=({S,P,D,N},{0,1,2,…,9},P,S)
P:
S?PD|D P->NP|N
D?0|2|4|6|8
N->0|1|2|3|4|5|6|7|8|9
(2) G[S]=({S,P,R,D,N,Q },{0,1,2,…,9},P,S)
P:
S?PD|P0|D P->NR|N R->QR|Q D?2|4|6|8
N->1|2|3|4|5|6|7|8|9 Q->0|1|2|3|4|5|6|7|8|9
6. 已知文法G：
<表达式>::=<项>|<表达式>+<项>|<表达式>-<项> <项>::=<因子>|<项>*<因子>|<项>/<因子> <因子>::=(<表达式>)|i。
试给出下述表达式的推导及语法树。
(1)i;(2)(i)(3)i*i; (4)i*i+i;(5)i+(i+i); (6)i+i*i。
解：
(1) v=<表达式>=><项>=><因子>=>i=w
(2) v=<表达式>=><项>=><因子>=>(<表达式>)=>(<项>)=>(<因子>)=>(i)=w (3) v=<表达式>=><项>=><项>*<因子>=><因子>*<因子>=>i*i=w (4) v=<表达式>=><表达式>+<项>=><项>+<项>=><项>*<因子>+<项>
=><因子>*<因子>+<因子>=>i*i+i=w
(5) v=<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<因子>=>i+(<表达式>)
=> i+(<表达式>+<项>)=>i+(<项>+<项>)=> i+(<因子>+<因子>)=>i+(i+i)=w (6) v=<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<项>=>i+<项>
=>i+<项>*<因子>=> i+<因子>*<因子>=> i+i*i=w
语法树见下图:
(1)i <表达式> <项> <因子> i
(2)(i) <表达式> <项> <因子> (<表达式> )
<项> <因子> i
(4) i*i+i <表达式>
(5) i+(i+i) <表达式>
<表达式>+<项> <项> <因子> i
<因子> (<表达式> )
<表达式> + <项> <项> <因子>
<因子> i
(3)i*i <表达式> <项>
<项>* <因子>
<因子> i
i
(6) i+i*i <表达式>
<表达式> + <项> <项> <因子> i
<项> * <因子> <因子> i
i
<表达式> + <项> <
项> <项> * <因子> <因子> i
i
<因子> i
i
7. 为句子i+i*i构造两棵语法树，从而证明下述文法G[<表达式>]是二义的。 <表达式>::=i|(<表达式>)|<表达式><运算符><表达式> <运算符>::=+|-|*|/
解：为句子i+i*i构造的两棵语法树如下：
<表达式> <表达式>
<表达式> + <表达式> <表达式> * <表达式>
i <表达式> * <表达式> <表达式> + <表达式> i
i i i i
所以，该文法是二义的。
8. 习题1中的文法G[S]是二义的吗？为什么？
答：是二义的。因为对于句子abc可以有两种不同的生成树，即：S=>Ac=>abc和S=>aB=>abc 11. 令文法G[E]为： E?T|E+T|E-T T?F|T*F|T/F F?(E)|i
证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。 解：可为E+T*F构造一棵语法树（见下图），所以它是句型。 E
E+T
T*F
从语法树中容易看出，E+T*F的短语有：
T*F是句型E+T*F的相对于T的短语，也是相对于规则T?T*F的直接短语。 E+T*F是句型E+T*F的相对于E的短语。 句型E+T*F的句柄（最左直接短语）是T*F。
12. 下述文法G[E]生成的语言是什么？给出该文法的一个句子，该句子至少含五个终结符，构造该句子的语法树。证明：<E><T><F><MOP><POP>是G[<E>]的句型，并指出该句型的所有短语、直接短语和句柄。 <E>?<E><T><POP>|<T> <T>?<T><F><MOP>|<F> <F>?a|b|c <POP>?+|- <MOP>?*|/ 解：
(1)计算文法G[E]的语言：
由于L(T)={(a|b|c)((a|b|c)(*|/))|n>=0} 所以L(E)={L(T)(L(T)(+|-))|n>=0}
n
n
(2)该文法的一个句子是aab*+,它的语法树是：
<E>
<E><T> <POP>
<T> <T> <F><MOP> +
<F> <F> b *
a a
(3) 证明：<E><T><F><MOP><POP>是G[<E>]的句型，并指出该句型的所有短语、直接短语和句柄。
由于下面的语法树可以生成<E><T><F><MOP><POP>，所以它是G[<E>]的句型。
<E>
<E><T> <POP>
<T> <F><MOP>
由于<E> => <E><T><POP>,且<T> => <T><F><MOP>,所以<T><F><MOP>是句型<E><T><F><MOP><POP>相对于<T>的短语，也是相对于规则<T> ? <T><F><MOP>的直接短语。
由于<E> => <E> 且<E> => <E><T><F><MOP><POP>,所以<E><T><F><MOP><POP>是句型<E><T><F><MOP><POP>相对于<E>的短语。
显然，句型<E><T><F><MOP><POP>的句柄是<T><F><MOP>。 14. 给出生成下述语言的上下文无关文法：
（1）{abab|n,m>=0} （2）{1010|n,m>=0}
（3）{WaW|W属于{0|a},W表示W的逆}
解：
（1）所求文法为G[S]=({S,A},{a,b},P,S),其中P为：S?AAA?aAb|ε
（2）所求文法为G[S]=({S,A},{0,1},P,S),其中P为： S?1S0|A
A?0A1|ε
（3）W属于{0|a}是指W可以的取值为{ε,0,a,00,a0,aa0,00aa,a0a0,…}
如果W=aa0a00,则W=00a0aa。
所求文法为G[S]=({S,P,Q},{0,a},P,S),其中P为： S?0S0|aSa|a
nmnm
t
*
t
*
t
nmmnnnmm
15. 语言{WaW}和{abcd}是上下文无关的吗？能看出它们反映程序设计语言的什么特性吗？
答：生成语言{WaW}的文法非常简单，如 G[S]: S?WaW
W?aW|bW|ε
可见G[S]是上下文无关的。
nmnm
生成语言{abcd}的文法非常复杂，用上下文无关文法不可能办到，只能用上下文有关文法。这是因
nnmm
为要在ac的中间插入b而同时要在其后面插入d。即a,c相关联，b,d相关联。 这说明对语言的限定越多（特别是语言中的符号前后关联越多），生成它的文法越复杂，甚至于很难找到一个上下文法无关文法。
16．给出生成下述语言的三型文法：
n
(1){a|n>=0}
nm
(2){ab|n,m>=1}
nmk
(3){abc|n,m,k>=0} 解：