第二章形式语言与文法练习题

S 推导出 “ 000111” ， 推导长度3
“ 000111” 归约到 S
+ 表示成 S ⇒ 000111
第2章 形式语言与文法 2.2 文法
2.2.3 相关概念
2．句型和句子
定义： 文法G（VN，VT，S ，P），若符号串x可由开始符号S推导出
* （S ⇒ x），则称 x 是 G 的一个句型，若x仅由终结符组成， 则称 x 为G 的一个句子。 注意：句型和句子都必须由开始符号S推出！
（2）用适当条数的规则描述了一个语言的全部句子。
第2章 形式语言与文法 2.1 语言
2.2 文法
2.2.1 文法的形式定义
2.2.2 文法的表示方法
2.2.3 相关概念
第2章 形式语言与文法
2.2 文法
2.2.1 文法的形式定义
1．终结符
不可分割的符号串，是组成句子的最基本的单位。
一个语言允许使用的所有终结符组成的集合称为终结符集， 用VT 表示。
则 |x|=4 , |y|=4 xy = “homework”
第2章 形式语言与文法
| xy | = 4+4 = 8
2.1 语言
2.1.1 语言的概念
方幂：符号串 x 的方幂就是 n个x 自身连接 次，表示为 xn 。 规定 x0 =ε。 成立的等式： x1=x ， x2=xx ， x3=xxx ，……
若n>0，则有： xn = xxn-1 = xn-1x
x* 表示 x 的任意多次方幂（可以是 0 次） x+ 表示 x 的任意非 0 次方幂。 【例2-3】 若 x = “ab” 则 x0 =ε x1 = “ab”
x2 = “abab”
第2章 形式语言与文法

