目录

考点一：文法，推导

1.按指定类型，给出语言的文法。

(1) L={ai bj|j ＞i≥0} 的上下文无关文法；
(2) 字母表 Σ={a,b} 上的同时只有奇数个 a 和奇数个 b 的所有串的集合的正规文法；
(3) 由相同个数 a 和 b 组成句子的无二义文法。

解：

(1) 由 L={ai bj|j ＞i≥0} 知，
所求该语言对应的上下文无关文法首先应有
S→aSb 型产生式， 以保证 b 的个数不少于 a 的个数；
其次， 还需有 S→Sb 或 S→b 型的产生式，
用以保证 b 的个数多于 a 的个数。因此，所求上下文无关文法 G[S]为
G[S] ：S→aSb|Sb|b
(2) 为了构造字母表 Σ={a,b} 上同时只有奇数个 a 和奇数个 b 的所有串集合的正规式，我们
画出如图 3-3 所示的 DFA，即由开始符 S 出发，经过奇数个 a 到达状态 A，或经过奇数个 b
到达状态 B；而由状态 A 出发，经过奇数个 b 到达状态 C(终态 )；同样，由状态 B 出发经过
奇数个 a 到达终态 C。

由图 3-3 可直接得到正规文法 G[S]如下：
G[S] ：S→ aA|bB
A→aS|bC|b
B→bS|aC|a
C→bA|aB|ε
(3) 我们用一个非终结符 A 代表一个 a(即有 A →a)，用一个非终结符 B 代表一个 b(即有 B→
b)；为了保证 a 和 b 的个数相同，则在出现一个 a 时应相应地出现一个 B，出现一个 b 时则
相应出现一个 A 。假定已推导出 bA ，如果下一步要推导出连续两个 b 时，则应有 bAbbAA 。
也即为了保证 b 和 A 的个数一致，应有 A→bAA ；同理有 B→aBB。此外，为了保证递归地
推出所要求的 ab 串，应有 S→aBS 和 S→bAS。由此得到无二义文法 G[S] 为
G[S] ：S→aBS|bAS|ε
A→bAA|a
B→aBB|b

2．构造一文法，使其描述的语言L = {ω |ω ∈ (a, b)*，且ω中含有相同个数的a和b}。

解：

S→ ε| aA|bB
A→ b| bS| aAA
B→ a| aS| bBB

考点二：最左推导，最右推导

3．令文法G[N]为

G[N]: N→D|ND
D→0|1|2|3|4|5|6|7|8|9

给出句子568的最左、最右推导。

解：

最左推导：N => ND=> NDD=> DDD=> 5DD=> 56D=> 568
最右推导：N => ND => N8=> ND8=> N68=> D68=> 568

考点三：语法树，二义文法

4.已知文法 G[S] 为 S→aSb|Sb|b，试证明文法 G[S] 为二义文法。

解：

由文法 G[S] ：S→ aSb|Sb|b，对句子 aabbbb 可对应如图 3-1 所示的两棵语法树。

因此，文法 G[S] 为二义文法 (对句子 abbb 也可画出两棵不同语法树 )。

5.已知文法 G[S] 为 S→SaS|ε，试证明文法 G[S]为二义文法。

解：

由文法 G[S] ：S→ SaS|ε，句子 aa 的语法树如图 3-2 所示

由图 3-2 可知，文法 G[S]为二义文法。

6．已知文法G[S]: S→aSbS|bSaS|ε

试证明G[S]是二义文法

证明：

该文法产生的语言是a的个数和b的个数相等的串的集合。该文法二义，

例如句子abab有两种不同的最左推导。

   S=> aSbS=> abS=> abaSbS=> ababS=> abab    
   S=> aSbS=> abSaSbS=> abaSbS=> ababS=> abab

7．设有文法G[S]:

S→S*S|S+S|(S)|i
该文法是否为二义文法,并说明理由？

解

该文法是二义文法，因为该文法存在句子i*i+i,该句子有两棵不同的语法树如图所示。

考点四：短语，直接短语，句柄，素短语

8．对于文法G[E]:

G[E]:E→E+T | T
T→T+P | P
P→(E) | i

写出句型P+T+(E+i)的所有短语、直接短语、句柄。

解：

短语：P、P+T、i、E+i、(E+i )、P+T+(E+i )；
直接短语：P、i；
句柄：P；

9．设有文法G[E]:

解：

考点五：消除左递归，提取公共左因子

10．已知文法G(S)：

S→S*aP| aP| *aP
P→+aP| +a

将文法G(S)改写为确定的文法G’(S)；

解：

原式 消除左递归后
A->Aa|B A—>BA’
A‘—>aA’|ε
原式 消除公共左因子后
A->aB1|aB2 A—>aA’
A‘—>B1|B2

1）消除左递归，文法变为：

 S→aPS’| *aPS’
 S’→ *aPS’ | ε
 P→+aP| +a

2）提取公共左因子，文法变为G’(S)：

S→aPS’| *aPS’
S’→ *aPS’ |ε
P→+aP’
P’→P| ε

11.下述文法描述了c语言整数变量的声明语句：


（1）查看这个文法有没有不确定因素：公共左因子，左递归


（2）

12.考虑文法


13.G[A]


（1）第一步：消除公共左因子

第二部：绘制表格求first,follow集，判断是否是LL(1)


第三步：判定有或的产生式

（2）构造分析表

(3)描述分析过程

栈 输入串 动作
#A aadl# A->aA’
#A’a aadl# 匹配
#A’ adl# A‘->ABl
#lBA adl# A->aA’
#lBA’a adl# 匹配
#lBA’ dl# A’->null
#lB dl# B->dB’
#lB’d dl# 匹配
#lB’ l# B’->null
#l l# 匹配
# # 分析成功

题4

V->NV'
V->NULL|[E]
E->VE'
E'->NULL|+E
N->i

FIRST([E])^FOLLOW(V')=NULL
FIRST(+E)^FOLLOW(E')=NULL
因为都为空集，所是LL1文法