4.6 节的练习

4.6.1

描述下列文法的所有可行前缀

1. 练习4.2.2-1的文法 S->0S1|01
2. ！ 练习4.2.1的文法 S->SS+|SS*|a
3. ！ 练习4.2.2-3的文法 S->S(S)S|ε

解答

以下提取左公因子和消除左递归后的文法均由练习 4.3.2 得到

1. 提取左公因子和消除左递归后的增广文法

    0) S' -> S
    1) S -> 0 A
    2) A -> 0 A 1
    3) A -> 1

   LR(0) 自动机

   

   可行前缀为 0+A?1?

2. 提取左公因子和消除左递归后的增广文法

    0) S' -> S
    1) S -> a B
    2) B -> a B A B
    3) B -> ε
    4) A -> +
    5) A -> *

   LR(0) 自动机

   

   可行前缀为 aB?|a{2,∞}(BAa+)*(B|B+|B*|BA|BAB)?

3. 提取左公因子和消除左递归后的增广文法

    0) S' -> S
    1) S -> A
    2) A -> (S) S A
    3) A -> ε

   LR(0) 自动机

   

   箭头太复杂，懒得归纳了

4.6.2

为练习4.2.1中的（增广）文法构造SLR项集。计算这些项集的GOTO函数。给出这个函数的语法分析表。这个文法是SLR文法吗？

解答

该文法的项集和 GOTO 函数见 4.6.1-2

FOLLOW 函数如下：

FOLLOW(S) = [$]
FOLLOW(A) = [a, $]
FOLLOW(B) = [+, * ,$]

语法分析表如下：

状态	ACTION				GOTO
	a	+	*	$	S	A	B
0	s2				s1
1				acc
2	s4	r3	r3	r3			s3
3				r1
4	s4	r3	r3	r3			s5
5		s7	s8			s6
6	s4	r3	r3	r3			s9
7	r4			r4
8	r5			r5
9		r2	r2	r2

无冲突，这显然是一个 SLR 文法

4.6.3

利用练习4.6.2得到的语法分析表，给出处理输入aa*a+时的各个动作。

解答

	栈	符号	输入	动作
1)	0		aa*a+$	移入
2)	02	a	a*a+$	移入
3)	024	aa	*a+$	根据 B -> ε 规约
4)	0245	aaB	*a+$	移入
5)	02458	aaB*	a+$	根据 A -> * 规约
6)	02456	aaBA	a+$	移入
7)	024564	aaBAa	+$	根据 B -> ε 规约
8)	0245645	aaBAaB	+$	移入
9)	02456457	aaBAaB+	$	根据 A -> + 规约
9)	02456456	aaBAaBA	$	根据 B -> ε 规约
10)	024564569	aaBAaBAB	$	根据 B -> aBAB 规约
11)	024569	aaBAB	$	根据 B -> aBAB 规约
12)	023	aB	$	根据 S -> aB 规约
13)	01	S	$	接受

4.6.4

对于练习4.2.2-1~4.2.2-7中的各个（增广）文法：

1. 构造SLR项集和他们的GOTO函数
2. 指出你的项集中的所有动作冲突
3. 如果存在SLR语法分析表，构造出这个语法分析表

4.6.5

说明下面的文法

S->AaAb|BbBa
A->ε
B->ε

是LL(1)的，但不是SLR(1)的。

解答

1. 该文法是 LL(1) 的

   见 4.4.3 节，p142 的判定标准

2. 该文法不是 SLR(1) 的

    I_0
   
    S' -> .S
    S -> .AaAb
    S -> .BbBa
    A -> .
    B -> .

   由于 FOLLOW(A) = FOLLOW(B) = [a, b]，所以当 I_0 后输入为 a 或 b 时，就会发生规约冲突。

4.6.6

说明下面的文法

S->SA|A
A->a

是SLR(1)的，但不是LL(1)的

解答

1. 该文法不是 LL(1) 的

   S -> SA 和 S -> A 均能推导出以 a 开头的串，所以不是 LL(1) 的

2. 该文法是 SLR(1) 的

   该文法生成的语法分析表是没有冲突的

4.6.7!!

考虑按照下面的方式定义的文法族 G_n：

S -> A_i b_i         其中1<=i<=n
A_i-> a_j A_j | a_j    其中1<=i,j<=n 且i<>n

说明：

1. G_n有 2n^2-n 个产生式
2. G_n有 2^n+n^2+n 个 LR(0) 项集
3. G_n是 SLR(1) 的

关于LR语法分析器的大小，这个分析结果说明了什么？

4.6.8!

我们说单个项可以看做一个 NFA 的状态，而有效项的集合就是一个 DFA 的状态。对于练习4.2.1的文法 S->SS+|SS*|a

1. 根据“将项看作一个NFA的状态”部分中的规则，画出这个文法的有效的转换图（NFA）
2. 将子集构造算法（算法3.20）应用于在（1）部分构造得到的NFA。得到的DFA和这个文法的LR(0)项集比有什么关系
3. ！！ 说明在任何情况下，将子集构造算法应用于一个文法的有效项的NFA所得到的就是该文法的 LR(0) 项集

4.6.9!

下面是一个二义性的文法

S->AS|b
A->SA|a

构造出这个文法的规范LR(0)项集族。如果我们试图为这个文法构造出一个LR语法分析表，必然会存在某些冲突动作。都有哪些冲突动作？假设我们使用这个语法分析表，并且在出现冲突时不确定地选择一个动作。给出输入abab时所有可能的动作序列