3. 有文法G[E]：E→－EE， E→－E，E →a|b|c 则文法 的句子－－a－bc的所有可能的语法树有（ ）棵。 A. 1 B. 2 C. 4 D. 3 4.有文法G[Sห้องสมุดไป่ตู้，如果S * x，( x∈VT)，则x是（ ）。 A. 句型 B. 句子 C. A和B D. 非A和B 二.构造一个上下文无关文法G，使得： L(G)={ a 2mbm |m>0}
第2章 练习题 章
一，单选题 1.给定文法：A→bA|cc,下面的符号串为该文法句子的是 （ ）。 ① cc ② bcbcc ③ bccbcc ④ bbbcc A. ①④ B. ①②③ C. ①③ D. ②③④ 2.文法G[Z]和语言L（ G[Z ]）存在如下关系（ ）。 A.一一对应：一个文法对应唯一的语言；并且反过来，一 个语言对应唯一的文法。 B.一个语言对应唯一的文法，反之则不然。 C.一个文法对应唯一的语言，反之则不然。 D.若G为非二义性文法，则C是正确的；若G为二义性文法 ，则一个文法不对应唯一的语言。
三.已知文法G[E]：E→ET+ | T T→TF* | F F→FP↑| P P→(E) | i 有句型TF*PP↑+，问此句型的短语，简单短语和句柄是 什么？（画语法树说明）
四.请用语法树证明文法G[s]是二义性的， G[s]： S→SS | (S) | ( )。
五.已知文法G[Z]：Z→AB A→aAb |ab B→Bc | ε 则，L(G[Z] )＝？

第2章形式语言基础2.2 设有文法G[N]: N -> D | NDD -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9(1)G[N]定义的语言是什么?(2)给出句子0123和268的最左推导和最右推导。

解答：(1)L(G[N])={(0|1|2|3|4|5|6|7|8|9)+} 或L(G[N])={α| α为可带前导0的正整数}(2)0123的最左推导：N ⇒ ND ⇒ NDD ⇒ NDDD ⇒ DDDD ⇒ 0DDD ⇒ 01DD ⇒ 012D ⇒ 0123 0123的最右推导：N ⇒ ND ⇒ N3 ⇒ ND3 ⇒ N23 ⇒ ND23 ⇒ N123 ⇒ D123 ⇒ 0123268的最左推导：N ⇒ ND ⇒ NDD ⇒ DDD ⇒ 2DDD ⇒ 26D ⇒ 268268的最右推导：N ⇒ ND ⇒ N8 ⇒ ND8 ⇒ N68 ⇒ D68 ⇒ 2682.4 写一个文法，使其语言是奇数的集合，且每个奇数不以0开头。

解答：首先分析题意，本题是希望构造一个文法，由它产生的句子是奇数，并且不以0开头，也就是说它的每个句子都是以1、3、5、7、9中的某个数结尾。

如果数字只有一位，则1、3、5、7、9就满足要求，如果有多位，则要求第1位不能是0，而中间有多少位，每位是什么数字（必须是数字）则没什么要求，因此，我们可以把这个文法分3部分来完成。

分别用3个非终结符来产生句子的第1位、中间部分和最后一位。

引入几个非终结符，其中，一个用作产生句子的开头，可以是1－9之间的数，不包括0，一个用来产生句子的结尾，为奇数，另一个则用来产生以非0整数开头后面跟任意多个数字的数字串，进行分解之后，这个文法就很好写了。

N -> 1 | 3 | 5 | 7 | 9 | BNB -> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | B02.7 下面文法生成的语言是什么？G1：S->ABA->aA| εB->bc|bBc G2：S->aA|a A->aS解答：B ⇒ bcB ⇒ bBc⇒ bbccB ⇒ bBc⇒ bbBcc ⇒ bbbccc……A ⇒εA ⇒ aA ⇒ aA ⇒ aA ⇒ aaA ⇒ aa……∴S ⇒ AB ⇒ a m b n c n , 其中m≥0,n≥1即L(G1)={ a m b n c n | m≥0,n≥1} S ⇒ aS ⇒ aA ⇒ aaS ⇒ aaaS ⇒ aA ⇒ aaS ⇒ aaaA ⇒aaaaS ⇒ aaaaa ……∴S ⇒ a2n+1 , 其中n≥0即L(G2)={ a2n+1 | n≥0}2.11 已知文法G[S]: S->(AS)|(b)A->(SaA)|(a)请找出符号串(a)和(A((SaA)(b)))的短语、简单短语和句柄。

形式语言与自动机课后作业答案第二章4．找出右线性文法，能构成长度为1 至5 个字符且以字母为首的字符串。

答：G={N,T,P,S}其中N={S,A,B,C,D} T={x,y} 其中x € {所有字母} y € {所有的字符} P 如下:S T x S T xA A f y A f yBB T y B T yC C T y C T yD D T y6．构造上下文无关文法能够产生L={ 3 / {a,b}*且3中a的个数是b的两倍}答：G={N,T,P,S}其中N={S} T={a,b} P 如下:S t aab S t aba S t baaS t aabS S t aaSb S t aSab S t SaabS t abaS S t abSa S t aSba S t SabaS t baaS S t baSa S t bSaa S t Sbaa7．找出由下列各组生成式产生的语言(起始符为S)(1) S t SaS S t b(2) S t aS b S t c(3) S T a S f aE aS答：(1) b(ab)n /n > 0}或者L二{(ba)n b/n > 0}(2) L={a n cb n /n > 0}(3) L={a2n+1 /n > 0}第三章1. 下列集合是否为正则集，若是正则集写出其正则式。

（1）含有偶数个a和奇数个b的{a,b}*上的字符串集合（2）含有相同个数a和b的字符串集合（3）不含子串aba的{a,b}*上的字符串集合答：（1）是正则集，自动机如下b b b b⑵不是正则集，用泵浦引理可以证明，具体见17题（2）（3）是正则集先看L '为包含子串aba的{a,b}*上的字符串集合显然这是正则集，可以写出表达式和画出自动机。

（略）则不包含子串aba的{a,b}*上的字符串集合L是L '勺非根据正则集的性质，L 也是正则集。

P2
9.对应图（a）(b)的状态转换图写出正则式。（图略） （1） 由图可知 q0=aq0+bq1+a+ε
q1=aq2+bq1 q0=aq0+bq1+a =>q1=abq1+bq1+aaq0+aa =(b+ab) q1+aaq0+aa =(b+ab) *( aaq0+aa)
=>q0=aq0+b(b+ab) *( aaq0+aa ) +a+ε
(2) 由生成式得：
S=aA+B ①
A=bB+cC ② B=a+bB ③ C=D+abB ④ D=dB ⑤ 由③得 B=b*a ⑥ 将⑤⑥代入④ C=d+abb*a=d+ab+a ⑦ 将⑥⑦代入② A=b+a+c(d+b+a) ⑧ 将⑥⑧代入① S=a(b+a+c(d+ab+a))+b*a
=ab+a+acd+acab+a+b*a
4．对下列文法的生成式，找出其正则式 （1） G=({S,A,B,C,D},{a,b,c,d},P,S),生成式 P 如下：
S→aA S→B
A→abS A→bB
B→b B→cC
C→D D→bB
D→d
（2） G=({S,A,B,C,D},{a,b,c,d},P,S),生成式 P 如下：
S→aA S→B
P: S→aS S→bS S→ε
(2) 右线性文法 G=({S},{a,b},P,S)
P: S→aS S→bS S→abb

