编译原理实验指导书2015.doc
《编译原理实验指导书2015.doc》由会员分享,可在线阅读,更多相关《编译原理实验指导书2015.doc(20页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、LIAOCHENG UNIVERSITY编译原理实验指导书聊城大学计算机学院2011年3月目录编译原理课程实验教学大纲1实验一词法分析器的设计3基本信息3实验目的3实验内容3实验扩充5实验说明5实验考核方式5实验辅导5实验二语法分析器的设计10基本信息10实验目的10实验内容10实验说明:10实验考核方式:10实验辅导11能力扩展19附录19编译原理课程实验教学大纲课程名称:编译原理英文名称:Compile principles设置形式:非独立设课课程模块:专业方向课实验课性质:专业实验课程编号:509615课程负责人:姜华大纲主撰人:姜华大纲审核人:左风朝一、学时、学分 课程总学时:72实验
2、学时:8课程学分:4二、适用专业及年级计算机科学与技术、软件工程三年级三、课程目标与基本要求编译原理课程是计算机专业的核心课程,是培养计算机技术高级人才的必修课程。该课程通过程序设计语言和语言处理软件的理论与技术的教学,培养学生利用计算机语言处理技术进行系统分析和软件设计的能力。是理论与实践并重的课程,这门实验课要综合运用一、二、三年级所学的多门课程的内容。实验目标与要求; 1学会用高级程序设计语言设计词法分析器。 2学会用高级程序设计语言设计语法分析器。四、主要仪器设备Windows操作系统,编程语言采用C、C+,集成调试环境采用TC或Microsoft Visual Studio 6五、实
3、验项目及教学安排序号实验项目名称实 验 内 容学时要求性质类别所用主要仪器及台套数所在实验室1用C或者 C+ 语言设计一个词法分析器1.确定编译中使用的表格、词法分析器的输出形式、标识符与关键字的区分方法。2.把词法分析器设计成一个独立的过程。4必做设计综合型微机,每人一台。计算机学院实验中心2用C或者 C+语言设计一个语法分析器。1.词法分析和语法分析在一起实现。2. 把语法分析器设计成一个独的过程。4必做设计综合型微机,每人一台。计算机学院实验中心六、考核方式及成绩评定根据学生实验出勤情况、实验态度、实验报告成绩等方面评定实验成绩。实验报告平均成绩(含实验理论)占实验成绩的50%,实验技能
4、平均成绩(含实验态度)占实验成绩的50%。 实验成绩占该课程考试总成绩的1020%。在机器上将程序及运行结果上传至服务器,由实习教师给出优、良、中、及格、不及格。七、实验教科书、参考书1实验教科书自编实验指导书。 2实验参考书实验一词法分析器的设计基本信息实验课程:编译原理设课形式:非独立课程学分:4实验项目:词法分析器的设计项目类型:设计项目学时:4实验目的1. 掌握词法分析的原理;2. 熟悉符号表的建立与单词的分类方法;3. 掌握词法分析器的设计与调试;实验内容1. 分析如表1所定义的PASCAL语言子集的语法,找出所有单词的组成及类别;2. 完成单词的分类及其编码;3. 完成保留字表、变
5、量名表和常数表的结构设计;4. 建立识别单词符号集合的DFA;5. 由DFA设计词法分析程序;6. 调试并运行词法分析程序;7. 实验结果分析。分析结果含义并写出自己的心得体会。表1.PASCAL语言子集的语法定义程序变量说明BEGIN语句表END.变量说明VAR变量表:类型;|空变量表变量表,变量|变量类型INTEGER语句表语句表;语句|语句语句赋值语句|条件语句|WHILE语句|复合语句|过程定义赋值语句变量=算术表达式条件语句IF关系表达式THEN语句ELSE语句WHILE语句WHILE关系表达式DO语句复合语句BEGIN语句表END过程定义PROCEDURE标识符参数表;BEGIN语
6、句表END参数表(标识符表)|空标识符表标识符表,标识符|标识符算术表达式算术表达式+项|项项项*初等量|初等量初等量(算术表达式)|变量|无符号数关系表达式算术表达式关系符算术表达式变量标识符标识符标识符字母|标识符数学|字母无符号数无符号数数字|数字关系符=|=|=|字母A|B|C|X|Y|Z数字0|1|2|8|9空提示: (1) 单词的分类。 可将所有标识符归为一类;将常数归为另一类;保留字和分隔符则可采取一词一类。 (2) 符号表的建立。 可事先建立一保留字表,以备在识别保留字时进行查询。变量名表及常数表则在词法分析过程中建立。 (3) 单词串的输出形式。 所输出的每一单词,均按形如
7、(CLASS,VALUE)的二元式编码。对于变量标识符和常数,CLASS字段为相应的类别码,VALUE字段则是该标识符、常数在其符号表中登记项的序号 (要求在变量名表登记项中存放该标识符的字符串,其最大长度为四个字符;常数表登记项中则存放该整数的二进制形式)。对于保留字和分隔号,由于采用一词一类的编码方式,所以仅需在二元式的CLASS字段上放置相应的单词的类别码,VALUE字段则为“空”。不过,为便于查看由词法分析程序所输出的单词串,也可以在CLASS字段上直接放置单词符号串本身。 测试用输入:测试用输入程序为。 Procedure program1(a, b);BeginVar xyz=50
8、;While ab do beginIf xyz=0 then xyz=50; xyz:=xyz-a; a:=a-1; endEnd实验扩充构造语言的词法分析程序,要求识别出变量类型并记录相关信息。实验说明实验环境:WINDOWS下,工具为Turbo C2.0或Visual C 6.0。实验考核方式1提交实验报告2演示程序和答辩(抽查)实验辅导1. 词法分析程序的功能词法分析程序又称为扫描器,其功能在于依次扫视字符串形式源程序中的各个字符,逐个识别出其中的单词,并将其转换为内部编码形式的单词符号串作确为输出。通常,可采用二元式(class,value)来表示一个单词符号的内部编码,其中:cla
9、ss为一整数码,用于表示该单词的类别;value则是该单词之值(如变量名在符号表中序号,常数的二进制表示,以及运算符和分隔符的编码等等)。概括地说,扫描器在其工作过程中,一般应完成下列的任务:(1)识别出源程序中的各个单词符号,并将其转换为内部编码形式;(2)删除无用的空白字符、回车字符以及其它非实质性字符;(3)删除注释;(4)进行词法检查,报告所发现的错误。此外,视编译工作流程的组织,一些编译程序在进行词法分析时,还要完成将所识别出的标识符登录到符号表的工作。 2. 实例分析对于表2所列的各类单词符号,词法分析程序可按图1所示的状态转换图来构造。表2 一个语言的单词符号及分类码表图1识别表
10、2所列语言单词的DFA及相关的语义过程相关变量和子程序说明如下:u 函数GETCHAR每调用一次,就把扫描指示器当前所指示的源程序字符送入字符变量ch,然后把扫描指示器前推一个字符位置。u 字符数组TOKEN用来依次存放一个单词词文中的各个字符。u 函数CAT每调用一次,就把当前ch中的字符拼接于TOKEN中所存字符串的右边。u 函数LOOKUP每调用一次,就以TOKEN中的字符串查保留字表,若查到,就将相应关键字的类别码赋给整型变量c;否则将c置为零。u 函数RETRACT每调用一次,就把扫描指示器回退一个字符位置 (即退回多读的那个字符)。u 函数OUT一般仅在进入终态时调用此函数,调用的
11、形式为OUT (c,VAL)。其中,实参c为相应单词的类别码或其助记符;当所识别的单词为标识符和整数时,实参VAL为TOKEN (即词文分别为字母数字串和数字串),对于其余种类的单词,VAL均为空串。函数OUT的功能是,在送出一个单词的内部表示之后,返回到调用该词法分析程序的那个程序。可参考的C语言源程序如下:# include # include # include # define ID6# define INT7# define LT8# define LE9# define EQ10# define NE11# define GT12# define GE13char TOKEN20;
12、extern int lookup (char*);extern void out (int, char*);extern reporterror (void);void scannerexample (FILE*fp)char ch;int i, c;ch=fgetc (fp);if (isalpha (ch)/*it must be a identifer!*/TOKEN0=ch;ch=fgetc (fp);i=1;while (isalnum (ch)TOKENi=ch;i+;ch=fgetc (fp);TOKENi=0fseek(fp,-1,1);/* retract*/c=looku
13、p (TOKEN);if (c=0) out (ID,TOKEN);else out (c, );Elseif(isdigit(ch)TOKEN0=ch;ch=fgetc(fp);i=1;while(isdigit(ch)TOKENi=ch;i+;ch=fgetc(fp);TOKENi=0;fseek(fp,-1,1);out(INT,TOKEN);Elseswitch(ch)case :ch=fgetc(fp);if(ch=)out(LE, );else if(ch=) out (NE, );elsefseek (fp,-1,1);out (LT, );break;case =:out(EQ
14、, );break;case :ch=fgetc(fp);if(ch=)out(GE, );elsefseek(fp,-1,1);out(GT, );break;default: reporterror( );break;return;实验二语法分析器的设计基本信息实验课程:编译原理设课形式:非独立课程学分:4实验项目:语法分析器的设计项目类型:设计项目学时:4实验目的1. 掌握自上而下语法分析的基本思想;2. 掌握利用预测分析法进行语法分析的原理和过程;3. 熟悉文法的机内表示;4. 掌握语法分析器的设计与调试,提高编程能力、动手能力以及独立分析问题、解决问题的能力和综合运用所学知识的能力。
15、实验内容1. 输入任意文法,改写文法使其成为LL(1)文法。 2. 构造文法的预测分析表;3. 设计堆栈和预测分析表的机内表示;4. 设计并书写语法分析程序;5. 调试并运行语法分析程序;6. 实验结果分析l 分析程序中文法存储所采用的数据结构l 分析结果并写出自己的心得体会提示: 对于所选定的分析方法,如有需要,应选择一种合适的数据结构,以构造所给文法的机内表示。 实验说明:实验环境:WINDOWS下,工具为Turbo C2.0或Visual C 6.0。实验考核方式:1. 提交实验报告2. 演示程序和答辩(抽查)实验预习实验辅导1. 设计原理及算法描述 所谓LL(1)分析法,就是指从左到右
16、扫描输入串(源程序),同时采用最左推导,且对每次直接推导只需向前看一个输入符号,便可确定当前所应当选择的规则。实现LL(1)分析的程序又称为LL(1)分析程序或LL1(1)分析器。 一个文法要能进行LL(1)分析,那么这个文法应该满足:无二义性,无左递归,无左公因子。当文法满足条件后,再分别构造文法每个非终结符的FIRST和FOLLOW集合,然后根据FIRST和FOLLOW集合构造LL(1)分析表,最后利用分析表,根据LL(1)语法分析构造一个分析器。2. 分析过程LL(1)的语法分析程序包含了三个部分,总控程序,预测分析表函数,先进先出的语法分析栈,本程序也是采用了同样的方法进行语法分析,该
17、程序是采用了C语言来编写,其逻辑结构图如图2所示。 图2 LL(1)语法分析逻辑结构图 LL(1)预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号a做哪种过程的。对于任何(X,a)总控程序每次都执行下述三种可能的动作之一: ()若X = a =#,则宣布分析成功,停止分析过程。 ()若X = a #,则把X从STACK栈顶弹出,让a指向下一个输入符号。 ()若X是一个非终结符,则查看预测分析表M。若MA,a中存放着关于X的一个产生式,那么,首先把X弹出STACK栈顶,然后,把产生式的右部符号串按反序一一弹出STACK栈(若右部符号为,则不推什么东西进STACK栈)。若
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 实验 指导书 2015
限制150内