当前位置：文档之家 › 编译原理实验经典指导

编译原理实验经典指导

  • 格式：pdf
  • 大小：346.86 KB
  • 文档页数：13

编译原理实验吴海涛2012-11-16目录相关问题说明 (1)实验题 (2)实验1 词法分析（2课时） (3)实验2 语法分析（2课时） (5)实验3 语义分析（2课时） (7)实验4 代码生成（2课时） (9)参考书目 (11)相关问题说明本课程共有4个实验，本课程中所实现的程序为普通C/C++程序或Java程序，在Windows环境下，属于控制台应用程序。

可以考虑为程序添加图形界面。

提交实验成果：1. 实验成果包括：⏹源程序。

用学号加姓名方式命名项目或源程序所在目录，例如，学号：100511xxx，姓名：某某，目录名就是：100511xxx某某。

只要源程序，不要编译后文件。

⏹实验报告。

2. 实验报告由班干部收齐后在实验后下一次上课时交给我（如果最后一次实验是最后一次课，则另做安排），源程序发我邮箱。

实验成果评价标准：1. 及时提交实验成果，过期再交，不计成绩。

2. 实验成果和他人雷同者，不计成绩。

3. 实验报告采用手写方式，书写格式按照数学与计算机学院要求执行，不按要求办事的，不计成绩。

4. 实验成果不完整的，即缺源程序或实验报告者，不计成绩。

5. 实验报告内容充实，能够真实反映实验情况的，酌情加分。

6. 实验报告字迹工整的，酌情加分。

7. 存在其他加分的可能性。

实验题编译整数四则运算表达式，将整数四则运算表达式翻译为汇编语言代码。

整数四则运算文法：<expr> ::= <expr> + <term> | <expr> - <term> | <term><term> ::= <term> * <factor> | <term> / <factor> | <factor><factor> ::= (<expr>) | num消除左递归得<expr> ::= <term> <expr-rest><expr-rest> ::= + <term> <expr-rest> | - <term> <expr-rest> |ε<term> ::= <factor> <term-rest><term-rest> ::= * <factor> <term-rest> | / <factor> <term-rest> | ε<factor> ::= (<expr>) | num其中<expr>、<expr-rest>、<term>、<term-rest>和<factor>为非终结符，+、-、*、/、(、)、num为终结符。

词法：1．运算符：+ - * /2．界符：( )3．num是非负整数。

4．空白包括空格、换行符和水平制表符。

用来分开运算符、界符和num。

也可以不包括换行符，这时换行符就成为表达式的终结标志。

实验1 词法分析（2课时）实验目的：了解词法分析器的功能和输出形式，掌握词法分析器设计原理和方法。

实验内容：设计并实现整数四则运算表达式的词法分析程序。

实验要求：编写程序，上机调试和测试，纪录调试和测试情况，结合程序进行分析。

实验环境：Visual C++ 6.0或以上版本，Windows 2000或以上版本，汇编工具（在Software子目录下）。

实现要点与提示：需要实现的词法分析程序的功能是，接受一个表达式，输出该表达式中的各类单词符号。

测试词法分析程序时，可以按照一定格式输出各类单词符号。

单词符号的种类和所属类型可定义如下typedef enum Symbol { ERR = -1, END, NUM, PLUS, MINUS, TIMES, SLASH, LPAREN, RPAREN } Symbol;对运算符和界符只需处理种类编码即可，而对num需要处理其对应的具体属性信息。

ERR表示词法分析错，END表示表达式分析结束。

例如1+2*(3+4)所对应的单词符号序列为NUM: 1+NUM: 2*(NUM: 3+NUM: 4)词法分析函数的原型如下Symbol gettoken();实现的具体方法可参考文献[1]中44-46页。

这里不涉及Reserve、InsertId和InsertConst。

在实现过程中可能会用到isdigit、isspace、getchar、ungetc、atoi等函数，使用时注意包含相关头文件。

状态转换图如下实现的具体方法也可以参考文献[3]中的47-53页和79-83页。

如果使用Lex或JFlex工具实现，则可参考文献[3]中86-90页、文献[4][5]以及Lex或JFlex工具的手册。

如果使用JLex或JFlex工具实现，则可参考JLex或JFlex的手册。

实验2 语法分析（2课时）实验目的：理解自上而下分析法的基本思想，理解递归下降分析法的基本思路，掌握构造递归下降子程序的方法。

实验内容：运用递归下降子程序法，实现整数四则运算表达式的语法分析程序。