4 题：文法G 的产生式集合如下，试给出句子aaabbbccc 的一个推导和一个归约S T aBCIaSBCCB T BCaB t abbB t bbbB t bbC t bccC t ccC t cc6 题：文法G 的产生式集合如下，请给出G 中每个语法范畴代表的集合S t aSaIaaSaaIaAaA t bAIbbbAIbBB t cBIcCC t ccCIDDD t dDId7 题: 给定如下文法，请用自然语言描述它们定义的语言(4)S t aBIbAA t aIaSIBAAB t bIbSIABB8题：设刀={0,1},请给出刀上下列语言的文法(3)所有以11 开头, 以11 结尾的串;(6)所有长度为偶数的串9题：设刀={a,b,c},构造下列语言的文法(2)L2={ a n b m|n,m》1}(3)L3={ a n b n a n|n》1}(4)L4={a n b m a k|n,m,k > 1}(6)L6={xwx T| x,w +}(7)L?={w | w = w T, w +}补充：对给定RGS t abAIbaBA t abAIabB t baBIba构造等价文法，新文法的产生式形如：A T a, A T aB, A,B € V , a€ T参考答案4、文法G的产生式集合如下，试给出句子S T aBC|aSBCCB T BCaB T abbB T bbbB T bbC T becC T eeC T ee答：S 二aSBC=aaSBCBC=aaaBCBCBC=aaabCBCBC=aaabBCCBC=aaabbCCBC=aaabbCBCC=aaabbBCCC=aaabbbCCC=aaabbbeeC=aaabbbeee6、文法G的产生式集合如下，请给出S T aSa|aaSaa|aAaA T bA|bbbA|bBB TC B|C CC T CC C|DDD T dD|d解：(注意方法)Set(D)= {d m| m> 1} set(C)= {e 2n d m| n> 0,m > 2}(注意：aaabbbeee的一个推导和一个归约G中每个语法范畴代表的集合d只要大于n mset(B)= {e d | n> 1,m> 2}set(A)= {b k e n d m| k> 1,n》1,m>2}set(S)= {a p b k e n d m a p| p> 1,k > 1, n> 1,m > 2} 问题：2,不一定是偶数，可以没有e)不可写作：S={……}讨论：*n nS= a Aa*n i m f n=a b Ba*二a n b m e x Ca n*n ■ m x_ —=a b e DDa5 a n b m e x d y a nn - m x - y nS ={a b e d a | n,m, x -1,y -2} 06级张言飞7（4）、给定如下文法，请用自然语言描述它们定义的语言S T aB|bAA T a|aS|BAAB t b|bS|ABB解：该文法定义字母表刀={a,b}上的所有a和b的个数相等的字符串构成的语言。

xxx
x y x+y
关于字符串的运算
其它 如 取头字符，取尾部，子串匹配 等 设ω1, ω2, ω3是字母表T上的字符串，称：
ω1是字符串ω1ω2的前缀， ω2是字符串ω1ω2的后缀， ω2是字符串ω1ω2ω3的子串。 空串是任何字符串的前缀，后缀及子串。 例：abc的前缀 a ab abc ε.
举例 = 0， bbaba = 5
ai 表示含有i个a的字符串
关于字符串的运算
连接（concatenation） 设 x, y为串, 且 x a1a2 … am, y b1b2 … bn, 则 x 与 y 的连接 x y a1a2 … am b1b2 … bn
连接运算的性质 ( x y ) z x（ y z ）
隐含的概念：如何表述子集的“特性和规则”，
举例 - 左右括号的匹配。
英文单词集 …, English, …, words , … C 语言程序集 … 字母表？ 汉语成语集 …, 马到成功, … 化学分子式集 …, H2O, …, NaCl , … any, 任意
语 言 （Languages）
举例：设T = {a，b} 则 L1 = {anbn | n≥1} L3 = { bk | k 是质数} L2 ={ε} 只有一个空句子的语言 L4 = { } = Φ 空语言 均为字母表T上的语言。
由语言的定义知语言是集合，对于集合的运算可 应用于对于语言的计算。如并，交，补，差。
语言的基本运算
字 符 串 （string）
概念 字母表 T 上的一个字符串（简称串），或称为 字（word），为 T 中字符构成的一个有限序列。
空串（empty string）, 用 表示，不包含任何
字符。

