编译原理实验报告 (2).doc

编译原理实验报告实验一 词法分析程序实现一、实验目的与要求通过编写和调试一个词法分析程序，掌握在对程序设计语言的源程序进行扫描的过程中，将字符形式的源程序流转化为一个由各类单词符号组成的流的词法分析方法。二、实验设计语言中具有的单词包括五个关键字begin、end、if、then、else；标识符；整型常数；六种关系运算符；一个赋值符和四个算术运算符。参考实现方法简述如下。单词的分类：构造上述语言中的各类单词符号及其分类码表。表I 语言中的各类单词符号及其分类码表单词符号类别编码类别码的助记符单词值begin1BEGINend2ENDif3IFthen4THENelse5ELSE标识符6ID字母打头的字母数字串整常数7INT数字串8LT=9LE=10EQ11NE12GT=13GE:=14IS+15PL-16MI*17MU/18DI识别表I所列语言中的部分单词的DFA及相关的语义过程将表I单词集中的整常数改为无符号常数，无符号常数的单词分类码助记符：UCON描述无符号数的正规文法和状态转换图：无符号数的右线性文法G1如下：无符号数 d余留无符号数无符号数 小数部分无符号数 d余留无符号数 d余留无符号数余留无符号数 十进小数余留无符号数 E指数部分余留无符号数 d余留无符号数 十进小数 E指数部分十进小数 d十进小数十进小数 d小数部分 d十进小数小数部分 d指数部分 d余留整指数指数部分 +整指数指数部分 -整指数指数部分 d整指数 d余留整指数整指数 d余留整指数 d余留整指数余留整指数 d图所示为上述文法的状态转换图，其中编号0、1、2、6分别代表非终结符号、及。文法G1的状态转换图包含语义处理过程的识别无符号数的状态矩阵3、 源程序/扫描器/#include#include#include#include#include#define BEGIN 1#define END 2#define IF 3#define THEN 4#define ELSE 5#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 PL 14#define MI 15#define MU 16#define DI 17#define TOKEN_SIZE 64#define TAB_SIZE 5char TOKENTOKEN_SIZE;extern int lookup(char *);extern void out(int ,char*);extern void report_error();int GetChar(void);int EXCUTE(int,int);int LEX(void);#define LETTER 0#define DIGIT 1#define POINT 2#define OTHER 3#define POWER 4#define PLUS 5#define MINUS 6#define ClassNo 100 #define ClassOther 200#define EndState -1int w,n,p,e,d;int Class;int ICON;float FCON;static int CurrentState;char ch;/信息表保存5个关键字typedef struct int ad; char id6;info_ele;info_ele TabTAB_SIZE=1,begin,2,end,3,if,4,then,5,else;void scanner_example(FILE *fp) /扫描器函数 int i,c; ch=fgetc(fp); if(isalpha(ch) /是否为字母 TOKEN0=ch; i=1; ch=fgetc(fp); while(isalnum(ch) /是否为字母或数字 TOKENi=ch; i+; ch=fgetc(fp); fseek(fp,-1,1); TOKENi=0; c=lookup(TOKEN); /调用输出函数out() if (c=0) out(ID,TOKEN); else out(c,TOKEN); else if(isdigit(ch) /判断是否为整数 TOKEN0=ch; i=1; ch=fgetc(fp); while(isdigit(ch)|ch=.|ch=e|ch=-) TOKENi=ch; i+; ch=fgetc(fp); fseek(fp,-1,1); TOKENi=0; out(INT,TOKEN);LEX(); else /判断运算符 if(ch= |ch=n); /遇见空格、回车继续 else switch(ch) case =:out(EQ,=); break; case :ch=fgetc(fp); if(ch=)out(GE,=); else fseek(fp,-1,1); out(GT,); break; case:ch=fgetc(fp); if(ch=) out(LE,) out(NE,); else fseek(fp,-1,1); out(LT,); break; case +:out(PL,+);break; case -:out(MI,-);break; case *:out(MU,*);break; case /:out(DI,/);break; default: report_error(); break; int lookup(char p) /查找是否为关键字 int i=0; for(i;iTAB_SIZE;i+) if(!strcmp(Tabi.id,p)return (Tabi.ad); return 0; void out(int a,char *p) /输出结果 switch(a) case BEGIN: printf(BEGIN,%s)n,p);break; case END : printf(END,%s)n,p); break; case IF: printf(IF,%s)n,p);break; case THEN: printf(THEN,%s)n,p);break; case ELSE: printf(ELSE,%s)n,p);break; case ID: printf(ID,%s)n,p);break; case INT:printf(UCON,%s)n,p);break; case LT:printf(LT,%s)n,p);break; case LE:printf(LE,%s)n,p);break; case EQ:printf(EQ,%s)n,p);break; case NE:printf(NE,%s)n,p);break; case GT:printf(GT,%s)n,p);break; case GE:printf(GE,%s)n,p);break; case PL:printf(PL,%s)n,p);break; case MI:printf(MI,%s)n,p);break; case MU:printf(MU,%s)n,p);break; case DI: printf(DI,%s)n,p);break; default: break; void report_error() printf(n有错误！n); exit(0);/识别无符号数/int HandleOtherWord(void)return ClassOther;int HandleError(void)printf(Error!n);return 0;int GetChar(int i)int c;c=(int)TOKENi;/scanf(d%,c);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)float pow(int,int);switch(state)case 0:switch(symbol)case DIGIT:n=0;p=0;e=1;w=d;CurrentState=1;Class=ClassNo;break;case POINT:w=0;n=0;p=0;e=1;CurrentState=3;Class=ClassNo;break;default:HandleOtherWord();ClassOther; CurrentState=EndState;break;case 1:switch(symbol)case DIGIT:w=w*10+d;break;case POINT:CurrentState=2;break;case POWER:CurrentState=4;break;default:ICON=w;CurrentState=EndState;printf(%dn,ICON);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;printf(%fn,FCON);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;printf(%fn,FCON);break;return CurrentState;int LEX(void)int ch,a=0;CurrentState=0;while(CurrentState!=EndState)ch=GetChar(a);EXCUTE(CurrentState,ch);a+;return Class;void main() extern char ch; FILE * fp; if(fp=fopen(data.txt,r)=NULL) /打开文件data.txt printf(nfile open error!n); exit(0); do scanner_example(fp); /调用扫描程序 while(ch!=EOF);四、测试输入：输出：实验二 语法分析程序实现一、实验目的与要求通过设计、编制、调试一个典型的语法分析程序（任选有代表性的语法分析方法，如算符优先法、递归下降法、LL(1)、SLR(1)、LR(1)等，作为编制语法分析程序的依据），对扫描器所提供的单词序列进行语法检查和结构分析，实现并进一步掌握常用的语法分析方法。2、 实验设计文法： | + | - | * | / | ()若将非终结符号、和分别用E、T、F和i代表，则文法可写成：ET|E+T|E-T TF|T*F|T/F Fi|(E)设计思路：用C语言编制算符优先分析法的语法分析程序。其中使用了分析栈stack，用来在分析过程中存放当前句型的某一前缀，一旦句型的最左素短语在栈顶形成，便立即进行归约。用两个数组stackMAXSTACK,a实现分析栈和余留符号栈。然后，构造该文法的算符优先关系矩阵。在此可以根据算术表达式中各算符的优先级和结合性，直接手工构造算符优先关系表。算符优先关系表+-*/()i#+-*/(=i#3、 源程序#include#define RIGHT 1#define ERROR 0#define MAXINPUT 300#define MAXSTACK 100char stackMAXSTACK,a=i,+,i,*,i,#; /* 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); /*归约函数*/char vt3=E,F,T; / /* determine if stack symbol is in Vt */算符优先表/int table88= 1,1,-1,-1,-1,1,-1,1, 1,1,-1,-1,-1,1,-1,1, 1,1,1,1,-1,1,-1,1, 1,1,1,1,-1,1,-1,1, -1,-1,-1,-1,-1,0,-1, , 1,1,1,1,1,1, , , 1,1,1,1,1,1, ,1, -1,-1,-1,-1,-1,-1,0,1 ;int CharToIndex(int ch) /算符转换表 int t; switch(ch) case +:t=0;break; case -:t=1;break; case *:t=2;break; case /:t=3;break; case (:t=4;break; case ):t=5;break; case i:t=6;break; case #:t=7;break; default:t=8;break; return t;int IsVt(int ch) /判断是否为终结符int i=0; while(ch!=vti) /查看是否为t数组中元素i+; if(i3)return 1; return 0;int IsHigherThan(int i,int j) /算符优先比较，前者是否高于后者 i = CharToIndex(i); j = CharToIndex(j); if(i =8 |j=8) return 0; else if(tableij=1) return 1; else return 0;int IsLowerThan(int i,int j) /算符优先比较，前者是否低于后者 i = CharToIndex(i); j = CharToIndex(j); if(i=8 |j=8) return 0; else if(tableij=-1) return 1; else return 0;int IsEqualTo(int i,int j) /算符优先比较，前者是否等于后者 i = CharToIndex(i); j = CharToIndex(j); if(i =8 |j=8) return 0; else if(tableij=0) return 1; else return 0;int Reduce(int begin,int end,int len) /归约函数 int i; char temp50; char NewVn=0; for(i=begin;i%cn,NewVn); return NewVn;int main () 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= #; do int j; r=ai+; if (IsVt(stackk) j=k; else j=k-1; while (IsHigherThan(stackj,r) int q; if(j!=0) do q=stackj; if (IsVt(stackj-1) j-; else j-=2; while(!IsLowerThan(stackj,q)&j!=0); NewVn=Reduce(j+1,k,k-j); if(NewVn = 0)printf(ERRORn); return ERROR; k=j+1; /* reduce the leftmost prime phrase */ stackk=NewVn; /* it is stackj+1 stackj+2 stackk */ if(stack1=E)printf(OK!n);return RIGHT; /*end of while*/ if (IsLowerThan(stackj,r) | IsEqualTo(stackj,r) stack+k=r;printf(移进 %cn,r); else return ERROR; while (r!=#);return RIGHT;四：测试 1、 输入：i+i*i # 输出结果：2、输入：i+i* #输出结果：实验三 语义分析程序实现一、实验目的与要求在实现词法、语法分析程序的基础上，编写相应的语义子程序，进行简单的语义处理，加深对语法制导翻译原理的理解，进一步掌握将语法分析所识别的语法范畴变换为某种中间代码（四元式）的语义分析方法，并完成相关语义分析器的代码开发。2、 实验设计对文法中的产生式添加语义处理子程序，完成无符号数的四则运算的计值处理，将输入的四则运算转换为四元式形式的中间代码。 程序中出现的主要语义变量和辅助函数的功能为： void QUATERNION(char *result,char *ag1,char *op,char *ag2);用来生成一个四元式，将其送到四元式表中。 char *newtemp(); 产生临时变量的函数，每调用一次都产生一个新的临时变量，并返回这个新的临时变量名。函数lrparser()在原来语法分析的基础上插入相应的语义动作：将输入串翻译成四元式序列。 void scaner();词法分析函数，分析输入单词。3、 源程序#include #include #include char prog100,token8,ch;int sta,p,m,n,sum,q;int flag;char *Tab6=begin,if,then,while,do,end;char *factor();char *expression();int douju();char *term();int statement();int lrparser();char *newtemp();void scaner();void QUATERNION(char *result,char *ag1,char *op,char *ag2);struct char op110; char ag1110; char ag2110; char result10; pQuad20;int lrparser() int schain=0; flag=0; if (sta=1) scaner(); /读下一个单词符号 schain=douju(); /调用语句串分析函数进行分析 if(sta=6) scaner(); /读下一个单词符号 if(sta=0)&(flag=0) printf(Success!n); /输出（“success”） else if(flag!=1)printf(short of end !n);/输出 缺end 错误 flag=1; exit(0); else printf(short of begin !n); /输出begin错误 flag=1; exit(0); return (schain);int douju() int schain=0; schain=statement(); /调用语句分析函数进行分析 if(sta=26) scaner(); /读下一个单词符号 schain=statement(); /调用语句分析函数进行分析 return (schain);int statement() char tt8,eplace8; int schain=0; if (sta=10) strcpy(tt,token); scaner(); if(sta=18) scaner(); /读下一个单词符号 strcpy(eplace,expression(); QUATERNION(eplace,tt,=,); schain=0; else printf(short of sign := !n); /输出缺少赋值号的错误 flag=1; exit(0); return (schain);char *expression() char *tp,*ep2,*eplace,*tt; tp=(char *)malloc(12); /分配空间 ep2=(char *)malloc(12); eplace=(char *)malloc(12); tt=(char *)malloc(12); strcpy(eplace,term(); /调用term分析产生表达式计算的第一项eplace while(sta=13)|(sta=14) if (sta=13) strcpy(tt,+); /操作符 tt= +或者 else strcpy(tt,-); scaner(); /读下一个单词符号 strcpy(ep2,term(); /调用term分析产生表达式计算的第二项ep2 strcpy(tp,newtemp(); /调用newtemp产生临时变量tp存储计算结果 QUATERNION(tp,eplace,tt,ep2); /生成四元式送入四元式表 strcpy(eplace,tp); return (eplace);char *term() /仿照函数expression编写 char *tp,*ep2,*eplace,*tt; tp=(char *)malloc(12); ep2=(char *)malloc(12); eplace=(char *)malloc(12); tt=(char *)malloc(12); strcpy(eplace,factor(); while(sta=15)|(sta=16) if (sta=15) strcpy(tt,*); else strcpy(tt,/); scaner(); /读下一个单词符号 strcpy(ep2,factor(); strcpy(tp,newtemp(); QUATERNION(tp,eplace,tt,ep2); strcpy(eplace,tp); return (eplace);char *factor() char *fplace; fplace=(char *)malloc(12); strcpy(fplace,); if(sta=10) strcpy(fplace,token); scaner(); /读下一个单词符号 else if(sta=11) itoa(sum,fplace,10); scaner(); /读下一个单词符号 else if(sta=27) scaner(); /读下一个单词符号 fplace=expression(); /调用expression分析返回表达式的值 if(sta=28)scaner(); /读下一个单词符号 else printf(error on ) !n); flag=1; exit(0); else printf(error on ( !n); flag=1; exit(0); return (fplace);char *newtemp() char *p; char m8; p=(char *)malloc(8); flag+; itoa(flag,m,10); strcpy(p+1,m); p0=t; return(p);void QUATERNION(char *result,char *ag1,char *op,char *ag2) /生成四元式 strcpy(pQuadq.result,result); strcpy(pQuadq.ag11,ag1); strcpy(pQuadq.op1,op); strcpy(pQuadq.ag21,ag2); q+;void scaner() /词法分析 sum=0; for(m=0;m8;m+)tokenm+=NULL; /清空token m=0; ch=progp+; while(ch= )ch=progp+