The design and implementation of the FIRE engine A

ThedesignandimplementationoftheFIREengine:AC++toolkitforFIniteautomataandRegularExpressionsBruceW.WatsonFacultyofMathematicsandComputingScienceEindhovenUniversityofTechnologyP.O.Box5135600MBEindhovenTheNetherlandsemail:[e-mail]17,1994AbstractThispaperdescribesthedesignandimplementationofversion1.1oftheFIREengine.TheFIREengineisaC++classlibraryimplementingniteautomataandregularexpressionalgorithms.Thealgorithmsimplementedinthetoolkitarealmostallofthosepresentedinthetaxonomiesofniteautomataalgorithms[Wat93a,Wat93b].ThereaderisassumedtobefamiliarwiththetwotaxonomiesandwithadvancedC++programmingtechniques.Thetoolkitisimplementedlargelyinanobject-orientedstyle,withniteautomataandregularexpressionsbeingdenedasclasses.Alloftheclassesandfunctionsinthetoolkitarepresentedinthesameformat.Foreachclass(orfunction)theformatincludesashortdescriptionofitsbehaviour,detailsofitsimplementation,andtechniquesforimprovingitsperformance.CONTENTSContents1Introduction31.1Codingconventionsandperformanceissues::::::::::::::::::::::31.1.1Performancetuning:::::::::::::::::::::::::::::::41.2Presentationconventions:::::::::::::::::::::::::::::::::4IFoundationclasses52Characterranges53Bitvectors154Statesandrelatedclasses245Transitionsandrelatedclasses356Relations47IIRegularexpressionsand-algebras677Regularexpressions677.1SimilarityofREs:::::::::::::::::::::::::::::::::::::757.2Derivatives::::::::::::::::::::::::::::::::::::::::838The-algebra848.1The-termalgebraRegRE:::::::::::::::::::::::::::::86IIIAutomataandtheircomponents899Abstractniteautomata8910DeterministicFAs9111ConstructingaDFA9811.1Abstractstatesandthesubsetconstruction::::::::::::::::::::::9811.2Derivativesofregularexpressions::::::::::::::::::::::::::::10311.3Itemsets:::::::::::::::::::::::::::::::::::::::::10712Finiteautomata12112.1The-algebraRegFA::::::::::::::::::::::::::::::::12813Reducedniteautomata13313.1The-algebraRegRFA::::::::::::::::::::::::::::::::14414Left-biasedniteautomata14715Right-biasedniteautomata15416Automataconstructions161IVMinimizingDFAs165CONTENTS17Helperfunctions16618Aho,Sethi,andUllman’salgorithm16819HopcroftandUllman’salgorithm17020Hopcroft’salgorithm17321Anewminimizationalgorithm175References17831IntroductionTheFIREengineisaclasslibraryimplementingniteautomataandregularexpressionalgo-rithms.Thealgorithmsimplementedareallofthealgorithmspresentedinthetaxonomiesofniteautomataalgorithms[Wat93a,Wat93b].Thispaperoutlinesthedesignandimplementationoftheclasslibrary,whichconsistsof9000linesofC++code.Anumberofothertoolkits(mostlyservingdierentpurposes)areavailable;theyaredetailedin[Wat94],whichalsocontainsanintroductiontotheFIREengine.InordertounderstandtheimplementationoftheFIREengine,thereaderisassumedtobefamiliarwiththetaxonomies[Wat93a,Wat93b],andwithC++terminologyandprogrammingtechniques.AnintroductiontotheC++languagecanbefoundin[Lip91,Str91](thelanguagereferenceappearsin[Str91,SE90]),whileanintroductiontoC++programmingtechniquescanbefoundin[Bud94].AdvancedC++programmingtechniquesarepresentedin[Cop92,MeS92,Mur93].Object-orientedprogramming,ingeneral,isdiscussedin[Boo94,Bud91,MeB88].Themosteectivewaytounderstandtheimplementationoftheclasslibraryistoreadthecodeandthecommentsembeddedwithinthecode.Theexplanationsgiveninthispaperareintendedasanoutline,toassistinunderstandingthecode.Thispaperisstructuredasfollows:PartIprovidesdescriptionsofallofthefoundationsclasses|thoseclassesusedintheimplementationsofotherclasses.PartIIgivesdescriptionsofallclassesrelatedtoregularexpressionsand-algebras.PartIIIgivesdescriptionsofallclassesimplementingniteautomata.PartIVpresentsthefunctionsimplementingdeterministicniteautomataminimizationalgorithms.Acknowledgements:Iwouldliketothankthefollowingpeoplefortheirassistanceinthepreparationofthispaper:Pieter’tHoen(forimplementingtwoofthealgorithmsfrom[Wat93b]),andKeesHemerik,ErikPoll,NanetteSaes,andGerardZwaan(forprovidingstylesuggestionsonthispaper).1.1CodingconventionsandperformanceissuesThetoolkitiscodedinastylewhichmakesheavyuseoftheassertfunction.Forallexceptthesimplestclasses,amemberfunctioncalledclassinvariantisdened;thismemberreturns1iftheobjectisstructurallysound,and0otherwise.Allmemberfunctionswhicharevisibletoclientsshouldonlybeinvokedonstructurallysoundobjectsandmustleavetheobjectinastructurallysoundcondition.Thefunctioncallassert(classinvariant())isexplicitlyinvokedatthebeginingandendofallsuchmemberfunctions(except,ofcourse,thefunctionclassinvariant).Thedenitionoftheclassinvariantisausefulstartingpointforunderstandingthestructureandimplementationofaparticularclass.Additionalassertionsareusedinplaceswheretheincorrectvaluesofvariables(orrelationsbetweenvariables)willcausecatastrophicresults(i.e.themachineislikelytocrash).Assertionsarealsousedinplaceswheretheymaybeofuseinunderstandingthesurroundingcode.Asmentionedbelow,assertcanbedisabledbycompilingwiththemacroNDEBUGdened|meaningthatthereisnoassertionoverheadinaproductionversionoftheFIREengine.Almostalloftheclasseshaveanostreami