编译原理及实践

《编译原理》课程

实验报告（临时）

题目

专业

班级

学号

姓名

指导教师

华东理工大学软件与管理信息学院

2006年9月22日

一.实验题目

二.实验成员

组长名字写在第一个，每个同学完成的基本任务是什么。

三.实验内容

本学期的编译实验内容是使用编译构造工具实现一个扩充PL0语言的编译器。

扩充PL0语言是在PL0语言的基础上增加对整型一维数组的支持、扩充IF-THEN-ELSE条件语句、增加REPEAT语句、支持带参数的过程和增加注释，如下所示：

（1）整型一维数组，数组的定义格式为：

VAR (:)

 其中上界和下界可以是整数或者常量标识名。

 访问数组元素的时候，数组下标是整型的表达式，包括整数、常量或者变量和它们的组合。例如，假设a是常量，b是整型变量，c是数组，这些访问方式都应该可以使用：c(1)，c(a)，c(b)，c(b+c(1))。

（2）扩充条件语句，格式为：

::= IF THEN [ELSE ]

（3）增加REPEAT语句，格式为：

::= REPEAT UNTIL

(4) 支持带参数（传值参数）的过程，定义和调用形式如下:

::= PROCEDURE [‘(’{, }‘)’] ;

::= CALL [‘(’ {, }‘)’] (5) 注释

单行注释以 { 开始，以 } 结束，注释内容不包括 {和 }.

完整的扩充PL0语言的EBNF范式见实验提供的文档所示。下文所说的PL0语言，如果不加说明，就是特指扩充PL0语言。

本实验实现的PL0语言编译器，输入是PL0源语言程序，输出是一个栈式机的汇编语言(PCODE)程序，然后解释执行。如图1所示。

1. 编译过程概述：

编译过程划分为词法分析，语法分析，语义分析，中间代码生成，代码优化和目标代码生成；

1) 词法分析：是从左到右一个字符一个字符读入源程序，对构成源程序的字符流进行扫描和分析，从而识别出一个个单词；

2) 语法分析：是在词法分析的基础上将单词序列分解成各类语法短语；

3) 语义分析：审查源程序有无语义错误；为代码生成阶段收集信息；

4) 中间代码生成：将程序变成一种内部表示形式；

5) 代码优化：对中间代码进行变换或进行改造；

6) 目标代码生成：把中间代码变换成特定机器上的绝对指令代码或汇编指令代码；

2. 编译过程是一个语言处理程序；它把一个高级语言程序翻译成某个机器的汇编或二进制代码程序。

3. 一个程序设计语言的完整定义应包括语法和语义两个方面；

4. 符号串： 有字母表的符号组成的任何有穷序列；

5. 符号串的方幂：设X是符号串，把X自身连接N次得到的符号串Z。Z为X的方幂。

6. 符号串集合 ， 闭包 ，正闭包。

7. 若一个文法存在某个句子对应两棵不同的语法树；则说这个文法是二义的。

8. 语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子；目前语法分析常用的方法：：自顶向下分析；自底向上分析。

9. 预测分析方法是自顶向下分析：一个预测分析器由三个部分组成

1) 预测分析程序

2) 先进后出栈

3) 预测分析表

10. 确定的有穷自动机（DFA）与不确定的有穷自动机的异同点；

相同点：其中K都是一个有穷集，它的每个元素称为一个状态；

E都是一个有穷字母表；它的每个元素称为一个输入字符；

是一个终态集；

不同点：DFA：f是转换函数，是K*E→K上的映像；

NFA：f是一个从K*E→K的子集的映像；

其实DFA是NFA的特例，对于每个NFA M，存在一个DFA M’使得L(M)=L(M‘)。

“编译原理”教学实践探究

摘要：教学需要“教”与“学”双方的密切配合。树立“学生为主体、教师为主导”的良好教学关系，是成功教学的关键。本文根据“编译原理”课程的特点，提出应用启发式教学的思想，提高学生在学习中的主体地位，多方面增强学生的学习兴趣。文章结合笔者17年的“编译原理”课程教学实践经验，总结了开展启发教学、提高教学质量的一些粗浅策略。

关键词：编译原理；文法；有穷自动机；下推自动机；启发教学；教学策略

教书育人是教师的天职。教学，顾名思义，包含“教”和“学”两个方面。教师需要“教”给学生知识和方法；而学生是学习的主体。我们要取得好的教学效果，首先要激发学生的学习兴趣。

良好的开端是成功的一半。开课伊始就让学生产生学习热情、学习兴趣是非常重要的。两千多年前，孔子曾说过：“知之者不如好之者，好之者不如乐之者。”意思是懂得它的人，不如爱好它的人；爱好它的人，又不如以它为乐的人。爱因斯坦也说过：“兴趣是最好的老师。”学生感兴趣了，教学就成功了一大半。

1.“编译原理”课程概述

“编译原理”课程是计算机科学专业的一门重要核心课程。计算机语言之所以能由单一的机器语言发展到今天的数千种高级语言，是因为有了编译技术。自从20世纪50年代早期第一个编译器出现以来，编译技术成为计算机科学中发展最迅速、最成熟的重要分支。自1966年设立图灵奖以来，程序设计语言、编译理论与方法方面的得奖成果约占总数的1/3。可见，程序语言及其编译的研究在计算机科学中始终处于非常重要的地位。

“编译”是将高级语言描述的程序转换成与之等价的低级语言表达的程序。在编译系统的设计与实现中，用到计算学科的很多基本原理、技术和方法。Alfred

V Aho编写的编译教材作为编译课程方面的经典教材，被奉为“龙书”。他在该书第一章的第一句话提到：“编写编译器的原理和技术具有十分普遍的意义，以至于在每个计算机科学家的研究生涯中，本书中的原理和技术都会反复用到。”北京工业大学的蒋宗礼教授认为，编译课程是计算机专业最为恰当、有效的知识载体之一。

编译原理课程设计

编译器的实现

学 院（系）：

学 生 姓 名：

学 号：

班 级：

同 组 人 ：

目 录

1 课设要求

1.1. 实现原理

1.2. 单词符号及类别表

1.3. 语法结构的概念

2 运行环境

3 整体设计思想

4 详细设计思想

4.1. 词法分析要紧算法

4.2. 语法分析要紧算法

4.3. 语义分析要紧算法

5 流程框图

6 函数相关说明

7 程序用例及运行结果

8 小组分工与合作

9 心得与体会

1课设要求

用C++语言对下述文法和单词表概念的语言做一个编译器，实现了LL（1）词法分析，语法分析，中间代码生成功能。 1.1. 实现原理

编译程序的工作进程一样能够分为五个时期：词法分析、语法分析、语义分析与中间代码产生、优化、目标代码生成。每一个时期在功能上是相对独立的，它一方面从上一个时期获取分析的结果来进行分析，另一方面由将结果传递给下一个时期。由编译程序的五个时期就对应了编译系统的结构。

表

格

管

理

出

错

处

理 单词符号

语法单元

中间代码

中间代码

目标代码 语法分析器

语义分析与中间代码生成器

优化器

目标代码生成器 词法分析器 1.2. 单词符号及类别表

1.3. 语法结构概念

P →{DS}

D →int ID ;{int ID;}

S→if (B) then S [else S ] | while (B) do S | { L } | ID=E

L→SL’

L’ →; L | 

B→T’ {∨T’}

T’ →F’ {∧ F’ }

F’ →ID relop ID | ID