编译原理试验指导

《编译原理试验指导》由会员分享，可在线阅读，更多相关《编译原理试验指导（13页珍藏版）》请在金锄头文库上搜索。

1、编译原理实验指导编译原理实验指导高丽高丽 淮阴工学院计算机工程系淮阴工学院计算机工程系内容简介内容简介编译原理是计算机专业中的一门专业必修课程，在理论上它要求学生掌握有关形式语言和自动机的抽象概念，在技术上要求学生能够熟练地利用各种数据结构进行编程，很具有挑战性。我们希望学生在学习完本课之后，能够对形式语言和其内部结构有一个较深刻的认识。本书包含三个实验：词法分析器，递归下降分析、语义与代码生成。这三个实验构成了编译器的主要组成部分，全部在 VC+6.0 环境下完成。编译原理实验指导2目目 录录实验一 词法分析实验.1实验二 递归下降分析.4实验三 语义及代码生成.8编译原理实验指导1实验一实

2、验一 词法分析实验词法分析实验1、实验目的、实验目的加深对词法分析器的工作过程的理解；加强对词法分析方法的掌握；能够采用一种编程语言实现简单的词法分析程序；能够使用自己编写的分析程序对简单的程序段进行词法分析。2、实验内容、实验内容对源程序进行词法分析：要求识别出关键字、标识符、数字和符号，并以（单词类别，单词值）二元组的形式显示。如 int a；经过词法分析程序后得到的二元组为：intintIDa; 以下为词法分析程序的测试数据main()int a,b;a = 10;b = a + 20;请对以上代码利用词法分析程序分析并得到相应的二元组。3、实验分析、实验分析在本次实验中是对一个简化的

3、c 语言程序进行分析，它的单词符号有： 标识符：字母打头，后接字母数字,识别出的标识符用 ID 标记。 保留字(它是标识符的子集)： if,else,for,while,do,int,write,read，识别出的保留字直接用该保留字标记。 无符号整数：由数字组成，用 NUM 标记。 分界符：+、-、*、/、(、)、 ；、 ，、=、=|ID|ID=| = a|b|z|A|B|Z=1|2|9|0=+|-|*|/|=|(|)|：|，|；|!编译原理实验指导2=|=|！=|=/*=*/identifiernumbersinglelworddoublewordfirstworderror*/lette

4、rdigit+、 ； 、=、!/*非*非=其他letter,digitdigitS图 1 单词符号的状态图根据状态图，分析相应动作就可以构造出词法分析程序的算法流程图，如下图所示，在程序开始时，首先读入一个字符，若为空字符，则继续读，直到读进一个非空字符，读进的字符有如下 6 种情况，要进行不同的处理。（1）字母。继续读，直到遇见空格、分界符、文件尾或非字母数字字符。组合标记符，查保留字表。若为保留字，输出相应单词记号；若不是，输出标记符的单词记号及单词值（标识符） 。（2）数字。继续读，直到遇见空格、或非数字字符出现或文件尾。输出无符号整数的单词记号及数字串。（3）=、!。读入下一个字符，判

5、断是否为双字符分界符，若是，组成双字符分界符，输出相应单词记号及双分界符；若不是，输出单分界符记号。（4）非=、/等与双分界符首字符不同的单分界字符。输出相应单词记号及单分界符。（5）/。读入下一个字符。若不是“*” ，输出/的单词记号；若是“*” ，进行注释处理。词法分析不输出“/*” ，并要跳过整个注释内容直到遇到“*/”为止，然后返回开始状态，继续识别下一个单词符号。（6）非法字符。如果读进的字符不属于上面任意情况，则说明词法分析程序从源程序读入了一个不合法的字符，即该字符不属于程序语言所定义的所有单词符号首字符集合。词法分析程序在遇到不合法字符时要进行错误处理，报告错误信息，跳过这个字

6、符，然后转入开始状态，继续识别下一个单词符号。编译原理实验指导3词法分析读字符结束结束是否为空字是否为字母是否为数字组合标示符是否为保留字查保留字输出标示符组合整数输出整数是否为纯单字符输出单字符读字符是否为,:=2):=|3):=int ID;4):=|5):= |6):= if () else 7):= while () 8):= for(,)9):=write ;10):=read ID;11):=12):=;|;13):= ID=|14):= |(|=| 15):=(+|-) 16):=(*| /) 17):=()|ID|NUM其中，规则 1 和规则 11 中的符号符号、为终结符号，不

