《编译原理》实验指导书.docx
《《编译原理》实验指导书.docx》由会员分享,可在线阅读,更多相关《《编译原理》实验指导书.docx(39页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、编译原理实验报告班级:计134班姓名:高晓倩学号:实验一 词法分析程序设计与实现一、实验目的通过编写和调试一个词法分析程序,掌握在对程序设计语言的源程序进行扫描的过程中,将字符流形式的源程序转化为一个由各类单词序列的词法分析方法。二、基本实验内容与要求假定一种高级程序设计语言中的单词主要包括五个关键字begin、end、if、then、else;标识符;无符号常数;六种关系运算符;一个赋值符和四个算术运算符,试构造能识别这些单词的词法分析程序(各类单词的分类码可参见表1)。输入:由符合和不符合所规定的单词类别结构的各类单词组成的源程序文件。输出:把所识别出的每一单词均按形如(CLASS,VAL
2、UE)的二元式形式输出,并将结果放到某个文件中。对于标识符和无符号常数,CLASS字段为相应的类别码的助记符;VALUE字段则是该标识符、常数的具体值;对于关键字和运算符,采用一词一类的编码形式,仅需在二元式的CLASS字段上放置相应单词的类别码的助记符,VALUE字段则为“空”。表1 语言中的各类单词符号及其分类码表单词符号类别编码类别码的助记符单词值begin1BEGINend2ENDif3IFthen4THENelse5ELSE标识符6ID字母打头的字母数字串无符号常数7UCON机内二进制表示8LT=9LE=10EQ11NE12GT=13GE:=14IS+15PL-16MI*17MU/1
3、8DI要求:1、上机前完成词法分析程序的程序流图,并选择好相应的数据结构。2、用于测试扫描器的实例源文件中至少应包含两行以上的源代码。3、对于输入的测试用例的源程序文件,词法正确的单词分析结果在输出文件中以二元式形式输出,错误的字符串给出错误提示信息。例如,若输入文件中的内容为:“if myid=1.5E2+100 then x:=y”,则输出文件中的内容应为:(IF, )(ID,myid)(GE, )(UCON,0.015)(PL, )(UCON,100)(THEN, )(ID,x)(IS, )(ID,y)三、实现方法1、一般实现方法说明词法分析是编译程序的第一个处理阶段,可以通过两种途径来
4、构造词法分析程序。其一是根据对语言中各类单词的某种描述或定义(如BNF),用手工的方式(例如可用C语言)构造词法分析程序。一般地,可以根据文法或状态转换图构造相应的状态矩阵,该状态矩阵连同控制程序一起便组成了编译器的词法分析程序;也可以根据文法或状态转换图直接编写词法分析程序。构造词法分析程序的另外一种途径是所谓的词法分析程序的自动生成,即首先用正规式对语言中的各类单词符号进行词型描述,并分别指出在识别单词时,词法分析程序所应进行的语义处理工作,然后由一个所谓词法分析程序的构造程序对上述信息进行加工。如美国BELL实验室研制的LEX就是一个被广泛使用的词法分析程序的自动生成工具。总的来说,开发
5、一种新语言时,由于它的单词符号在不停地修改,采用LEX等工具生成的词法分析程序比较易于修改和维护。一旦一种语言确定了,则采用手工编写词法分析程序效率更高。本实验建议使用手工编写的方法。在一个程序设计语言中,一般都含有若干类单词符号,为此可首先为每类单词建立一张状态转换图,然后将这些状态转换图合并成一张统一的状态图,即得到了一个有限自动机,再进行必要的确定化和状态数最小化处理,最后添加当进行状态转移时所需执行的语义动作,就可以据此构造词法分析程序了。2、单词分类与词法分析器的设计为了使词法分析程序结构比较清晰,且尽量避免某些枝节问题的纠缠,我们假定要编译的语言中,全部关键字都是保留字,程序员不得
6、将它们作为源程序中的标识符;在源程序的输入文本中,关键字、标识符、无符号常数之间,若未出现关系和算术运算符以及赋值符,则至少须用一个空白字符加以分隔。作了这些限制以后,就可以把关键字和标识符的识别统一进行处理。即每当开始识别一个单词时,若扫视到的第一个字符为字母,则把后续输入的字母或数字字符依次进行拼接,直至扫视到非字母、数字字符为止,以期获得一个尽可能长的字母数字字符串,然后以此字符串查所谓保留字表(此保留字表要事先造好),若查到此字符串,则取出相应的类别码;反之,则表明该字符串应为一标识符。采用上述策略后,针对表1中的部分单词可以参考图1和程序1,用C语言编写出符合以上几项要求的一个扫描器
7、程序。图1 识别表1所列语言中的部分单词的DFA及相关的语义过程图1中所出现的语义变量及语义函数的含义和功能说明如下:函数GETCHAR:每调用一次,就把扫描指示器当前所指示的源程序字符送入字符变量ch,然后把扫描指示器前推一个字符位置。字符数组TOKEN:用来依次存放一个单词词文中的各个字符。函数CAT:每调用一次,就把当前ch中的字符拼接于TOKEN中所存字符串的右边。函数LOOKUP:每调用一次,就以TOKEN中的字符串查保留字表,若查到,就将相应关键字的类别码赋给整型变量c;否则将c置为零。函数RETRACT:每调用一次,就把扫描指示器回退一个字符位置(即退回多读的那个字符)。函数OU
8、T:一般仅在进入终态时调用此函数,调用的形式为OUT(c,VAL)。其中,实参c为相应单词的类别码助记符;实参VAL为TOKEN(即词文)或为空串。函数OUT的功能是,在送出一个单词的内部表示之后,返回到调用该词法分析程序的那个程序。3、词法分析程序的实现程序1 根据图1编写的扫描器# include # include # include # define ID 6# define INT 7# define LT 8# define LE 9# define EQ 10# define NE 11# define GT 12# define GE 13char TOKEN20;extern
9、 int lookup (char*);extern void out (int, char*);extern report_error (void);void scanner_example (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=l
10、ookup (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;cas
11、e =: out(EQ, ); break;case : ch=fgetc(fp);if(ch=)out(GE, );elsefseek(fp,-1,1);out(GT, );break;default: report_error( ); break;return; 程序1中所用的若干函数以及主程序有待于具体编写,并需事先建立好保留字表,以备查询。例如:/* 建立保留字表 */#define MAX_KEY_NUMBER 20 /*关键字的数量*/#define KEY_WORD_END “waiting for your expanding” /*关键字结束标记*/char *KeyWord
12、TableMAX_KEY_NUMBER=“begin”,“end”, “if”, “then”, “else”, KEY_WORD_END;/* 查保留字表,判断是否为关键字 */int lookup (char *token)int n=0;while (strcmp(KeyWordTablen, KEY_WORD_END) /*strcmp比较两串是否相同,若相同返回0*/if (!strcmp(KeyWordTablen, token) /*比较token所指向的关键字和保留字表中哪个关键字相符*/return n+1; /*根据单词分类码表I,设置正确的关键字类别码,并返回此类别码的值
13、*/break;n+;return 0; /*单词不是关键字,而是标识符*/4、无符号常数的识别注意按照本实验题目的具体要求,需要将图1和程序1中整常数的识别扩展为无符号常数,以满足题目的要求。关于无符号数的文法可参见图2,表2和程序2。描述无符号数的右线性文法G1如下:无符号数 d余留无符号数无符号数 小数部分无符号数 d余留无符号数 d余留无符号数余留无符号数 十进小数余留无符号数 E指数部分余留无符号数 d余留无符号数 十进小数 E指数部分十进小数 d十进小数十进小数 d小数部分 d十进小数小数部分 d指数部分 d余留整指数指数部分 +整指数指数部分 -整指数指数部分 d整指数 d余留整
14、指数整指数 d余留整指数 d余留整指数余留整指数 d图2所示为上述文法的状态转换图,其中编号0、1、2、6分别代表非终结符号、及。图2 文法G1的状态转换图无符号数识别中的语义处理方法见嵌入了语义动作的状态矩阵表2,其功能是在扫描源程序字符串的过程中,把识别出的字符串形式的无符号数的值,逐步转换为相应的二进制整数(ICON)或二进制浮点数(FCON)的内部形式。(注:考虑能否采用C语言的库函数实现此语义处理工作;是否可将无符号常数这一类单词进一步细分成整型常数和浮点型常数两类单词。)根据表2所示的加入了语义过程说明的识别无符号数的状态矩阵,编写词法分析程序,部分实现代码如程序2所示。表2 包含
15、语义处理过程的识别无符号数的状态矩阵程序2 单词分类码为UCON的无符号数的识别程序四、源程序:五、实验结果:# include # include # include # include # include # define MAX_KEY_NUMBER 20 /*关键字的数量*/# define KEY_WORD_END waiting for your expanding /*关键字结束标记*/# define ID 6# define INT 7# define LT 8# define LE 9# define EQ 10# define NE 11# define GT 12# d
16、efine GE 13# define IS 14# define PL 15# define MI 16# define MU 17# define DI 18# define UCON 19# define DIGIT 1# define POINT 2# define OTHER 3# define POWER 4# define PLUS 5# define MINUS 6/ #define UCON 7 /Suppose the class number of unsigned constant is 7#define ClassOther 200#define EndState -
17、1int w,n,p,e,d;int Class; /Used to indicate class of the wordint ICON;float FCON;static int CurrentState; /Used to present current state, the initial value:0FILE *fp1;int GetChar (void);int EXCUTE (int,int);int LEX (void);char TOKEN20;int lookup (char*);void out (int, char*);void report_error ();cha
18、r *KeyWordTableMAX_KEY_NUMBER=begin,end, if, then, else, KEY_WORD_END;/* 查保留字表,判断是否为关键字 */int lookup (char *token)int n=0;while (strcmp(KeyWordTablen, KEY_WORD_END) /*strcmp比较两串是否相同,若相同返回0*/if (!strcmp(KeyWordTablen, token) /*比较token所指向的关键字和保留字表中哪个关键字相符*/return n+1; /*根据单词分类码表I,设置正确的关键字类别码,并返回此类别码的值
19、*/break;n+;return 0;void scanner_example (FILE *fp)char ch; int point;int isE;int i,c;while(!feof(fp)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= 0;if(ch!= )if(!feof(fp)fseek(fp,-1,1); / retract*判断
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译原理 编译 原理 实验 指导书
限制150内