编译原理实践及应用

附录 部分习题参考答案

第1章参考答案：

1，2，3，4，5，6，7解答：略！

第2章参考答案：

1，2，3：解答：略！ 4. 解答：

A：① B：③ C：① D：②

5. 解答： 用E表示<表达式>，T表示<项>，F表示<因子>，上述文法可以写为：

E → T | E+T T → F | T*F

F → (E) | i 最左推导：

E=>E+T=>E+T+T=>T+T+T=>F+T+T=>i+T+T=>i+F+T=>i+i+T =>i+i+F=>i+i+i

E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i 最右推导：

E=>E+T=>E+F=>E+i=>E+T+i=>E+F+i=>E+i+i=>T+i+i =>F+i+i=>i+i+i

E=>E+T=>E+T*F=>E+T*i=>E+F*i=>E+i*i=>T+i*i=>F+i*i =>i+i*i i+i+i和i+i*i的语法树如下图所示。

i+i+i、i+i*i的语法树

6. 解答：

(1) 终结符号为：{or,and,not,(,),true,false}

非终结符号为：{b

上机内容：词法分析部分（2.1节），其余部分不用做。后文代码供参

考，也可使用自己熟悉的语言另外编写代码。

上机地点：C205教室

上机时间：六月八号（周一）第四大节

序言 .......................................................................................................................................................... 2 第一部分 PL/0语言及其编译器 ........................................................................................................... 3 1. PL/0语言介绍 ................................................................................................................................. 3 1.1 PL/0语言的语法图

序言 .......................................................................................................................................................... 1 第一部分 PL/0语言及其编译器 ........................................................................................................... 2 1. PL/0语言介绍 ................................................................................................................................. 2 1.1 PL/0语言的语法图 ...................................................................................

作业题:

2.1(a,c,d), 2.8(a,c,d), 2.12, 3.3, 3.4, 4.8, 4.12

5.8(a,b,c), 5.12, 6.7, 6.8, 6.13 7.4, 7.15

第二章作业： 2．1 (a) a | a[a-z]*a

(c) [1-9][0-9]* (d) [0-9]*[02468]

2.8（a）

Start a a [b-z] [b-z]

a

正则表达式中丢了单独a的情况的比较多，另外有些同学在有NFA到DFA的转化过程

中，不能够正确的确定最终的状态，造成有两个终结状态的情况。 （c）

Start [0-9]

[1-9]

（d）

问题比较多，建议同学画出DFA图生成的全部过程。

2.12

3．4

a a a b a bb b a a b b b a （c）.rewrite this grammar to establish the correct precedences for the operator.

rexp -> rexp “|” rexp1 | rexp1 rexp1 -> rexp1 r

编译原理试题

一、填空题 1、汇编程序将________翻译成________；编译程序将________翻译成________。 2、编译程序工作工程可以划分为______、______、______、______和______等5个基本阶段，同时还会伴有______和______。

3、对编译程序而言，输入数据是______，输出数据是______。

4、已知文法G[E]：E—>T|E+T|E-F，T－>F|T*F|T/F，F—>(E)|I，(“,”是间隔符号，不是文法中的符号)。该文法的开始符号（识别字符）是______，终结符号集合VT是______，非终结符号结合VN是______，句型T+T*F+i的短语有____________。该文法消除直接左递归，改写后的文法为E－>________，T－>________，F－>________。

5、Chomsky定以来寺中形式语言的文法分别为：________文法（又称________文法）、________文法（又称________文法）、________文法（又称________文法）、________文法（又称________文法）。 6、编译过程中扫描器所完成的任务是从____

编译原理试题

一、填空题 1、汇编程序将________翻译成________；编译程序将________翻译成________。 2、编译程序工作工程可以划分为______、______、______、______和______等5个基本阶段，同时还会伴有______和______。

3、对编译程序而言，输入数据是______，输出数据是______。

4、已知文法G[E]：E—>T|E+T|E-F，T－>F|T*F|T/F，F—>(E)|I，(“,”是间隔符号，不是文法中的符号)。该文法的开始符号（识别字符）是______，终结符号集合VT是______，非终结符号结合VN是______，句型T+T*F+i的短语有____________。该文法消除直接左递归，改写后的文法为E－>________，T－>________，F－>________。

5、Chomsky定以来寺中形式语言的文法分别为：________文法（又称________文法）、________文法（又称________文法）、________文法（又称________文法）、________文法（又称________文法）。 6、编译过程中扫描器所完成的任务是从____

1. 编译程序的功能（P1，图1.1）

1) 高级语言程序（源程序）→编译程序→低级语言程序（目标程序） 2)

