编译语言与文法
文法和语言（1）
L (G) = { an
|n≥0 } 解答: G : S→aS|ε
L (G) = { an |n≥1 }
解答: G :
S→aS|a
L (G) = { an b m
|n≥1, m≥1 } 解答: G 1:S→AB A →aA|a B →bB|b G2: S →aA
A →aA|B
B→bB|b
L (G) = { an b m
|n≥0, m≥0 } 解答: G 1:S→AB A →aA|ε B →bB|ε
G2: A →aA|B
B→bB|ε
L (G) = { an b m c k
|n, m, k≥0 } 解答: G :
S→aS|B
B→bB|C
C→cC|ε
L(G) = { an b n
| n≥0 }解答: G : S →aSb |ε
L(G) = { an b n
| n≥1 }解答: G :
S →aSb | ab
L(G) = { an
ba n
| n≥0 } 文法和语言（2）
L (G) = { an
|n≥1，n 为奇数 } 解答: G : S→aaS | a
L (G) = { an |n≥0，n 为非负偶数 }
解答: G : S→aaS | ε
L (G) = { an b n
|n≥1，n 为奇数 }
解答: G : S→aaSbb | ab
L (G) = { an b n
|n≥0，n 为非负偶数 }
解答: G : S→aaSbb | ε
L (G) = { am b n c n
| m为奇数，n 为非负偶数 }
解答: G : S→AB A →aaA | a
B →bbBcc | ε L (G) = { am b n
| n>m≥1 } 解答1:
G:
S→AB
1. Σ={a,b}, 正规式 (a|b)a(a|b)*a 表示的语言有什么特点。【解答】 第2个符号是a ，且以a 结尾
2. Σ={a,b}, 正规式 (ba | a)* 表示的语言有什么特点。 【解答】 每个b 都有a 跟在后面
解答: G : S →aSa | b
L(G) = { an
ba n
| n≥1 } 解答: G 1: S →aSa | aba
G2: S →aAa
A →aAa | b
L (G) = { an b m c m
| n≥0,m≥1 } 解答: G [S]: S →AB
A→aA|ε
B→bBc|bc
L (G) = { an b m c m
| n≥1,m≥0 } 解答: G 1[S]: S→AB
A→aA|a
B→bBc|ε
L (G) = { a n b n a m b m
| n≥0,m≥0 } 解答: G 2: S→AB
A→aAb|ε
B →aBb|ε
G1:
S→AA
A→aAb|ε
L (G) = { 1n 0m 1m 0n
| n,m≥0 } 解答: G : S→1S0 | A
A →0A1 | ε
L (G) = { WaWr
| W∈{0|a}*，W r
表示W 的逆序 } 解答: G :
S→0S0 S →aSa S →a
A →aAb| ab
B →bB | b 解答2:
G:
S→Sb | Ab A→aAb | ab
提示：
b 的个数比a 多 a m b n = m m n-m ( m≥1, n-m≥1 )
L (G) = { an b m
| 2n>m≥n ≥1 }
解答: G : S→aSb | ab
S →aSbb
L (G) = { an b m
| 2n≥m ≥n ≥1 } 解答: G : S→aSb | ab
S →aSbb | abb
L (G) = { an b m
| 2n>m>n≥1 } 解答: G : S→aSb | aabbb
S →aSbb
3. 设 L ⊆{0,1}* , L中的符号串以‘0’开头并且以‘1’结尾;
(1) 写出定义集合L 的正规式。 (2) 构造识别集合L 的DFA 。 【解答】 定义集合L 的正规式：0(0|1)*1
4. 设 L ⊆{a,b,c}*, L是满足下述条件的符号串构成的语言:
(1) 若出现a, 则其后至少紧跟两个c; (2) 若出现b, 则其后至少紧跟一个c 。
文法和语言自测题及解答
二、简答题
1. 写一个文法G, 使得 L (G) = { ab a | n, m ≥ 0 } 【解答】 G : S →aSa | B
B →bB |ε
n m k n m n
试写出定义语言L 的正规式 【解答】 ( acc | bc | c )* 1. 已知文法 G :
A→aABl | a B→Bb | d
(1). 试写出与文法G 等价的LL(1)文法G' 。 (2). 构造G' 的预测分析表。
(3). 对输入串aade#进行LL(1)分析。 【解答】 (1) G': A→aT (2)
T→ABl | ε B →dB' B' →bB' | ε
2. 写一个三型文法G, 使得 L (G) = { ab c | n, m, k ≥ 1 } 【解答】 G : S →aS | aB
B →bB | bC C →cC | c
3. 描述由下列文法所产生的语言的特点
G:
S→SS | 1A0 A→1A0 | ε
【解答】
L (G ) ={1010... 10|n 1, n 2,..., n k
n 1n 1n 2n 2n k n k
n
n m
m
该语言的特点是产生的句子中,0和1的个数相同, 并且若干相邻的1后面必然紧跟数量相同的连续的0 4. 化简以下文法:
G: S→aS | W | U
U→a V→bV | ac W→aW
2. 给出定义语言L ＝{ 1a01a0 | n≥1, m≥0 }的LL(1)文法G 。并说明G 为LL(1)文法的理由。 【解答】 G: S →AB
A →1A0 | 1a0 B →1B0 | a
文法G 存在左公因子, 所以不是LL(1)文法, 可进行变换提取左公因子, 得到G' G': S →AB
A →1C C →A0 | a0
别.
FIRST(S) = {1} FIRST(A) = {1} FIRST(C) = {1,a} FIRST(D) = {1,a}
构造G' 的预测分析表, 不含多重定义入口, 所以G' 是LL(1)文法。 (也可以按照LL(1)判别条件进行判别)
B →1B0 | a
文法G' 中不含空产生式, 所以只需求出FIRST 集合进行LL(1)判
【解答】 化简后的文法 G’: S→aS | U U→a 二、综合题
1. 文法G 及其LR 分析表如下, 请给出对串 baba# 的分析过程。
G : (1) S→DbB(2) D→d(3) D→ε(4) B→a(5) B→Bba(6) B →ε
二、综合题
预测分析表