编译原理实验指导书.doc

编译原理实验指导书适用专业：计算机应用编制单位：上海电力学院计信学院计算机系编制时间：2005年8月第一章 前言本实验指导书提供的实验情况如下：1、 实验次数：本课程总共开设4次实验。2、 总实验学时：为17学时3、 实验硬件和环境需求：（1） 微机，64M以上内存。（2） 安装了相应的高级语言程序设计系统，如：C语言，或DELPHI，C+，JAVA等高级语言的程序设计环境。（3） 安装了相应的汇编语言程序设计系统。4、 实验所需的基础知识：学生应该熟悉高级程序设计的方法，数据结构和汇编语言课程的相关基本知识。5、 实验分基础部分和提高部分，供学生按照自己的能力和水平选择，基础部分的内容是配合编译原理课程的教学进度设计的，应该是必需完成的实验。第二章 基础实验实验一 词法分析一、实验目的：通过本实验理解词法分析的整个过程，处理对象和处理的结果，了解词法分析在整个编译过程中的作用。二、实验学时：4学时。三、实验内容根据给出的简单语言的词法构成规则和单词集合，编制词法分析程序，要求能将用给定简单语言语言书写的源程序进行词法分析，同时建立相应的符号表文件存放正确的单词。输出分析结果于文件中，包括：（1） 正确的单词符号及其单词种类的序对二元组。（2） 错误单词的信息。若有错误，必须输出错误单词在源程序中的行位置。具体输出形式为：二元组：（单词种类，单词内码值）或三元组：（单词种类，单词内码值，源程序中的行号）单词种类见五。四、实验方法 构造识别单词集的自动机，编写程序实现。五、实验的处理单词集（注：单词种类统一分类如下：）单词符号 单词种类任意变量名 0(1) 2 3 4; 5= 6+ 7* 8 9 10 ， 11 12整型常数 30main 20int 21if 22then 23else 24return 25出错 100六、处理程序例和处理结果例例1：源程序： main()y=x-1; 处理结果：(26,main)(1,()(2,)(3,)(0,y)(6,=)(0,x)(,d-(20,1)(5,;)(4,)例2：源程序main() int a,b; 6：a; b=a-1; 处理结果：(26,main)(1,()(2,)(3, (21,”int”)(0,a)(11,)(0,b)(5,”;”)(30,6)(100,:)(0,a)(5,”;”)(0,b)(6,=)(0,a)(100,-)(30,1)(5,”;”)(4, ) )七、参考代码#include #define n 100main() char an,t; int i,r=1,m=0; a0=n; for(i=1;i+) scanf(%c,&t); if(t!=#) ai=t; r+; else break; for(i=1;i) printf( 9n); else if(c=) printf(=0 & a*i=0 & a*i+1=a & a*i=A & a*i=0 & a*i=a & a*i+1=A & a*i+1=1 & a*i+1=9) *i=*i+1;goto loop1; else printf( 0n); else if(a*i!=( & a*i!=) & a*i!= & a*i!= &a*i!=; & a*i!=+ & a*i!= & a*i!=, & a*i!= & a*i!= & a*i!=# & a*i!=n) *m=1;实验二 语法分析一、实验目的：通过本实验理解语法分析的作用，分析对象、分析的方式和处理的结果，是重点内容。二、实验学时：5学时。三、实验内容根据给出的简单语言的语法构成规则（见五），编制语法分析程序，要求能将词法分析输出的单词文件用给定的语法规则书写的源程序进行语法分析，输出相应的语法分析结果和错误信息。关于错误信息：基础篇不要求错误种类，只需给出出错位置。四、实验方法 可以选用递归下降法，LL(1)分析法，或LR分析法实现。对于后两种方法，要先构造分析表再编写程序实现。 五、文法定义简单的表达式文法如下：E-E+T|E-T|TT-T*F|T/F|FF-(E)|i、六、处理程序例 例1: 正确源程序例：i+(i+i)*i-i例2: 错误源程序例：i+(i+)-i实验三 语义分析一、实验目的：通过本实验理解语义分析的作用，分析对象、分析的方式和处理的结果，为代码生成准备。二、实验学时：4学时。三、实验内容对简单语言的源程序的语法分析结果进行语义分析，进行语义处理，输出分析结果，包括1、 类型不一致错误2、 未定义先引用错误信息。要求：对实验2中的文法，若出现混合类型的运算，对字符与数值型的混合运算视作错误处理；对整型和浮点型混合运算，则将整型转换为浮点型。四、实验方法 可以选用在语法分析的同时进行，或者单独一遍进行。使用符号表辅助实现。五、实验程序例：main()int a,b;float x,y,z;char s1,s2;a=1;b=a+a;c=a+b;x=a*b; y=a+x;s1=a;s2=a+s1;实验四 代码生成一、实验目的：通过本实验了解目标代码生成的过程和方法。二、实验学时：4学时。三、实验内容对简单语言的源程序在语法、语义分析完成后，将符合简单语言定义的源程序生成相应的汇编格式的目标代码，采用asm86的汇编语言指令集。四、实验方法 可以采用如下方法完成: 对表达式文法中的两元运算，使用寄存器ax存放第一元算量和运算结果，然后再存入对应的变量在内存开辟的单元中。每一次的两两运算分解成取第一操作数，运算，存储运算结果三部分的代码，以便统一处理。五、实验程序例：源程序例：main()int x,y,fact;fact:=0;fact:=fact+y;x:=x-1;所生成的目标代码结果形式：data segmentglobal dw 50 dup(?)temporal dw 20 dup(?)Din db 50 dup(?)Dout db 50 dup(?)count db ? data endscode segmentassume cs:code,ds:datamain proc far start: mov ax,data mov ds,axmov bx, offset global mov si , 2 add si , si mov ax , bx+si mov bx , offset temporal mov bx+ 0 , ax mov bx, offset global mov si , 1 add si , si mov ax , bx+si mov bx, offset temporal mov cx, bx+ 0 ADD ax, cx mov bx , offset global mov si , 2 add si , si mov bx+si , ax mov bx, offset global mov si , 0 add si , si mov ax , bx+si mov bx , offset temporal mov bx+ 0 , ax mov ax , 1 mov bx, offset temporal mov cx, bx+ 0 sub cx, ax mov ax, cx mov bx , offset global mov si , 0 add si , si mov bx+si , ax main endpcode ends end start 第三章 设计题该部分的实验题是包含了较多成分的简单语言的设计题，比基础部分具有更复杂的语言规则和处理。需要有一定的程序设计的基础和对编译原理的透彻了解，需要约20学时来完成。完成后的结果是一个可以独立运行的小编译系统。一、 小编译器的实现1、 目的：本设计的目的是将符合以下c语言子集定义的源程序经过词法分析，语法分析,语义分析后生成正确程序的目标代码和可执行的文件运行，否则给出各阶段分析出的错误信息。2、 语法定义：C语言子集的语法图（1）程序main说明部分函数体（2）说明部分变量说明函数说明（3）变量说明；intchar变量，;（4）变量IDNUM（5）函数说明ID(形式参数)（6）形式参数intchar变量，（7）函数体语句序列（8）函数调用ID(实际参数)（9）实际参数变量，（10）表达式项+-项（11）因子IDNUM(表达式) （12）语句函数调用语句序列条件式IF语句序列ELSE语句序列条件式WHILE表达式=变量SCANF(变量)，PRINTF(表达式)，+-ID条件式;表达式ID=FOR（13）语句序列语句；（14）项因子*/因子 （15）条件式 表达式表达式=（16） ID: (字母)(字母|数字)*NUM: (数字)(|数字)*3、 主要步骤与方法(1) 可以采用各阶段分开，也可以通过互相调用的方式进行。(2) 为了便于进行语义分析和生成目标代码，可采用语法树形式存储前面的分析结果。二、 PL/0语言及其编译器的扩充和修改1、 目的：对现存的PL/0编译程序修改或扩充，使它的功能更加齐全，更接近完整的高级语言编译器。2、 内容：要求完成的修改或扩充包括以下：（可以根据学时调整）（1） 注释注释由(*和*)包含，不允许嵌套。（2） 布尔类型的数据布尔类型的BNF为：var_option | var var_decl_listvar_decl_list var_decl | var_decl_list var_declvar_decl ident_list : data_typedata_type integer | boolean这种修改包括：（i） 区别整型与布尔型变量、常量和表达式。（ii） 增加按严格计算的布尔类型运算符and、or和not。这些算符以及己有的运算符的优先级与Pascal语言相同。（iii） 能够使用布尔常量true和false。（iv） 把PL/0语言中的“条件”概念一般化为Pascal语言那样。（v） 布尔表达式可以比较大小：false true（3） 布尔表达式的短路计算增加布尔类型（见（2），除（2）的（ii）外），但对and和or采取短路计算。（4） 数组增加由任何数据类型构造的一维数组。数组的下标限于纯量类型。注意：数组可以由其它的数组来构造，因而必须考虑多维数组的情况。数组的上下界可为任意的纯量常数。数组的定义如下：data_type integer | boolean | array const.const of data_typeconst ident | number语言中允许有数组说明，对数组元素赋值，在表达式中引用数组元素。为了便于解释执行，可能要增加新的PL/0机器操作指令。（5） 参数:语法同Pascal，采用值-结果方式传递（不用var声明）。（6） 函数:语法同Pascal。 （7） else子句和repeat语句（8） for语句，语法参照Pascal或C语言（9） 实现PL/0语言的输入、输出语句。其语法、语义定义和Pascal语言相同。可以仅仅实现一次输入或输出一个值的语句语句参数固定；也可以实现完全和Pascal语言一样，能够接受任意个数参数的输入或输出语句。注意：上面的这些要求有时会互相影响：例如实现布尔类型数据，则数组和参数就应该能处理其相互组合的情况，如布尔型数组（包括多维数组）、布