实验要求：编写程序，上机调试和测试，纪录调试和测试情况，结合程序进行分析。

实验环境：Visual C++ 6.0或以上版本，Windows 2000或以上版本，汇编工具（在Software子目录下）。

实现要点与提示：需要实现的语法分析程序的功能是，接受一个表达式，分析该表达式，并根据输入正确与否给出相应信息。

测试时，如果输入的表达式分析正确，则输出表示分析正确的信息；否则，输出表示分析错误的信息。

下面的叙述主要参考了文献[1]。

分析程序由一组递归过程组成，文法中每个非终结符对应一个过程。

在分析过程中，语法分析程序需要调用实验1所实现的词法分析程序。

几个全局过程和变量：ADVANCE，把输入串指示器IP指向下一个输入符号，即读入一个单字符号。

SYM，IP当前所指的输入符号。

ERROR，出错处理子程序。

每个非终结符有对应的子程序的定义，在分析过程中，当需要从某个非终结符出发进行展开(推导)时，就调用这个非终结符对应的子程序。

例：给定文法G(E)：E→TE'E'→+TE' |εT→FT'T'→*FT' |εF→(E) | i对应的递归子程序为PROCEDURE E; BEGINT;E'END; PROCEDURE E'; IF SYM=‘+’ THEN BEGINADVANCE;T;E'END; PROCEDURE T; BEGINF;T'END;PROCEDURE T';IF SYM=‘*’ THENBEGINADVANCE;F;T'END;PROCEDURE F;IF SYM=‘i’ THEN ADVANCE ELSE IF SYM=‘(’ THEN BEGINADVANCE;E；IF SYM=‘)’ THEN ADVANCEELSE ERROR END ELSE ERROR;主程序为：PROGRAM PARSER; BEGINADVANCE;E;IF SYM <>’#’ THENERROREND.或者对应的递归子程序为：PROCEDURE E;BEGINT;E'END;PROCEDURE T;BEGINF;T'END;PROCEDURE E';IF SYM=‘+’ THENBEGINADVANCE;T;E'END ELSE IF SYM<>‘#’ AND SYM<>’)’ THEN ERROR; PROCEDURE T'; IF SYM=‘*’ THENBEGINADVANCE;F;END ELSE IF SYM<>‘#’ ANDSYM<>’)’AND SYM<>’+’ THEN ERROR; PROCEDURE F;IF SYM=‘i’ THEN ADVANCEELSE IF SYM=‘(’ THENBEGINADVANCE;E;IF SYM=‘)’ THEN ADVANCEELSE ERROREND ELSE ERROR主程序为：PROGRAM PARSER;BEGINADVANCE;EEND;具体实现语法分析程序时，ADVANCE的功能由实验1中的gettoken实现。

程序中可设置一个全局变量nexttoken，与SYM对应，保存调用gettoken时的返回结果。

ERROR的一种简单实现是输出错误提示，然后调用exit，使程序立即终止执行。

实现整数四则运算表达式的语法分析程序时，可在上面例子的基础上修改扩充。

实现的具体方法也可以参考文献[3]中的43-47页和128-129页。

如果使用Yacc或Bison工具实现，则可参考文献[3]中170-177页以及文献[4][5]。

如果使用Java CUP工具实现，则可参考Java CUP的手册。

实验3 语义分析（2课时）实验目的：理解属性文法，理解语法制导翻译的基本思想和方法。

实验内容：设计并实现实现整数四则运算的递归下降翻译器。

实验要求：编写程序，上机调试和测试，纪录调试和测试情况，结合程序进行分析。

实验环境：Visual C++ 6.0或以上版本，Windows 2000或以上版本，汇编工具（在Software子目录下）。

实现要点与提示：需要实现的语义分析程序的功能是，接受一个表达式，分析该表达式，并在分析的过程中建立该表达式的抽象语法树。

由于四则运算表达式的抽象语法树可基本上看作是二叉树，因此中序遍历序列应该和输入的表达式一样——除了没有括号之外。

可输出中序遍历序列检测程序功能是否正确。

如果每个分支节点用一个临时变量标记，则对四则运算表达式的抽象语法树进行后序遍历，可以得到输入表达式所对应的四元式序列（实验4要用到这样的四元式序列）。

例如输入1+2*(3+4)，对应的抽象语法树的中序遍历序列、四元式序列分别为1 +2 *3 + 4和+ 3 4 T1* 2 T1 T2+ 1 T2 T3抽象语法树的一种类型定义为typedef int V alType;typedef struct ASTNode {Symbol sym;V alType val;struct ASTNode * arg1, *arg2;} ASTNode, *AST;创建节点的操作为ASTNode *mknode(Symbol op, ASTNode *arg1, ASTNode *arg2);返回新创建的一个运算节点，标号是op，域arg1和arg2分别指向一棵子树。

