一种实现Thompson算法的新方法.doc

一种实现Thompson算法的新方法 第23卷 Vo1.23 第9期 NO.9 重庆工学院(自然科学) JournalofChongqingInstituteofTechnology(NaturalScience) 2009年9月 Sep.2009 一 种实现Thompson算法的新方法 黄贤英,陈薇薇 (重庆理工大学,重庆400050) 摘要:介绍了Thompson算法的基本思想,提出一种利用算符优先关系表来实现Thompson 算法的方法,以实现正规式到有穷自动机的转换.描述了算法的解决思路,算符优先表的生成和 NFA的表示.算法测试表明,该方法可以大大简化算法的实现,提高编译程序的工作效率. 关键词:编译程序;正规式;有穷自动机;Thompson方法;算符优先 中图分类号:TP301文献标识码:A文章编号:1671—0924(2009)09—0081—03 ANewMethodofRealizingThompsonalgorithminLexicalAnalysis HUANXian—ying.CHENWei-wei (ChongqingUniversityofTechnology,Chongqing400050,China) Abstract:Lexicalanalysisisthefoundationofacompiler.Itstypicalrealizationistoexpresstheword— constructingruleusingtheregularexpression,thentranslateittoNFAandDFA,lastanalyzethewords ofthesourceprogrammer.Thompsonalgorithmisaneffectalgorithmtotranslateagivenregular expressiontoanequivalentNFA.Butit,sdifficulttorealizeitusingadvancedlanguagefe.g.C language).Thispaperintroducesamethodusingoperator—firstrelationtabletorealizeit.Experiment showsthatthismethodsimplifiestheprogrammingandbooststheefficiencyofthecompiler. Keywords:compiler;regularexpression;NFA;thompsonalgorithm;operatorfirst 词法分析在高级语言编译过程中占有非常重 要的地位,主要任务是判断给定的符号串是否符 合语言的构词规则.主要有2种表示单词构成规 则的工具:正规式和有穷自动机.正规式在编译程 序中用来描述语言中单词的词法结构;有穷自动 机主要用来识别某符号串是否符合单词的构成规 则,即用来判定某符号串是否是某语言的一个单 词.二者在描述单词构成规则上是等价的【1J. 在构造某种语言的词法分析程序时二者的作 用如图1所示.首先是用与自然语言描述相对接 近的正规式来描述,然后将正规式转换为NFA,经 确定化为DFA,再最小化为最小DFA,最小DFA 就可以方便地转换为词法分析程序. 圣薹兰萎 收稿日期:2009—04-f8 基金项目:重庆市自然科学基金资助项目(CSTC,2007BB2405). 作者简介:黄贤英(1967一),女,重庆人,博士,教授,主要从事软件工程应用研究. 82重庆工学院 可见,实现正规式到NFA的转换是词法分析 程序实现中重要的一步,其运行效率直接影响词 法分析程序的生成效率.本文中将算符优先方法 应用到Thompson算法的实现上,实现正规式到 NFA的转换,大大提高了词法分析程序的生成 效率. 1Thompson算法的基本思想 1.1正规式和有穷自动机的概念 正规式是一组定义规则,由更简单的正规式 构成,每个正规式r表示一个语言(r).正规式有 3种最基本的关系:连接关系C=A-B;或 关系C=AlB;闭包:l:关系C=A,表示A出 现零次或多次.另外的关系都可以由这3种关系 合成.如C语言中标识符的正规式定义为由下划 线或字母开头,后跟若干个下划线,字母或数字的 组合,用正规式表示为:ID=(下划线I字母)? (下划线I字母I数字).形式语言的理论告诉我 们:正规式可以转换成为一张转换图,即有穷自 动机. 有穷自动机理论是描述词法规则的基本理 论.NFA可以看作一种特殊的有穷自动机,它是带 有原始内部存储的机器的抽象模型.一个NFA可 以表示成一个5元组:N=(S,∑,m,oy,F,sO), 其中:Js为有穷状态集合;∑为有穷输入