语言学2章测试题及答案一、选择题（每题2分，共20分）1. 语言学的主要研究对象是什么？A. 语言的起源B. 语言的结构C. 语言的演变D. 语言的使用答案：B2. 下列哪项不是语言学的分支学科？A. 语音学B. 语法学C. 心理学D. 语义学答案：C3. 索绪尔认为语言符号是由哪两部分组成的？A. 语音和语义B. 符号和意义C. 能指和所指D. 形式和内容答案：C4. 语言的最小意义单位是什么？A. 音素B. 词C. 语素D. 句子5. 语言的交际功能不包括以下哪一项？A. 信息传递B. 情感表达C. 思维工具D. 艺术创作答案：C6. 语言的规范性主要体现在哪个方面？A. 发音B. 语法C. 词汇D. 所有选项答案：D7. 语言的多样性主要体现在哪些方面？A. 语言结构B. 语言使用C. 语言发展D. 所有选项答案：D8. 语言的演变不包括以下哪一项？A. 语音变化B. 词汇变化C. 语法变化D. 语言消亡答案：D9. 以下哪种现象不属于语言接触？B. 融合C. 分化D. 同化答案：C10. 语言的标准化通常不涉及以下哪一项？A. 发音规范B. 词汇规范C. 语法规范D. 语言的起源答案：D二、填空题（每题2分，共20分）1. 语言学研究的两个主要对象是______和______。

答案：语言；言语2. 索绪尔将语言符号分为______和______。

答案：能指；所指3. 语言的三个基本功能包括______、______和______。

答案：表达功能；交际功能；思维功能4. 语音学研究的是______和______。

答案：语音的产生；语音的感知5. 语用学研究的是______和______。

答案：语境；意义6. 语言的演变包括______、______和______。

答案：语音变化；词汇变化；语法变化7. 语言的接触现象包括______、______和______。

答案：借用；融合；同化8. 语言的多样性表现在______、______和______。

显然:字母表上的符号串可形成一个集合(可数无穷)
注: 1.符号串的组成是有序的.如:01≠10,ab≠ba 2.空符号串为不包含任何符号的符号串,记为: ε 3.符号串的长度:符号串所含符号的个数.设符号串为x,则x的 长度为∣x∣。
例:∣a∣=1 ∣abc∣=3 特别：|ε |＝0 即空符号串的长度为零．
注：{ε }A=A{ε}=A A=A =A (其中 为空集)
注: ε 不属于 ={ }
， 即空符号串并不属于空集
4.符号串集合的方幂
设A为符号串集合,则定义 1 2 0 A={ε} A=A A=AA 3 2 2 A=AA=AA=AAA
……
A=A A=AA =AA……A (n个) 例:设A={a,b} 0 1 A={ε} A={a,b} 2 2 A={aa,ab,ba,bb} (A共有2 =4个长度为2的元素) 3 2 A=AA={aa,ab,ba,bb}{a,b} ={aaa,aba,baa,bba,aab,abb,bab,bbb}
3.推导
有了文法，怎样由文法推导出与该文法相应的
语言？为此引入了“推导”等概念。
1)直接推导
设x,y是V*中任意符号串，若用一次产生式可以 从x推出y，则称y是x的直接推导，记为：x y。 （或称符号串x直接产生了符号串y，或称y直接 归约到x）
例：设G[S]: S::=0S1|01 则有如下一些直接推导：
●
例:汉语:人们无法列出全部的句子.但人们可以 给出一些规则,用这些规则来说明(或定义)句 子的组成结构. 如:汉语句子结构： <句子>∷=<主语><谓语> <主语>∷=<代词>︱<名词> <代词>∷=我︱你︱他 <名词>∷=王明︱大学生︱工人︱英语 <谓语>∷=<动词><直接宾语> <动词>∷=是∣学习 <直接宾语>∷=<代词>∣<名词>