7、是元符号，而规则 6、7、8中出现的符号(和)也是终结符号，不是元符号。为了便于理解规则中的每个符号含义，下面对应上面的每条规则，给出中文表达形式：1） :=2） :=|3） :=int ；4） :=|5） :=|6） := if () else 7） :=while() 8） :=for(;) 9） :=write ;10） :=read ;编译原理实验指导511） :=12） :=；|；13） :=|14） :=|(|=|15） :=(+|-)16） :=(*|/)17） :=()|构造递归下降子程序，然后对测试程序进行分析，如果输入的测试程序没有语法错误，则显示语法分析成功；如果有错误，

8、则该语法分析程序遇到错误时，立即停止分析，并报告错误信息。测试程序如下： int a;int b;int c;read a;b=a;(2+a);if (avartablep,datap -int IDnname-defn,t;动作解释：vartablep 指出符号表的最后一个记录的下一个位置，即第一个空白记录位置。每当有一个记录加入符号表，该值加 1；datap 表示已经分配的地址空间，它开始时为 0，每声明一个变量，该值则根据变量类型累加，如整型加 2，实型加 4 等等。name-defn, t 的动作：查询符号表，从 vartablep 所指的前一个位置起往回查直到第一个记录，若没有，将标

9、识符名 n 及类型 1、datap 的值填入符号表 vartablep 所指的位置，然后 vartablep 加 1，datap 根据类型 t 增加;若有，报告错误：变量重复定义。（2）:=IDnLOOKndASSIGN =STOd |（3）:=|GT|LES|=GE|LE|=EQ|!=NOTEQ （4）:=(+ADD |-SUB) （5）:=(*MULT | /DIV) （6）:=()| IDnLOOKndLOADd |NUMiLOADIi（2） 、 （3） 、 （4） 、 （5） 、 （6）规则中的动作符号解释如下：LOOKnd:查符号表 n，给出变量地址 d; 没有，变量没定义ASSIG

10、N：超前读一个符号，如果是=，则表示进入赋值表达式，如果不是=，则选择，然后还要将超前读的这个符号退回。STOd：输出指令代码 STO d, 且 codep+(因产生了指令，所以指令记数加 1)LOADIi：输出指令代码 LOADI i ,且 codep+LOADd ：输出指令代码 LOAD d , 且 codep+GT、ADD 等：输出后的指令代码 GT、ADD 等（7）:=if ()BRFlabel1 BRlabel2 SETlabellabel1 else SETlabellabel2其中动作符号的含义如下编译原理实验指导9BRFlabel1 ：输出 BRF label1,codep+

11、BRlabel2：输出 BR label2,codep+ SETlabellabel1：设置标号 label1 SETlabellabel2：设置标号 label2（8）:=while SETlabellabel1() BRFlabel2 BRlabel1 SETlabellabel2动作解释如下：SETlabellabel1：设置标号 label1BRFlabel2 ：输出 BRF label2,codep+BRlabel1：输出 BR label1,codep+SETlabellabel2：设置标号 label2（9）:=for (;SETlabellabel1BRFlabel2BRlab

12、el3;SETlabellabel4 BRlabel1) SETlabellabel3 BRlabel4SETlabellabel2 动作解释：SETlabellabel1：设置标号 label1BRFlabel2 ：输出 BRF label2,codep+BRlabel3：输出 BR label3,codep+SETlabellabel4：设置标号 label4BRlabel1：输出 BR label1,codep+SETlabellabel3：设置标号 label3BRlabel4：输出 BR label4,codep+SETlabellabel2：设置标号 label2 （10）:=wr

13、ite OUT;动作解释： OUT：输出 OUT（11）:=read IDn LOOKnd INd;动作解释：LOOKnd:查符号表 n，给出变量地址 d; 没有，变量没定义IN：输出 INSTId：输出指令代码 STI d抽象机常用汇编指令如下：LOAD D 将 D 中的内容加载到操作数栈LOADI 常量 将常量压入操作数栈LOAD （D） 将变量地址 D 压入操作数栈STO D 将操作数栈栈顶单元内容存入 DADD 将次栈顶单元与栈顶单元内容相加，和置于栈顶SUB 将栈顶单元减去次栈顶单元内容，差置于栈顶编译原理实验指导10MULT 将次栈顶单元与栈顶单元内容相乘，积置于栈顶DIV 将栈顶

14、单元除次栈顶单元内容，商置于栈顶（分母为栈) BR lab 无条件转移到 lab BRF lab 检查栈顶单元逻辑值，若为假（0）则转移到 labEQ 将栈顶两单元做等于比较，并将结果真或假（1 或 0）置于栈顶NOTEQ 将栈顶两单元做不等于比较，并将结果真或假（1 或 0）置于栈顶GT 次栈顶大于栈顶操作数，则栈顶置 1，否则置 0LES 次栈顶小于栈顶操作数，则栈顶置 1，否则置 0GE 次栈顶大于等于栈顶操作数，则栈顶置 1，否则置 0LE 次栈顶小于等于栈顶操作数，则栈顶置 1，否则置 0AND 将栈顶两单元做逻辑与运算，并将结果真或假（1 或 0）置于栈顶OR 将栈顶两单元做逻辑或运算，并将结果真或假（1 或 0）置于栈顶NOT 将栈顶的逻辑值取反构造语义和代码生成程序，然后对测试程序进行分析测试程序int a;int b;read a;write a;if (a=10) b=1; else b=2;write b;while (a=6) b=3;write b;b=0;for(a=0;a5;a=a+1) b=4;write b;3、实验分析、实验分析在本实验中仍采用递归下降分析法，根据实验二中的语法分析，用上面给出的各语句程序替换语法分析对应的同名函数程序，即可将语法分析改为语义分析和代码生成程序。为了简化起见，在类 C 编译程序中