合集下载

编译原理实验指导

编译原理实验指导

编译原理实验指导编译原理实验指导⽬录实验1：⽂法的读⼊和输出 (3)实验2：词法分析程序的设计 (5)实验3：LL（1）⽂法构造 (7)实验4：语法分析程序的设计（1） (9)实验5：语法分析程序的设计（2） (11)实验6：逆波兰式的翻译和计算 (15)实验7：语法制导的三地址代码⽣成 (17)实验1 ⽂法的读⼊和输出⼀、实验⽬的熟悉⽂法的结构，了解⽂法在计算机内的表⽰⽅法。

⼆、实验内容1、设计⼀个表⽰⽂法的数据结构；2、从⽂本⽂件中读⼊⽂法，利⽤定义的数据结构存放⽂法，并输出；3、本实验结果还将⽤于实验3。

三、实验要求1、了解⽂法定义的4个部分：G（Vn, Vt, S, P）Vn ⽂法的⾮终结符号集合，在实验中⽤⼤写的英⽂字母表⽰；Vt ⽂法的终结符号集合，在实验中⽤⼩写的英⽂字母表⽰；S 开始符号，在实验中是Vn集合中的⼀个元素；P 产⽣式，分左部和右部，左部为⾮终结符号中的⼀个，右部为终结符号或⾮终结符号组成的字符串，如S->ab|c2、根据⽂法各个部分的性质，设计⼀个合理的数据结构⽤来表⽰⽂法，1）若使⽤C语⾔编写，则⽂法可以设计成结构体形式，结构体中应包含上述的4部分，2）若使⽤C++语⾔编写，则⽂法可以设计成⽂法类形式，类中⾄少含有4个数据成员，分别表⽰上述4个部分⽂法数据结构的具体设计由学⽣根据⾃⼰想法完成，并使⽤C或C++语⾔实现设计的数据结构。

3、利⽤完成的数据结构完成以下功能：1）从⽂本⽂件中读⼊⽂法（⽂法事先应写⼊⽂本⽂件）；2）根据⽂法产⽣式的结构，分析出⽂法的4个部分，分别写⼊定义好的⽂法数据结构的相应部分；3）整理⽂法的结构；4）在计算机屏幕或者⽂本框中输出⽂法，⽂法输出按照⼀个⾮终结符号⼀⾏，开始符号引出的产⽣式写在第⼀⾏，同⼀个⾮终结符号的候选式⽤“|”分隔的⽅式输出。

四、实验环境PC微机DOS操作系统或Windows 操作系统Turbo C 程序集成环境或Visual C++ 程序集成环境五、实验步骤1、根据⽂法定义，设计出⽂法数据结构2、⽤学⽣选择的语⾔，实现⽂法的数据结构3、编写调试⽂法读⼊和输出程序，4、测试程序运⾏效果：从⽂本⽂件中读⼊⼀个⽂法，在屏幕上输出，检查输出结果。

《编译原理》实验指导及报告书(新)课件

《编译原理》实验指导及报告书(新)课件

《编译原理》实验指导及报告书 / 学年第学期姓名：______________学号：______________班级：______________指导教师：______________计算机科学与工程学院2016编译原理实验初步一、实验目的1、熟练掌握使用CODEBLOCK进行C程序编程，提高阅读程序与调试程序的能力。

2、掌握堆栈与队列的应用。

3、掌握C语言中对字符串处理的常见函数与方法。

4、熟悉编程规范，养成对重要的程序段进行必要的注释说明。

二、实验内容与步骤1、下面的程序是对一个简单的算术表达式进行计算求值，并输出表达式的值与该表达式的后缀形式。

该程序在求值与转换后缀形式时使用了2个堆栈和1个队列。

请认真阅读程序和调试，并将程序补充完整。

#include<stdio.h>#include<malloc.h>#include<string.h>#define ERROR 0#define OK 1#define STACK_INT_SIZE 10 /*存储空间初始分配量*/#define Queue_Size 20typedef int ElemType; /*定义元素的类型*/typedef struct{char Qdata[Queue_Size];int front,rear;}SeqQueue;typedef struct{ElemType *base;ElemType *top;int stacksize; /*当前已分配的存储空间*/}SqStack;SqStack OPTR, OPND;SeqQueue SeQ;char PreTab[7][7]={{'>','>','<','<','<','>','>'},{'>','>','<','<','<','>','>'},{'>','>','>','>','<','>','>'},{'>','>','>','>','<','>','>'},{'<','<','<','<','<','=','x'},{'>','>','>','>','x','>','>'},{'<','<','<','<','<','x','='}}; // 该矩阵中，X字符表示不存在优先关系，在分析过程查找到这个值，表示表达式有错。

