Smart schema validator

Abstract

XML (eXtensible Markup Language) is de meest gebruikte taal voor het uitwisselen van data op het internet. Het is de W3C standaard voor het uitwisselen van informatie over het internet. Een XML-document voldoet gewoonlijk aan een bepaalde structuur, opgelegd door een XML-schema. De meest populaire schema’s zijn DTD en XML Schema. DTD’s en XML Schema’s zijn om te zetten in een grammatica met reguliere expressies. Deze vereisen echter dat deze expressies dan one-unambiguous zijn. Bij XML Schema noemt men deze vereiste Unique Particle Attribution (UPA). In deze thesis onderzoeken we een aantal methodes. We bestuderen een methode om na te gaan of een reguliere expressie one-unambiguous is, een methode om na te gaan of de taal van een expressie one-unambiguous is en een methode om reguliere expressies om te zetten in een equivalente one-unambiguous reguliere expressie als er een dergelijke expressie bestaat. We zouden deze methodes willen gebruiken in een smart schema validator, zodat die een alternatief kan aanbieden als er een fout tegen UPA gemaakt wordt. Praktische tests op een uitgebreide verzameling van willekeurig gegenereerde reguliere expressies tonen aan dat het algoritme in de praktijk bruikbaar is qua uitvoeringstijd. Een groot deel van de onderzochte expressies had echter geen one-unambiguous equivalent. Om dat de expressies automatisch gegenereerd worden is het resultaat van het algoritme vaak onnodig lang. Dit probleem kan zich in het algemeen voordoen bij automatisch gegenereerde expressies. Daarom hebben we besloten ook methodes te onderzoeken die een expressie verkorten. We hebben enkele variaties van twee algemene methodes bestudeerd: een algoritme verkleinen, met behulp van herschrijfregels, of een kleinere expressie genereren uit de minimale deterministische automaat. In onze tests bleek de methode met behulp van herschrijfregels beter te werken, met als extra voordeel dat deze methode de one-unambiguity van de originele expressie bewaard.