编译原理课程实践环节.pdf

《编译原理》课程实践环节

如果你对本课程实践环节的题目、要求或内容等方面的设计有任何意见或建议，欢迎联系中山大学计算机
科学系李文军老师（[e-mail]）。

实验题目：程序设计语言SP的自动排版工具

在正式开始你的实验之前，请务必花足够时间仔细阅读完本文档关于实验的描述与约定！

实验目的

本实验是一个基于编译原理课程核心教学内容的综合性实验，利用一门简单程序设计语言的
处理工具设计与实现，帮助学生通过实践深入理解和牢固掌握编译技术中词法分析、语法分
析、语法制导翻译等重要环节。

本实验的主要目标包括：

1、掌握词法分析器的工作原理与构造方法，并能够推广到对文本的串匹配搜索等其他同类
型应用。

2、掌握词法分析器自动生成工具lex或类似工具的工作原理与使用方法，学习如何编写一
个lex源文件以解决词法分析或模式匹配问题，初步体会软件自动化的基本思路。

3、掌握递归下降的预测分析方法以及语法制导的翻译技术，学习如何根据BNF语法定义和
应用需求设计一个翻译模式，并利用高级程序设计语言的递归机制实现一个翻译模式。

4、掌握语法分析器自动生成工具yacc或类似工具的工作原理与使用方法，学习如何编写一
个yacc源文件以解决语法分析及语法制导翻译问题，进一步加深体会软件自动化的基本
思路。

5、通过加强设计方面的讨论与编程风格的实践，提高对面向对象设计的认识，养成良好的
编程习惯与规范，并学会多个工程文档的组织与提交。
李文军：《编译原理》课程实践环节

程序设计语言SP

SP是一门支持简单算术功能的玩具型程序设计语言，易于分析和实现，适合作为语言实现
初学者的处理对象。

SP语言是一门大小写无关语言，其程序中仅允许使用33个变量，其名字分别为X、Y、Z、
X0、…、X9、Y0、…、Y9、Z0、…、Z9；所有变量和表达式的类型均为整数类型。SP语
言仅支持四类语句，其语义描述如下：

READvar从控制台读入一个int类型的值，并保存在变量var中

WRITEexpr将表达式expr的值输出到控制台

LETvar=expr将变量var的当前值设置为表达式expr的值

GOTOlabel[IFexpr]跳转到指定的行；如果指定表达式expr，则仅当expr≧0
时才跳转

SP语言语法定义的完整BNF描述如下：
<program>::=<progline>|<program><progline>
<progline>::=<number>:<stmt>;|<stmt>;
<stmt>::=READ<var_id>|
WRITE<expr>|
LET<var_id>=<expr>|
GOTO<number>|
GOTO<number>IF<expr>
<expr>::=<term>|<term>+<term>|<term>-<term>
<term>::=<factor>|<factor>*<factor>|<factor>/<factor>
<factor>::=(<expr>)|<number>|<var_id>
<var_id>::=<letter>|<letter><digit>
<number>::=<digit>|<number><digit>
<letter>::=a|b|...|z|A|B|...|Z
<digit>::=0|1|...|9

例如，以下SP源程序可用于计算两个非负整数X和Y的最大公约数：
READX;READY;
100:GOTO200IFY-X;
LETX=X-Y;
GOTO100;
200:GOTO300IFX-Y;
LETY=Y-X;
GOTO100;
300:WRITEX;

-2-
李文军：《编译原理》课程实践环节

实验一：熟悉BNF定义

SP语言的BNF定义给出了该语言语法方面的形式化规格说明。仔细阅读SP语言的BNF定
义，并完成以下实验内容。

实验步骤

步骤1.1、编写SP源程序

遵循SP语言的BNF定义，编写两个语法正确的SP源程序。要求在这两个源程序中，用到
SP语言的所有语法构造，即你编写的两个源程序加在一起覆盖了SP语言提供的语句、表达
式、变量、数值等各种构造。如果有可能，你编写的SP源程序最好是有其实际意义的，譬
如一个求阶乘的程序或一个求最小公因子的程序等。注意，这里仅要求你编写语法正确的SP
源程序，并未强制要求这些源程序是语义正确的。

然后，参考SP语言的BNF定义，编写两个含有语法错误的SP源程序。要求在这两个源程
序中，既包含一些词法错误（例如：不合法的标识符、不合法的常量等），也包含一些语法
错误（例如：括号不匹配、表达式缺少运算符、表达式缺少操作数、命令缺少关键字等）。

这些语法正确的和语