Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
83 lines (49 sloc) 2.17 KB

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)|ε

解答

  1. 0, 00, 0…0
  2. a, aa, a…a

4.6.2

为练习4.2.1中的(增广)文法构造SLR项集。计算这些项集的GOTO函数。给出这个函数的语法分析表。这个文法是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)的。

4.6.6

说明下面的文法

S->SA|A
A->a

是SLR(1)的,但不是LL(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时所有可能的动作序列