2.6 设文法 G 的产生式集如下,请给出 G 的每个语法范畴代表的集合.
S→aSa|aaSaa|aAa A→bA|bbbA|bB B→cB|cC C→ccC|DD D→dD|d 解:
set(D)={d}+ set(C)={ c2n dm| m≥2 n≥0} set(B)={ c n d m |m≥2 n≥1} set(A)={ bpcndm | p≥1, m≥2, n≥1} set(S)={ aqbpcndmaq| p≥1 ,m≥2, n≥1, q≥1} ******************************************************************************* 7．给定如下文法，请用自然语言描述它们定义的语言。 （吴贤珺 02282047） ⑴ A→aaA│aaB B→Bcc│D#cc D→bbbD│# 解：该语言由四部分组成：第一部分是偶数个 a（至少有两个） ，第二部分是 3 的倍数个 b （可以是 0 个） ，第三部分是两个“#”号，第四部分是偶数个 c（至少有两个） 。 ⑵ A→0B│1B│2B B→0C│1C│2C C→0D│1D│2D│0│1│2 D→0B│1B│2B 解：该语言的句子是字母表∑＝{0,1,2}上所有长度为 3 的倍数的字符串，且非空。 ⑶ A→0B│1B│2B B→0C│1B│2B C→0E│1D│2D│0│1│2 D→0C│1B│2B E→0E│1D│2D│0│1│2 解：观察发现 C 和 E 所对应产生式右部是相同的。所以将文法化简成如下的形式： A→0B│1B│2B B→0C│1B│2B C→0C│1D│2D│0│1│2 D→0C│1B│2B 作出状态图如下： 0 0 0, 1, 2
=>aaabBCCBC =>aaabbCCBC =>aaabbCBCC =>aaabbBCCC =>aaabbbCCC =>aaabbbcCC =>aaabbbccc 推导二： S=>aSBC =>aaSBCBC =>aaaBCBCBC =>aaaBBCCBC =>aaaBBCBCC =>aaabbCBCC =>aaabbBCCC =>aaabbbCCC =>aaabbbcCC =>aaabbbccc 归约一、归约二分别为推导一和推导二的逆过程 ******************************************************************************* 5 句子 abeebbeeba 的一个推导如下： （陈伟芳 学号？？） S=>aAa 使用产生式 SaAa =>aSSa 使用产生式 ASS =>abAbSa 使用产生式 SbAb =>abSSbSa 使用产生式 ASS =>abeSbSa 使用产生式 Se =>abeebSa 使用产生式 Se =>abeebbAba 使用产生式 SbAb =>abeebbSSba 使用产生式 ASS =>abeebbeSba 使用产生式 Se =>abeebbeeba 使用产生式 Se 不能给出 abeebbeeb 的归约，因为由文法 G 中产生式推出的句子只有三种情况：头尾都是 a,头尾都是 b，或者只有一个 e，而 abeebbeeb 上面三个条件都不符合，所以它不是文法 G 的 一 个 句 子 ， 当 然 也 就 不 能 给 出 它 的 一 个 归 约 了 。 *******************************************************************************

第一章练习题（绪论）一、选择题1．编译程序是一种常用的软件。

A) 应用B) 系统C) 实时系统D) 分布式系统2．编译程序生成的目标代码程序是可执行程序。

A) 一定B) 不一定3．编译程序的大多数时间是花在上。

A) 词法分析B) 语法分析C) 出错处理D) 表格管理4．将编译程序分成若干“遍”将。

A)提高编译程序的执行效率；B)使编译程序的结构更加清晰，提高目标程序质量；C)充分利用内存空间，提高机器的执行效率。

5．编译程序各个阶段都涉及到的工作有。

A) 词法分析B) 语法分析C) 语义分析D) 表格管理6．词法分析的主要功能是。

A) 识别字符串B) 识别语句C) 识别单词D) 识别标识符7．若某程序设计语言允许标识符先使用后说明，则其编译程序就必须。

A) 多遍扫描B) 一遍扫描8．编译方式与解释方式的根本区别在于。

A) 执行速度的快慢B) 是否生成目标代码C) 是否语义分析9．多遍编译与一遍编译的主要区别在于。

