资源描述：
《自动词法分析程序生成器LEX的实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、型微垫计算机系统第!春第!期啤小自动词法分析程序生成器∀#∃的实现张豪煌荣广颐,%中国纺织大学自动化系侧试中心&摘要从正则式,∋的最小出发逐步构造能够识别这些正则式所定义的单词列(、确,,定有限自动机是∀#∃的核心工作它包括有自动机化确定化和最小化三个算法。本。,∀#∃,文具体给出了它们的实现显然通过这样具体地介绍的实现技术对,、于解决许多可归结或部分可归结为正则式识别的问题诸如何法分析模式识别和·,、。文本编挥等具有实际的指导意义),,,,,∀#.。关键词正则式单词词法分析∗+,−+,一、概述,/,∀
2、,。∀#∃是一种生成器它能根据输入的词分规格自动地生成相应的词分程序见图0,,具体而言词分规格/由一系列的二元组%1,&组。、,∀#成其中1是用正则式表示的词分程序所需识别单词的模∋∀·,,是当识别出模式。式1后词分程序应做的语义动作通——,12图∀#∃自动生成侧分程序常语义动作,将给具有模式的单词返回一个指示值有,。时它还要做填写符号表%当遇到标识符时&等额外工作,,从正则式出发逐步构造能够识别这些正则式所定义的单词列的最小确定有限自动机,一是∀#.的核心工作它主要包括以下三个算法)从正则式3#转
3、换到∗+,的正则式自动机化,,,,),了算祛从∗+,转换到−+,的自动机确定化算法从−+,转换到−+,的自动机状态数。。认目最小化算法,/见图43#’5队摘‘’〕队一’忿印舀舀舀‘图4逐步构造识别3#的−+人,,()、,)和,6。在以后各节中将分别给出算法的实现、)二自动机化算法,),、’·’,,’’、作为输入,的正则式3#由字母表公中各符号%并通常省略&7%或者&一4一,。:。闭包&以及左右圆括号按照一定规律组合而成具体定义可参见〔」〕如%809&的9(,’(’。,:·通常位于右上方井省略为了处理方便起
4、见可考虑把它表示成形式%8;9&8(9(玩以后的示例将沿用这个正则式。,))可分解为如下两部分工作(,8(。··邓逆波兰化成3#,%如上例9099(&(,,。4据3#,循自小至大原则滚雪球似地构造∗+,,,),,有必要指出的一点是这种对的二分法并不是必要的恰恰相反实际编程时完全可)。以把它们合起来以产生一个较为高效的,程序现在把它们分解开来的唯一目的是为了把,。,,,注意力集中到关键之处以便更清晰地说明问题实际上用算符优先法循下述二规则3#)可简便地将逆波兰化(,’’。’,。’,双目符7和优先级相同且低
5、于单目符(‘,‘’‘’,‘’。4遇%,入栈遇&则退出栈中各算符至紧邻的&且退&<,设和=分别表示子自动机∗的初态及终态最终的∗+,是在初始的子自动机基础上经一。)。系列的递归扩充而成的,算法可概要地表述如图6容易看出采用上述较为保守的方法产生出∗)的+,具有如下三个特性(只有一个初态和终态,(,’,4当翰入符号为八%空&时任一状,态最多只有两条出弧当输入符号为4(∗一2∗?,。字母表中的字母时只有一条出弧(,(’(6不计并符设3#,串共有>个字,>。符则对应的∗+,有?个状态因而,可以采用三个≅4>的数
6、组/ΑΒ9(6(止(∗?、、。∗Χ.Δ∗Χ.Ε?来表示∗+,状态<由三元组ΑΒ9〔<〕,Χ笼Ε,Γ.Ε,%Φ∗0〔<〕∗?〔<〕&表示其ΙΗ凡0<,中ΦΑ川9〔<〕表示状态的输入符号∗Χ.Ε0〔<〕和、洲陌二Ε4〔幻指示状态0出弧转向的状态若状态<只,。。有一条出孤则∗Χ.Ε4%<〕置。参见图Η圈6算法人思扭示Ε栈ΦΔ1,存放构造过程中的一系列子冰,,,/Δϑ。,,自动机以初终态对%<=&形式存贮9∗+,栈的指针为过程1Δ/Κ%<=&压子自动机,。。。,%<Λ&入栈1Γϑ,过程则把栈顶的子自动机弹出Μ
7、指示串3#’的当前位置∗ΓΝ从开始?。逐步增至>用以作各状态的编号ΧΕ8ΕΧΓ,/ΑΒ,.:,.Ε,Γ,.Ε,.Ε。过程ΦΦΕ%∗∗0∗?&将状态∗各域依次置成ΦΑΒ∗0∗?。转向。表示未定义,,),,),ϑΟ0,对于上例的正则式运用算法得到的∗+冉表示如图Η所示,终止时/Δ+,ϑ〕(/Δ(=+Π.,0。咖〔和9∗+,〔ϑ〕分卿0给出结果∗的初态和终态+本例它们分另提Θ和4Η)人ϑ十。,Μ,Γ,∗ΧΓ,ΓΝΡ3#1#,ΣΡ,。‘,ΜΡΜ,3#〔Μ〕/七艺ΣΥ#∗Τ+一44一仑它心Τ∗ΧΧΡ乏,∗ΓΝ
8、,∗记Χ一<,8,,。,ΦΧΦΕ8触%∗目∗必&Χ一,Χ,1“卜%∗闭∗阅&ςΩΣΩ切Ν/ΙΙ#∗−Τ+,二,ΛΣΥ#∗Ξ#ςΤ∗∗闭ΧΧΡ4,,∗冈Χ一.,‘,Δ一(,(旋侣加加%∗ΓΝΦ9∗+,〔ϑ〕Φ山∗+,〔约&一。,‘,Χ,,决侣切触《Φ曲∗+人〔ϑ均=∗讨&决Ε%Φ(9∗+,〔约(=,》,∗Χ,。&,匕咖ΓΝ1,1叩一1Δ%∗Χ一盆,∗司Χ&,叩血ΓΝςΩΣΩΧ>Ν/,Ι#∗−,二,。,
