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) = [+, * ,$]

语法分析表如下：

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

4.6.3

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

解答

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时所有可能的动作序列