A)多遍编译是编译的五大部分重复多遍执行，而一遍编译是五大部分只执行一遍；B)一遍编译是对源程序分析一遍就立即执行，而多遍编译是对源程序重复多遍分析再执行；C)多遍编译要生成目标代码才执行，而一遍编译不生成目标代码直接分析执行；D)多遍编译是五大部分依次独立完成，一遍编译是五大部分交叉调用执行完成。

10．编译程序分成“前端”和“后端”的好处是A)便于移植B)便于功能的扩充C)便于减少工作量D)以上均正确第二章练习题（文法与语言）一、选择题1．文法 G 产生的 (1) 的全体是该文法描述的语言。

A.句型B. 终结符集C. 非终结符集D. 句子2．若文法 G 定义的语言是无限集，则文法必然是 (2) A递归的 B 上下文无关的 C 二义性的 D 无二义性的3． Chomsky 定义的四种形式语言文法中， 0 型文法又称为(A)文法；1 型文法又称为(C)文法；2 型语言可由(G) 识别。

A 短语结构文法B 上下文无关文法C 上下文有关文法D 正规文法E 图灵机F 有限自动机G 下推自动机4．一个文法所描述的语言是(A)；描述一个语言的文法是(B)。

第二章高级语言及其语法描述本章要点1. 程序语言的定义；2. 高级程序语言一般结构和主要共同特征；3. 正确理解上下文无关文法基本概念，包括：文法的定义、推导、句型、句子、语言、语法树、二义性等；4. Chomsky文法分类；本章目标掌握和理解程序语言的定义、高级语言的一般特征及程序语言的语法描述。

本章重点1. 语法，词法规则与语法规则；2. 语义和语义规则；3. 数据类型与操作；4. 推导，最左推导和最右推导；5. 语法分析树和二义性；本章难点1. 二义性文法；2. Chomsky各个文法类；作业题一、单项选择题：（按照组卷方案，至少15道小题）1. Chomsky把文法分成四种类型，0型、1型、2型和3型。

3型文法也称为，2型文法也称为。

a.上下文无关文法b.上下文相关文法c.正则文法d.短语文法2. 许多广为使用的语言，如Fortran、C、Pascal等，属于。

a. 强制式语言b. 应用式语言c. 基于规则的语言d. 面向对象的语言3. 设G是一个文法，S是开始符号。

若S⇒*α，α∈(V T∪V N)*，则称α是一个。

a. 句子b. 句型c. 推导d. 语言4. 一个数据类型通常包括的三种要素中，没有下面的。

a. 用于区别这种类型的数据对象的属性；b. 这种类型的数据对象可以具有的值；c. 对这种类型的数据对象的内存分配；d. 可以作用于这种类型的数据对象的操作；5. Chomsky把文法分成四种类型，其中，也称正规文法a. 0型b. 1型c. 2型d. 3型6. 语言的词法规则一般用Chomsky的型文法来描述：a. 0b. 1c. 2d. 37. 文法S→(L)|aL→L，S|S中，下面是该文法中的终结符号。

a. Sb. ，c. Ld. |8. 文法G所描述的语言是的集合。

a. 文法G的字母表∑中的所有符号组成的符号串；b. 文法G的字母表∑的闭包∑*中的所有符号串；c. 文法G的识别符号推出的所有符号串；d. 文法G的识别符号推出的所有终结符号串；9. 语言L={αcα | α∈(a|b)*}，该语言是_____________语言。

第2章形式语言的基本知识习题答案第 1 题文法G＝({A,B,S},{a,b,c},P,S)其中P 为：S→Ac|aBA→abB→bc写出L(G[S])的全部元素。

答案：L(G[S])={abc}第 2 题文法G[N]为：N→D|NDD→0|1|2|3|4|5|6|7|8|9G[N]的语言是什么？答案: 允许0 开头的非负整数或者G[N]的语言是V+。

V={0,1,2,3,4,5,6,7,8,9}第3题为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，7等构造一个文法。

答案：G[S]:S->S+D|S-D|DD->0|1|2|3|4|5|6|7|8|9第 4 题已知文法G[Z]：Z→aZb|ab写出L(G[Z])的全部元素。

答案：L(G[Z])={a n b n|n>=1}第 5 题（答案不唯一）写一文法，使其语言是偶正整数的集合。

