习题第3章文法和语言参考答案
1．写一文法，使其语言是偶整数集合。
解：允许以0打头
G：N→+A|-A|A
A→DA|E
D→0|1|2|3|4|5|6|7|8|9
E→0|2|4|6|8
2．写一文法，使其语言是偶整数集合，但不允许由0打头。
解：0除外
G：N→+A|-A|A
A→CB|E
B→DB|E
C→1|2|3|4|5|6|7|8|9
D→0|1|2|3|4|5|6|7|8|9
E→0|2|4|6|8
3．写一文法G，使得L(G) = { a m b n| m≥0, n≥1 }
解：G1:S→aS|T或 G2:S→aS|bT 或 G3:S→aS|Sb|b
T→bT|b T→bT|ε
4．写一文法G，使得L(G) = { a m b n c p| m≥0, n≥0, p≥0 }
解：G1:S→ABC或G2:S→Sc|T 或 G3:A→aA|bB|cC|εA→aA|ε T→Tb|R B→bB|cC|ε
B→bB|ε R→Ra|ε C→cC|ε
C→cC|ε
5．设有文法G1：S → AaB
S → a
A → AB
A → b
A →ε
B → bB
B →ε
写一文法G2，使得L(G1) = L(G2)，并且G2不含空规则。
解：G2:S→BaB|Ba|aB|a 或G2:S→bB|Sb|a
B→bB|b
6．写一文法，使其语言是十位数不是0的整数集合。
解：G：N→SA
S→+|-|ε
A→D|CD|BCD
B→B D|C
C→1|2|3|4|5|6|7|8|9
D→0|1|2|3|4|5|6|7|8|9
7．写出以下文法G所定义的语言L(G)。
G：S → SaS
S → b
S → d
解：L(G)={(xa)n x|n≥0, x∈{b,d}}
={((b|d)a)n(b|d)|n≥0}
={(b|d)(a(b|d))n|n≥0}
8．设有文法G1：S → Sab | c | d
将其改写成以下形式的文法G2，每条规则形如：
V → xW
或V → y
其中V和W为非终结符，x和y为终结符串。
解：G：S→cT|dT|c|d
T→abT|ab
9．设有文法G1：S → abcdB
B → efgB
B → b
将其改写成以下形式的3型文法G2，每条规则形如：
V → pW
或V → q
其中V和W为非终结符，p和q为终结符。
解：G：S→aA
A→bB
B→cC
C→dD
D→eE|b
E→fF
F→gD
10．设有文法G1：S → aBBaS
B → bbAA
A → aAbBc
A → a
将其改写成以下形式的文法G2，每条规则形如：
V → pX1X2…X n
或V → q
其中V和X i为非终结符，p和q为终结符。
解：G：S→aBBPS
P→a
B→bQAA
Q→b
A→aAQBR|a
R→c
11．已知C语言的下标变量形如：
a[E][E]…[E]
按第10题要求的文法G2的形式写出下标变量文法。
解：G：S→aA
A→[EB
B→]A
B→]
12．设有文法G1：S → aBcA
S → aBdB
A → bA
A → aB
B → Bd
B → a
将其改写成文法G2，使得对每个非终结符均无两个不同规则能导出相同的终结开头符。
解：G2：S→aB|P
P→cA|dB
A→bQ
Q→A|B
B→aD
D→dD|ε
13．设有文法G：S → aBbD
B → bSD
B → aDa
B → bb
D → aBD
证明L(G)为空语言。
解：∵D的唯一规则是无穷递归的，也就是无用规则
又∵开始符S的唯一规则含有D，也是无用规则
∴文法G的规则全是无用规则
故L(G)为空语言。
14．设有文法G1：S → 0Y | 1X | 1Y | 1S |ε
X → 1Y | 1S |ε
Y → 1Z
Z → 1S |ε
将其改写成不含空规则的文法G2，且L(G1) = L(G2)∪{ε}。
解：G2：S→0Y|1X|1Y|1S|1
X→1Y|1S|1
Y→1Z|1
Z→1S|1
15．设有文法 G ：E → E+T | T T → T*F | F F → i | (E)
（1）构造句子(i*i+i)*i 的语法树，并写出该句子的规范推导过程；
（2）构造句型F*(T+i)+i 的语法树，并求出该句型的所有短语、简单短语和句柄。 解：(1) 句子(i*i+i)*i 的语法树 规范推导过程：
E =〉T =〉T*F
=〉T*i
=〉F*i
=〉(E)*i
=〉(E+T)*i
=〉(E+F)*i
=〉(E+i)*i
=〉(T+i)*i
=〉(T*F+i)*i
=〉(T*i+i)*i
=〉(F*i+i)*i
=〉(i*i+i)*i
(2) 句型F*(T+i)+i 的语法树 短语 简单短语 句柄
F*(T+i)+i F*(T+i)
F F F
(T+i)
T+i
T T
i i i i
E
* T F E ( ) F T i + E T T * T F F i
i F i E
+ E T *
T F T F T
E ( )
F i F
+ E T i
16．构造一个二义性文法。 解：二义性文法G ：S→aS|Sa|a
∵句子aa 存在两棵语法树：
∴G 是二义性文法。
17．教材3.14题
解：(1) G1:S→CD (2) G2:S→1S0|A (3) G3:S→0S0|aSa|a C→aCb|ε A→0A1|ε
D→aDb|ε 18．教材3.16题
解：(1) G1:A→aA|ε (2) G2:A→aA|aB (3) G3:A→aA|bB|cC|ε B→bB|b B→bB|cC|ε C→cC|ε
S
a
S
a
S
S
习题第3章文法和语言 1．写一文法，使其语言是偶整数集合，但不允许由0打头。3．写一文法G，使得L(G) = { a m b n| m≥0, n≥1 } 4．写一文法G，使得L(G) = { a m b n c p| m≥0, n≥0, p≥0 } 5．设有文法G1：S → AaB S → a A → AB A → b A →ε B → bB B →ε 写一文法G2，使得L(G1) = L(G2)，并且G2不含空规则。6．写一文法，使其语言是十位数不是0的整数集合。 7．写出以下文法G所定义的语言L(G)。 G：S → SaS S → b S → d 8．设有文法G1：S → Sab S → c S → d 将其改写成以下形式的文法G2，每条规则形如： V → xW 或V → y 其中V和W为非终结符，x和y为终结符串。 9．设有文法G1：S → abcdB B → efgB B → b 将其改写成以下形式的3型文法G2，每条规则形如： V → pW 或V → q 其中V和W为非终结符，p和q为终结符。 10．设有文法G1：S → aBBaS B → bbAA A → aAbBc A → a 将其改写成以下形式的文法G2，每条规则形如： V → pX1X2…X n 或V → q 其中V和X i为非终结符，p和q为终结符。 11．已知C语言的下标变量形如： a[E][E]…[E] 按第10题要求的文法G2的形式写出下标变量文法。12．设有文法G1：S → aBcA
S → aBdB A → bA A → aB B → Bd B → a 将其改写成文法G2，使得对每个非终结符均无两个不同规则能导出相同的终结开头符。13．设有文法G：S → aBbD B → bSD B → aDa B → bb D → aBD 证明L(G)为空语言。 14．设有文法G1：S → 0Y | 1X | 1Y | 1S |ε X → 1Y | 1S |ε Y → 1Z Z → 1S |ε 将其改写成不含空规则的文法G2，且L(G1) = L(G2)∪{ε}。 15．设有文法G：E → E+T | T T → T*F | F F → i | (E) （1）构造句子(i*i+i)*i的语法树，并写出该句子的规范推导过程； （2）构造句型F*(T+i)+i的语法树，并求出该句型的所有短语、简单短语和句柄。16．构造一个二义性文法。 17. 课本P49. 第14题（1）（2） 18. 课本P49. 第16题（2）
第一章 1、将编译程序分成若干个“遍”是为了。 a．提高程序的执行效率 b．使程序的结构更加清晰 c．利用有限的机器内存并提高机器的执行效率 d．利用有限的机器内存但降低了机器的执行效率 2、构造编译程序应掌握。 a．源程序b．目标语言 c．编译方法d．以上三项都是 3、变量应当。 a．持有左值b．持有右值 c．既持有左值又持有右值d．既不持有左值也不持有右值 4、编译程序绝大多数时间花在上。 a．出错处理b．词法分析 c．目标代码生成d．管理表格 5、不可能是目标代码。 a．汇编指令代码b．可重定位指令代码 c．绝对指令代码d．中间代码 6、使用可以定义一个程序的意义。 a．语义规则b．语法规则 c．产生规则d．词法规则 7、词法分析器的输入是。 a．单词符号串b．源程序 c．语法单位d．目标程序 8、中间代码生成时所遵循的是- 。 a．语法规则b．词法规则 c．语义规则d．等价变换规则 9、编译程序是对。 a．汇编程序的翻译b．高级语言程序的解释执行 c．机器语言的执行d．高级语言的翻译 10、语法分析应遵循。 a．语义规则b．语法规则 c．构词规则d．等价变换规则 二、多项选择题 1、编译程序各阶段的工作都涉及到。 a．语法分析b．表格管理c．出错处理 d．语义分析e．词法分析 2、编译程序工作时，通常有阶段。 a．词法分析b．语法分析c．中间代码生成 d．语义检查e．目标代码生成 三、填空题 1、解释程序和编译程序的区别在于。 2、编译过程通常可分为5个阶段，分别是、语法分析、代码优化和目标代码生成。 3、编译程序工作过程中，第一段输入是，最后阶段的输出为程序。
习题第3章文法和语言参考答案 1．写一文法，使其语言是偶整数集合。 解：允许以0打头 G：N→+A|-A|A A→DA|E D→0|1|2|3|4|5|6|7|8|9 E→0|2|4|6|8 2．写一文法，使其语言是偶整数集合，但不允许由0打头。 解：0除外 G：N→+A|-A|A A→CB|E B→DB|E C→1|2|3|4|5|6|7|8|9 D→0|1|2|3|4|5|6|7|8|9 E→0|2|4|6|8 3．写一文法G，使得L(G) = { a m b n| m≥0, n≥1 } 解：G1:S→aS|T或 G2:S→aS|bT 或 G3:S→aS|Sb|b T→bT|b T→bT|ε 4．写一文法G，使得L(G) = { a m b n c p| m≥0, n≥0, p≥0 } 解：G1:S→ABC或G2:S→Sc|T 或 G3:A→aA|bB|cC|εA→aA|ε T→Tb|R B→bB|cC|ε B→bB|ε R→Ra|ε C→cC|ε C→cC|ε 5．设有文法G1：S → AaB S → a A → AB A → b A →ε B → bB B →ε 写一文法G2，使得L(G1) = L(G2)，并且G2不含空规则。 解：G2:S→BaB|Ba|aB|a 或G2:S→bB|Sb|a B→bB|b 6．写一文法，使其语言是十位数不是0的整数集合。 解：G：N→SA S→+|-|ε A→D|CD|BCD B→B D|C C→1|2|3|4|5|6|7|8|9 D→0|1|2|3|4|5|6|7|8|9
7．写出以下文法G所定义的语言L(G)。 G：S → SaS S → b S → d 解：L(G)={(xa)n x|n≥0, x∈{b,d}} ={((b|d)a)n(b|d)|n≥0} ={(b|d)(a(b|d))n|n≥0} 8．设有文法G1：S → Sab | c | d 将其改写成以下形式的文法G2，每条规则形如： V → xW 或V → y 其中V和W为非终结符，x和y为终结符串。 解：G：S→cT|dT|c|d T→abT|ab 9．设有文法G1：S → abcdB B → efgB B → b 将其改写成以下形式的3型文法G2，每条规则形如： V → pW 或V → q 其中V和W为非终结符，p和q为终结符。 解：G：S→aA A→bB B→cC C→dD D→eE|b E→fF F→gD 10．设有文法G1：S → aBBaS B → bbAA A → aAbBc A → a 将其改写成以下形式的文法G2，每条规则形如： V → pX1X2…X n 或V → q 其中V和X i为非终结符，p和q为终结符。 解：G：S→aBBPS P→a B→bQAA Q→b A→aAQBR|a R→c
第三章文法和语言课后习题参考答案 1. L(G)={abc} 2. L(G[N])是无符号整数。 3.G3: E→D+E | D-E | D D→0|1|2|3|4|5|6|7|8|9 4. L(G[Z])={a n b n | n>0} 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)<表达式>=><项>=><因子>=>i (2)<表达式>=><项>=><因子>=>(<表达式>)=>(<项>)=>(<因子>)=>(i) (3)<表达式>=><项>=><项>*<因子>=><因子>*<因子>=>i*i (4)<表达式>=><表达式>+<项>=><项>+<项>=><项>*<因子>+<项> =><因子>*<因子>+<因子>=>i*i+i=w (5)<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<因子>=>i+(<表达式>) => i+(<表达式>+<项>)=>i+(<项>+<项>)=> i+(<因子>+<因子>)=>i+(i+i) (6)<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<项>=>i+<项> =>i+<项>*<因子>=> i+<因子>*<因子>=> i+i*i
第3章文法和语言 第1题 文法G＝({A,B,S},{a,b,c},P,S)其中P为： S→Ac|aB A→ab B→bc 写出L(G[S])的全部元素。 答案： L(G[S])={abc} 第2题 文法G[N]为： N→D|ND D→0|1|2|3|4|5|6|7|8|9 G[N]的语言是什么？ 答案: G[N]的语言是V+。V={0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD.... =>NDDDD...D=>D......D 或者：允许0开头的非负整数？ 第３题 为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。答案： G[S]: S->S+D|S-D|D D->0|1|2|3|4|5|6|7|8|9 第4题 已知文法G[Z]： Z→aZb|ab 写出L(G[Z])的全部元素。 答案： Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbb L(G[Z])={a n b n |n>=1} 第5题 写一文法，使其语言是偶正整数的集合。要求： (1) 允许0打头； (2)不允许0打头。 答案： (1)允许0开头的偶正整数集合的文法E→NT|D T→NT|D N→D|1|3|5|7|9 D→0|2|4|6|8 (2)不允许0开头的偶正整数集合的文法E→NT|D T→FT|G N→D|1|3|5|7|9 D→2|4|6|8 F→N|0 G→D|0 第6题
已知文法G： <表达式>::=<项>｜<表达式>＋<项> <项>::=<因子>｜<项>*<因子> <因子>::=（<表达式>）｜i 试给出下述表达式的推导及语法树。 （５）i+(i+i) （６）i+i*i
第3章 文法和语言 第1题 文法G ＝({A,B,S},{a,b,c},P,S)其中P 为： S→Ac|aB A→ab B→bc 写出L(G[S])的全部元素。 答案： L(G[S])={abc} 第2题 文法G[N]为： N →D|ND D →0|1|2|3|4|5|6|7|8|9 G[N]的语言是什么？ 答案: G[N]的语言是V+。V={0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD.... =>NDDDD...D=>D......D 或者：允许0开头的非负整数？ 第３题 为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。 答案： G[S]: S->S+D|S-D|D D->0|1|2|3|4|5|6|7|8|9 第4题 已知文法G[Z]： Z →aZb|ab 写出L(G[Z])的全部元素。 答案： Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbb L(G[Z])={a n b n |n>=1} 第5题 写一文法，使其语言是偶正整数的集合。 要求： (1) 允许0打头； (2)不允许0打头。 答案： (1)允许0开头的偶正整数集合的文法 E→NT|D T→NT|D N→D|1|3|5|7|9 D→0|2|4|6|8 (2)不允许0开头的偶正整数集合的文法 E→NT|D T→FT|G N→D|1|3|5|7|9 D→2|4|6|8 F→N|0 G→D|0 第6题
已知文法G： <表达式>::=<项>｜<表达式>＋<项> <项>::=<因子>｜<项>*<因子> <因子>::=（<表达式>）｜i 试给出下述表达式的推导及语法树。 （５）i+(i+i) （６）i+i*i
练习1. 文法和语言 1. 文法: Z → U0 | V1 U → Z1 | 1 V → Z0 | 0 (1) 请写出全部由此文法描述的只含有四个符号的句子. (2) 该文法是 Chomsky 几型文法? Answer ： (1) 1010, 0110, 1001, 0101 (2) 3型文法 2. 给定前缀表示的表达式文法 G : (1) E → -EE (2) E → -E (3) E → a (4) E → b (5) E → c 试问 --a-bc 是否 L(G) 的句子?若是,请给出该句子所有可能的分析树;若不是,请说明理由. Answer : --a-bc 是L(G)的句子。所有可能的分析树如下。 (1) (2) (3) E -E E -E c -E b E -E E -E -E E E -- E E c -E E 3. 考虑文法： S → ( L ) | a L → L, S | S 写出句型 ( a , ( a , a ) ) 的最左推导和最右推导。 Answer : (1) 最左推导： S lm =>(L)lm =>(L,S)lm =>(S,S)lm =>(a,S)lm =>(a,(L))lm =>(a,(L,S))lm =>(a,(S,S))lm =>(a,(a,S))lm =>(a,(a,a)) (2) 最右推导： S rm =>(L)rm =>(L,S)rm =>(L,(L))rm =>(L,(L,S))rm =>(L,(L,a))rm =>(L,(S,a))rm =>(L,(a,a))rm =>(S,(a,a))rm =>(a,(a,a)) 4. 考虑文法：
第三章文法和语言 3.1 文法的直观概念和语言概述 当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。 1、语言概述 语言是由句子组成的集合，是由一组符号所构成的集合。 汉语--所有符合汉语语法的句子的全体 英语--所有符合英语语法的句子的全体 程序设计语言--所有该语言的程序的全体 每个句子构成的规律 2、研究语言每个句子的含义 每个句子和使用者的关系 3、研究程序设计语言 每个程序构成的规律 每个程序的含义 每个程序和使用者的关系 4、语言研究的三个方面 语法 Syntax 语义 Semantics 语用 Pragmatics 语法 -- 表示构成语言句子的各个记号之间的组合规律 语义 -- 表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系） 语用 --表示在各个记号所出现的行为中，它们的来源、使用和影响。 每种语言具有两个可识别的特性，即语言的形式和该形式相关联的意义。 语言的实例若在语法上是正确的，其相关联的意义可以从两个观点来看，其一是该句子的创立者所想要表示的意义，另一是接收者所检验到的意义。这两个意义并非总是一样的，前者称为语言的语义，后者是其语用意义。幽默、双关语和谜语就是利用这两方面意义间的差异。 如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。 形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。 是程序设计语言语法分析研究的基础。 3.2符号与符号串 1、字母表∑：符号（元素）的非空有穷集合。 2、符号串：由字母表∑中的符号组成的任何有穷序列称为该字母表上的符号串。1.空符号串ε (没有符号的符号串)是∑上的符号串 2.若x是∑上的符号串,a是∑的元素,则xa是∑上的符号串 3. y是∑上的符号串,当且仅当它可以由1和2导出。 例如：Σ={a,b} ε,a,b,aa,ab,aabba…都是∑上的符号串 3、符号串的运算 符号串的长度：符号串中符号的个数.符号串s的长度记为|s|。 如001110的长度是6。 空符号串，即不包含任何符号的符号串，用ε表示，其长度为0，即｜ε｜=0。 符号串的连接：设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串. 由于ε的含义，显然有ε x=x ε =x。 例如 x=ST，y=abu，则它们的连接xy=STabu，看出｜x｜=2，｜y｜=3，｜xy｜=5 符号串的方幂符号串自身连接n次得到的符号串a n 定义为 aa…aa n个a a1=a, a2=aa且a0=ε4、符号串集合：若集合A中所有元素都是某字母表∑上的符号串，则称A为字母表∑上的符号串
《编译原理》课后习题答案第三章 第3 章文法和语言 第1 题 文法G＝({A,B,S},{a,b,c},P,S)其中P 为： S→Ac|aB A→ab B→bc 写出L(G[S])的全部元素。 答案： L(G[S])={abc} 第2 题 文法G[N]为： N→D|ND D→0|1|2|3|4|5|6|7|8|9 G[N]的语言是什么？ 答案: G[N]的语言是V+。V={0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD.... =>NDDDD...D=>D......D 或者：允许0 开头的非负整数？ 第３题 为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。答案： G[S]: S->S+D|S-D|D D->0|1|2|3|4|5|6|7|8|9 第4 题 已知文法G[Z]： Z→aZb|ab 写出L(G[Z])的全部元素。 盛威网（https://www.doczj.com/doc/6b8129503.html,）专业的计算机学习网站 1 《编译原理》课后习题答案第三章 答案： Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbb L(G[Z])={anbn|n>=1} 第5 题 写一文法，使其语言是偶正整数的集合。要求： (1) 允许0 打头； (2)不允许0 打头。 答案： (1)允许0 开头的偶正整数集合的文法 E→NT|D T→NT|D N→D|1|3|5|7|9 D→0|2|4|6|8
(2)不允许0 开头的偶正整数集合的文法 E→NT|D T→FT|G N→D|1|3|5|7|9 D→2|4|6|8 F→N|0 G→D|0 第6 题 已知文法G： <表达式>::=<项>｜<表达式>＋<项> <项>::=<因子>｜<项>*<因子> <因子>::=（<表达式>）｜i 试给出下述表达式的推导及语法树。 （５）i+(i+i) （６）i+i*i 盛威网（https://www.doczj.com/doc/6b8129503.html,）专业的计算机学习网站 2 《编译原理》课后习题答案第三章 答案： <表达式> <表达式> + <项> <因子> <表达式> <表达式> + <项> <因子> i <项> <因子> i <项> <因子> i （ ) (5) <表达式> =><表达式>＋<项> =><表达式>＋<因子> =><表达式>＋（<表达式>） =><表达式>＋（<表达式>＋<项>） =><表达式>＋（<表达式>＋<因子>） =><表达式>＋（<表达式>＋i） =><表达式>＋（<项>＋i） =><表达式>＋（<因子>＋i） =><表达式>＋（i＋i） =><项>＋（i＋i） =><因子>＋（i＋i）