《编译原理实验》实验指导书

广州大学实验课程建设项目编译原理实验实验指导书广州大学计算机科学与教育软件学院2015年3月实验过程要求在面向对象设计与开发的课程实验过程中，要求学生做到：（1）预习实验指导书有关部分，认真做好实验内容的准备，就实验可能出现的情况提前思考和分析。（2）仔细观察上机时出现的各种现象，记录主要情况，做出必要说明和分析。（3）认真书写实验报告。实验报告包括实验目的和要求，实验情况及其分析。对需编程的实验，写出程序设计说明，给出源程序框图和清单。（4）遵守机房纪律，服从辅导教师指挥，爱护实验设备。机器号（5）每次上机应按照实际所用的机器在签到表内的签名栏签到登记。若所用机器编号大于50（签到表最大编号），则应在实际编号-50所得的编号行内账户名栏内签到，并在姓名前后用括号括起来。第一次上机时选择与自己的班序号相同编号的机器。此后每次使用第一次签到所用的机器（如忘记，可参考考勤签到表上的第1次签名），不得自行更改。如确需换机，须征得老师的同意后在第1次上机签名栏内注明变更机号（原机号不得涂抹掉）并按新机号上机，否则后果自负。教师将以登记的（第一次）机号作为学生考勤与课堂纪律巡查的依据。如果登记的机号上无人，则视为该机号登记的学生缺勤。如果签到的机号上没有人，则该签到的学生将被视为作弊而受到惩罚。假设姓名为“张三”，签到格式为：机器号帐户名签名3（53）机器号帐户名签名3（53）若所使用的机器不在课表指定的课室，则还应注明课室号，如下图所示：机器号帐户名签名3（53）机器号帐户名签名3（53）如果登记的机器出现故障，需要换机时，应首先告知指导教师，经确认后可以换到其它没有被占用的机器，并要求在课程的后续上机中使用该机器、签到。若在课中更换了机器，则需在第一次签名处标注新机号，同时在签到表的下部空表中注明用小号字体注明换机原因并通知机房管理员:故障机器号新机器号签名3(键盘坏)38故障机器号新机器号签名3(键盘坏)38（6）考勤员/学委/班长/其他班干部/其他同学在上课前到机房管理室417领取实验日志并填写实验项目、时间等内容后传给各位同学签名，课后放回原处。（7）实验课程不得迟到。未能正常出勤者，所缺实验不补。实验的验收将分为两个部分。第一部分是上机操作，包括检查程序运行和即时提问。第二部分是提交书面的实验报告。此外，针对以前教学中出现的问题，本实验将采用阶段检查方式，每个实验都将应当在规定的时间内完成并检查通过，过期视为未完成该实验，不计成绩。以避免期末集中检查产生的诸多不良问题，希望同学们抓紧时间，合理安排，认真完成。实验报告要求1. 无论是否为团队实验，每个实验都必须以个人为单位单独提交一份实验报告，且在该实验大纲结束的后一周内上系统提交。每迟交一周扣除等级分一级。第十七周结束前必须提交所有实验报告，此后不再接收。2. 实验报告不必列出操作步骤细节，但应体现出独立工作的成果，不得雷同：a) 问题的描述；b) 整体的解决思路、流程或算法；c) 重要的实验结果。该结果应由学生自已独立实验所得，体现出个人所用的实验数据、思路、算法；d) 实验中遇到的困难及解决办法、心得。3. 实验报告中的图、表、核心代码尽量不使用屏幕截图，便于批改、查看，也可减少报告文档的存储空间。4. 实验一和实验二只需给出一个子系统范围内的静态模型和动态模型即可。实验三要求给出完整的系统模型，并在实验一、二的基础上加入设计的内容并全面优化模型。5. 本指导书仅用作实验工具的操作指导，其示例系统为图书馆管理系统。请学生按学号从“Error! Reference source not found.”中选择题目进行实验并提交报告。6. 实验报告电子版的文件夹名称为学生姓名_学号，其实验报告文件名格式为：姓名_学号.doc，其它文件名格式为：姓名_学号_文档标题.doc/mdl/，其中实验报告文件必须包含实验的全部成果，并按打印要求排版。7. 最后一次提交实验报告时，由学委（亦可委托班长等班干部代办）将全班所有同学的实验报告集中起来，以非压缩的格式刻录到一张光盘上。文件夹格式为：目 录实验过程要求2实验报告要求4实验要求6实验内容6实验二：语法分析7实验要求7实验内容7实验三：综合实验8实验要求8实验内容8实验一：词法分析实验目的设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。针对表达各类词语的一组正规表达式，设计一个确定化的最简的有限自动机，对输入的符号串进行单词划分及词类识别。实验要求可多人组队，但要求小组最终实现的系统（词法分析）器是完整的、并且每个成员都完成各自独有的工作。要求词法分析器的输入是字符串（或源程序文本文件），输出是源程序中各单词的字符串、起止位置、词的类别。实验内容将词法分析器分解为以下几个部分：1. 正规表达式的解析：将正规表达式中的符号分解为常量字符、正规表达式标识符和正规表达式运算符，然后基于正规表达式运算将正规表达式分解为更小的正规表达式（通过正规表达式运算符进行串接）。2. 正规表达式到NFA的转换：根据转换规则，基于正规表达式运算，将正规表达式转换为非确定有限自动机，并确定各类词的终止状态。3. NFA的确定化：通过计算各状态的传递闭包，将NFA确定化，并确定各类词的终止状态。4. 最小化：通过子集法，求得最简的确定有限自动机，并确定各类词的终止状态。例如：分析C语言子集的词法1） 关键字 main if else int return void while （都是小写）2） 专用符号 = + * / = = = = != ； ： ， ( )3） 其他模式（正规表达式） STRING:= * 此为Unix正则表达式的写法，意指引号包围的、由非引号字符提组成的字符串。 ID:=letter(letter|digit)* INT:=digit digit* letter:= a|z|A|Z digit:= 0|94）空格由空白、制表符和换行符组成空格一般用来分隔ID、NUM、专用符号和关键字，词法分析阶段通常被忽略。实验二：语法分析实验目的 设计、编制并调试一个语法分析程序，加深对语法分析原理的理解。实验要求可多人组队（不要求与上次实验成员相同），但要求小组最终实现的系统（语法分析）器是完整的、并且每个成员都完成各自独有的工作。要求语法分析器的输入是单词串（含词的字符串形式、在源文件中的起止位置、词的类别），输出是源程序中各句子的单词起止编号、句子的语法树。实验内容鉴于语法分析的方法有多种，要求各组实现不同的语法分析器，其内容按组长的学号（除以4后的余数加1）来确定：1. 递归下降分析器。可分解为：文法输入及解析、消除左递归、提取左公共因子、产生式匹配。2. LL(1)分析器。可分解为：文法输入及解析、分析表构造（含SELECT集求解）、主控程序、语法树展示。3. 算符优先文法分析器。可分解为：文法输入及解析、分析表构造、主控程序、语法树展示。4. LR(1)分析器。可分解为：文法输入及解析、分析表构造（含项目及项目簇集求解）、主控程序、语法树展示。实验三：综合实验实验目的学生运用编译原理的知识在实验技能和方法自行设计实验方案并加以实现。实验要求可多人组队（不要求与上次实验成员相同），但要求小组最终实现的系统（语法分析）器是完整的、并且每个成员都完成各自独有的工作。实验内容完成一个相对完整的编译器，该编译完成对变量类型（整数/浮点数）定义、赋值、四则运算、逻辑运算、跳转与循环控制功能。其输入是源程序（参见“一个四则运算源程序示例”），输出是所有变量的最终值。int i=0;int sum=0;float average=0.0;while (i0）的整数。可自行定义、实现，也可借用第三方的工具（如C/Java的随机数生成函数）。)sum=sum+ rand(999);i=i+1;if(i0) average=sum*1.0/i;printf(“共生成了%d个数字，其和为：%d，平均数为%d”, i, sum, average);elseprintf(“没有生成斜体数字!”);一个四则运算源程序示例