要求：(1) 允许0 打头；(2)不允许0 打头。

答案：(1)允许 0 开头的偶正整数合的文法E→NT|DT→NT|DN→D|1|3|5|7|9D→0|2|4|6|8(2)不允许 0 开头的偶正整数集合的文法E→NT|DT→FT|GN→D|1|3|5|7|9D→2|4|6|8F→N|0G→D|0第 6 题已知文法G：<表达式>::=<项>｜<表达式>＋<项><项>::=<因子>｜<项>*<因子><因子>::=（<表达式>）｜i试给出下述表达式的最左推导及语法树。

（1）i+(i+i)（2）i+i*i答案：(1) <表达式>=><表达式>＋<项>=><表达式>＋<因子>=><表达式>＋（<表达式>）=><表达式>＋（<表达式>＋<项>）=><表达式>＋（<表达式>＋<因子>）=><表达式>＋（<表达式>＋i）=><表达式>＋（<项>＋i）=><表达式>＋（<因子>＋i）=><表达式>＋（i＋i）=><项>＋（i＋i）=><因子>＋（i＋i）=>i＋（i＋i）(2) <表达式>=><表达式>＋<项>=><表达式>＋<项>*<因子>=><表达式>＋<项>*i=><表达式>＋<因子>*i=><表达式>＋i*i=><项>＋i*i=><因子>＋i*i=>i＋i*i第7 题为句子i+i*i 构造两棵语法树，从而证明下述文法G[〈表达式〉]是二义的。

编译原理形式语言题+答案第一篇：编译原理形式语言题+答案第2章形式语言1．试分别构造产生下列语言的文法：（1）{an#bn|n≥0}∪{cn#dn|n≥0}；（2）任何不是以0打头的所有奇整数所组成的集合。

答：(1)对应文法为G(S)=({S,X,Y},{a,b,c,d,#}, {S→X, S→Y, X→aXb|#, Y→cYd|# },S)(2)G(S)=({S,A,B,I,J},{0,1,2,3,4,5,6,7,8,9}, {S→J|IBJ, B→0B|IB|ε, I→J|2|4|6|8, J→1|3|5|7|9},S)2．对于下列的文法S→AB|cA→bA|aB→aSb|c试给出句子bbaacb的最右推导。

答：S=>AB=>AaSb=> Aacb=>bAacb=>bbAacb=>bbaacb3．已知文法G[S]:S->(AS)|(b)A->(SaA)|(a)请找出符号串(a)和(A((SaA)(b)))的短语、简单短语和句柄。

答：因为S 不能⇒(a), 所以(a)不是文法的句型。

没有短语、直接短语和句柄。

因为S ⇒(AS)⇒(A(AS))⇒(A((SaA)S))⇒(A((SaA)(b))),所以(A((SaA)(b)))是文法的句型。

短语：(A((SaA)(b)))，((SaA)(b))，(SaA)，(b)直接短语：(SaA)，(b)句柄：(SaA)S（AS)（AS)（S a A)（b)4．试描述由下列文法所产生的语言的特点：（1）S→10S0S→aAA→bAA→a（2）S→aSSS→a答：(1)本文法构成的语言集为：L(G)={(10)nabma0n|n,m≥0}。

(2)由L(G)={a2n-1|n≥1}可知，该语言特点是：产生的句子是奇数个a。

附加题：试证明文法S→AB|DCA→aA|aB→bBc|bcC→cC|cD→aDb|ab 为二义性文法。

。
可以产生语言 L。
A aAb | b
C． Z AbB
Ab
D. Z aAb
A aA | a
A aAb | b
（8）若一个文法是递归的，则它产生语言的句子个数 。 A. 必定是无穷的 B. 根据情况而定 C．是有穷个 D. 有穷个，但是个数很大 （9）文法 G : S xSx | y 所识别的语言是 。
3
B → Bb|ε G[S]产生的语言是什么？G[S]能否改写为等价的正则文法? 四、文法题 （1）文法 G[S ] :
S aSb | P P bPc | bQc Q Qa | a
（1）它是乔姆斯基的哪一种文法？ （20S | 0 | 1A B 1A | 0B A 1 | 1S | 0B
符号串是 L(G) 中的句子。 A. 10100010011011 B. 0101001110010010 C．1101010011110111 D. 10100111011010110 （4）有限自动机能识别 。 A. 上下文无关文法 B. 上下文有关文法 C．正规文法 D. 短语文法 （5）由文法的开始符号经 0 步或多部推导产生的文法符号序列是 A. 短语 B. 句柄 C． 句型 D. 句子 （6）一个句型中的最左 称为该句型的句柄 。 A. 短语 B. 直接（简单）短语 C．素短语 D. 终结符号 （7）已知语言 L {a n bbn | n 1} ，则下列文法中， A. Z aZb | aAb B. A aAb
1
A. xyx C． x n yxn (n 0) （10）有文法 G[S ] :
B. ( xyx) * D. x * yx*
S aA | a | bc A aS | bB B aC | bA | b C aB | bS

