Parallel and Distributed Systems Section

DelftUniversityofTechnologyParallelandDistributedSystemsReportSeriesTheRuleLanguage2.0LeoBreebaartreportnumber:PDS–1997–001PDSISSN1387–2109Publishedandproducedby:ParallelandDistributedSystemsSectionFacultyofInformationTechnologyandSystemsDepartmentofTechnicalMathematicsandInformaticsDelftUniversityofTechnologyZuidplantsoen42628BZDelftTheNetherlandsInformationaboutParallelandDistributedSystemsReportSeries:[e-mail]elandDistributedSystemsSection:©1997ParallelandDistributedSystemsSection,FacultyofInformationTechnologyandSystems,DepartmentofTechnicalMathematicsandInformatics,DelftUniversityofTechnology.Allrightsreserved.Nopartofthisseriesmaybereproducedinanyformorbyanymeanswithoutpriorwrittenpermissionofthepublisher.TheRuleLanguage2.0page1Chapter1—IntroductionThisdocumentdescribesthegrammarofversion2.0oftheRuleLanguage(RL),ashasbeenimplementedintheRotansystem.TheRuleLanguageisaspecialpurposehighlevellanguage,intendedtoprovideaneasy-to-useinterfacefortransformingTmdatastructures.(ForinformationonTm,see[4]and[5].)ThefirstversionsofboththeRotansystemandtheRuleLanguageweredevelopedaspartoftheParToolproject([1],[6]).ThoseversionswerenotyetbasedonTm.Instead,adatastructureformatofourowndevisingwasused,limitingthegeneralapplicabilityofthesystem.ForRL2.0wehave,apartfromadaptingthelanguagetotakethenewTmbasisintoac-count,alsoevaluatedallthepreviousexperienceswithRL1.0(documentedinChapter7of[2]),andasaresultre-designedthelanguagetobebothmorepowerfulandmoreuser-friendly.Forconsistency’ssake,thestructureandstyleofthisdocumentpurposelyresemblesthatoftheVnusLanguageSpecification([4]).Someactualcontenthasbeenborrowedfromthatdocumentaswell,withnodisrespecttotheoriginalauthorintended.ThanksareduetoKeesvanReeuwijk,FritsKuijlmanandHenkSipsfortheirinputandsupportduringallphasesoftheRL2.0andRotandevelopmentprocess.Delft,October1997TheRuleLanguage2.0page2Chapter2—GrammarNotation2.1ThepurposeofthegrammarrulesThegrammaroftheRL(unlessexplicitlyspecifiedotherwisewewillassumeRLmeans:RL2.0)isformallydefinedinappendixA.Throughoutthetext,partsofthisgrammarareshownasillustrations.Fordidacticpurposes,thesepartscansometimesdeviateslightlyfromtheofficialversion.Thetextaccompanyingthegrammarrulesisintendedtoannotateandclarifythelan-guage.Textinitalicsindicatesopenquestionsthatstillneedananswer,orpartsofthelanguagethatwereunimplementedatthemomentofwriting.2.2ThenotationThegrammarconsistsofaseriesofproductions,whereeachproductionspecifiesthederivationofanonterminalsymbolfromterminalsandothernonterminals.Non-terminalsymbolsareshowninanitalicfont,terminalsymbolsareshowninacourierfont.Thedefinitionofanonterminalisintroducedbythenameofthenonterminalbeingde-fined,followedbyacolon.Oneormorealternativeproductionrulesthenfollowonsuc-ceedinglines.Forexample,theproduction:builtinFunctionCall:close(tree)statesthatthenonterminalbuiltinFunctionCallproducestheterminalstring“close(”,followedbythenonterminaltree,followedbytheterminal“)”.Toclarifythemeaningofthelanguageconstruct,itisallowedtoprefixanonterminalwithaname,followedbyadash.Thisprefixisignoredintheinterpretationofthegrammarrules.Forexample,thefollowingproductionisidenticaltothepreviousone:builtinFunctionCall:close(argument-tree)Aproductionmayhavemorethanonealternative;eachalternativeislistedonasepa-rateline,orinaseparateproduction.Forexample,atreehasseveralpossibleproduc-tions:TheRuleLanguage2.0page3tree:simpleTreerule-identifier(tree)tree:builtinFunctionCallThesubscriptedsuffix‘opt’,whichmayappearafteraterminalornonterminal,indicatesanoptionalsymbol.Thissuffixisashorthandfortwogrammarrules,onethatomitstheoptionalelement,andonethatincludesit.Forexample:pattern:domainNodepredicateoptisashorthandfor:pattern:domainNodedomainNodepredicateIfagrammarrulecontainsmorethanoneoptionalsymbol,allcombinationsofpresenceandabsenceofthesymbolsareallowed.Whenallthealternativeproductionsofanonterminalconsistofsingleterminalsym-bols,amorecompactnotationisused,whereallalternativesarelistedinacontiguouslist.Forexample:relationOp:oneof==!=Finally,thesymbol‘λ’denotestheemptyproduction.TheRuleLanguage2.0page4Chapter3—LanguageConstructs3.1CommentsTheRuleLanguagesupportstwoformsofcomment:linecomments,thatstartwith‘//’,andendattheendoftheline;andmulti-linecomments,thatstartwith‘/*’andendwith‘*/’.Commentcannotbenested.3.2Rulesrules:ruleListruleList:ruleruleListruleRulesarelikeCfunctions:allareequalandeachcanbeinvokedseparatelybytheout-sideworld.Thelanguagedoesnotrecogniseorenforcetheconceptofa(file-based)pro-gramasisusuallythecaseinotherprogramminglanguages.ThehierarchicalapproachofRL1.0(rules,drivers,engines)iscompletelygone.Instead,theRLparserseesasourcefileasasequenceofindividualrules.FortheRuleLanguage,differentrun-timesystemsarepossible.ThecurrentRotanim-plementationdefinesaruleinterpreter,whichdynamicallyreadsinarulefile,andmakestheparsedrulesavailableasinstancesoftheRlibclassRuleinanSTLcon-tainer.àWhatisstillneeded(andisinfactcrucialfortheabilitytohandleruleswit