Defining and parsing visual languages with layered

PARSINGVISUALLANGUAGESWITHLAYEREDGRAPHGRAMMARS1DefiningandParsingVisualLanguageswithLayeredGraphGrammars1J.REKERS*ANDA.SCH¨URRy*DepartmentofComputerScience,LeidenUniversity,NielsBohrweg1,2333CALeiden,TheNetherlands,[e-mail],andyLehrstuhlf¨urInformatikIII,RWTHAachen,Ahornstr.55,D-52074Aachen,Germany,[e-mail]ages(VLs)mayoftenberegardedasassembliesofpictorialobjectswithspatialrelationshipslike“above”or“contains”betweenthem,i.e.theirrepresentationsareakindofdirectedgraphs.Suchaspatialrelationshipgraphisoftencomplementedbyamoreabstractgraph,whichprovidesinformationaboutthesyntax(andthesemantics)ofthevisualsentenceinamoresuccinctform.Asbothrepresentationsaregraphs,graphgrammarsareanaturalmeansfordefiningtheconcreteandtheabstractsyntaxofVLs.TheycanbeusedtogeneratesyntaxdirectedVLeditors,whichsupport“freeediting”andparsingoftheirunderly-inggraphstructures.Unfortunately,allefficientlyworkinggraphgrammarparsingalgorithmsdealwithrestrictedclassesofcontext-freegraphgrammarsonly,whilemoregeneralclassesofgraphgrammarsarenecessaryfordefiningmanyVLs.Thismotivatedustodeveloptheno-tionoflayeredcontext-sensitivegraphgrammars,togetherwithabottom-up/top-downparsingalgorithm.1.IntroductionandmotivationInreadingthevisuallanguageliterature,oranybookonsoftwareengineering,onecannothelpbutnoticethatalargevarietyofvisuallanguagesexistsofwhichonlyafewareequippedwithaproperformalsyntaxdefinition.Inthispaperwewillshowhowgraphgrammarscanbeusedassyntaxdefinitionformalismforgraphicallanguages,andwewilldevelopagraphicalpars-ingalgorithmbasedonthesegrammars.Westartwiththecontextofourworkbydiscussingtheinternalrepresentationsnecessarytosupporteditingandexecutionofvisualprograms,byshowinghowgraphgrammarsfitin,andbyarguingwhygraphparsingwouldbeusefulforusersofvisuallanguages.1.1.TheinternalrepresentationsofadiagramForauserofavisuallanguage,thetwomostimportantaspectsofavisualprogramareitsphys-icallayout(whattheuserseesandmanipulates),anditsmeaning(whattheuserexpresseswithit).Anyimplementationofthelanguagehastomaintainthecorrespondencebetweenthesetwoaspects.WediscussthisinmoredetailandwilluseEntity-Relationship(ER)diagramsasexamplelanguagetoillustratetheproposeddatastructures.Theabstractsyntaxgraph(ASG)representationofadiagramreflectstheinternal(log-ical)structureofthediagramaccordingtoitsvisuallanguage.Nodesandedgesinthis1Thisistechnicalreport96-09ofLeidenUniversity;availablebyftpfromftp.wi.leidenuniv.nl,file/pub/CS/TechnicalReports/1996/tr96-09.ps.gz.ThispaperwillappearintheSeptember1996issueoftheJournalofVisualLanguagesandComputing.2REKERS&SCH¨URRBooktitleauthorpublisherpubhashasrelatesrelatesEntityAttrAttrRelationshipEntity(a)exampleERdiagram(b)abstractsyntaxLineLineLineDiamondLineRectttttttttcontainscontainscontainscontainsTextTextTextTextElliElliRectText(topleft=(107,440),textitems=[’Book’])Text(topleft=(93,468),textitems=[’title’])Text(topleft=(128,468),textitems=[’author’])Text(topleft=(194,440),textitems=[’publisher’])Elli(center=(142,464),size=(17,6))Elli(center=(142,464),size=(17,6))Elli(center=(100,464),size=(17,6))Rect(topleft=(100,447),botright=(142,426))Line(start=(100,458),end=(107,447))Line(start=(142,458),end=(135,447))Line(start=(142,437),end=(152,437))Rect(topleft=(190,447),botright=(242,426))Poly(points=[(152,437)(166,451)(180,437)(166,423)])Line(start=(180,437),end=(190,437))Text(topleft=(157,440),textitems=[’pub’])(c)spatialrelations(d)physicallayoutFigure1:Theinternalrepresentationsofadiagramgraphrepresentationcorrespondtolanguageconstructs,butdonotdeterminehowtheseconstructslooklike.Forinstance,thegraphofFig.1(b)isanappropriateASGfortheERdiagramofFig.1(a).Thisrepresentationcontainsjusteverythingnecessarytointerpretthediagram.However,theERdiagramhastoberepresentedonascreentotheuser,andinordertodosoaphysicalrepresentationofthediagrammustexist.Thephysicallayoutofavisualprogramisbuiltupfromsomepredefinedgraphicalobjects(suchasLine,Rect,Elli,andText)withproperties(suchaslocation,size,color,andpenkind).Thisleveldefineswhattheuserseesandmanipulates.Forexample,thephysicallayoutoftheERdiagramofFig.1(a)isshowninFig.1(d).Thisrepresentationcontainsjusteverythingnecessarytodisplaythediagram.Inordertorelatethesetwo,quitedifferent,representationsofadiagramsomeintermedi-atedatastructureisnecessarythatrepresentsthepictorialstructureofthediagram.Thespatialrelationsgraph(SRG)abstractsfromthephysicallayout:itcontainsallgraphi-calobjects,butinsteadofcontainingallindividualproperties,itrepresentsthehigherlevelspatialrelationswhichholdbetweenitsobjects(touch,contains,leftof,labels).Further-more,itmayusehigherlevelobjects,suchasDiamondinsteadofPoly.AnexampleofanSRGisgiveninFig.1(c).NotehowmuchmoredetailthisgraphcontainscomparedtothecorrespondingASG.TheSRGandtheASGrepresentationofavisualsentencearebothgraphs,butonlyveryspecifickindsofgraphsrepresentactualvisualsentences.Agraphgrammarcanbeusedtodefinewhatgraphsarecorrect,andspecifieshowsuchgraphsmaybeconstructed.Forexample,Sec.1.2presentssuchagraph