2020/11/5
h
16
2.2 形式定义
• 约定
⑴ 对一组有相同左部的产生式 αβ1，αβ2 ，… ，αβn 可以简单地记为： αβ1|β2|…|βn 读作：α定义为β1，或者β2，…，或者βn。并
且称它们为α产生式。β1，β2，…，βn称为 候选式(candidate)。
2020/11/5
h
17
2020/11/5
h
7
2.1 启示
<动词>走在 <动词>进入 <形容词短语>很抽象的 <名词短语>北京 <名词短语>哈尔滨 <名词短语>形式语言
2020/11/5
h
8
2.1 启示
<名词短语>中国
<名词短语>教育
<名词短语>集合
<名词短语> WTO
<名词短语>美丽的城市
<名词短语>祖国的首都
<名词短语>数学的基础
中有时候又称之为语法范畴。
20/11/5
h
12
2.2 形式定义
– T——为终极符(terminal)的非空有穷集。 a∈T，a叫做终极符。由于V中变量表 示语法范畴，T中的字符是语言的句子中
出现的字符，所以，有V∩T=Φ。
– S——S∈V，为文法G的开始符号(start symbol)。
2020/11/5
<名词短语>社会发展的前面
<句号>。
2020/11/5
h
9
2.1 启示
• 表示一个语言，需要4种东西 ⑴形如<名词短语>的 “符号”

第二章高级语言及其语法描述本章要点1. 程序语言的定义；2. 高级程序语言一般结构和主要共同特征；3. 正确理解上下文无关文法基本概念，包括：文法的定义、推导、句型、句子、语言、语法树、二义性等；4. Chomsky文法分类；本章目标掌握和理解程序语言的定义、高级语言的一般特征及程序语言的语法描述。

本章重点1. 语法，词法规则与语法规则；2. 语义和语义规则；3. 数据类型与操作；4. 推导，最左推导和最右推导；5. 语法分析树和二义性；本章难点1. 二义性文法；2. Chomsky各个文法类；作业题一、单项选择题：（按照组卷方案，至少15道小题）1. Chomsky把文法分成四种类型，0型、1型、2型和3型。

3型文法也称为，2型文法也称为。

a.上下文无关文法b.上下文相关文法c.正则文法d.短语文法2. 许多广为使用的语言，如Fortran、C、Pascal等，属于。

a. 强制式语言b. 应用式语言c. 基于规则的语言d. 面向对象的语言3. 设G是一个文法，S是开始符号。

若S⇒*α，α∈(V T∪V N)*，则称α是一个。

a. 句子b. 句型c. 推导d. 语言4. 一个数据类型通常包括的三种要素中，没有下面的。

a. 用于区别这种类型的数据对象的属性；b. 这种类型的数据对象可以具有的值；c. 对这种类型的数据对象的内存分配；d. 可以作用于这种类型的数据对象的操作；5. Chomsky把文法分成四种类型，其中，也称正规文法a. 0型b. 1型c. 2型d. 3型6. 语言的词法规则一般用Chomsky的型文法来描述：a. 0b. 1c. 2d. 37. 文法S→(L)|aL→L，S|S中，下面是该文法中的终结符号。

a. Sb. ，c. Ld. |8. 文法G所描述的语言是的集合。

a. 文法G的字母表∑中的所有符号组成的符号串；b. 文法G的字母表∑的闭包∑*中的所有符号串；c. 文法G的识别符号推出的所有符号串；d. 文法G的识别符号推出的所有终结符号串；9. 语言L={αcα | α∈(a|b)*}，该语言是_____________语言。