编译原理第二次小作业

Homework 2

向首兴 2014013421

1. 对于一个文法若消除了左递归、提取了左公因子后是否一定为LL(1)文法？试对下面文法进行改写，并对改写后的文法进行判断。

(1) A → aABe | a

B → Bb | d

答：对该文法消除左递归：

B → Bb | d

=> B → dC

C → bC | ε

对该文法提取左公因子：

A → aABe | a => A → aD

D → ABe | ε

改写后的文法：

A → aD B → dC C → bC | ε D → ABe | ε First(A) = {a}

Follow(A) = {d, #}

First(C) = {b, ε} First(D) = {a, ε}

Follow(C) = {e} Follow(D) = {d, #}

For C: First(bC) ∩ First(ε) = {b} ∩ {ε} = Ø

First(bC) ∩ Follow(C) = {b} ∩ {e} = Ø

For D: First(ABe) ∩ First(ε) = {a} ∩ {ε} = Ø

First(ABe) ∩ Follow(D) = {a} ∩ {d, #} = Ø

由上验证：该文法是LL(1)文法。

(2) S → Ab| Ba

A → aA | a B → a

答：该文法没有左递归；

对该文法提取左公因子：

A → aA | a

=> A → aC

C → A | ε

改写后的文法：

S → Ab| Ba A → aC B → a

First(S) = {a} First(A) = {a} First(B) = {a} First(C) = {a, ε}

Follow(S) = {#} Follow(A) = {b} Follow(B) = {a} Follow(C) = {b}

For S: First(Ab) ∩ First(Ba) = {a} ∩ {a} = {a}

由上验证：该文法不是LL(1)文法。

2. 给定文法G(S):

S → a | ^ | (T) T → T,S | S

写出如下句型的最左归约。 (1) (a,a)

答：(a,a) → (S,a) → (T,a) → (T,S) → (T) → S

(2) (a,(a,a))

答：(a,(a,a)) → (S,(a,a)) → (T,(a,a)) → (T,(S,a)) → (T,(T,a)) → (T,(T,S)) → (T,(T)) → (T,S)

→ (T) → S

(3) (((a,a),^,(a)),a)

答：(((a,a),^,(a)),a)→ (((S,a),^,(a)),a)→ (((T,a),^,(a)),a)→ (((T,S),^,(a)),a)→ (((T),^,(a)),a)

→ ((S,^,(a)),a) → ((T,^,(a)),a) → ((T,S,(a)),a) → ((T,(a)),a) → ((T,(S)),a) → ((T,(T)),a) → ((T,S),a)→ ((T),a) → (S,a) →(T,a) → (T,S) → (T) → S

3. 给定文法G(S):

S → aAb A → BcA|B B → idt|ε

请分别写出下列句型的句柄。 (1) aidtcBcAb 答：树形图如下：

句柄：BcA

(2) aidtccb 答：树形图如下：

句柄：ε (3) ab

答：树形图如下：

黄色部分即为句柄：ε (4) aidtb

答：树形图如下：

句柄：ε或idt

4. 写出如下文法的LR(0)项目集规范族。

(1) S → aS | bS | a

答：设该文法的拓广文法为：

S' → S S → aS | bS | a

如下计算其LR(0)项目集规范族： C := { CLOSURE ({S' → .S})} Repeat

For C 中每一项目集I 和每一文法符号X Doif GO(I, X)非空且不属于C

Then 把GO(I, X)放入C 中

Until C不再增大

计算流程：

C := { CLOSURE ({S' → .S, S →.aS, S → .bS, S → .a})} C := { CLOSURE ({S' → .S, S →.aS, S → .bS, S → .a}),

CLOSURE ({S' → S.}),

CLOSURE ({S →a.S, S → a.,S →.aS, S → .bS, S → .a }), CLOSURE ({S → b.S, S →.aS, S → .bS, S → .a }), CLOSURE ({S → aS.}), CLOSURE ({S → bS.}), }

所以项目集规范族为：

C := { CLOSURE ({S' → .S, S →.aS, S → .bS, S → .a}),

CLOSURE ({S' → S.}),

CLOSURE ({S →a.S, S → a.,S →.aS, S → .bS, S → .a }), CLOSURE ({S → b.S, S →.aS, S → .bS, S → .a }), CLOSURE ({S → aS.}), CLOSURE ({S → bS.}), }

(2) S → (L) | a

L → L,S | S

答：设该文法的拓广文法为：

S' → S S → (L) | a L → L,S | S

计算流程：

C := { CLOSURE ({S' → .S, S →.(L), S → .a}) }

C := { CLOSURE ({S' → .S, S →.(L), S → .a}),

CLOSURE ({S' → S.}),

CLOSURE ({S → (.L), L → .L,S, L → .S, S →.(L), S → .a}), CLOSURE ({S → a.}),

CLOSU RE ({S → L.,S, S → (L.)}), CLOSURE ({L →S.}),

CLOSURE ({S → L,.S, S →.(L), S → .a}), CLOSURE ({S → (L).}), CLOSURE ({S → L,S.}) }

所以项目集规范族为：

C := { CLOSURE ({S' → .S, S →.(L), S → .a}),

CLOSURE ({S' → S.}),

CLOSURE ({S → (.L), L → .L,S, L → .S, S →.(L), S → .a}), CLOSURE ({S → a.}),

CLOSURE ({S → L.,S, S → (L.)}), CLOSURE ({L →S.}),

CLOSURE ({S → L,.S, S →.(L), S → .a}), CLOSURE ({S → (L).}), CLOSURE ({S → L,S.}) }

5. 写出如下文法的LR(0)自动机。

S → SS | (S) | a

答：该文法的拓广文法的LR(0)自动机的状态表如下：

该文法的拓广文法的LR(0)自动机的状态转移表如下：(# - 起始状态，*-终结状态)

6. 试为如下文法构造SLR(1)语法分析表, 要求画出LR(0)自动机。

bexpr → bexpr or bterm | bterm bterm → bterm and bfactor | bfactor bfactor → not bfactor | ( bexpr ) | true | false

说明：bexpr, bterm, 和 bfactor 为非终结符，其它符号为终结符。 答：令S = bexpr, A = bterm, B= bfactor. 该文法的拓广文法为：

(1)S' → S (2)S → S or A (3)S → A (4)A → A and B (5)A → B (6)B → not B (7)B → ( S ) (8)B → true (9)B → false

First(S') = {not, (, true, false} First(S) = {not, (, true, false} First(A) = {not, (, true, false} First(B) = {not, (, true, false}

Follow(S') = {#} Follow(S) = {#, or, )} Follow(A) = {#, or, ), and} Follow(B) = {#, or, ), and}

LR(0)自动机的状态表如下：(# - 起始状态，*-终结状态)

SLR(1)语法分析表如下：

LR(0)自动机如下：(绿色：起始状态；蓝色：指针；黄色：终结状态)

7. 证明文法

S → A a A b | B b B a A → ε B → ε

是LL(1)文法，但不是SLR(1)文法。 答：

First(S) = {a, b}

Follow(S) = {#}

First(A) = {ε} First(B) = {ε}

Follow(A) = {a, b} Follow(B) = {a, b}

For S: First(AaAb)∩First(BbBa) = {a} ∩{b} = Ø 由上验证：该文法是LL(1)文法。 下证该文法不是SLR(1)文法：

该文法的拓广文法为：

(1)S' → S (2)S → A a A b (3)S → B b B a (4)A → ε (5)B → ε

LR(0)自动机如下：(绿色：起始状态；蓝色：指针；黄色：终结状态)

SLR(1)语法分析表如下：

由上分析表中存在表项为多重定义，该文法不是SLR(1)文法。 故该文法是LL(1)文法，但不是SLR(1)文法，得证。

感谢您的耐心阅读

Homework 2

向首兴 2014013421

1. 对于一个文法若消除了左递归、提取了左公因子后是否一定为LL(1)文法？试对下面文法进行改写，并对改写后的文法进行判断。

(1) A → aABe | a

B → Bb | d

答：对该文法消除左递归：

B → Bb | d

=> B → dC

C → bC | ε

对该文法提取左公因子：

A → aABe | a => A → aD

D → ABe | ε

改写后的文法：

A → aD B → dC C → bC | ε D → ABe | ε First(A) = {a}

Follow(A) = {d, #}

First(C) = {b, ε} First(D) = {a, ε}

Follow(C) = {e} Follow(D) = {d, #}

For C: First(bC) ∩ First(ε) = {b} ∩ {ε} = Ø

First(bC) ∩ Follow(C) = {b} ∩ {e} = Ø

For D: First(ABe) ∩ First(ε) = {a} ∩ {ε} = Ø

First(ABe) ∩ Follow(D) = {a} ∩ {d, #} = Ø

由上验证：该文法是LL(1)文法。

(2) S → Ab| Ba

A → aA | a B → a

答：该文法没有左递归；

对该文法提取左公因子：

A → aA | a

=> A → aC

C → A | ε

改写后的文法：

S → Ab| Ba A → aC B → a

First(S) = {a} First(A) = {a} First(B) = {a} First(C) = {a, ε}

Follow(S) = {#} Follow(A) = {b} Follow(B) = {a} Follow(C) = {b}

For S: First(Ab) ∩ First(Ba) = {a} ∩ {a} = {a}

由上验证：该文法不是LL(1)文法。

2. 给定文法G(S):

S → a | ^ | (T) T → T,S | S

写出如下句型的最左归约。 (1) (a,a)

答：(a,a) → (S,a) → (T,a) → (T,S) → (T) → S

(2) (a,(a,a))

答：(a,(a,a)) → (S,(a,a)) → (T,(a,a)) → (T,(S,a)) → (T,(T,a)) → (T,(T,S)) → (T,(T)) → (T,S)

→ (T) → S

(3) (((a,a),^,(a)),a)

答：(((a,a),^,(a)),a)→ (((S,a),^,(a)),a)→ (((T,a),^,(a)),a)→ (((T,S),^,(a)),a)→ (((T),^,(a)),a)

→ ((S,^,(a)),a) → ((T,^,(a)),a) → ((T,S,(a)),a) → ((T,(a)),a) → ((T,(S)),a) → ((T,(T)),a) → ((T,S),a)→ ((T),a) → (S,a) →(T,a) → (T,S) → (T) → S

3. 给定文法G(S):

S → aAb A → BcA|B B → idt|ε

请分别写出下列句型的句柄。 (1) aidtcBcAb 答：树形图如下：

句柄：BcA

(2) aidtccb 答：树形图如下：

句柄：ε (3) ab

答：树形图如下：

黄色部分即为句柄：ε (4) aidtb

答：树形图如下：

句柄：ε或idt

4. 写出如下文法的LR(0)项目集规范族。

(1) S → aS | bS | a

答：设该文法的拓广文法为：

S' → S S → aS | bS | a

如下计算其LR(0)项目集规范族： C := { CLOSURE ({S' → .S})} Repeat

For C 中每一项目集I 和每一文法符号X Doif GO(I, X)非空且不属于C

Then 把GO(I, X)放入C 中

Until C不再增大

计算流程：

C := { CLOSURE ({S' → .S, S →.aS, S → .bS, S → .a})} C := { CLOSURE ({S' → .S, S →.aS, S → .bS, S → .a}),

CLOSURE ({S' → S.}),

CLOSURE ({S →a.S, S → a.,S →.aS, S → .bS, S → .a }), CLOSURE ({S → b.S, S →.aS, S → .bS, S → .a }), CLOSURE ({S → aS.}), CLOSURE ({S → bS.}), }

所以项目集规范族为：

C := { CLOSURE ({S' → .S, S →.aS, S → .bS, S → .a}),

CLOSURE ({S' → S.}),

CLOSURE ({S →a.S, S → a.,S →.aS, S → .bS, S → .a }), CLOSURE ({S → b.S, S →.aS, S → .bS, S → .a }), CLOSURE ({S → aS.}), CLOSURE ({S → bS.}), }

(2) S → (L) | a

L → L,S | S

答：设该文法的拓广文法为：

S' → S S → (L) | a L → L,S | S

计算流程：

C := { CLOSURE ({S' → .S, S →.(L), S → .a}) }

C := { CLOSURE ({S' → .S, S →.(L), S → .a}),

CLOSURE ({S' → S.}),

CLOSURE ({S → (.L), L → .L,S, L → .S, S →.(L), S → .a}), CLOSURE ({S → a.}),

CLOSU RE ({S → L.,S, S → (L.)}), CLOSURE ({L →S.}),

CLOSURE ({S → L,.S, S →.(L), S → .a}), CLOSURE ({S → (L).}), CLOSURE ({S → L,S.}) }

所以项目集规范族为：

C := { CLOSURE ({S' → .S, S →.(L), S → .a}),

CLOSURE ({S' → S.}),

CLOSURE ({S → (.L), L → .L,S, L → .S, S →.(L), S → .a}), CLOSURE ({S → a.}),

CLOSURE ({S → L.,S, S → (L.)}), CLOSURE ({L →S.}),

CLOSURE ({S → L,.S, S →.(L), S → .a}), CLOSURE ({S → (L).}), CLOSURE ({S → L,S.}) }

5. 写出如下文法的LR(0)自动机。

S → SS | (S) | a

答：该文法的拓广文法的LR(0)自动机的状态表如下：

该文法的拓广文法的LR(0)自动机的状态转移表如下：(# - 起始状态，*-终结状态)

6. 试为如下文法构造SLR(1)语法分析表, 要求画出LR(0)自动机。

bexpr → bexpr or bterm | bterm bterm → bterm and bfactor | bfactor bfactor → not bfactor | ( bexpr ) | true | false

说明：bexpr, bterm, 和 bfactor 为非终结符，其它符号为终结符。 答：令S = bexpr, A = bterm, B= bfactor. 该文法的拓广文法为：

(1)S' → S (2)S → S or A (3)S → A (4)A → A and B (5)A → B (6)B → not B (7)B → ( S ) (8)B → true (9)B → false

First(S') = {not, (, true, false} First(S) = {not, (, true, false} First(A) = {not, (, true, false} First(B) = {not, (, true, false}

Follow(S') = {#} Follow(S) = {#, or, )} Follow(A) = {#, or, ), and} Follow(B) = {#, or, ), and}

LR(0)自动机的状态表如下：(# - 起始状态，*-终结状态)

SLR(1)语法分析表如下：

LR(0)自动机如下：(绿色：起始状态；蓝色：指针；黄色：终结状态)

7. 证明文法

S → A a A b | B b B a A → ε B → ε

是LL(1)文法，但不是SLR(1)文法。 答：

First(S) = {a, b}

Follow(S) = {#}

First(A) = {ε} First(B) = {ε}

Follow(A) = {a, b} Follow(B) = {a, b}

For S: First(AaAb)∩First(BbBa) = {a} ∩{b} = Ø 由上验证：该文法是LL(1)文法。 下证该文法不是SLR(1)文法：

该文法的拓广文法为：

(1)S' → S (2)S → A a A b (3)S → B b B a (4)A → ε (5)B → ε

LR(0)自动机如下：(绿色：起始状态；蓝色：指针；黄色：终结状态)

SLR(1)语法分析表如下：

由上分析表中存在表项为多重定义，该文法不是SLR(1)文法。 故该文法是LL(1)文法，但不是SLR(1)文法，得证。

感谢您的耐心阅读