4.4 节的练习
4.4.1
为下面的每个文法设计一个预测分析器，并给出预测分析表。你可能先要对文法进行提取左公因子或者消除左递归的操作。
练习 4.2.2 中 1 - 7 中的文法。
解答
-
S -> 0 S 1 | 0 1
step1. 提取左公因子
S -> 0 A
A -> S 1 | 1
step2. 消除左递归
S -> 0 A
A -> 0 A 1 | 1
step3. 预测分析表
| 非终结符号 |
输入符号 |
| 0 |
1 |
$ |
| S |
S -> 0 A |
|
|
| A |
A -> 0 A 1 |
A -> 1 |
|
-
S -> + S S | * S S | a
step1. 无左公因子
step2. 无左递归
step3. 预测分析表
| 非终结符号 |
输入符号 |
| + |
* |
a |
$ |
| S |
S -> + S S |
S -> * S S |
S -> a |
|
-
! S -> S (S) S | ε
step1. 无左公因子
step2. 消除左递归
S -> A
A -> (S) S A | ε
step3. 预测分析表
| 非终结符号 |
输入符号 |
| ( |
) |
$ |
| S |
S -> A |
S -> A |
S -> A |
| A |
A -> (S) S A
A -> ε |
A -> ε |
A -> ε |
-
! S -> S + S | S S | (S) | S * | a
step1. 提取左公因子
S -> SA | (S) | a
A -> +S | S | *
进一步提取终结符
S -> SA | T
A -> +S | S | *
T -> (S) | a
step2. 消除左递归(根据 p135 的算法 4.19)
i = 1
S -> TB
B -> AB | ε
i = 2
j = 1
A -> +S | TB | *
i = 3
j = 1
无需处理
j = 2
无需处理
得到最终的产生式
S -> TB
B -> AB | ε
A -> +S | TB | *
T -> (S) | a
step3. first && follow
first(T) = [(, a]
first(A) = [+, *] + first(T) =[+, *, (, a]
first(B) = [ε] + first(A) = [ε, +, *, (, a]
first(S) = first(T) = [(, a]
follow(T) = [$, +, *, (, a]
follow(A) = [$, +, *, (, ), a]
follow(B) = [$]
follow(S) = [$, +, *, (, ), a]
step4. 预测分析表
| 非终结符号 |
输入符号 |
| ( |
) |
+ |
* |
a |
$ |
| S |
S -> TB |
|
|
|
S -> TB |
|
| B |
B -> AB |
|
B -> AB |
B -> AB |
B -> AB |
B -> ε |
| A |
A -> TB |
|
A -> +S |
A -> \* |
A -> TB |
|
| T |
T -> (S) |
|
|
|
T -> a |
|
-
S -> (L) | a 以及 L -> L, S | S
step1. 无左公因子
step2. 消除左递归
S -> (L) | a
L -> SA
A -> ,SA | ε
step3. 预测分析表
-
grammar for boolean expressions:
bexpr -> bexpr or bterm | bterm
bterm -> bterm and bfactor | bfactor
bfactor -> not bfactor | ( bexpr ) | true | false
step1. 无左公因子
step2. 消除左递归
bexpr -> bterm bexpr'
bexpr' -> or bterm bexpr' | ε
bterm -> bfactor bterm'
bterm' -> and bfactor bterm' | ε
bfactor -> not bfactor | (bexpr) | true | false
step3. first && follow
first(bexpr) = first(bterm) = first(bfactor) = [not, (, true, false]
first(bexpr') = [or, ε]
first(bterm') = [and, ε]
follow(bexpr) = follow(bexpr') = [), $]
follow(bterm) = follow(bterm') = [or, $]
follow(bfactor) = [and, $]
step4. 预测分析表
| 非终结符号 |
输入符号 |
| and |
or |
not |
( |
) |
true |
false |
$ |
| bexpr |
|
|
bexpr -> bterm bexpr' |
bexpr -> bterm bexpr' |
|
bexpr -> bterm bexpr' |
bexpr -> bterm bexpr' |
|
| bexpr' |
|
bexpr' -> or bterm bexpr' |
|
|
bexpr' -> ε |
|
|
bexpr' -> ε |
| bterm |
|
|
bterm -> bfactor bterm' |
bterm -> bfactor bterm' |
|
bterm -> bfactor bterm' |
bterm -> bfactor bterm' |
|
| bterm' |
|
bterm' -> and bfactor bterm' |
|
|
bterm' -> ε |
|
|
bterm' -> ε |
| bfactor |
|
|
bfactor -> not bfactor |
bfactor -> (bexpr) |
|
bfactor -> true |
bfactor -> false |
|
4.4.2 ！！
有没有可能通过某种方法修改练习 4.2.1 中的文法，构造出一个与该练习中的语言（运算分量为 a 的后缀表达式）对应的预测分析器？
解答
S -> SS+ | SS* | a
step1. 提取左公因子
S -> SSA | a
A -> + | *
step2. 消除左递归
i = 1
S -> aB
B -> SAB | ε
A -> + | *
i = 2
j = 1
S -> aB
B -> aBAB | ε
A -> + | *
step3. 预测分析表
| 非终结符号 |
输入符号 |
| + |
* |
a |
$ |
| S |
|
|
S -> aB |
|
| A |
A -> + |
A -> * |
|
|
| B |
B -> ε |
B -> ε |
B -> SAB |
B -> ε |
4.4.3
计算练习 4.2.1 的文法的 FIRST 和 FOLLOW 集合。
解答
- first(S) = [a]
- follow(S) = [a, +, *]
4.4.4
计算练习 4.2.2 中各个文法的 FIRST 和 FOLLOW 集合。
解答
-
S -> 0 S 1 | 0 1
- first(S) = [0]
- follow(S) = [1, $]
-
S -> + S S | * S S | a
- first(S) = [+, *, a]
- follow(S) = [+, *, a, $]
-
S -> S (S) S | ε
- first(S) = [(, ε]
- followS(S) = [), $]
-
S -> S + S | S S | (S) | S * | a
- first(S) = [(, a]
- follow(S) = [+, (, ), a, *, $]
-
S -> (L) | a 以及 L -> L, S | S
- first(S) = [(, a]
- follow(S) = [",", $]
- first(L) = first(S) = [(, a]
- follow(L) = [), “,”, $]
-
S -> a S b S | b S a S | ε
- first(S) = [a, b, ε]
- follow(S) = [a, b, $]
-
下面的布尔表达式对应的文法：
bexpr -> bexpr or bterm | bterm
bterm -> bterm and bfactor | bfactor
bfactor -> not bfactor | (bexpr) | true | false
4.4.5
文法 S -> aSa | aa 生成了所有由 a 组成的长度为偶数的串。我们可以为这个文法设计一个带回溯的递归下降分析器。如果我们选择先用产生式 S -> aa 展开，那么我们只能识别串 aa。因此，任何合理的递归下降分析器将首先尝试 S -> aSa。
- ！ 说明这个递归下降分析器识别输入 aa，aaaa 和 aaaaaaaa，但识别不了 aaaaaa。
- ！！ 这个递归下降分析器识别什么样的语言？
注意
以下题目请参考 Aho 本人的讲义：Aho: Properties of Context-Free Languages，本地副本
此外还有另一篇内容相似的文章，本地副本
关于 CNF 和 CYK 算法，有较多相关资料，自行搜索
4.4.6 !
如果一个文法没有产生式体为 ε 的产生式，那么这个文法就是无 ε 产生式的。
- 给出一个算法，他的功能是把任何文法转变成一个无 ε 产生式的生成相同语言的文法（唯一可能的例外是空串——没有哪个无 ε 产生式的文法能生成 ε）。提示：首先找出所有可能为空的非终结符号。非终结符号可能为空是指它（可能通过很长的推导）生成 ε。
- 将你的算法应用于文法 S -> aSbS | bSaS | ε
4.4.7 ！
单产生式是指其产生式体为单个非终结符号的产生式，即形如 A -> B 的产生式。
- 给出一个算法，它可以把任何文法转变成一个生成相同语言（唯一可能的例外是空串）的、无 ε 产生式、无单产生式的文法。提示：首先消除 ε 产生式，然后找出所有满足下列条件的非终结符号对 A 和 B：存在 A =*=> B。
- 将你的算法应用于 4.1.2 节的算法。
- 说明作为 （1） 的一个结果，我们可以把一个文法转换成一个没有环的等价文法。
4.4.8 ！！
如果一个文法的每个产生式要么形如 A -> BC，要么形如 A -> a，那么这个文法就成为 Chomsky 范式（Chomsky Normal Form， CNF）。说明如何将任意文法转变成一个生成相同语言（唯一可能的例外是空串——没有 CNF 文法可以生成 ε）的 CNF 文法。
4.4.9 ！
对于每个具有上下文无关的语法，其长度为 n 的串可以在 O(n^3) 的时间内完成识别。完成这种识别工作的一个简单方法称为 Cocke-Younger-Kasami（CYK）算法。该算法基于动态规划技术。也就是说，给定一个串 a_1a_2…a_n，我们构造出一个 nxn 的表 T 使得 T_ij 是可以生成子串 a_ia_i+1…aj 的非终结符号的集合。如果基础文法是 CNF 的，那么只要我们按照正确的顺序来填表：先填 j-i 值最小的条目，则表中的每一个条目都可以在 O(n) 时间内填写完毕。给出一个能够正确填写这个表的条目的算法，并说明你的算法的时间复杂度为 O(n^3)。填完这个表之后，你如何判断 a_1a_2…a_n 是否在这个语言中？
4.4.10 ！
说明我们如何能够在填好练习 4.4.9 中的表之后，在 O(n) 的时间内获得 a_1a_2…a_n 对应的一颗语法分析树？提示：修改练习 4.4.9 中的表 T，使得对于表的每个条目 T_ij 中的每个非终结符号 A，这个表同时记录了其他条目中的哪两个非终结符号组成的对偶使得我们将 A 放到 T_ij 中。
4.4.11 ！
修改练习 4.4.9 中的算法，使得对于任意符号串，他可以找出至少需要执行多少次插入、删除和修改错误（每个错误是一个字符）的操作才能将这个串变成基础文法的语言的句子。
4.4.12 ！
stmt -> if e then stmt stmtTail
| while e do stmt
| begin list end
| s
stmtTail -> else stmt
| ε
list -> stmt listTail
listTail -> ; list
| ε
上面的代码给出了对应于某些语句的文法。你可以将 e 和 s 当做分别代表条件表达式和“其他语句”的终结符号。如果我们按照下列方法来解决因为展开可选“else”（非终结符号 stmtTail）而引起的冲突：当我们从输入中看到一个 else 时就选择消耗掉这个 else。使用 4.4.5 节中描述的同步符号的思想：
- 为这个文法构造一个带有错误纠正信息的预测分析表。
- 给出你的语法分析器在处理下列输入时的行为：
- if e then s; if e then s end
- while e do begin s; if e then e; end
