编译原理第二次小作业

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)文法，得证。

感谢您的耐心阅读


相关内容

  • 编译原理第一次作业

    • <编译原理>课程实验报告 **************************源代码******************************* #include"iostream" #include"string" using namespac ...

  • 程序设计基础记分作业1答案

    • <程序设计基础>记分作业1答案 单选题.(共7道试题,每题3分) 1.系统软件的核心软件是( A ). A.操作系统 B.编译程序 C.汇编程序 D.机器语言 2.世界公认的第一台通用电子数字计算机是美国宾夕法尼亚大学莫尔学院的莫奇利和埃克特领导的科研小组建造的,取名为( B ). A. ...

  • 编译原理大作业(哈工大)

    • 编译原理大作业 论文 学号:1093710411 姓名:周国栋 哈尔滨工业大学软件学院 2012年1月 第一章 综述 第1章 综述 1.1 语法分析概述 语法分析是编译过程的一个逻辑阶段.语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语 1.2 分析方法 语法分析主要有两种:自顶向下的 ...

  • 计算机网络课程作业

    • <计算机网络>课程作业 一． 编程实现mail client 1. 开发环境工具 (1)使用编程工具:Eclipse (2)使用的语言:Java (3)使用的开发包:javamail-1_4版 (4)开发平台:window7 2. 所需要的知识 (1)计算机网络的基本知识 (2)了解SM ...

  • 2016年苏教版八年级信息技术教案

    • 第1课 认识机器人 课时1 教学目的: 1．了解机器人的基本定义和主要分类. 2．了解机器人的主要发展方向. 3．以知识普及为主线,引导学生理解机器人的涵义. 4．采用自主学习.合作学习的方式,了解机器人技术及其发展方向. 5．接受高科技的启发,学人所长,并与同学们一起交流感受. 6．感悟机器人与普 ...

  • 编译原理_语法分析_实验报告

    • <编译原理及实践>结课大作业 <语法分析> 学生姓名 艾力娜·托里干 学 号 所属学院 信息工程学院 专 业 计算机科学与技术 班 级 信息工程学院 一．LL(1)预测语法分析器 [实现目标] 简单的算术表达式的LL(1)语法分析器 实现工具 Microsoft Visual ...

  • 编译原理论文

    • 编译原理心得体会 编译原理是计算机专业的一门重要专业课,旨在介绍编译程序构造的一般原理和基本方法,在计算机本科教学中占有十分重要的地位. 该课程理论性与实践性都很强,我们在学习 是普遍感到内容非常抽象,不易理解,内容多且繁琐,难以完整.全面地掌握编译原理的有关知识,更不用说灵活运用编译原理知识从事相 ...

  • 张瑞编译原理实验报告

    • 黑龙江大学 "编译原理课程设计"读书报告 学院 年级 专业 学号 姓名 报告日期 成绩 软件学院 2012级 软件工程 20122515 张瑞 2014年6月28日 黑龙江大学计算机科学技术学院 黑龙江大学软件学院 概述 "编译原理"课程是计算机专业中一门重要 ...

  • "编译原理"教学实践探究

    • "编译原理"教学实践探究 摘要:教学需要"教"与"学"双方的密切配合.树立"学生为主体.教师为主导"的良好教学关系,是成功教学的关键.本文根据"编译原理"课程的特点,提出应用启发式教学的思想,提高学生 ...

热门内容

标签

悼词范文 事故   书信格式范文50字   学生会个人计划范文   普通公司员工的年终总结报告范文   老师请假条范文   政府红头文件范文   开光仪式讲话稿范文   优秀员工申请范文   销售员工作小结范文   商场开业启事范文   土地处罚决定书范文   预算员实习日记范文   评鉴意见范文   主席调研会议议程