A Reusable Object-Oriented Approach to Formal Spec

AReusableObject-OrientedApproachtoFormalSpecificationsofProgrammingLanguages0DUMDQ0HUQLN0LWMD/HQLa(QLV$YGLaDX^HYL`9LOMHP#XPHUUniversityofMariborFacultyofElectricalEngineeringandComputerScienceSmetanova17,2000Maribor,[e-mail]ngprogramminglanguagesemanticsareanexcellenttoolforprogramminglanguagedesignanddevelopment.However,theyarenotwidelyusedsincetheyarenotmodular,extensibleandreusable.Inthepaperanewmodular,extensibleandreusableapproachforspecifyingprogramminglanguageswithattributegrammarsispresented.Theconceptsofobject-orientedprogramming,i.e.templates,multipleinheritance,andobject-orientedimplementationofsemanticdomains,areintegratedwithattributegrammars.Withtheproposedapproachalanguagedesignerhasthechancetodesignincrementallyalanguageorreusesomefragmentsfromotherprogramminglanguagespecifications.TheproposedapproachhasbeenimplementedinourcompilergeneratortoolLISAver.2.0.MOTS-CLES:KEYWORDS:languagespecifications,reusability,extensibility,attributegrammars,compilergenerators2Documentnumérique.Vol.1-n°1/19971IntroductionCompilerconstructionisoftenmentionedasoneofthefewreallysystematicallymanageddisciplines.Thereisalongtraditionofproducingcompilers,underlyingtheoriesarewellunderstoodandthereexistmanyapplicationgeneratorswhichautomaticallyproduceacompileroraninterpreterfromtheformalprogramminglanguagespecification.Formalmethodsforprogramminglanguagedescriptionalsoserveasatoolforprogramminglanguagedevelopmentanddesign.Theprogramminglanguageswhichhavebeendesignedwithoneofthevariousformalmethodshaveabettersyntaxandsemantics,lessexceptionsandareeasiertolearn.However,despiteoftheobviousadvantages,noneofthecurrentlymostwidelyusedformalmethodsforprogramminglanguagedescription,suchasdenotationalsemantics,operationalsemantics,axiomaticsemantics,orattributegrammars,havegainedmorepopularityandgeneraluse.Somereasonsforthisare:semanticsismuchmoredifficulttodescribethanthesyntax,andsemanticsdescriptionisnoteasytoread.Weareconvincedthattherealproblemwiththeseformalmethodsisthelackofmodularity,extensibilityandreusability.Sinceprogramminglanguagedesignisaniterativeprocess,designersneedpartialdescriptionsthatcanbeeasilyreused,extendedandmodified.Inthepaperanewapproachtomodularity,extensibilityandreusabilityofattributegrammarsispresented.AttributegrammarshavebeenintroducedbyD.E.Knuth[KNU68]andsincethenareproventobeusefulinspecifyingthesemanticsofprogramminglanguages,inautomaticconstructingofcompilers/interpreters,inspecifyingandgeneratinginteractiveprogrammingenvironmentsandinmanyotherareas.Attributegrammarsareageneralizationofcontext-freegrammarsinwhicheachsymbolhasanassociatedsetofattributesthatcarrysemanticinformation,andwitheachproductionasetofsemanticruleswithattributecomputationisassociated.Inattributegrammarssemanticsisgiveninadeclarativeratherthananoperationalnotation.However,ordinaryattributenotationhasdeficiencieswhichbecomeapparentinspecificationsforrealprogramminglanguages.Suchspecificationsarelarge,unstructuredandarehardtounderstand,modifyandmaintain.Therefore,inrecentyears,theresearchonattributegrammarshasshiftedfromtheoreticalinvestigationstoimprovingattributegrammarsasamethodology,andtodesigningsystemswithmajoremphasisonpragmaticissues[PAA95].Inthispaperanewapproachthatovercomesthedrawbacksofordinaryattributegrammarsispresented.Theconceptsfromobject-orientedprogramming,i.e.template,multipleinheritance,andobject-orientedimplementationofsemanticdomains,areintegratedwithattributegrammars.Withtemplatesweareabletodescribethesemanticruleswhichareindependentofgrammarproductionrules.Specificationswithtemplatesarereusable,shorterandeasiertoreadandmaintain.Withmultipleinheritanceweareabletoorganizespecificationsinsuchawaythatspecificationscanbeinheritedandspecializedfromancestorspecifications.Multipleattributegrammarinheritancesupportsreusabilityandextensibilityofattributegrammars.Withobject-orientedimplementationofsemanticdomainsweareabletoreusevarioussemanticdomainsinimplementingdifferentprogramminglanguagesbyinheritanceoraggregation.Thepaperisanextensionofthepaper[MER98].Reusablesyntaxandsemanticspecificationsarepresentedinsections2and3.Furtheron,insection4,ourimplementationandexperiencearebrieflydescribed.Insection5relatedworkisDocumentnumérique.Vol.1-n°1/19973described.Itisfollowedbytheconclusioninsection7.ApartofspecificationsforPLMlanguageispresentedinappendix.Weassumethatthereaderisfamiliarwithattributegrammars.2ReusablesyntaxspecificationsInformalmethodsforprogramminglanguagedescription(regularexpressions,BNFandattributegrammars)wearelookingforcomponentswhichcanbereusedinthespecificationforanotherprogramminglanguage.InformalspecificationsofprogramminglanguageitiseasytonoticethatthemainpartofsuchaspecificationconsistsofthesemanticspecificationandthemuchsmallerpartconsistsofBNFandregularexpressions.Therefore,ourattentioninsearchingforreusablecomponentswasmainlyfocusedonsemanticspecifications.Sincesemanticscannotbedefinedwithoutthesyntax,alsothere