2. 编译过程和编译程序的结构（P2）

1) 编译过程划分成了词法分析、语法分析、语义分析、中间代码生成、代码优化、目

标代码生成六个阶段 2) 编译程序结构框图

3)

3. 解释程序（P7）

1) 不需要在运行前把源程序翻译成目标代码，也可以让我们实现在某台机器上运行程

序并生成结果 2)

4. 一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程

序的总体结构图。 （P11，习题2） 答：一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。

词法分析程序：从左到右扫描源程序，识别单词及其相关属性

语法分析程序：分析源程序的结构，判别它是否为相应程序设计语言中的一个合法程序

语义分析程序：审查源程序有无语义错误，为代码生成阶段收集类型信息 中间代码生成程序：将源程序变成一种内部 表示形式。

代码优化程序：对中间代码进行变换或改造，使生成的代码更为高效

目标代码生

编译原理复习题

一、填空题：

1、编译方式与解释方式的根本区别在于（ 是否生成目标代码 ）。

2、对编译程序而言，输入数据是（ 源程序 ），输出结果是（ 目标程序 ）。

3、如果编译程序生成的目标程序是机器代码程序，则源程序的执行分为两大阶段：（编译阶段 ）和（ 运行阶段 ）。

4、如果编译程序生成的目标程序是汇编语言程序，则源程序的执行分成三个阶段：（ 编译阶段）、（汇编阶段）和（运行阶段）。

5、自顶向下语法分析方法会遇到的主要问题有（ 回溯 ）和（ （左递归带来的）无限循环 ）。 6、LL(k)分析法中，第一个L的含义是（ 从左到右进行分析 ），第二个L的含义是（ 每次进行最左推导 ），“k”的含义是（向输入串中查看K个输入符号 ）。

7、LL(1)分析法中，第一个L的含义是（从左到右进行分析 ），第二个L的含义是（每次进行最左推导 ），“1”的含义是（向输入串中查看1个输入符号 ）。

8、自顶向下语法分析方法的基本思想是：从（识别符号）出发，不断建立（ 直接推导 ），试图构造一个推导序列，最终由它推导出与输入符号相同的（ 符号串 ）。

9、自底向上语法分析方法的基本思想是：从待输入的符号串开始，利用文法的规则步步向上进行（直接归约

装 订 线

编译原理试题及答案

一、单项选择题(共10小题，每小题2分，共20分)

1．语言是 A

A．句子的集合 B．产生式的集合 C．符号串的集合 D．句型的集合 2．编译程序前三个阶段完成的工作是 C A．词法分析、语法分析和代码优化 B．代码生成、代码优化和词法分析

C．词法分析、语法分析、语义分析和中间代码生成 D．词法分析、语法分析和代码优化

3．一个句型中称为句柄的是该句型的最左 D A．非终结符号 B．短语 C．句子 D．直接短语 4．下推自动机识别的语言是 C A．0型语言 B．1型语言 C．2型语言 D．3型语言

5．扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即 B

A． 字符 B．单词

编译原理实验

吴海涛 2013-11-1

目 录

相关问题说明................................................................................................................ 1 实验题............................................................................................................................ 2 实验1 词法分析（2课时）........................................................................................ 3 实验2 语法分析（2课时）........................................................................................ 5 实验3 语义分析（2课时）.................................