《编译与反编译技术实战 》一3.2 词法分析器的手工实现
本文共 11409 字，大约阅读时间需要 38 分钟。
本节书摘来自华章出版社《编译与反编译技术实战 》一书中的第3章，第3.2节，庞建民 主编 ，刘晓楠 陶红伟 岳 峰 戴超 编著，更多章节内容可以访问云栖社区“华章计算机”公众号查看。
3.2 词法分析器的手工实现
手工构造词法分析器首先需要将描述单词符号的正规文法或者正规式转化为状态转换图，然后再依据状态转换图进行词法分析器的构造。状态转换图是一个有限方向图，结点代表状态，用圆圈表示；状态之间用箭弧连接，箭弧上的标记（字符）代表射出结点状态下可能出现的输入字符或字符类。一张转换图只包含有限个状态，其中有一个为初态，至少要有一个终态（用双圈表示）。大多数程序语言的单词符号都可以用状态转换图予以识别。具体过程如下：
1）从初始状态出发。2）读入一个字符。3）按当前字符转入下一状态。4）重复步骤2～3直到无法继续转移为止。在遇到读入的字符是单词的分界符时，若当前状态是终止状态，说明读入的字符组成了一个单词；否则，说明输入字符串不符合词法规则。这里我们以一个C语言子集作为例子，说明如何基于状态转换图手工编写词法分析器，该语言子集几乎包含了C语言所有的单词符号。主要步骤是，首先给出描述该子集中各种单词符号的词法规则，其次构造其状态转换图，然后根据状态转换图编写词法分析器。表3-1列出了这个C语言子集的所有单词符号以及它们的种别编码。该语言子集所包含的单词符号有：1）标识符：以字母、下划线开头的字母、数字和下划线组成的符号串。2）关键字：标识符的子集，C语言的关键字共有32个（为了测试加入了输入输出函数，共计34个）。3）无符号十进制整数：由0到9数字组成的字符串。4）算符和界符：“{”“}”“[”“]”“（”“）”“.”“->”“～”“++”“--”“!”“&”“*”“/”“%”“+”“-”“<<”“>>”“>”“>=”“<”“<=”“==”“!=”“^”“|”“&&”“||”“?”“=”“/=”“*=”“%=”“+=”“-=”“&=”“^=”“|=”“,”“#”“;”“:”，共计44个。表3-1 C语言子集的单词符号及种别编码
keyword→ void | char | int | float | double | short | long | signed | unsigned | struct | union | enum | typedef | sizeof | auto | static | register | extern | const | volatile | return | continue | break | goto | if | else | switch | case | default | for | do | while | scanf | printf
2）标识符文法：
letter→A | … | Z | a | …| zdigit→0 | 1 | … | 9id→letter rid |- ridrid→letter rid |- rid |digit rid | ε
3）无符号整数文法：
digit→0 | 1 | … | 9digits→digit rdigitrdigit→digit rdigit |ε
4）算符和界符的文法：
op→{ | } | [ | ] | ( | ) | . | -bigger | ~ | +plus | -minus | ! | & | * | / | % | + | - | bigger | > | >equal | < | plus→+minus→-less→ 依据上述文法可得到如图3-2所示的状态转换图。其中，终态上的星号（*）表示此时还要把超前读出的字符退回，即搜索指针回调一个字符位置。在状态2时，所识别出的标识符应先与表的前34项逐一比较，若匹配，则该标识符是一个保留字，否则就是标识符。如果是标识符，则返回相应的种别编码和标识符本身。在状态4时，将识别的常数种别编码和常数值返回。在状态7、12、16、19、23时，为了识别相应的算符需进行超前搜索。
#include#include #include #include #include #include using namespace std;struct symbol{ char * str; int coding;};char *keyword_list[34] = { "void", "char", "int", "float", "double", "short", "long", "signed", "unsigned", "struct", "union", "enum", "typedef", "sizeof", "auto", "static", "register", "extern", "const", "volatile", "return", "continue", "break", "goto", "if", "else", "switch", "case","default","for","do","while","scanf","printf"};char *operator_list[44] = { "{","}","[","]","(",")",".","->","~","++","--","!","&","*","/","%","+","-","<<",">>",">", ">=","<","<=","==","!=","^","|","&&","||","?","=","/=","*=","%=","+=","-=","&=","^=","|=",",","#",";",":"};char ch; //读入的字符char strToken[20] = "";/ /读入的字符串int eof_flag = 0;int num = 1;//编码的数字（为了递增）int row = 1;struct symbol keywords[34];struct symbol identifiers[44];FILE *fp = NULL;FILE *fw = NULL;ofstream out;//给单词符号设定种别编码void initialization() { //给关键字设定种别编码 for (int i = 0;i < 34;i++) { keywords[i].str = keyword_list[i]; keywords[i].coding = num; num++; } //给算符和界符设定种别编码 for (i = 0;i < 44;i++) { identifiers[i].str = operator_list[i]; identifiers[i].coding = num; num++; } //数字79，标识符80}//把下一个字符读入ch中void getNextChar(FILE *ffp){ if ((ch = getc(ffp)) == EOF) { eof_flag = 1; } if (ch == '\n') row++;}//检查ch的字符是否为空白符、回车或者制表符，若是，则反复调用getNextChar ()，直至ch中读入一非上述符号void getbc(FILE * ffp){ while (ch == ' ' || ch == '\n' || ch == '\t') { getNextChar(ffp); }}//判断ch是否为字母bool isLetter(char ch){ return isalpha(ch);}//判断ch是否为数字bool isDigit(char ch){ return isdigit(ch);}//判断ch是否为下划线bool isUnderline(char ch){ if (ch == '_') return 1; else return 0;}//将输入的字符ch连接到strTokenvoid concat(){ char * tmp = &ch; strcat(strToken, tmp);}//把搜索指针回调一个字符位置void retract(FILE * ffp){ fseek(ffp, -1, SEEK_CUR); ch = ' ';}//对于strToken中的字符串判断它是否为保留字，若它是保留字则给出它的编码，否则返回0int reserve_string(char * str) { for (int i = 0;i < 34;i++) { if ((strcmp(str, keywords[i].str)) == 0) { return keywords[i].coding; } } return 0;}//返回strToken中所识别出的算符和界符编码int reserve_operator(char* ch){ for (int i = 0;i < 44;i++) { if ((strcmp(ch, identifiers[i].str)) == 0) { return identifiers[i].coding; } } return 0;}//出错处理void error(){ printf("\n ********Error*********************\n"); printf(" row %d Invaild symbol ! ! ! ", row); printf("\n ********Error*********************\n"); exit(0);}//词法分析void LexiscalAnalyzer(){ int num = 0, val = 0, code = 0; strcpy(strToken, ""); getNextChar(fp); getbc(fp); switch (ch) { case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'g': case 'h': case 'i': case 'j': case 'k': case 'l': case 'm': case 'n': case 'o': case 'p': case 'q': case 'r': case 's': case 't': case 'u': case 'v': case 'w': case 'x': case 'y': case 'z': case 'A': case 'B': case 'C': case 'D': case 'E': case 'F': case 'G': case 'H': case 'I': case 'J': case 'K': case 'L': case 'M': case 'N': case 'O': case 'P': case 'Q': case 'R': case 'S': case 'T': case 'U': case 'V': case 'W': case 'X': case 'Y': case 'Z': case '_': while (isLetter(ch) || isDigit(ch) || isUnderline(ch)) { concat(); getNextChar(fp); } retract(fp); code = reserve_string(strToken); if (code = = 0) { printf("(%d , %s)\n", 79, strToken); } else { printf("(%d , %s)\n", code, strToken); } break; case'0': case'1': case'2': case'3': case'4': case'5': case'6': case'7': case'8': case'9': while (isdigit(ch)) { concat(); getNextChar(fp); } retract(fp); printf("(%d , %s)\n",80, strToken); break; case '{': concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); break; case '}': concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); break; case '[': concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); break; case ']': concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); break; case '(': concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); break; case ')': concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); break; case '.': concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); break; case '-': concat(); getNextChar(fp); if (ch == '>') { concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); } else if (ch == '-') { concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); } else if (ch == '=') { concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); } else { retract(fp); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); } break; case '~': concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); break; case '+': concat(); getNextChar(fp); if (ch == '+') { concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); } else if (ch == '=') { concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); } else { retract(fp); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); } break; case '*': concat(); getNextChar(fp); if (ch == '=') { concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); } else { retract(fp); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); } break; case '&': concat(); getNextChar(fp); if (ch == '=') { concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); } else if (ch == '&') { concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); } else { retract(fp); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); } break; case '!': concat(); getNextChar(fp); if (ch == '=') { concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); } else { retract(fp); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); } break; case '%': concat(); getNextChar(fp); if (ch == '=') { concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); } else { retract(fp); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); } break; case '<': concat(); getNextChar(fp); if (ch == '=') { concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); } else if (ch == '<') { concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); } else { retract(fp); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); } break; case '>': concat(); getNextChar(fp); if (ch == '=') { concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); } else if (ch == '>') { concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); } else { retract(fp); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); } break; case '=': concat(); getNextChar(fp); if (ch == '=') { concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); } else { retract(fp); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); } break; case '^': concat(); getNextChar(fp); if (ch == '=') { concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); } else { retract(fp); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); } break; case '|': concat(); getNextChar(fp); if (ch == '=') { concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); } else if (ch == '|') { concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); } else { retract(fp); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); } break; case '?': concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); break; case '/': concat(); getNextChar(fp); if (ch == '=') { concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); } else if (ch == '/') //跳过注释 { getNextChar(fp); while (ch != '\n') { getNextChar(fp); } break; } else if (ch == '*')//跳过注释 { getNextChar(fp); while (ch != '*') { getNextChar(fp); } getNextChar(fp); if (ch == '/'); break; } else { retract(fp); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); } break; case ',': concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); break; case '#': concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); break; case ';': concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); break; case ':': concat(); code = reserve_operator(strToken); printf("(%d , %s)\n", code, strToken); break; default: if (ch == EOF) { eof_flag = 1; break; } error(); }}//主函数int main(){ initialization(); char name[1024]; cout<<"从文件读入："; cin>>name; fp=fopen(name,"r"); out.open("result.txt"); while(!feof(fp)) { if (eof_flag == 1) { exit(1); } LexiscalAnalyzer(); } fclose(fp); out.close(); return 0;}
转载地址：http://msyyo.baihongyu.com/
你可能感兴趣的文章
Android上成功实现了蓝牙的一些Profile
查看>>
基于jQuery图片自适应排列显示代码
查看>>
NEURAL NETWORKS, PART 1: BACKGROUND
查看>>
jquery对同级的td做radio限制
查看>>
Delphi XE5 常用功具与下载
查看>>
存储过程由结构表生成表
查看>>
C# 批处理制作静默安装程序包
查看>>
柯南君：看大数据时代下的IT架构（5）消息队列之RabbitMQ--案例（Work Queues起航）...
查看>>
2015 Multi-University Training Contest 2 1002 Buildings
查看>>
java 产生的固体物的基础上 增删改的SQL声明
查看>>
在自己的网站添加关注新浪关注按钮
查看>>
【MySQL笔记】mysql来源安装/配置步骤和支持中国gbk/gb2312编码配置
查看>>
一句话的设计模式(转)
查看>>
（剑指Offer）面试题54：表示数值的字符串
查看>>
Centos下安装mysql 总结
查看>>
ORM武器：NHibernate（三）五个步骤+简单对象CRUD+HQL
查看>>
UIScrollView offset in UINavigationController
查看>>
怎么从sqlserver 数据库导出 insert 的数据语句
查看>>
BZOJ4245 : [ONTAK2015]OR-XOR
查看>>
Android Properties 存储
查看>>