编译原理课程设计C语言词法分析器语法分析器.doc

编译原理课程设计C语言词法分析器语法分析器             姓名： 某某某 学号： 班级： 软件一班 学院： 信息科学与技术学院2014年11月17日目录1C语言词法分析器的设计31.1实验目的31.2实验要求31.3实验环境31.4实现分析31.4.1词法分析的理论构架31.4.2程序入口设计41.4.3程序执行中的流程41.4.4程序的出口设计51.5源代码51.6结果分析81.7收获与体会112语法分析器122.1实验目的122.2实验要求122.3实验环境122.4实现分析122.4.1LL(1)分析方法的思想122.4.2程序的入口分析122.4.3程序运行的流程132.4.4程序的出口设计142.5源代码142.6结果分析272.7收获与体会30参考文献：311 C语言词法分析器的设计1.1 实验目的通过设计、编制、调试一个具体的词法分析程序，加深对词法分析原理的理解，并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。1.2 实验要求所编写的词法分析器要能对最基本的C语言程序进行词法分析。1.3 实验环境1. Windows 7操作系统2. 华硕笔记本，内存4G，处理器i53. 装有Microsoft Visual Studio 2010,并安装framework4.01.4 实现分析1.4.1 词法分析的理论构架词法分析器的功能输入源程序，按照构词规则分解成一系列单词符号。单词是语言中具有独立意义的最小单位，包括关键字、标识符、运算符、界符和常量等(1) C语言的关键字经过搜索共有32个， 是由程序语言定义的具有固定意义的标识符。我编写的词法分析器只将其中的一部分常用的定义在程序中，他们有"break","case","char","const","continue","default","do","double","else","enun", "extern","float","for","goto","if","int","long","return","static","struct","switch","sizeof","typedef","union","unsigned","void","volatile","while"而对于C语言的一些保留字如“main”、“return”等我没有将其放入关键字的范围内。(2) 标识符 用来表示各种名字，如变量名，数组名，过程名等等。(3) 常数  常数的类型一般有整型、实型、布尔型、文字型等。(4) 运算符 我在本词法分析器里面定义了“+”、“-”、“*”、“/”四种运算符。(5) 界符 我则定义了如下11种 ',' '' '.' '(' ')' '' '' '=' ':' '' ''1.4.2 程序入口设计次法分析入口的设计方法很多，为了我们每次运行时方便起见，我们将我们的C语言程序放入一个txt文件中，每次我们运行程序时，程序将自行读取文件中的C语言代码，并将对其进行词法分析将分析结果输出到控制台，这样的输入方法避免了我们重复输入程序的问题，我们需要对某程序进行词法分析时，我们只需要将我们的C语言程序拷贝到我们的txt文件中，运行程序即可进行词法分析了。开始1.4.3 程序执行中的流程打开txt文件读取C语言代码扫描、是否读取到相应字符NNNN N NYYY Y YY界符？关键字？标识符？运算符？常数？记录标号记录标号记录标号记录标号记录标号输出结束1.4.4 程序的出口设计上面我们讲解了我们词法分析器的入口，但是我们的输出是怎样设计的呢。首先为了使我们的程序有参考对照，我将我们的C语言程序首先输出到控制台上，以便与后面的词法分析是做一个参考，无需再去打开我们相应的txt文件做对照了。其次，我将我的关键字和相应的界符以及相应的运算符都编上一个序号，并且将其一一个二元式的方式输出到控制台上，以便灾后面的词法分析结果中形成对比。最后我们将词法分析的结果输出到控制台上，输出格式为，我们将每一句代码作为一个单位，在每句代码后面我们将给出本局代码分析得到词法分析后的字符标号。例如：Typedef struct |22|19| 其意义就是Typedef 和struct对应的标号为22和19这两种种别1.5 源代码/ cifa.cpp : 定义控制台应用程序的入口点。#include "stdafx.h"#include <iostream>#include <fstream>#include <sstream>#include <string>#include <vector>#include <algorithm>#include<stdlib.h>using namespace std;bool isLetter(char ch) if (ch>='A' && ch<='Z') | (ch>='a' && ch<='z') return true; else return false;bool isDigit(char ch) if (ch>='0' && ch<='9') return true; else return false;bool isP(char ch) if(ch='+'|ch='*'|ch='-'|ch='/') return true; else return false;bool isJ(char ch) if(ch=','|ch=''|ch='.'|ch='('|ch=')'|ch=''|ch=''|ch='='|ch=':'|ch='<'|ch='>'|ch=''|ch=''|ch='#') return true; / else return false;bool isBlank(char ch) if(ch=' '|ch='t') return true; else return false;int main() string src,ste,s; char ch0,ch,ch12; char ktt5520="break","case","char","const","continue","default","do","double","else","enun","extern","float","for","goto","if","int","long","return","static","struct","switch","sizeof", "typedef","union","unsigned","void","volatile", "while","标识符","无符号数" ",","",":",".","(",")","","","？","+","-","+","-","*","/","=","<",">","<>","=",">=","!=","","","#" / int pos=0; FILE *fp; fp=fopen("d:in.txt","r"); ch0=fgetc(fp); while(ch0!=EOF) /if(ch0!='t')src+=ch0; src+=ch0; ch0=fgetc(fp); src+='#' cout<<src<<endl; ch=srcpos+; ste=" " for(int j=0;j<54;j+)cout<<j<<kttj<<endl; cout<<"词法分析:n" while(ch!='#') char str20; if(ch!='n') if(isDigit(ch) /判断常数 int i=0; while(isDigit(ch)|ch='.') stri+=ch; /i+; ch=srcpos+; stri='0' ste=ste+"|"+"22" cout<<str; continue; else if(isLetter(ch) /判断字符 int i=0,j; while(isLetter(ch)|isDigit(ch) stri+=ch; /i+; ch=srcpos+; stri='0' for(j=0;j<28;j+) /判断是否关键字 int t=strcmp(str,kttj); if(t=0) stringstream ss; ste+="|" ss<<ste;ss<<j; ss>>ste; break; if(j=28)ste=ste+"|"+"28" / cout<<" " cout<<str; continue; else if(isP(ch) /判断是否运算符 int i=0,j; stri+=ch; stri='0' for(j=34;j<38;j+) int t=strcmp(str,kttj); if(t=0) stringstream ss; ste+="|" ss<<ste;ss<<j; ss>>ste; break; cout<<str; ch=srcpos+; continue; else if(isJ(ch) /判断是否界符 int i=0,j; while(isJ(ch) stri+=ch; ch=srcpos+; stri='0' for(j=23;j<47;j+) int t=strcmp(str,kttj); if(t=0) stringstream ss; ste+="|" ss<<ste;ss<<j; ss>>ste; break; cout<<str; continue; else if(isBlank(ch) cout<<ch; ch=srcpos+; continue; else cout<<ste<<endl; ste=" " ch=srcpos+; system("pause"); return 0;1.6 结果分析我将下面这段代码放到我的txt文件中#include "stdio.h"#include "malloc.h"/存储空间申请函数malloc的头文件#include"stdlib.h"/用于清屏函数 system("CLS")的头文件 #include"conio.h"/用于getch()函数的头文件#define OK 1/宏定义OK为“1”即为真#define ERROR 0/宏定义ERROR为“0”即为假#define MAXQSIZE 10/最大队列长度+1typedef struct int *base;/用于存放 int数据类型的指针，存放输入的数据 int front; int rear; SqQueue;/用于存放队列的结构体int Choice(SqQueue *Q);/申明函数Choice后面将用到int InitQueue(SqQueue *Q)/创建一个空队列Q->base=(int *)malloc(MAXQSIZE*sizeof(int);/为base申请空间 if(!Q->base) printf("队列构建失败（按任意键返回主菜单）n");getch();system("CLS");Choice(Q);Q->front =Q->rear = 0;/队列头，尾的初始化 return OK;int main()SqQueue *Q;/定义队列 QQ = (SqQueue*) malloc(MAXQSIZE*sizeof(SqQueue);/为Q申请空间InitQueue(Q);/构造空队列Choice(Q);/调用选择函数，获取主菜单return OK;运行后的结果：如图1.1 我先将txt文件中的代码取出图 1.1如图1.2 将我的标号显示在控制台上图 1.2如图1.3 输出词法分析结果图 1.3上述结果和我的预期一样，实现了对C语言的词法分析。1.7 收获与体会首先，这个词法分析器我是用C语言编写，工作量确实有点大，但是由于扎实的C语言基本功，我还是很快的编写出了程序，是我对C语言的使用更加熟练了，此外由于是编写的C语言词法分析器，所以我需要更全面深刻的去了解C语言的知识，使我找到了一些盲区，比如有一些C语言的关键字还不是很熟悉。其次，我还认真的学习了编译原理的词法分析知识，对正规式，状态转换图，以及自动机的知识有了新的理解，并将其运用到我的程序中来，大大的开阔了我的视野，使我的编程能力又上了一个台阶2 语法分析器2.1 实验目的通过设计、编制、调试一个具体的语法分析程序，加深对语法分析原理的理解，学习并掌握一种语法分析的方法，让我们巩固上课内容，学习LL(1)分析法，学会自上而下的文法分析方法。2.2 实验要求语法分析是编译过程的核心部分。他的任务是在词法分析识别单词符号串的基础上，分析并判断程序的的语法结构是否符合语法规则。由此编写一个语法分析器。2.3 实验环境1、 Windows 7操作系统2、 华硕笔记本，内存4G，处理器i53、 装有Visual C+ 6.0,并安装framework4.0注：因为本程序使用到了fprintf和fscanf两个系统函数，由于Microsoft Visual Studio 2010出于安全考虑将这两个函数的参数增加为了4个，但是本程序依旧使用的老版本时的三个参数，所以本程序只能在Visual C+ 6.0上运行。2.4 实现分析2.4.1 LL(1)分析方法的思想自定向下分析时从左向右扫描输入串，分析过程中采用的最左推导，并且只需向右看一个符号就可以决定如何推导，通过给定的文法构造预测分析表和实现某个符号串 的分析。 我们知道一个文法要能进行LL（1）分析，那么这个文法应该满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL（1）分析表，最后利用分析表，根据LL(1)语法分析构造一个分析器。LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈。2.4.2 程序的入口分析本程序为了实现语法分析器的重用性，我设置了必须先将我们需要分析的文法输入，但是为了能够高效的输入文法，我设定了将文法的产生式放在相应的txt文件中，每次我们只需将我们的文法产生式放入次txt文件，运行程序就会自动将该文法的LL（1）分析表生成，如此我们便可以高效的实现语法分析。除此之外我还设定了本程序的编写者，和文件位置的指定。会在结果分析中有具体反映。输以输入以#结束的符号串。2.4.3 程序运行的流程#和文法开始符号进栈第一个输入符号读进a栈顶符号托出去放X中X弹栈，将y1y2yk逆序放入S栈中，若右部符号串为，则不进栈X=a?XÎVT?X=#?查MX,a=Xy1y2ykX=a?将下一个输入符号读进aXÎVT?出错出错STOPYYYYYNNNNN2.4.4 程序的出口设计为了方便，我先将txt文件中的产生式输出到了控制台上以便观察，我将读出的产生式分为左部，中部，右部，并将其分别读入proNodei.leftSym,、 proNodei.midSym0 、proNodei.midSym1)、proNodei.rightSymj。因为中部我定义的是“->”符号故必须需要两个结构参数来存储。将产生式输出后，我用读到的产生式构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL（1）分析表。并将其输出到控制台上。最后读入我们将需要分析的式子，通过LL（1）分析表生成的规约，把式子放入规约栈中分析，并将分析过程输出到控制台上。2.5 源代码/ yufa2.cpp : 定义控制台应用程序的入口点。#include <iostream>#include <stdio.h>#include <string.h>#include <stdlib.h>#include <ctype.h>using namespace std; #define Pro_MidSym_Max 2#define Pro_RightSym_Max 10#define UnTInfo_Fir_Max 10#define UnTInfo_Fol_Max 10#define STACK_INIT_SIZE 100#define STACKINCREMENT 10 typedef struct ProNode /产生式结构 char leftSym; /产生式左边的符号 char midSymPro_MidSym_Max; /产生式推导符号 char rightSymPro_RightSym_Max; /产生式右边的符号，不超过十个 int length; /产生式长度ProNode; typedef struct UnTInfo /每个非终结符的信息结构，包括first和follow集合 char firstUnTInfo_Fir_Max; char followUnTInfo_Fol_Max;UnTInfo;typedef struct /构造顺序栈,存储符号 char *base; char *top; int stacksize;SqStack;typedef struct QNode /构造单链队列，存储输入符号串 char data; struct QNode *next;QNode,*QueuePtr; typedef struct QueuePtr front; /队头指针 QueuePtr rear; /队尾指针LinkQueue;int proNum; /产生式个数char UnTerminate15; /非终结符表char Terminate15; /终结符表char ProNull20; /记录能产生空字符的非终结符ProNode sheet1515; /分析表char select1515; /select集合，以便于构造分析表LinkQueue Remain; /剩余符号串 void InitUnTInfo(UnTInfo unTInfo,int unTInfoNum); /初始化函数，对每个非终结符的信息结构进行初始化void InitProNode(ProNode proNode,int proNum); /初始化函数，对每个非终结符的产生式结构进行初始化void InitStack(SqStack &s); /初始化栈void InitQueue(LinkQueue &q); /初始化队列void EnQueue(LinkQueue &q,char c); /在队尾插入新的元素void Exit(); /栈溢出处理函数void Error();/出错处理void Push(SqStack &s, char c); /入栈char Pop(SqStack &s); /出栈void InitSheet(ProNode* sheet,int m,int n) ; /初始化分析表函数bool ReadPro(ProNode proNode,char fileName);/从文件读取产生式函数void PrintPro(ProNode proNode,int proNum); /显示产生式void SetUnTerminate(char UnTerminate,ProNode proNode,int proNum); /设置非终结符表void SetTerminate(char UnTerminate,ProNode proNode,int proNum); /设置终结符表int GetNumofUT(char UnTerminate); /获得非终结符个数int GetNumofT(char Terminate); /获得终结符个数int GetUTLoaction(char UnTerminate,char c); /获得非终结符在非终结符表中的位置int GetTLocaction(char UnTerminate,char c); /获得终结符在终结符表中的位置void First(ProNode proNode,UnTInfo unTInfo); /计算各非终结符的First集void Follow(ProNode proNode,UnTInfo unTInfo); /计算各非终结符的Follow集void AddChar(char chArray,char c); /将非终结符的所有first值加入First集void AddCharToChar(char chArray,char otherArray); /将非终结符的所有first集加入First集void AddFollow(char follow,char c); /将非终结符的所有follow值加入Follow集bool IsNull(char c); /非终结符能否产生空字符bool IsTerminate(char c); /判断是否为终结符号void SetSheet(ProNode proNode,UnTInfo unTInfo); /设置分析表void SetSelect(ProNode proNode,UnTInfo unTInfo);/设置Select集合void InputSym(); /输入字符串函数void Scan(); /分析扫描的主控程序char GetSym(LinkQueue &q) ; /获取下一字符void PrintSym(SqStack &s); /显示符号栈符号void PrintRemain(LinkQueue &q); /显示剩余符号串void PrintSheet(int row,int col); /显示所使用产生式void Success(); /分析成功void main() char fileName10; cout<<"编制人：徐玉松，20122617，软件一班"<<endl; cout<<"请输入放有产生式的文件（如：xuyusong.txt）:"<<endl; cin>>fileName; ProNode proNode20; InitProNode(proNode,20); if(ReadPro(proNode,fileName) /*输出文法产生式*/ cout<<"该文法产生式为："<<endl; PrintPro(proNode,proNum); /*设置非终结符表和终结符表*/ SetUnTerminate(UnTerminate,proNode,proNum); SetTerminate(Terminate,proNode,proNum); /* 输出First集*/ int NumofUT = GetNumofUT(UnTerminate); int NumofT = GetNumofT(Terminate); UnTInfo unTinfo20; InitUnTInfo(unTinfo,20); /* 输出First集*/ First(proNode,unTinfo); /* 输出Follow集*/ Follow(proNode,unTinfo); /*设置select*/ SetSelect(proNode,unTinfo); /*输出sheet*/ cout<<endl<<"分析表:"<<endl; SetSheet(proNode,unTinfo); cout<<"t" for(int jj = 0 ; jj < NumofT ; jj+) cout<<Terminatejj<<"t" cout<<endl; for(int mm = 0 ; mm < NumofUT ; mm+) cout<<UnTerminatemm<<"t" for(int mn = 0 ; mn < NumofT; mn+) PrintSheet(mm,mn); cout<<"t" cout<<endl; InputSym(); /输入字符串 Scan(); /主控程序 else Error(); void InitProNode(ProNode proNode,int proNum) /初始化函数，对每个非终结符的产生式结构进行初始化 for(int i = 0 ; i < proNum ; i+) proNodei.leftSym = '0' memset(proNodei.midSym,0,Pro_MidSym_Max); memset(proNodei.rightSym,0,Pro_RightSym_Max); proNodei.length = 0; void InitUnTInfo(UnTInfo unTInfo,int unTInfoNum) /初始化函数，对每个非终结符的信息结构进行初始化 for(int i = 0 ; i < unTInfoNum;i+) int firLength = strlen(unTInfoi.first); int folLength = strlen(unTInfoi.follow); memset(unTInfoi.first,0,UnTInfo_Fir_Max); /将非终结符号的Frist集合初始化为空串 memset(unTInfoi.follow,0,UnTInfo_Fol_Max); /将非终结符号的follow集合初始化为空串 void InitStack(SqStack &s) /初始化栈 s.base = (char *)malloc(STACK_INIT_SIZE * sizeof(char); if(!s.base) Exit(); s.top = s.base; s.stacksize = STACK_INIT_SIZE; void Push(SqStack &s, char c) /入栈 if(s.top - s.base >= s.stacksize) /栈满，追加存储空间 s.base = (char *)realloc(s.base,(s.stacksize + STACKINCREMENT) * sizeof(char); if(!s.base) Exit(); /存储分配失败 s.top = s.base + s.stacksize; s.stacksize += STACKINCREMENT; *(s.top) = c; s.top = s.top + 1; char Pop(SqStack &s) /出栈 if(s.top = s.base ) return NULL; s.top = s.top