编译原理实验指导书

编译原理实验指导书

编译原理实验指导书计算机学院实验1 词法分析程序一、实验目的构造simple语言的词法分析程序，程序要求能对输入的字符串流进行词法分析。

在实验的过程中，学会应用单词分析的方法——NFA(非确定有穷自动机)和DFA(确定有穷自动机)，加深对词法分析原理的理解。

二、实验内容编写为任一正则文法(见实验参考(一)simple惯用的词法)构造非确定有穷自动机NFA并转换成确定有穷自动机DFA，并对任给的一个输入串(见实验参考(二)测试用输入串)进行词法分析的程序，程序的输出为单词的序列(见实验参考(三)程序输出形式)。

三、实验参考(一)simple 惯用的词法1. 下面是语言的关键字：Begin if then while do end所有的关键字都是保留字，并且必须是小写。

2. 下面是专用符号：:= + * / < <= <> > >= = ; ( ) #3. 其他单词是标识符(ID)和整型常数(NUM)，通过下列正规式定义：ID = letter(letter| digit)*NUM = digit digit*letter = a |…| z | A |…| Zdigit = 0 |…| 9小写和大写字母是有区别的。

思考：构造实数的正规表达式，力争实现对实数的识别及表示。

4. 空格由空白、换行符和制表符组成。

空格一般用来分隔ID、NUM、运算符和关键字，词法分析阶段通常被忽略。

5. 各种单词符号对应的种别码如下表所示：(二)词法分析程序的功能1. 输入为所给文法的源程序字符串。

2. 程序的输出形式为单词串的输出形式。

所输出的每一单词，均按形如(syn，token和sum)的二元式编码。

其中，syn 为单词种别码；token为存放的单词自身字符串；sum为整型常数。

3．测试源程序片断：begin x:=9; if x>0 then x:=2*x+1/3;end #。

编译原理实验指导书

编译原理实验指导书

陕西理工学院数学与计算机科学学院《编译原理》实验指导班级网络10级指导教师曹阳计算机工程教研室2012年8月25日编译原理实验指导书一、实验的目的《编译原理》是针对计算机专业的学生开设的一门专业基础课程，对引导学生进行科学思维和提高学生解决实际问题的能力有重要的作用。

开设“编译原理实验”的主要目的是让学生加深理解编译原理的基本理论、方法、词法分析、语法分析、中间代码的生成直到最后的代码生成，了解编译器原理，从而提高学生分析问、题解决问题的能力。

通过实验实现以下基本目标：1.深化已学的知识，完成从理论到实践的转化通过实验，进一步加深对编译原理基本思想、原理的了解。

2. 提高分析和解决实际问题的能力实验不仅是编译原理的一次模拟训练，同时通过实验，积累经验，提高分析和解决问题的能力。

3.培养“开拓创新”能力大力提倡和鼓励在程序中使用新方法，新技术。

激发学生实践的积极性与创造性，开拓思路，设计新算法，进行新创意，培养创造性能力。

二、参加实验的学生应具备的条件参加实验的学生应当具备计算机程序设计的一些基础的知识。

即学生应当熟练掌握和使用一种计算机操作系统(windows操作系统等)、一种程序设计语言(vb、vc、c、delphi等)。

三、实验要求实验的要求体现于整个工作的各个阶段中，可根据所选课题的特点而有所侧重，但应达到如下的基本要求：(1) 根据课题任务制定合理、可行的工作计划任务；(2) 制定适当的技术方案；(3) 学生在老师的指导下独立完成设计过程；(4) 撰写实验报告（包括实验内容中各个阶段所要求的文字材料）；(5) 通过实验检查评定；四、实验项目与内容提要五、实验课程考核办法1、该实验课程考核成绩按百分制计算，满分为100分，60分为及格，60分以上者可获取该学分。

2、该实验课考核由三部分组成：实验课前预习（20%），实验操作（60%），实验报告（20%）。

3、各部分成绩由实验指导教师在每个实验项目完成后分别给出，在学期结束后或完成全部实验项目后综合给出该门实验课的成绩。