• Introduction
• 1. 1.Introduction
• 2. 2.A Simple Syntax-Directed Translator
• 3. 3.Lexical Analysis
• 4. 4.Syntax Analysis
• 5. 5.Syntax-Directed Translation
• 6. 6.Intermediate-Code Generation
• 7. 7.Run-Time Environments
• 8. 8.Code Generation
• 9. 12.InterProcedural Analysis
• Published with GitBook

4.4 节的练习

4.4.1

解答

1. 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
2. S -> + S S | * S S | a

step1. 无左公因子

step2. 无左递归

step3. 预测分析表

非终结符号 输入符号
+ * a \$
S S -> + S S S -> * S S S -> a
3. ! 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 -> ε
4. ! 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
5. S -> (L) | a 以及 L -> L, S | S

step1. 无左公因子

step2. 消除左递归

`````` S -> (L) | a
L -> SA
A -> ,SA | ε
``````

step3. 预测分析表

6. 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 ！！

解答

``````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

解答

• first(S) = [a]
• follow(S) = [a, +, *]

4.4.4

解答

1. S -> 0 S 1 | 0 1
• first(S) = [0]
• follow(S) = [1, \$]
2. S -> + S S | * S S | a
• first(S) = [+, *, a]
• follow(S) = [+, *, a, \$]
3. S -> S (S) S | ε
• first(S) = [(, ε]
• followS(S) = [), \$]
4. S -> S + S | S S | (S) | S * | a
• first(S) = [(, a]
• follow(S) = [+, (, ), a, *, \$]
5. S -> (L) | a 以及 L -> L, S | S
• first(S) = [(, a]
• follow(S) = [",", \$]
• first(L) = first(S) = [(, a]
• follow(L) = [), ",", \$]
6. S -> a S b S | b S a S | ε
• first(S) = [a, b, ε]
• follow(S) = [a, b, \$]
7. 下面的布尔表达式对应的文法：

`````` bexpr -> bexpr or bterm | bterm
bterm -> bterm and bfactor | bfactor
bfactor -> not bfactor | (bexpr) | true | false
``````

4.4.5

1. ！ 说明这个递归下降分析器识别输入 aa，aaaa 和 aaaaaaaa，但识别不了 aaaaaa。
2. ！！ 这个递归下降分析器识别什么样的语言？

4.4.6 !

1. 给出一个算法，他的功能是把任何文法转变成一个无 ε 产生式的生成相同语言的文法（唯一可能的例外是空串——没有哪个无 ε 产生式的文法能生成 ε）。提示：首先找出所有可能为空的非终结符号。非终结符号可能为空是指它（可能通过很长的推导）生成 ε。
2. 将你的算法应用于文法 S -> aSbS | bSaS | ε

4.4.7 ！

1. 给出一个算法，它可以把任何文法转变成一个生成相同语言（唯一可能的例外是空串）的、无 ε 产生式、无单产生式的文法。提示：首先消除 ε 产生式，然后找出所有满足下列条件的非终结符号对 A 和 B：存在 A =*=> B。
2. 将你的算法应用于 4.1.2 节的算法。
3. 说明作为 （1） 的一个结果，我们可以把一个文法转换成一个没有环的等价文法。

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

1. 为这个文法构造一个带有错误纠正信息的预测分析表。
2. 给出你的语法分析器在处理下列输入时的行为：
1. if e then s; if e then s end
2. while e do begin s; if e then e; end