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

编译原理实验报告班级：计134班姓名：高晓倩学号：实验一 词法分析程序设计与实现一、实验目的通过编写和调试一个词法分析程序，掌握在对程序设计语言的源程序进行扫描的过程中，将字符流形式的源程序转化为一个由各类单词序列的词法分析方法。二、基本实验内容与要求假定一种高级程序设计语言中的单词主要包括五个关键字begin、end、if、then、else；标识符；无符号常数；六种关系运算符；一个赋值符和四个算术运算符，试构造能识别这些单词的词法分析程序（各类单词的分类码可参见表1）。输入：由符合和不符合所规定的单词类别结构的各类单词组成的源程序文件。输出：把所识别出的每一单词均按形如（CLASS，VALUE）的二元式形式输出，并将结果放到某个文件中。对于标识符和无符号常数，CLASS字段为相应的类别码的助记符；VALUE字段则是该标识符、常数的具体值；对于关键字和运算符，采用一词一类的编码形式，仅需在二元式的CLASS字段上放置相应单词的类别码的助记符，VALUE字段则为“空”。表1 语言中的各类单词符号及其分类码表单词符号类别编码类别码的助记符单词值begin1BEGINend2ENDif3IFthen4THENelse5ELSE标识符6ID字母打头的字母数字串无符号常数7UCON机内二进制表示<8LT<=9LE=10EQ<>11NE>12GT>=13GE:=14IS+15PL-16MI*17MU/18DI要求：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、一般实现方法说明词法分析是编译程序的第一个处理阶段，可以通过两种途径来构造词法分析程序。其一是根据对语言中各类单词的某种描述或定义（如BNF），用手工的方式（例如可用C语言）构造词法分析程序。一般地，可以根据文法或状态转换图构造相应的状态矩阵，该状态矩阵连同控制程序一起便组成了编译器的词法分析程序；也可以根据文法或状态转换图直接编写词法分析程序。构造词法分析程序的另外一种途径是所谓的词法分析程序的自动生成，即首先用正规式对语言中的各类单词符号进行词型描述，并分别指出在识别单词时，词法分析程序所应进行的语义处理工作，然后由一个所谓词法分析程序的构造程序对上述信息进行加工。如美国BELL实验室研制的LEX就是一个被广泛使用的词法分析程序的自动生成工具。总的来说，开发一种新语言时，由于它的单词符号在不停地修改，采用LEX等工具生成的词法分析程序比较易于修改和维护。一旦一种语言确定了，则采用手工编写词法分析程序效率更高。本实验建议使用手工编写的方法。在一个程序设计语言中，一般都含有若干类单词符号，为此可首先为每类单词建立一张状态转换图，然后将这些状态转换图合并成一张统一的状态图，即得到了一个有限自动机，再进行必要的确定化和状态数最小化处理，最后添加当进行状态转移时所需执行的语义动作，就可以据此构造词法分析程序了。2、单词分类与词法分析器的设计为了使词法分析程序结构比较清晰，且尽量避免某些枝节问题的纠缠，我们假定要编译的语言中，全部关键字都是保留字，程序员不得将它们作为源程序中的标识符；在源程序的输入文本中，关键字、标识符、无符号常数之间，若未出现关系和算术运算符以及赋值符，则至少须用一个空白字符加以分隔。作了这些限制以后，就可以把关键字和标识符的识别统一进行处理。即每当开始识别一个单词时，若扫视到的第一个字符为字母，则把后续输入的字母或数字字符依次进行拼接，直至扫视到非字母、数字字符为止，以期获得一个尽可能长的字母数字字符串，然后以此字符串查所谓保留字表（此保留字表要事先造好），若查到此字符串，则取出相应的类别码；反之，则表明该字符串应为一标识符。采用上述策略后，针对表1中的部分单词可以参考图1和程序1，用C语言编写出符合以上几项要求的一个扫描器程序。图1 识别表1所列语言中的部分单词的DFA及相关的语义过程图1中所出现的语义变量及语义函数的含义和功能说明如下：函数GETCHAR：每调用一次，就把扫描指示器当前所指示的源程序字符送入字符变量ch，然后把扫描指示器前推一个字符位置。字符数组TOKEN：用来依次存放一个单词词文中的各个字符。函数CAT：每调用一次，就把当前ch中的字符拼接于TOKEN中所存字符串的右边。函数LOOKUP：每调用一次，就以TOKEN中的字符串查保留字表，若查到，就将相应关键字的类别码赋给整型变量c；否则将c置为零。函数RETRACT：每调用一次，就把扫描指示器回退一个字符位置（即退回多读的那个字符）。函数OUT：一般仅在进入终态时调用此函数，调用的形式为OUT(c，VAL)。其中，实参c为相应单词的类别码助记符；实参VAL为TOKEN（即词文）或为空串。函数OUT的功能是，在送出一个单词的内部表示之后，返回到调用该词法分析程序的那个程序。3、词法分析程序的实现程序1 根据图1编写的扫描器# include <stdio.h># include <ctype.h># include <string.h># 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 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=lookup (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, " "); 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 *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，设置正确的关键字类别码，并返回此类别码的值*/break;n+;return 0; /*单词不是关键字，而是标识符*/4、无符号常数的识别注意按照本实验题目的具体要求，需要将图1和程序1中整常数的识别扩展为无符号常数，以满足题目的要求。关于无符号数的文法可参见图2，表2和程序2。描述无符号数的右线性文法G1<无符号数>如下：无符号数 d余留无符号数无符号数 ·小数部分无符号数 d余留无符号数 d余留无符号数余留无符号数 ·十进小数余留无符号数 E指数部分余留无符号数 d余留无符号数 ·十进小数 E指数部分十进小数 d十进小数十进小数 d小数部分 d十进小数小数部分 d指数部分 d余留整指数指数部分 +整指数指数部分 -整指数指数部分 d整指数 d余留整指数整指数 d余留整指数 d余留整指数余留整指数 d图2所示为上述文法的状态转换图，其中编号0、1、2、6分别代表非终结符号<无符号数>、<余留无符号数>、<十进小数>、<小数部分>、<指数部分>、<整指数>及<余留整指数>。图2 文法G1<无符号数>的状态转换图无符号数识别中的语义处理方法见嵌入了语义动作的状态矩阵表2，其功能是在扫描源程序字符串的过程中，把识别出的字符串形式的无符号数的值，逐步转换为相应的二进制整数（ICON）或二进制浮点数（FCON）的内部形式。（注：考虑能否采用C语言的库函数实现此语义处理工作；是否可将无符号常数这一类单词进一步细分成整型常数和浮点型常数两类单词。）根据表2所示的加入了语义过程说明的识别无符号数的状态矩阵，编写词法分析程序，部分实现代码如程序2所示。表2 包含语义处理过程的识别无符号数的状态矩阵程序2 单词分类码为UCON的无符号数的识别程序四、源程序：五、实验结果：# include <stdio.h># include <stdlib.h># include <ctype.h># include <string.h># include <math.h># 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# define 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 -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 ();char *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，设置正确的关键字类别码，并返回此类别码的值*/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*判断一个单词结束c=lookup (TOKEN);if (c=0) out (ID,TOKEN); else out (c," ");else if(isdigit(ch) /判断是数字？TOKEN0=ch; ch=fgetc(fp); i=1; /EXCUTE (CurrentState,ch);while(isdigit(ch)|ch='.') /if(ch='.')point=1;TOKENi=ch; i+;ch=fgetc(fp);if(ch='E')isE=1;TOKENi=ch;i+;ch=fgetc(fp);if(ch='-')TOKENi=ch;i+;ch=fgetc(fp);TOKENi= '0'if(ch!=' ')fseek(fp,-1,1);/i-;LEX();/if(point=1&&isE=1)out(UCON,TOKEN);/else/out(INT,TOKEN);else switch(ch)case '<': ch=fgetc(fp);if(ch='=')out(LE," ");else if(ch='>') out (NE," ");else fseek (fp,-1,1);out (LT," ");break;case '=': out(EQ, " "); break;case '>': ch=fgetc(fp);if(ch='=')out(GE," ");elsefseek(fp,-1,1);out(GT," ");break;case ':': ch=fgetc(fp);if(ch='=')out(IS," ");elsefseek(fp,-1,1);break;case '+': out(PL," ");break;case '-': out(MI," ");break;case '*': out(MU," ");break;case '/': out(DI," ");break;case ' ':break;default: report_error(); break; void report_error()printf("error");int HandleOtherWord (void) return ClassOther;int HandleError (void) printf ("Error!n"); return 0;int GetChar (int i)int c; c=TOKENi; if(isdigit(c) d=c-'0'return DIGIT; if (c='.') return POINT; if (c='E'|c='e') return POWER; if (c='+') return PLUS; if (c='-') return MINUS; return OTHER;int EXCUTE (int state, int symbol)switch (state)case 0:switch (symbol) case DIGIT: n=0;p=0;e=1;w=d;CurrentState=1;Class=0;break; case POINT: w=0;n=0;p=0;e=1;CurrentState=3;Class=1;break; default: HandleOtherWord( );Class=ClassOther; CurrentState=EndState; break; case 1:switch (symbol) case DIGIT: w=w*10+d;break; /CurrentState=1 case POINT: CurrentState=2;Class=1;break; case POWER: CurrentState=4;Class=1;break; default: ICON=w;CurrentState=EndState; break; case 2:switch (symbol) case DIGIT: n+;w=w*10+d;break; case POWER: CurrentState=4;break; default: FCON=w*pow(10,e*p-n);CurrentState=EndState; break; case 3:switch (symbol) case DIGIT: n+;w=w*10+d;CurrentState=2;break; default: HandleError( );CurrentState=EndState; break; case 4:switch (symbol) case DIGIT: p=p*10+d;CurrentState=6;break; case MINUS: e=-1;CurrentState=5;break; case PLUS: CurrentState=5;break; default: HandleError( );CurrentState=EndState; break; case 5:switch (symbol) case DIGIT: p=p*10+d;CurrentState=6;break; default: HandleError( );CurrentState=EndState; break; case 6:switch (symbol) case DIGIT:p=p*10+d;break; default: FCON=w*pow(10,e*p-n);CurrentState=EndState; break; return CurrentState;int LEX (void)int chh; CurrentState=0; int i=0;while (CurrentState!=EndState)chh=GetChar(i+); EXCUTE (CurrentState,chh); return Class;void out(int c,char *v)char* cl = ""switch (c)case 1: cl = "BEGIN" break;case 2: cl = "END" break;case 3: cl = "IF" break;case 4: cl = "THEN" break;case 5: cl = "ELSE" break;case 6: cl = "ID" break;case 7: cl = "INT" break;case 8: cl = "LT" break;case 9: cl = "LE" break;case 10: cl = "EQ" break;case 11: cl = "NE" break;case 12: cl = "GT" break;case 13: cl = "GE" break;case 14: cl = "IS" break;case 15: cl = "PL" break;case 16: cl = "MI" break;case 17: cl = "MU" break;case 18: cl = "DI" break;case 19: cl = "UCON" break;default: break;if (c=19)if(Class=0)fprintf(fp1,"(%s,%d)n",cl,ICON);else if(Class=1)fprintf(fp1,"(%s,%f)n",cl,FCON);elsefprintf(fp1,"(%s,%s)n",cl,v);void main() char *fname="Myfile.txt" FILE *fp;fp1=fopen("d: result.txt" , "w");if(fp=fopen(fname,"r")=NULL)printf("nSorry, Can't open the file!n");getchar();exit(0); else scanner_example(fp); fclose(fp);fclose(fp1);输入的文件内容： 输出的文件结果：实验二 语法分析程序设计与实现一、实验目的任选一种有代表性的语法分析方法，如算符优先法、递归下降法、LL(1)、SLR(1)、LR(1)等，通过设计、编制、调试实现一个典型的语法分析程序，对实验一所得扫描器提供的单词序列进行语法检查和结构分析，实现并进一步掌握常用的语法分析方法。二、基本实验内容与要求选择对各种常见高级程序设计语言都较为通用的语法结构算术表达式的一个简化子集作为分析对象，根据如下描述其语法结构的BNF定义G2<算术表达式>，任选一种学过的语法分析方法，针对运算对象为无符号常数和变量的四则运算，设计并实现一个语法分析程序。G2<算术表达式>：<算术表达式> <项> | <算术表达式>+<项> | <算术表达式>-<项><项> <因式> | <项>*<因式> | <项>/<因式><因式> <运算对象> | (<算术表达式>)若将语法范畴<算术表达式>、<项>、<因式>和<运算对象>分别用E、T、F和i代表，则G2可写成：G2E：E T | E+T | E-T T F | T*F | T/F F i | (E)输入：由实验一输出的单词串，例如：UCON，PL，UCON，MU，ID ······输出：若输入源程序中的符号串是给定文法的句子，则输出“RIGHT”，并且给出每一步分析过程；若不是句子，即输入串有错误，则输出“ERROR”，并且显示分析至此所得的中间结果，如分析栈、符号栈中的信息等，以及必要的出错说明信息。要求:1、确定语法分析程序的流程图，同时考虑相应的数据结构，编写一个语法分析源程序。2、将词法、语法分析合在一起构成一个完整的程序，并调试成功。3、供测试的例子应包括符合语法规则的语句，及分析程序能判别的若干错例。对于所输入的字符串，不论对错，都应有明确的信息输出。三、实现方法1、一般实现方法说明为了在对源程序的一遍扫描过程中，同时完成词法和语法分析任务，应注意首先修改实验一中的词法分析程序，将它编写为子程序的形式，以便供语法分析程序调用。另外，应加强错误检查，对输入符号串中的词法、语法错误，给出必要的说明信息，尽可能多地、确切地指出错误的位置、原因和性质。例如，在词法分析阶段，对当前正在处理的字符ch，可进一步定义一些与该字符相关的信息row和col，即定义：char ch; /*The current character*/int row; /*The line number position of the current character*/int col; /*The column number position of the current character*/分别表示该字符所在的行和列，这些内容在出错处理时用来提供和源程序位置相关的信息。2、采用具有递归功能的高级语言编制递归下降法的语法分析程序运算对象i可以进一步定义为变量、常数等，例如，此处将i定义为：i<变量> <变量><标识符> <标识符><字母> <字母>A|B|C|X|Y|Z利用扩充的BNF消除G2E中E和T的直接左递归后，采用递归下降法分析上述算术表达式的框图见图3。其中ZC过程为总控程序，被设计成可以分析无穷多个算术表达式，主要完成：通知外界键入算术表达式。控制E过程分析算术表达式。根据分析结果之正误，分别输出不同的信息。E、T和F三个过程分别对应<算术表达式>、<项>和<因式>三个产生式的处理。它们都利用到一个公共过程ADVANCE。ADVANCE过程负责从输入字符串ST中取出下一个字符，并存入SYM中等待分析；然后再剔除ST中的首字符，这可通过挪动字符串指针的办法来实现（而实际上是通过调用词法分析程序来实现ADVANCE功能的）。变量TZ之值标志分析的结果，表明表达式是否有错。图3 递归下降法分析算术表达式的框图(a) ZC过程 (b) E过程 (c) T过程 (d) F过程 (e) ADVANCE过程3、基于预测分析法的语法分析程序参考教材P121例4.3，首先编写无二义性的简单算术表达式的文法(4.1)，并通过消除左递归对其进行改写得到文法(4.1)。然后求出如表4-1所示的各个FIRST集和FOLLOW集。再检查是不是LL(1)文法，并按照LL(1)文法构造如表4-2所示的预测分析表。最后根据预测分析器的工作流程，实现预测分析器的控制程序。4、算符优先分析法的语法分析程序 如程序3所示。其中使用了分析栈stack，用来在分析过程中存放当前句型的某一前缀，一旦句型的最左素短语在栈顶形成，便立即进行归约。程序3 算符优先分析算法#define RIGHT 1#define ERROR 0#define MAXINPUT 300#define MAXSTACK 100#define STARTSYMBOL Sint stackMAXSTACK，aMAXINPUT; /* a is input line */int IsHigherThan (int, int); /* priority detection */int IsLowerThan (int, int); /* priority detection */int IsEqualTo (int, int); /* priority detection */int Reduce (int begin, int end, int len);int IsVt (int); /* determine if stack symbol is in Vt */int parser (void)int i, k, r, NewVn; /* NewVn holds left side of a production */i=0; k=0; /* i, k is index of a and stack separately */stack0= #;doint j;r=ai+;if (IsVt(stackk) j=k; else j=k-1;while (IsHigherThan(stackj,r)int q;do q=stackj;if (IsVt(stackj-1) j-; else j-=2; while(!IsLowerThan(stackj,q);NewVn=Reduce(stackj+1,stackk,k-j);k=j+1; /* reduce the leftmost prime phrase */stackk=NewVn; /* it is stackj+1 stackj+2 stackk */ /*end of while*/if (IsLowerThan(stackj,r) | IsEqualTo(stackj,r)stack+k=r;else return ERROR; while (r!=#);return RIGHT;程序3给出的仅是采用算符优先分析方法的示意性识别算法，还有许多工作要做。如：首先要确定一种合适的数据结构，以便构造所给文法G2<算术表达式>的机内表示。然后，构造该文法的算符优先关系矩阵，在此可根据算术表达式中各算符的优先级和结合性，直接手工构