神马文学网CSDN技术中心 编译原理
来源：百度文库 编辑：神马文学网 时间：2024/04/28 07:05:20
编译原理_使用哈希表给词法识别加速 选择自csumck 的 Blog
关键字 编译原理_使用哈希表给词法识别加速
出处
昨天和同学讨论词法分析的状态机制的效率问题，我写的词法分析器查找状态是使用遍历查找，效率太低。想到在《编译原理与实践》一书中提到了使用折半查找和哈希表映射。
下面是我的转台转化机制的主要代码：
//状态机状态枚举
typedef enum {PLUS,MINUS,MULTI,DIVIDE,NUMBER,IDENTI,JINGHAO,COMMENT,IF,ELSE,END,REPEAT,UNTIL,ASSIGN,EQUAL,LESS,GREATER,LPAREN,RPAREN,SEMI,EXPRESSION,START,UNKNOWN} LexTokenType;
//状态转换结构
typedef struct {LexTokenType beg; char Domainbeg; char Domainend; LexTokenType end;} TransState;
//有限状态机状态转换描述
TransState trans[] ={
{NUMBER,‘0‘,‘9‘,NUMBER},
{IDENTI,‘A‘,‘Z‘,IDENTI},
{IDENTI,‘a‘,‘z‘,IDENTI},
{IDENTI,‘0‘,‘9‘,IDENTI},
{START,‘ ‘,‘ ‘,START},
{START,‘\t‘,‘\t‘,START},
{START,‘\n‘,‘\n‘,START},
{START,‘\r‘,‘\r‘,START},
{START,‘0‘,‘9‘,NUMBER},
{START,‘A‘,‘Z‘,IDENTI},
{START,‘a‘,‘z‘,IDENTI},
{START,‘+‘,‘+‘,PLUS},
{START,‘-‘,‘-‘,MINUS},
{START,‘*‘,‘*‘,MULTI},
{START,‘/‘,‘/‘,DIVIDE},
{START,‘<‘,‘<‘,LESS},
{START,‘>‘,‘>‘,GREATER},
{START,‘(‘,‘(‘,LPAREN},
{START,‘)‘,‘)‘,RPAREN},
{START,‘;‘,‘;‘,SEMI},
{START,‘=‘,‘=‘,ASSIGN},
{DIVIDE,‘/‘,‘/‘,COMMENT},
{COMMENT,‘\n‘,‘\n‘,START},
{COMMENT,‘\n‘+1,127,COMMENT},
{COMMENT,1,‘\n‘-1,COMMENT},
{COMMENT,-128,-1,COMMENT},//为支持汉字注释
{ASSIGN,‘=‘,‘=‘,EQUAL},
};
上面的代码中共列举了27中状态转换。最坏情况下，程序将遍历全部27种转换。效率在这里大打折扣。
哈希函数的确定：
我们的查找过程主要是比较输入字符，因此可将输入字符作为查找项的主关键字。由于不同状态也会输入相同字符，所以将初始状态也作为关键字。我们用下面的代码生成一个函数映射。
int size = sizeof(trans)/sizeof(TransState);
for(int i=0; i{cout<<((int)trans[i].beg+(int)trans[i].Domainbeg+(int)trans[i].Domainend)<注意到每两种转换的输入范围至少会相差2，因此使用下面的代码：
for(int i=0; i{cout<<((int)trans[i].beg+(int)trans[i].Domainbeg+(int)trans[i].Domainend)/2+64<输出为：
118
144
176
119
106
83
84
87
127
152
184
117
119
116
121
134
136
114
115
133
135
112
77
136
72
3
131
((int)trans[i].beg+(int)trans[i].Domainbeg+(int)trans[i].Domainend)/2+64的范围在0到300多之间，用这样大的表就可存放哈希表。上面输出的最大值为184，所以关键字大与184的不用查表也知道不存在相应的转换。这样哈希表的大小缩小在184。为了支持汉字注释，状态机中允许出现扩展ACII字符。如果把这一要求去掉，我们的哈希表可缩小到127。
作者Blog：http://blog.csdn.net/csumck/
相关文章
自己写的线程池类(使用C++,pure API,Mutex,Event)
编译原理_使用哈希表给词法识别加速
编译原理_语法分析部分
编译原理_词法分析部分
操作系统——PCB模拟代码
关键字 编译原理_使用哈希表给词法识别加速
出处
昨天和同学讨论词法分析的状态机制的效率问题，我写的词法分析器查找状态是使用遍历查找，效率太低。想到在《编译原理与实践》一书中提到了使用折半查找和哈希表映射。
下面是我的转台转化机制的主要代码：
//状态机状态枚举
typedef enum {PLUS,MINUS,MULTI,DIVIDE,NUMBER,IDENTI,JINGHAO,COMMENT,IF,ELSE,END,REPEAT,UNTIL,ASSIGN,EQUAL,LESS,GREATER,LPAREN,RPAREN,SEMI,EXPRESSION,START,UNKNOWN} LexTokenType;
//状态转换结构
typedef struct {LexTokenType beg; char Domainbeg; char Domainend; LexTokenType end;} TransState;
//有限状态机状态转换描述
TransState trans[] ={
{NUMBER,‘0‘,‘9‘,NUMBER},
{IDENTI,‘A‘,‘Z‘,IDENTI},
{IDENTI,‘a‘,‘z‘,IDENTI},
{IDENTI,‘0‘,‘9‘,IDENTI},
{START,‘ ‘,‘ ‘,START},
{START,‘\t‘,‘\t‘,START},
{START,‘\n‘,‘\n‘,START},
{START,‘\r‘,‘\r‘,START},
{START,‘0‘,‘9‘,NUMBER},
{START,‘A‘,‘Z‘,IDENTI},
{START,‘a‘,‘z‘,IDENTI},
{START,‘+‘,‘+‘,PLUS},
{START,‘-‘,‘-‘,MINUS},
{START,‘*‘,‘*‘,MULTI},
{START,‘/‘,‘/‘,DIVIDE},
{START,‘<‘,‘<‘,LESS},
{START,‘>‘,‘>‘,GREATER},
{START,‘(‘,‘(‘,LPAREN},
{START,‘)‘,‘)‘,RPAREN},
{START,‘;‘,‘;‘,SEMI},
{START,‘=‘,‘=‘,ASSIGN},
{DIVIDE,‘/‘,‘/‘,COMMENT},
{COMMENT,‘\n‘,‘\n‘,START},
{COMMENT,‘\n‘+1,127,COMMENT},
{COMMENT,1,‘\n‘-1,COMMENT},
{COMMENT,-128,-1,COMMENT},//为支持汉字注释
{ASSIGN,‘=‘,‘=‘,EQUAL},
};
上面的代码中共列举了27中状态转换。最坏情况下，程序将遍历全部27种转换。效率在这里大打折扣。
哈希函数的确定：
我们的查找过程主要是比较输入字符，因此可将输入字符作为查找项的主关键字。由于不同状态也会输入相同字符，所以将初始状态也作为关键字。我们用下面的代码生成一个函数映射。
int size = sizeof(trans)/sizeof(TransState);
for(int i=0; i
for(int i=0; i
118
144
176
119
106
83
84
87
127
152
184
117
119
116
121
134
136
114
115
133
135
112
77
136
72
3
131
((int)trans[i].beg+(int)trans[i].Domainbeg+(int)trans[i].Domainend)/2+64的范围在0到300多之间，用这样大的表就可存放哈希表。上面输出的最大值为184，所以关键字大与184的不用查表也知道不存在相应的转换。这样哈希表的大小缩小在184。为了支持汉字注释，状态机中允许出现扩展ACII字符。如果把这一要求去掉，我们的哈希表可缩小到127。
作者Blog：http://blog.csdn.net/csumck/
相关文章
自己写的线程池类(使用C++,pure API,Mutex,Event)
编译原理_使用哈希表给词法识别加速
编译原理_语法分析部分
编译原理_词法分析部分
操作系统——PCB模拟代码
CSDN技术中心 编译原理
1CSDN技术中心 编译原理
google搜索原理论文 - web开发 - CSDN技术中心
CSDN技术中心 Log4j
CSDN技术中心 Log4Net使用指南
CSDN技术中心 正则表达式
CSDN技术中心 数据压缩技术简史
CSDN技术中心 Windows管道技术简述
编译原理
csdn技术中心 mysql 性能优化
csdn技术中心 自己写ant task
CSDN技术中心 再再论指针----篇首语
CSDN技术中心 Java打印程序设计
CSDN技术中心 试用Nutch (1)
CSDN技术中心 INTEL 汇编指令集
Annotation简介 - java - CSDN技术中心
JAVA字符集 - java - CSDN技术中心
CSDN技术中心-网络最经典命令行
CSDN技术中心 Java NIO API详解
CSDN技术中心 oSIP开发者手册
CSDN 文档中心：Java规则引擎工作原理及其应用
csdn技术中心 sip和isup协议互通的研究
csdn技术中心 delphi中资源文件使用详解
CSDN技术中心 Linux以及各大发行版介绍