词法分析实验 实验指导.doc

实验一 简单词法分析器构造一 实验目的1、 掌握正则表达式、有限自动机2、 构造简单的词法分析器二 词法规则（C语言分析及状态转换图）1、C语言说明C语言有以下记号及单词（1）标识符：以字母开头的，后跟字母或数字组成的符号串。（2）保留字：标识符的子集。（3）无符号数（4）关系运算符：（5）标点符号：+、*、/、（、）、：、，、；等（6）赋值号：:=（7）注释标记：以/*开始，以*/结束。（8）单词符号间的分隔符：空格。2、记号的正规表达式（略）（1）标识符 L（L/D）*（2）无符号整数（3）无符号数（4）关系运算符（5）赋值号（6）标点符号（7）注释头符号3、状态转换图为每种记号的文法构造出相应的状态转换图，让这些状态转换图公用一个初态，就可以得到词法分析器的状态转换图，如图1所示。（部分）. 图 1 状态转换图三、词法分析器的构造与实现1、词法分析器的算法框图在开始状态，首先要读进一个字符。若读入的是一个空格（包括blank,tab,newline）就跳过它，再继续读字符，知道读进一个非空字符为止。在标识符状态，识别并组合出一个标识符之后，还必须加入一些动作，以便查保留字表，确定识别出的单词符号是保留字，还是用户自定义标识符，并输出相应的记号。在无符号数状态，可识别出各种常数，包括整数在内。在组数的同时，还要做从十进制数到二进制数的转换。.2、程序结构图： ERROROUTPUT ScannerIsAlphaIsnumberIsOther注：1 Scanner 功能：完成初始化，并循环调用子模块完成单词的识别2 IsAlpha 功能：识别保留字和标识符3 IsNumber 功能：识别数字4 IsOther 功能：识别其他字符5 OutPut 功能：输出识别的单词（二元式）6 Error 功能：出错处理 程序代码（略）/* 程序名称：编译原理之词法分析器* * 注 意：此分析器只对C语言子集进行处理*/#include #include #include #include #include #define KEYWORD_LEN 32 /保留字个数#define STR_MAX_LEN 300 /标识符最大长度#define PRO_MAX_LEN 20480 /源程序最大长度#define STB_MAX_LEN 1000 /符号表最大容量#define CTB_MAX_LEN 1000 /常数表最大容量#define ERROR 0 /错误#define ID (KEYWORD_LEN+1) /标识符#define CONST (KEYWORD_LEN+2) /常量#define OPERAT (KEYWORD_LEN+3) /运算符#define DIVIDE (KEYWORD_LEN+4) /界符int errorLine=0;char proBufferPRO_MAX_LEN = ; /存储程序代码的全局缓冲区char ch; /读出来的当前字符char wordgetSTR_MAX_LEN; /标识符 或 常量int point = 0; /源程序当前位置指针char signTabSTB_MAX_LENSTR_MAX_LEN; /符号表int pointSTB = 0; /符号表指针char constTabCTB_MAX_LENSTR_MAX_LEN; /常量表int pointCTB = 0; /常数表指针char kwTabKEYWORD_LEN10= /保留字表 C语言一共有32个保留字关键字 auto, break, case, char, const, continue, default, do, double, else, enum, extern, float, for, goto, if, int, long, register, return, short, signed, sizeof, static, struct, switch, typedef, union, unsigned, void, volatile, while;char errorTab50= /错误代码表 /*0*/未知错误, /*1*/非法的字符, /*2*/不正确的字符常量表达, /*3*/不正确的字符串表达, /*4*/不正确的数字表达, /*5*/注释丢失*/;typedef struct signDuality int kind; int value;*pDualistic, Dualistic;/函数声明void pretreatment(); /预处理void ProcError(int id); /错误bool GetChar(); /获得一个字符不包括结束标记bool GetBC(); /获得一个非空白字符void Concat(char *str); /将ch连接到str后int Reserve(char *str); /对str字符串查找保留字表 若是一个保留字-返回其编码 否则返回0void Retract(); /将搜索指示器回调一个字符位置int InsertId(char *str);/将str串以标识符插入符号表，并返回符号表指针int InsertConst(char *str); /将str串以常数插入符号表，并返回常数表指针bool wordAnalyse(pDualistic pDu); /词法分析 true正常/end/预处理 将缓冲区内的源代码去掉注释和无效空格【所谓的无效空格是指出现在非字符串/ 常量中的空格】void pretreatment()int lines=0; char tmpPRO_MAX_LEN; /先将处理结果保存到临时空间，这样虽然浪费空间但是节约 /时间 int tmpp = 0; /这个临时空间的末尾指针 bool flg; char tmpc; /去掉注释先 /注释有两种 一种是C+风格的/ 另一种是C风格的/*/ point = 0; do flg = GetChar(); if(ch = /) flg = GetChar(); switch(ch) case /: do flg = GetChar(); while(!(ch = n | flg = false);/ | ch = 0);/注释一直到行尾或文件结束 if(ch = n) Retract(); /归还换行 break; case *: do flg = GetChar(); tmpc = ch; /为了保证出错处理程序能正确定位出错位置 保留注释中的换行 if(tmpc = n) tmptmpp+ = tmpc; flg = GetChar(); Retract(); /归还一个字符 while(flg & !(flg & tmpc = * & ch = /); flg = GetChar(); if (!flg) ProcError(5); break; default: /不是任何一种注释 Retract(); Retract(); GetChar(); tmptmpp+ = ch; flg = GetChar(); tmptmpp+ = ch; else tmptmpp+ = ch; while(flg); tmptmpp = 0; strcpy(proBuffer,tmp);/错误void ProcError(int id) printf(nError:第%d行,%sn,errorLine, errorTabid);/获得一个字符bool GetChar() if(point PRO_MAX_LEN & proBufferpoint != 0) /如果当前下标合法且当前字符为结束标记则取字符增游标 ch = proBufferpoint+; if (ch = n) errorLine +; return true; ch = 0; return false;/获得一个非空白字符bool GetBC() do if(!GetChar() /获取字符失败 ch = 0; return false; while(isspace(ch); /直到获得一个非空白字符 return true;/将ch连接到str后void Concat(char *str) int i; for(i=0; stri; +i); stri = ch; stri+1 = 0;/对str字符串查找保留字表 若是一个保留字-返回其编码 否则返回0int Reserve(char *str) int i; for(i=0; i 0) errorLine -; point -;/将str串以标识符插入符号表，并返回符号表指针int InsertId(char *str) int i; for(i=0; i pointSTB; +i) if(0 = strcmp(signTabi, str) return i; strcpy(signTabpointSTB+, str); return (pointSTB-1);/将str串以常数插入常量表，并返回常数表指针int InsertConst(char *str) int i; for(i=0; i kind = ID; pDu-value = value; else pDu-kind = code; pDu-value = -1; return true; case D: while(isdigit(ch) wordgeti+ = ch; GetChar(); wordgeti = 0; Retract(); value = InsertConst(wordget); pDu-kind = CONST; pDu-value= value; return true;/().,! !=sizeof=&=|=?:+=/-=*=/=%=kind = ERROR; pDu-value = 0; else value = InsertConst(wordget); pDu-kind = CONST; pDu-value = value; return true; /字符常量 case : wordgeti+ = ch; / GetChar(); wordgeti+ = ch; if(ch = ) / n /如果是转义字符则要多接收一个字符 GetChar(); / ch = wordgeti+ = ch; GetChar(); wordgeti+ = ch; wordgeti = 0; if(ch != ) /b printf(%s,wordget); ProcError(2); pDu-kind = ERROR; pDu-value = 0; else value = InsertConst(wordget); pDu-kind = CONST; pDu-value = value; return true; case (: case ): case : case : case .: case ,: case : case ?: case : case ;: case : case : case #: wordgeti+ = ch; wordgeti = 0; pDu-kind = DIVIDE; /界符 pDu-value = -1; return true; case !: /!= wordgeti+ = ch; GetChar(); if (ch=) wordgeti+ = ch; else Retract(); wordgeti=0; break; case : / = wordgeti+ = ch; GetChar(); if (ch = : / = wordgeti+ = ch; GetChar(); if (ch = | ch = =) wordgeti+ = ch; else Retract(); wordgeti=0; break; case =: / = wordgeti+ = ch; GetChar(); if (ch = =) wordgeti+ = ch; else Retract(); wordgeti=0; break; case &: / & &= wordgeti+ = ch; GetChar(); if (ch = & | ch = =) wordgeti+ = ch; else Retract(); wordgeti=0; break; case |: / | |= wordgeti+ = ch; GetChar(); if (ch = | | ch = =) wordgeti+ = ch; else Retract(); wordgeti=0; break; case +: / + += wordgeti+ = ch; GetChar(); if (ch = + | ch = =) wordgeti+ = ch; else Retract(); wordgeti=0; break; case -: / - -= - wordgeti+ = ch; GetChar(); if (ch = - | ch = = | ch = ) wordgeti+ = ch; else Retract(); wordgeti=0; break; case *: / * *= wordgeti+ = ch; GetChar(); if (ch = * | ch = =) wordgeti+ = ch; else Retract(); wordgeti=0; break; case /: / /= wordgeti+ = ch; GetChar(); if (ch = =) wordgeti+ = ch; else Retract(); wordgeti=0; break; case %: / %= wordgeti+ = ch; GetChar(); if (ch = =) wordgeti+ = ch; else Retract(); wordgeti=0; break; case : / = wordgeti+ = ch; GetChar(); if (ch = =) wordgeti+ = ch; else Retract(); wordgeti=0; break; case 0: return false; default: ProcError(1); return false; pDu-kind = OPERAT; return true;int main() Dualistic tmp; pDualistic ptmp = &tmp; FILE *fin, *fout; int i; char c; printf(源代码读入n); /将源程序读入缓冲区 if (fin=fopen(Test.c,r) = NULL) printf(Cannot open infilen); return 0; i = 0; while(c = fgetc(fin) != EOF) if(i = PRO_MAX_LEN-1) printf(n程序代码太长，无法处理a); return 0; proBufferi+ = c; fclose(fin); /关闭文件 proBufferi+ = 0; printf(n*n源代码读入成功，源代码如下:n%s,proBuffer); printf(n按任意键继续n); getch(); /预处理 printf(n预处理n); pretreatment(); printf(n*n预处理成功，去掉注释后的源代码为:n%s*,proBuffer); printf(n按任意键继续n); getch(); printf(n词法分析n); point = 0; /词法分析 if (fout=fopen(Result.txt,wb) = NULL) printf(建立文件Result.txt失败。n); return 0; i = 0; errorLine = 0; /错误行归零 do if(i+ PRO_MAX_LEN)/防止遇到BUG 导致程序死循环无限写文件 break; if(!wordAnalyse(ptmp) break; if (ptmp-value = -1) fprintf(fout, t,ptmp-kind); else fprintf(fout, t,ptmp-kind, ptm