一种实现Thompson算法的新方法  

A New Method of Realizing Thompson algorithm in Lexical Analysis

作　　者：黄贤英[1] 陈薇薇[1] 

机构地区：[1]重庆理工大学,重庆400050

出　　处：《重庆工学院学报（自然科学版）》2009年第9期81-83,114,共4页Journal of Chongqing Institute of Technology

基　　金：重庆市自然科学基金资助项目(CSTC;2007BB2405)

摘　　要：介绍了Thompson算法的基本思想,提出一种利用算符优先关系表来实现Thompson算法的方法,以实现正规式到有穷自动机的转换.描述了算法的解决思路、算符优先表的生成和NFA的表示.算法测试表明,该方法可以大大简化算法的实现,提高编译程序的工作效率.Lexical analysis is the foundation of a compiler. Its typical realization is to express the wordconstructing rule using the regular expression, then translate it to NFA and DFA, last analyze the words of the source programmer. Thompson algorithm is an effect algorithm to translate a given expression to an equivalent NFA. But it＇s difficult to realize it using advanced regular language （ e. g. C language）. This paper introduces a method using operator-first relation table to realize it. Experiment shows that this method simplifies the programming and boosts the efficiency of the compiler.

关 键 词：编译程序 正规式 有穷自动机 Thompson方法 算符优先 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]