词法分析.doc

编译原理课程设计报告一、 设计概述(设计目的、环境、要求)1、 设计目的本次课程设计的目的是通过使用一个通用的能够自动根据正规表达式生成词法分析程序的工具程序设计一个简单语言的词法分析器,使学生充分理解课程理论内容和工具软件的使用技巧,掌握所涉及的典型数据结构,算法及方法,为今后在大型软件系统实践中设计性能优良的软件系统打下基础。2、 设计环境实验环境为Windows操作系统下，词法分析使用的主要工具是flex。3、 设计要求使用Flex工具，实现Decaf语言词法分析工作，对Decaf语言编写的源程序从左至右逐个字符进行扫描，产生一个单词序列。二、 实验步骤(包括基本程序的分析步骤、测试的例子)1、编写程序的分析步骤（1）根据pp2所提供的scanner.l文件修改我们所需的词法分析程序scanner.l。/* *scanner.l * *Flex输入文件，生成scanner*/%#include #include #include #include #include #include scanner.h#include hashtable.h#include utility.h#include /* *Global variable: yylval *- *全局变量，我们可以从yylval中获得每个token的属性。 *以后这个变量由bison/yacc自动生成，在这个实验里面，我们手动定义。*/YYSTYPE yylval;/* *Global variable: yylloc *- *全局变量，我们可以从yylloc中获得每个token的位置属性。 *以后也由bison/yacc自动生成。*/struct yyltype yylloc;static int curLineNum, curColNum;static char curLine512;static void DoBeforeEachAction(); #define YY_USER_ACTION DoBeforeEachAction();Hashtable hasht;%option stack%s N C %x COPY/* *在这里定义你的辅助定义和开始条件*/decimal 0-9HEX_decimal (decimal|a-fA-F)+HEX_INTEGER 0XxHEX_decimal+INTEGER decimal+EXPONENT Ee-+INTEGERDOUBLE (INTEGER(.)decimal*EXPONENT?)BEG_STRING (n*)STRING (BEG_STRING)IDENTIFIER (a-zA-Za-zA-Z0-9_*)OPERATOR +-*/%=,.;!()BEG_COMMENT (/*)END_COMMENT (*/)SINGLE_COMMENT (/n*)WHITE t*/* *以下是你的识别规则(patten&action)。 * 注意空格问题和括号引号匹配问题，一旦出错很难查出。*/% .* strncpy(curLine, yytext, sizeof(curLine); curColNum = 1; yy_pop_state(); yyless(0); yy_pop_state();n curLineNum+; curColNum = 1; if (YYSTATE != COPY) yy_push_state(COPY); WHITE /* ignore space & tabs in normal or comment */ /* - Comments - */BEG_COMMENT yy_push_state(C); END_COMMENT yy_pop_state(); ReportError(&yylloc, Input ends with unterminated comment.); return 0; *n/* /* grab all non-star, non-slash, non-newline */. /* ignore everything else that doesnt match */ SINGLE_COMMENT /* skip to end of line for / comment */ /* - Keywords - */void return T_Void; int return T_Int; double return T_Double; bool return T_Bool; string return T_String; class return T_Class; extends return T_Extends; this return T_This; null return T_Null; while return T_While; for return T_For; if return T_If; else return T_Else; return return T_Return; New return T_New; NewArray return T_NewArray; Print return T_Print; ReadInteger return T_ReadInteger; ReadLine return T_ReadLine; /* - Operators - */= return T_LessEqual; = return T_GreaterEqual;= return T_Equal; != return T_NotEqual; & return T_And; | return T_Or; OPERATOR return yytext0; /* - Constants - */true|false yylval.boolConstant = (yytext0 = t); return T_BoolConstant; INTEGER egerConstant = strtol(yytext, NULL, 10); return T_IntConstant; HEX_INTEGER egerConstant = strtol(yytext, NULL, 16); return T_IntConstant; DOUBLE yylval.doubleConstant = atof(yytext); return T_DoubleConstant; STRING strcpy(yylval.stringConstant,yytext); return T_StringConstant; BEG_STRING/n ReportError(&yylloc, Illegal newline in string constant %s, yytext); BEG_STRING ReportError(&yylloc, Input ends with unterminated string %s, yytext); /* - Identifiers - */IDENTIFIER Declaration *temp; if(temp=hasht.st_lookup(strdup(yytext)=NULL) temp=new Declaration(yytext,yylloc.first_line,1);hasht.st_insert(*temp); else temp-IncrementOccurrences(); yylval.decl=temp; return T_Identifier; /* - Default rule (error) - */. ReportError(&yylloc,Unrecognized char: %c, yytext0); %void yyerror(char *msg)ReportError(&yylloc, %s, msg);void Inityylex() BEGIN(N); / Start in Normal state yy_push_state(COPY); / but copy first line at start curLineNum = 1; curColNum = 1;int yywrap()return (1);static void DoBeforeEachAction() yylloc.first_line = curLineNum; yylloc.first_column = curColNum; yylloc.last_column = curColNum + yyleng - 1; curColNum += yyleng;const char *GetLineNumbered(int num) return (num = curLineNum) ? curLine : NULL;（2）根据pp1所提供的SYMTAB.C和SYMTAB.H文件修改我们所需要的哈希表的头文件hashtable.h和实现哈希表的程序hashtable.cpp由于在数据结构方面为了实现很方便的进行查找，插入，删除等操作。于是把它的数据结构设计成一哈稀表结构，哈稀表的查找，插入等操作是快速的。所设计的哈稀结构符号表结构如下： 对标识符的处理 Y查找，返回对象指针找到否？N出现次数+1生成一个新的对象然后插入将数据赋值给yylva.decl程序hashtable.cpp/*Hashtable.cpp:add your code below:*/#include #include stdlib.h#include declaration.h#include hashtable.h/* SHIFT is the power of two used as multiplierin hash function */#define SHIFT 4int Hashtable:hash ( const char * key ) int temp = 0;int i = 0;while (keyi != 0) temp = (temp declation.GetName() != 0)l = l-next;if (l = NULL) l = (LineList) malloc(sizeof(struct LineListRec);l-declation = declation;l-next = hashTableh;hashTableh=l;Declaration * Hashtable:st_lookup (const char* name) int h = hash(name);LineList l = hashTableh;while (l != NULL) & (strcmp(name,l-declation.GetName() != 0)l = l-next;if (l = NULL) return NULL;else return &(l-declation);hashtable.h /*hashtable: hashtable的实现方法不会影响最后的结果，所以大家可以自由发挥。 允许大家使用类struct等方法，不过要做相应的改动。 hashtable主要存储变量的声明，由于经常查询，所以要用速度比较快的hashtable来实现*/#ifndef _H_hashtable#define _H_hashtable#include #include declaration.h#define MaxDecla 256class Declaration;#define SIZE 211typedef struct LineListRecDeclaration declation;struct LineListRec * next;*LineList;static LineList hashTableSIZE;static int location = 0;class Hashtable private:public:int hash(const char *key);void st_insert(Declaration declation);Declaration *st_lookup(const char *name );#endif （3）修改变量声明declaration.cpp文件，实现delcaration类 declaration.cpp /* *declaration.cpp *delcaration类的实现。 *pp1需要你来实现它*/#include declaration.h#include #include Declaration:Declaration(const char *str,int lineNum,int num)name=strdup(str);lineFound=lineNum;numoccur=num;const char * Declaration:GetName()return name;int Declaration:GetLineFound()return lineFound;int Declaration:GetOccurrences()return numoccur;void Declaration:IncrementOccurrences()numoccur+;/* *Print() *- *由main.c调用，注意控制输出格式，使得你的输出和例子中的输出保持一致。*/void Declaration:Print()printf(%s seen %d time(s), first on line %d)n,name,numoccur,lineFound);注：因为name是字符串，所以