编 译 原 理实 验 指 导 书编译原理课程组2003年12月概 述一、本课程实践的目的和任务编译原理是一门实践性很强的课程，只有通过实践，才能真正掌握。实际的编译程序是十分复杂的，有时由多达十几万条指令组成。为此，编译原理的实践教学，采用简化编译过程的办法，选择最关键的个环节词法分析、语法分析（包括语义处理、产生无优化的目标指令）、连接调试，进行编程和调试训练。每个环节作为一个实践课题。先分别编程调试，再连接在一起总调。二、实践方法任何一个实用的高级语言，其语法都比较复杂，如选其作为源语言，很难实践全过程。故本实践将定义一个简化的语言 C/C+ 语言的一个子集作为源语言，分个课题，设计调试出它的编译程序。前后贯穿这一条主线进行实践。每次都可利用课余时间编程，利用上机时间进行输入和调试。建议使用 C/C+ 语言或C语言。三、实践报告的规范和要求每个课题完成后写出实践报告。实践报告包括程序设计时考虑的算法和方法；调试过程中出现的问题和解决的措施；打印出程序清单和调试时所用的源程序。四、简化的 C/C+ 语言子集的定义 C/C+ 语言子集的语法定义 C/C+ 子集程序变量说明分程序。变量说明空VAR变量表：INTEGER；变量表变量变量，变量表变量标识符分程序BEGIN语句组END语句组语句语句；语句组语句赋值语句条件语句WHILE语句分程序赋值语句变量：算术表达式条件语句IF布尔表达式THEN语句ELSE语句WHILE语句WHILE布尔表达式DO语句算术表达式项算术表达式项算术表达式项项初等量项初等量项初等量初等量无符号数变量（算术表达式）关系表达式算术表达式关系运算符算术表达式标识符字母标识符字母标识符数字无符号数数字无符号数数字关系运算符| | | | |字母 ABCDEFGHIJKLMNOPQRSTUVWXYZ数字 1234567890实验1 词法分析介绍词法分析程序的编程与调试。（2学时）一、目的与要求）目的通过设计调试词法分析程序，实现从源程序中分出各种单词的方法；加深对课堂教学的理解；提高词法分析方法的实践能力。）要求 掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。 掌握词法分析的实现方法。 上机调试编出的词法分析程序。二、实践题 题目用 C/C+ 语言编写前述 C/C+ 子集的词法分析程序。）主程序设计考虑，（参阅后面给出的程序框架）主程序的说明部分为各种表格和变量安排空间。数组k为关键字表，每个数组元素存放一个关键字。采用定长的方式，较短的关键字后面补空格。P 数组存放分界符。为了简单起见，分界符、算术运算符和关系运算符都放在p表中（学生编程时，应建立算术运算符表和关系运算符表，并且各有类号），合并成一类。id 和ci 数组分别存放标识符和常数。instring 数组为输入源程序的单词缓存。outtoken 记录为输出内部表示缓存。还有一些为造表填表设置的变量。主程序开始后，先以人工方式输入关键字，造k表；再输入分界符等造 p 表。主程序的工作部分设计成便于调试的循环结构。每个循环处理一个单词；接收键盘上送来的一个单词；调用词法分析过程；输出每个单词的内部码。）词法分析过程考虑该过程取名为 lexical，它根据输入单词的第一个字符（有时还需读第二个字符），判断单词类，产生类号：以字符k表示关键字；i表示标识符；c 表示常数；p 表示分界符；s 表示运算符（学生编程时类号分别为1,2,3,4,5）。对于标识符和常数，需分别与标识符表和常数表中已登记的元素相比较，如表中已有该元素，则记录其在表中的位置，如未出现过，将标识符按顺序填入数组 id 中，将常数变为二进制形式存入数组中 ci 中，并记录其在表中的位置。lexical 过程中嵌有两个小过程：一个名为 getchar，其功能为从 instring 中按顺序取出一个字符，并将其指针 pint 加 1 ；另一个名为 error，当出现错误时，调用这个过程，输出错误编号。将词法分析程序设计成独（入口）立一遍扫描源程序的结构。其流程图见图1。图1 词法分析程序流程图 要求 所有识别出的单词都用两个字节的等长表示，称为内部码。第一个字节为 t ，第二个字节为 i 。 t 为单词的种类。关键字的 t=；分界符的 t=；算术运算符的 t=；关系运算符的 t=；无符号数的 t=；标识符的 t=。i 为该单词在各自表中的指针或内部码值。表 1-1 为关键字表；表 1-2 为分界符表；表 1-3 为算术运算符的 i 值；表 1-4 为关系运算符的 i 值。表1-1 关键字表表1-2 分界符表指针1关键字指针1分界符0MAIN0，11；22.3IF 3:=4THEN4(5ELSE5)6FOR7WHILE表1-3 算术运算符表1-4 关系运算符i 值算术运算符i 值关系运算符00H10H+01H21H/04H=05H表1-1只供参考，具体实现时要求参考C语言手册中的保留字表选择一个子集。常数表和标识符表是在编译过程中建立起来的。其 i 值是根据它们在源程序中出现的顺序确定的。常数分析程序、关键字和标识符分析程序、其他单词分析程序请参阅范例自行设计。下面给出部分程序的算法框架，设计实现时需要补充完善。三、程序框架 plexical(input,output); CONST keylen=10; identlen=10; outreco=RECORD char ty; integer point; END; outreco Integer cip,ip,pint,i,j,l,m,errorx; CHAR charl, instring10, p16,2; integer ci 10; string kkeylen, idkeylen; string token; outreco outtoken; OF char;PROCEDURE lexical integer l,m,num; boolean b; PROCEDURE getchar charl:=instring pint ; pint:=pint+1 /*getchar*/ PROCEDURE error putchar(error,errorx) /*error*/ FOR (1:=1; inentlen)token1:= ; getchar; WHILE char1= DO getchar; IF char1 IN a.z THEN /*处理标识符*/ m:=1; WHILE (char1 IN a.z) OR (char1 IN 0.9) DO IF m=identlen THEN tokenm:=char1; m:=m+1 ; getchar /*while*/ pint:=pint-1; 1:=1; b:=false; WHILE (1=keylen) AND (NOT b) DO b:=true; i:=1; WHILE (i=identlen) AND b DO IF k1 i=tokeni THEN i:=i+1 ELSE b:=false; IF NOT b THEN l:=l+1 IF 1=keylen THEN outtoken.ty:=k; outtoken.point:=1 ELSE l:=1; b:=false; WHILE (l=ip) AND (NOT b ) DO b:=true; i:=1; WHILE (iip THEN ip:=ip+1;