编译原理实验报告.docx

38 / 38编译原理实验报告实验一 词法分析程序实现一、实验目的与要求通过编写和调试一个词法分析程序，掌握在对程序设计语言的源程序进行扫描的过程中，将字符形式的源程序流转化为一个由各类单词符号组成的流的词法分析方法。二、实验设计语言中具有的单词包括五个关键字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的状态转换图包含语义处理过程的识别无符号数的状态矩阵三、源程序Lex.h #ifndef _LEX_H#define _LEX_H#define MAX_LENGTH 256#define MAX_KET_NUMBER 6#define EndState -1#define BEGIN 1#define END 2#define IF 3#define THEN 4#define ELSe 5#define ID 6#define UCON 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 DI 17#define MUL 18#define DIV 19#define PLUS 20#define MINUS 21#define LKUOHAO 22#define RKUOHAO 23#define JING 40/无符号数识别有关定义#define DIGIT 51#define POINT 52#define OTHER 53#define POWER 54#define ZHENG 55#define FU 56#endifLex.c#include#include#includelex.h#include#include#includeint isInt=1;/数的类型 1 整数 0 小数static int CurrentState=0;int number_state_switch(int state, char c);/char tokenMAX_LENGTH;/存放识别符号串 const char *key_workMAX_KET_NUMBER=,begin,end,if,then,else;const char *MAP= NULL,BEGIN,END,IF,THEN,ELSE,ID,UCON,LT, LE,EQ,NE,GT,GE,IS,PL,MI,DI,MUL,DIV,PLUS,MINUS,(,) ;/类别码映射为字符用于输出FILE *ifp,*ofp;/输入输出文件int lex(); /从输入文件 识别一个符号存于 token 并返回它的类型码void out(int type,char *token);/识别单词 输出到文件 int lookup(char *token);/返回token 的类别码 extern void report_error();int isstop=1;int row=1;int col=0;int w,n,p,e,d;/w*e*10(p)int zhengshu;/存放整数double xiaoshu;/存放小数int main(int argc,char *args) if(argc1) if(ifp=fopen(args1,r)=NULL) printf(打开文件失败!); if(ofp=fopen(out.txt,w)=NULL) printf(打开文件失败!); else printf(ERROR:NO FILE); return 0; int type; while(isstop) type=lex(); out(type,token); printf(词法分析完成，保存在out.txt文件中！n); fclose(ifp); fclose(ofp);void out(int type,char *token)/输出单词以二元组的形式 fputc(,ofp); fputs(MAPtype,ofp); fputc(,ofp); if(type=UCON) if(isInt=1) fprintf(ofp,%d,zhengshu); else fprintf(ofp,%lf,xiaoshu); else fputs(token,ofp); fputc(),ofp); fputc(n,ofp);int lookup(char *token) /查找符号串的类型 int i; for(i=1;iMAX_KET_NUMBER;i+) if(!strcmp(key_worki,token) token0=0; return i; return ID;void report_error()printf(%d,%d)error:相关字符：%sn,row,col,token);exit(1);int lex() /词法分析函数 char ch;/当前字符 int i=0; do ch=fgetc(ifp); if(ch=n|ch=r) row+; col=0; else col+; while(ch= |ch=r|ch=n|ch=t);/去掉无效字符 if(isalpha(ch) /字母开头 则此单词是自定义符号串或关键字 tokeni=ch;i+;ch=fgetc(ifp);col+;while(isalnum(ch) tokeni=ch; i+; ch=fgetc(ifp); col+;tokeni=0;if(ch=EOF)isstop=0;elsefseek(ifp,-1,1);col-;return lookup(token); else if(isdigit(ch)/数字开头无符号数 CurrentState=0;do tokeni=ch;i+;CurrentState=number_state_switch(CurrentState,ch); /掉无符号数表驱动函数识别无符号数if(CurrentState!=EndState)ch=fgetc(ifp);col+;while(CurrentState!=EndState);tokeni-1=0;if(ch=EOF)isstop=0;elsefseek(ifp,-1,1);/多读一个col-;return UCON; else /其他符号是运算符 token0=ch;token1=0;fgetc(ifp);if(feof(ifp) isstop=0; elsefseek(ifp,-1,1); switch(ch) case )return NE; else if(ch=EOF)isstop=0;else fseek(ifp,-1,1); return LT; break; case =:return EQ;break; case :ch=fgetc(ifp); col+; if(ch=) return GE; else if(ch=EOF)isstop=0;elsefseek(ifp,-1,1);return GT; break; case *:return MUL; break; case +:return PLUS; break; case -:return MINUS; break; case /:return DIV; break; case (:return LKUOHAO; break; case ):return RKUOHAO; break; case #:return JING; break; default : report_error();break; int number_state_switch(int state, char c)/无符号数状态表驱动函数 int symbol; if(isdigit(c)symbol=DIGIT; else if (c=.) isInt=0;symbol=POINT; else if (c=e|c=E)symbol=POWER; else if (c=+)symbol= ZHENG; else if (c=-)symbol= FU; switch (state) case 0:switch (symbol) case DIGIT: d=c-0;n=0;p=0;e=1;w=d;CurrentState=1;break; case POINT: w=0;n=0;p=0;e=1; CurrentState=3;break; default: report_error( );CurrentState=EndState; break; case 1:switch (symbol) /CurrentState=1 case DIGIT: d=c-0;w=w*10+d;break; case POINT: CurrentState=2;break; case POWER: CurrentState=4;break; default: isInt=1;zhengshu=w;CurrentState=EndState; break; case 2:switch (symbol) case DIGIT: d=c-0;n+;w=w*10+d;break; case POWER: CurrentState=4;break; default: isInt=0;xiaoshu=w*pow(10.0,e*p-n);CurrentState=EndState; break; case 3:switch (symbol) case DIGIT: d=d-0; n+;w=w*10+d;CurrentState=2;break; default: report_error( );CurrentState=EndState; break; case 4:switch (symbol) case DIGIT: d=c-0;p=p*10+d;CurrentState=6;break; case ZHENG: e=-1;CurrentState=5;break; case FU: CurrentState=5;break; default: report_error( );CurrentState=EndState; break; case 5:switch (symbol) case DIGIT: d=c-0; p=p*10+d;CurrentState=6;break; default: report_error( );CurrentState=EndState; break; case 6:switch (symbol) case DIGIT: d=c-0; p=p*10+d;break; default: isInt=0;xiaoshu=w*pow(10.0,e*p-n);CurrentState=EndState; break; return CurrentState; 四、测试输入：输出：实验二 语法分析程序实现一、实验目的与要求通过设计、编制、调试一个典型的语法分析程序（任选有代表性的语法分析方法，如算符优先法、递归下降法、LL(1)、SLR(1)、LR(1)等，作为编制语法分析程序的依据），对扫描器所提供的单词序列进行语法检查和结构分析，实现并进一步掌握常用的语法分析方法。二、实验设计文法： | + | - | * | / | ()若将非终结符号、和分别用E、T、F和i代表，则文法可写成：ET|E+T|E-T TF|T*F|T/F Fi|(E)设计思路：用C语言编制算符优先分析法的语法分析程序。其中使用了分析栈stack，用来在分析过程中存放当前句型的某一前缀，一旦句型的最左素短语在栈顶形成，便立即进行归约。用两个数组stackMAXSTACK,a实现分析栈和余留符号栈。然后，构造该文法的算符优先关系矩阵。在此可以根据算术表达式中各算符的优先级和结合性，直接手工构造算符优先关系表。算符优先关系表+-*/()i#+-*/(=i#三、源程序Programmer.h #ifndef _PROGRAMMER_H#define _PROGRAMMER_H#define STACK_LENGTH 20#define STACK_INCREASE 20extern void report_error();typedef struct _StackElemint status; /状态char symble;/符号*StackElem;typedef struct _Stack StackElem elem;int top; /栈顶int tail;/栈底*Stack;void push(Stack s,_StackElem e);/入栈 把e压入堆栈sint pop(Stack s,StackElem e);/出栈 栈顶元素返回void init_stack(Stack s);/初始化堆栈void destroy_stack(Stack s);/销毁堆栈typedef struct _LinkList /slr分析表行可用 数组下表表示 char symble;/符号 即slr 分析表的列 char type; / s action移进 /r action规约 /g goto转移 / a action acc int number;/下一个状态 _LinkList *next;/下一个节点*LinkList;typedef struct _ChanShengShiint length;char *g;*ChanShengShi;int status_switch(Stack s,int cur,char c);/slr(1)驱动#endifProgrammer.c#includeprogrammer.h#includelex.c#include#include#includeusing namespace std;ChanShengShi chanshengshi;/存放产生式char *symble;/存放第一行符号LinkList table; /存放表格用于查表extern void report_error();void init_stack(Stack s)/初始化堆栈 s-elem=(StackElem)malloc(STACK_LENGTH*sizeof(_StackElem);/为堆栈初始化分配内存空间 if(s-elem)=NULL) printf(堆栈初始化失败n);exit(1); s-elem0.status=STACK_LENGTH;/栈底元素status存放堆栈大小 s-top=0; s-tail=0;void push(Stack s,StackElem e)/入栈 把e压入堆栈s s-top+; if(s-top=s-elem0.status)/s-elem0.status 堆栈当前大小 当满时扩展堆栈大小 realloc(s-elem,(s-elem0.status)+STACK_INCREASE)*sizeof(_StackElem); s-elems-top.status=e-status; s-elems-top.symble=e-symble; int pop(Stack s,StackElem e)/出栈 栈顶元素位置返回 if(s-top0) e-status=s-elems-top.status; e-symble=s-elems-top.symble; s-top-; else printf(堆栈已空。n); return s-top;void destroy_stack(Stack s)/销毁堆栈 free(s-elem); free(s);void create_table()/读取slr分析表并存储在 table 链表中 FILE *pf; int status_count=0; int symble_count=0; if(pf=fopen(slr.txt,r)=NULL) printf(打开表slr.txt文件失败n);exit(1); char temp; do /统计行数列数 fscanf(pf,%c,&temp); if(temp=t&status_count=0) symble_count+; else if(temp=n) status_count+; if(feof(pf) break; while(1); table=(LinkList)malloc(sizeof(_LinkList)*status_count); symble=(char*)malloc(sizeof(char)*(symble_count+1); symblesymble_count=0; fseek(pf,0,0); symble_count=0; status_count=0; LinkList tem,tail; /建立slr分析表 while(1) /第一行 符号表 读取并存在 symble 数组 fscanf(pf,%c,&temp); if(temp!= &temp!=t&temp!=n)/一行除了空格 t n 便是slr符号 symblesymble_count=temp; symble_count+; else if(temp=n)/换行则符号表统计完了 break; fseek(pf,-1,1); int count=-1;/记录列符号位置 对应symble 索引 while(!feof(pf) fscanf(pf,%c,&temp); if(temp=t)/每有一个t 列的状态便加1 一行状态存在symble 数组 count 是数组索引值 count+; else if(temp=n&!feof(pf)/每换一行状态便加1 tail=&tablestatus_count;/status_count 可代表列的状态 status_count+; count=-1; else if(temp=a|temp=s|temp=r|temp=g) tem=(LinkList)malloc(sizeof(_LinkList);/开辟节点存储信息tem-symble=symblecount;/存取符号 即表的一行对应的元素 tem-type=temp; /存贮动作类型char num256;int i=0;dofscanf(pf,%c,&temp);numi=temp;i+;while(0=temp&tempnumber=atoi(num);/存储下一个状态fseek(pf,-1,1);tail-next=tem; /连接链表tail=tem;tail-next=NULL; tem=NULL; fclose(pf); if(pf=fopen(chanshengshi.txt,r)=NULL) printf(打开表chanshengshi.txt文件失败n);exit(1); int rowcount=0; char *g; int length; char temps256; do /统计产生式的个数 fscanf(pf,%s,temps); rowcount+; while(!feof(pf); chanshengshi=(ChanShengShi)malloc(sizeof(_ChanShengShi)*rowcount); rewind(pf); rowcount=0; do /存储产生式在chanshengshi数组里 g=(char*)malloc(sizeof(char)*256); fscanf(pf,%s,g); length=strlen(g); chanshengshirowcount.length=length; chanshengshirowcount.g=g; rowcount+; while(!feof(pf); fclose(pf);int go(int cur,char c)/查goto表 LinkList temp=&tablecur;/获取curstatus 状态所在行的表 while(temp!=NULL) temp=temp-next; if(temp-type=g&temp-symble=c) return temp-number; report_error(); exit(1);int move_in(Stack s,int number,char c)/移近 _StackElem e; e.symble=c; e.status=number; push(s,&e); /符号和状态移入堆栈中 return e.status; int regulate(Stack s,int number,char c)/按number号产生式规约 _StackElem e; int curstatus; for(int i=0;isymble=c)/查到 if(temp-type=a)/识别完成语法正确 接受 printf(语法分析完成！n); return -1; else if(temp-type=s)/移进 return move_in(s,temp-number,c);else if(temp-type=r)/规约 return regulate(s,temp-number,c); temp=temp-next;/如果结束还没有查到那么语法错误 report_error();/报错 exit(1);int main(int argc,char *args) Stack s=(Stack)malloc(sizeof(_Stack); init_stack(s);/创建并初始化堆栈 create_table();/根据分析表文件创建分析表 int cur=0; _StackElem e; e.symble=#; e.status=0; push(s,&e); if(argc1) if(ifp=fopen(args1,r)=NULL) printf(打开文件失败!); else printf(ERROR:NO FILE); return 0; int type; while(isstop) type=lex(); switch(type) case UCON: cur=status_switch(s,cur,i);break;case PLUS: cur=status_switch(s,cur,+); break;case MUL: cur=status_switch(s,cur,*); break;case DIV: cur=status_switch(s,cur,/); break;case MINUS: cur=status_switch(s,cur,-); break;case LKUOHAO: cur=status_switch(s,cur,(); break;case RKUOHAO: cur=status_switch(s,cur,); break;case JING : cur=status_switch(s,cur,#); break; default:report_error();isstop=1; if(cur!=-1) /语法错误 report_error(); fclose(ifp);四：测试1、 输入： 输出结果：2、 输入：输出：3、 输入：输出结果： 实验三 语义分析程序实现一、实验目的与要求在实现词法、语法分析程序的基础上，编写相应的语义子程序，进行简单的语义处理，加深对语法制导翻译原理的理解，进一步掌握将语法分析所识别的语法范畴变换为某种中间代码（四元式）的语义分析方法，并完成相关语义分析器的代码开发。二、实验设计对文法中的产生式添加语义处理子程序，完成无符号数的四则运算的计值处理，将输入的四则运算转换为四元式形式的中间代码。 程序中出现的主要语义变量和辅助函数的功能为： void QUATERNION(char *result,char *ag1,char *op,char *ag2);用来生成一个四元式，将其送到四元式表中。 char *newtemp(); 产生临时变量的函数，每调用一次都产生一个新的临时变量，并返回这个新的临时变量名。函数lrparser()在原来语法分析的基础上插入相应的语义动作：将输入串翻译成四元式序列。 void scaner();词法分析函数，分析输入单词。三、 源程序#includeprogrammer.h#includelex.c#include#include#includeusing namespace std;ChanShengShi chanshengshi;/存放产生式char *symble;/存放第一行符号LinkList table; /存放表格用于查表extern void report_error();union Shuint zhengshu;double xiaoshu;struct Wordint isInt;Shu shu;void init_stack(Stack s)/初始化堆栈 s-elem=(StackElem)malloc(STACK_LENGTH*sizeof(_StackElem);/为堆栈初始化分配内存空间 if(s-elem)=NULL) printf(堆栈初始化失败n);exit(1); s-elem0.status=STACK_LENGTH;/栈底元素status存放堆栈大小 s-top=0; s-tail=0;void push(Stack s,StackElem e)/入栈 把e压入堆栈s s-top+; if(s-top=s-elem0.status)/s-elem0.status 堆栈当前大小 当满时扩展堆栈大小 realloc(s-elem,(s-elem0.status)+STACK_INCREASE)*sizeof(_StackElem); s-elems-top.status=e-status; s-elems-top.symble=e-symble; int pop(Stack s,StackElem e)/出栈 栈顶元素位置返回 if(s-top0) e-status=s-elems-top.status; e-symble=s-elems-top.symble; s-top-; else printf(堆栈已空。n); return s-top;void destroy_stack(Stack s)/销毁堆栈 free(s-elem); free(s);void create_table()/读取slr分析表并存储在 table 链表中 FILE *pf; int status_count=0; int symble_count=0; if(pf=fopen(slr.txt,r)=NULL) printf(打开表slr.txt文件失败n);exit(1); char temp; do /统计行数列数 fscanf(pf,%c,&temp); if(temp=t&status_count=0) symble_count+; else if(temp=n) status_count+; if(feof(pf) break; while(1); table=(LinkList)malloc(sizeof(_LinkList)*status_count); symble=(char*)malloc(sizeof(char)*(symble_count+1); symblesymble_count=0; fseek(pf,0,0); s