编译原理实验指导书(2015)

LIAOCHENGUNIVERSITY编译原理实验指导书聊城大学计算机学院2011年3月《编译原理》课程实验指导书I目录《编译原理》课程实验教学大纲.............................1实验一词法分析器的设计.................................3基本信息........................................................3实验目的........................................................3实验内容........................................................3实验扩充........................................................5实验说明........................................................5实验考核方式....................................................5实验辅导........................................................5实验二语法分析器的设计................................10基本信息.......................................................10实验目的.......................................................10实验内容.......................................................10实验说明：.....................................................10实验考核方式：.................................................10实验辅导.......................................................11能力扩展.......................................................19附录...........................................................19《编译原理》课程实验指导书1《编译原理》课程实验教学大纲课程名称：编译原理英文名称：Compileprinciples设置形式：非独立设课课程模块：专业方向课实验课性质：专业实验课程编号：509615课程负责人：姜华大纲主撰人：姜华大纲审核人：左风朝一、学时、学分课程总学时：72实验学时：8课程学分：4二、适用专业及年级计算机科学与技术、软件工程三年级三、课程目标与基本要求《编译原理》课程是计算机专业的核心课程，是培养计算机技术高级人才的必修课程。该课程通过程序设计语言和语言处理软件的理论与技术的教学，培养学生利用计算机语言处理技术进行系统分析和软件设计的能力。编译原理是理论与实践并重的课程，这门实验课要综合运用一、二、三年级所学的多门课程的内容。实验目标与要求；1．学会用高级程序设计语言设计词法分析器。2．学会用高级程序设计语言设计语法分析器。四、主要仪器设备Windows操作系统，编程语言采用C、C++，集成调试环境采用TC或MicrosoftVisualStudio6五、实验项目及教学安排序号实验项目名称实验内容学时要求性质类别所用主要仪器及台套数所在实验室1用C或者C++语言设计一个词法分析器1.确定编译中使用的表格、词法分析器的输出形式、标识符与关键字的区分方法。2.把词法分析器设计成一个独立的过程。4必做设计综合型微机，每人一台。计算机学院实验中心2用C或者C++语言设计一个语法分析器。1.词法分析和语法分析在一起实现。2.把语法分析器设计成一个独的过程。4必做设计综合型微机，每人一台。计算机学院实验中心六、考核方式及成绩评定《编译原理》课程实验指导书2根据学生实验出勤情况、实验态度、实验报告成绩等方面评定实验成绩。实验报告平均成绩（含实验理论）占实验成绩的50%，实验技能平均成绩（含实验态度）占实验成绩的50%。实验成绩占该课程考试总成绩的10％—20%。在机器上将程序及运行结果上传至服务器，由实习教师给出优、良、中、及格、不及格。七、实验教科书、参考书1．实验教科书自编实验指导书。2．实验参考书《编译原理》课程实验指导书3实验一词法分析器的设计基本信息实验课程：编译原理设课形式：非独立课程学分：4实验项目：词法分析器的设计项目类型：设计项目学时：4实验目的1.掌握词法分析的原理；2.熟悉符号表的建立与单词的分类方法；3.掌握词法分析器的设计与调试；实验内容1.分析如表1所定义的PASCAL语言子集的语法，找出所有单词的组成及类别；2.完成单词的分类及其编码；3.完成保留字表、变量名表和常数表的结构设计；4.建立识别单词符号集合的DFA；5.由DFA设计词法分析程序；6.调试并运行词法分析程序；7.实验结果分析。分析结果含义并写出自己的心得体会。表1.PASCAL语言子集的语法定义〈程序〉→〈变量说明〉BEGIN〈语句表〉END.〈变量说明〉→VAR〈变量表〉：〈类型〉；|〈空〉〈变量表〉→〈变量表〉，〈变量〉|〈变量〉〈类型〉→INTEGER〈语句表〉→〈语句表〉；〈语句〉|〈语句〉〈语句〉→〈赋值语句〉|〈条件语句〉|〈WHILE语句〉|〈复合语句〉|〈过程定义〉〈赋值语句〉→〈变量〉∶=〈算术表达式〉〈条件语句〉→IF〈关系表达式〉THEN〈语句〉ELSE〈语句〉〈WHILE语句〉→WHILE〈关系表达式〉DO〈语句〉〈复合语句〉→BEGIN〈语句表〉END《编译原理》课程实验指导书4〈过程定义〉→PROCEDURE〈标识符〉〈参数表〉；BEGIN〈语句表〉END〈参数表〉→(〈标识符表〉)|〈空〉〈标识符表〉→〈标识符表〉，〈标识符〉|〈标识符〉〈算术表达式〉→〈算术表达式〉+〈项〉|〈项〉〈项〉→〈项〉*〈初等量〉|〈初等量〉〈初等量〉→(〈算术表达式〉)|〈变量〉|〈无符号数〉〈关系表达式〉→〈算术表达式〉〈关系符〉〈算术表达式〉〈变量〉→〈标识符〉〈标识符〉→〈标识符〉〈字母〉|〈标识符〉〈数学〉|〈字母〉〈无符号数〉→〈无符号数〉〈数字〉|〈数字〉〈关系符〉→=|＜|＜=|＞|＞=|＜＞〈字母〉→A|B|C|…|X|Y|Z〈数字〉→0|1|2|…|8|9〈空〉→提示：(1)单词的分类。可将所有标识符归为一类；将常数归为另一类；保留字和分隔符则可采取一词一类。(2)符号表的建立。可事先建立一保留字表，以备在识别保留字时进行查询。变量名表及常数表则在词法分析过程中建立。(3)单词串的输出形式。所输出的每一单词，均按形如(CLASS，VALUE)的二元式编码。对于变量标识符和常数，CLASS字段为相应的类别码，VALUE字段则是该标识符、常数在其符号表中登记项的序号(要求在变量名表登记项中存放该标识符的字符串，其最大长度为四个字符；常数表登记项中则存放该整数的二进制形式)。对于保留字和分隔号，由于采用一词一类的编码方式，所以仅需在二元式的CLASS字段上放置相应的单词的类别码，VALUE字段则为“空”。不过，为便于查看由词法分析程序所输出的单词串，也可以在CLASS字段上直接放置单词符号串本身。测试用输入：测试用输入程序为。《编译原理》课程实验指导书5Procedureprogram1(a,b)；BeginVarxyz=50;WhileabdobeginIfxyz=0thenxyz=50;xyz:=xyz-a;a:=a-1;endEnd实验扩充构造语言的词法分析程序，要求识别出变量类型并记录相关信息。实验说明实验环境：WINDOWS下，工具为TurboC2.0或VisualC6.0。实验考核方式1．提交实验报告2．演示程序和答辩（抽查）实验辅导1.词法分析程序的功能词法分析程序又称为扫描器，其功能在于依次扫视字符串形式源程序中的各个字符，逐个识别出其中的单词，并将其转换为内部编码形式的单词符号串作确为输出。通常，可采用二元式（class，value）来表示一个单词符号的内部编码，其中：class为一整数码，用于表示该单词的类别；value则是该单词之值（如变量名在符号表中序号，常数的二进制表示，以及运算符和分隔符的编码等等）。《编译原理》课程实验指导书6概括地说，扫描器在其工作过程中，一般应完成下列的任务：（1）识别出源程序中的各个单词符号，并将其转换为内部编码形式；（2）删除无用的空白字符、回车字符以及其它非实质性字符；（3）删除注释；（4）进行词法检查，报告所发现的错误。此外，视编译工作流程的组织，一些编译程序在进行词法分析时，还要完成将所识别出的标识符登录到符号表的工作。2.实例分析对于表2所列的各类单词符号，词法分析程序可按图1所示的状态转换图来构造。表2一个语言的单词符号及分类码表《编译原理》课程实验指导书7图1识别表2所列语言单词的DFA及相关的语义过程相关变量和子程序说明如下：函数GETCHAR每调用一次，就把扫描指示器当前所指示的源程序字符送入字符变量ch，然后把扫描指示器前推一个字符位置。字符数组TOKEN用来依次存放一个单词词文中的各个字符。函数CAT每调用一次，就把当前ch中的字符拼接于TOKEN中所存字符串的右边。函数LOOKUP每调用一次，就以TOKEN中的字符串查保留字表，若查到，就将相应关键字的类别码赋给整型变量c；否则将c置为零。函数RETRACT每调用一次，就把扫描指示器回退一个字符位置(即退回多读的那个字符)。函数OUT一般仅在进入终态时调用此函数，调用的形式为OUT(c，VAL)。其中，实参c为相应单词的类别码或其助记符；当所识别的单词为标识符和整数时，实参VAL为TOKEN(即词文分别为字母数字串和数字串)，对于其余种类的单词，VAL均为空串。函数OUT的功能是，在送出一个单词的内部表示之后，返回到调用该词法分析程序的那个程序。《编译原理》课程实验指导书8可参考的C语言源程序如下：#includestdio.h#includectype.h#includestring.h#defineID6#defineINT7#defineLT8#defineLE9#defineEQ10#defineNE11#defineGT12#defineGE13charTOKEN［20］；externintlookup(char*);externvoidout(int,char*);externreporterror(void);voidscannerexample(FILE*fp){charch;inti,c;ch=fgetc(fp);if(isalpha(ch))/*itmustbeaidentifer!*/{TOKEN［0］=ch;ch=fgetc(fp);i=1;while(isalnum(ch)){TOKEN［i］=ch;i++；ch=fgetc(fp);}TOKEN［i］=′＼0′fseek(fp,-1,1);/*retract*/c=lookup(TOKEN);if(c==0)out(ID,TOKEN);elseout(c,)；}Elseif(isdigit(ch)){TOKEN［0］=ch;ch=fgetc(fp);i=1;while(isdigit(ch)){TOKEN［i］=ch;i++;ch=fgetc(fp);《编译原理》课程实验指导书9}TOKEN［i］=′＼0′；fseek(fp,-1,1);out(INT,TOKEN);}Elseswitc