Talen en automaten/2011-12/producten/XML

definitive

XML

Laurens van den Bercken, Dennis Obster

http://upload.wikimedia.org/wikipedia/commons/6/68/XML.svg

Talen en automaten 2011-12

15:25 B

Laurens van den Bercken Bachelor Informatica  e-mail  cursuspagina

Bestand:Laurens van den Bercken.jpg

Dennis Obster  e-mail  cursuspagina

Bestand:Dennis Obster.jpg

Beschrijving

XML staat voor Extensible Markup Language en is de standaard van het World Wide Web Consortium voor de syntax van formele opmaaktalen. De opbouw van XML is zo gekozen dat het voor een machine/computer leesbaar is maar ook voor een mens. XML wordt voornamelijk gebruikt als opslag-structuur. Maar sinds de komst van AJAX wordt het ook erg vaak gebruikt om gegevens via internet te versturen.

Voorbeeld

<?xml version="1.0" encoding="utf-8"?>
<verenigingen>
 <vereniging>
  <verenigingscode>31415</verenigingscode>
  <verenigingsnaam>Van den Bercken voetbalvereniging</verenigingsnaam>
  <aantalleden>0</aantalleden>
  <leden>
  </leden>
 </vereniging>

 <vereniging>
  <verenigingscode>666</verenigingscode>
  <verenigingsnaam>ObSTER</verenigingsnaam>
  <aantalleden>2</aantalleden>
  <leden>
   <lid>
    <ID>1</ID>
    <naam>Dennis</naam>
    <contributie>35,31</contributie>
   </lid>
   <lid>
    <ID>2</ID>
    <naam>Laurens</naam>
    <contributie>30123,13</contributie>
   </lid>
  </leden>
 </vereniging>
</verenigingen>

Syntax

De syntax van XML luidt als volgt:

Elke tag moet worden afgesloten met een sluittag

Elke keer als je een <x> schrijft, moet je dit ook weer afsluiten met </x>. Een tag kan ook binnen zichzelf alweer gesloten worden zoals <x />. In het voorbeeld hieronder is x <lid>.
Voorbeeld

<vereniging>
 <lid name="Dennis">
</vereniging>

Dit is fout. Juiste syntax zou zijn:

<vereniging>
 <lid name="Dennis" />
</vereniging>

Tags zijn hoofdlettergevoelig

In XML zijn tags hoofdlettergevoelig. Door bijvoorbeeld <x>...</X> te doen sluit je <x> niet.
Voorbeeld

<vereniging>
 <lid>Laurens</Lid>
</vereniging>

Dit is fout. Juiste syntax zou zijn:

<vereniging>
 <lid>Laurens</lid>
</vereniging>

Elementen moeten genesteld zijn

Dit houdt in wanneer je meerdere elementen hebt, zoals in het voorbeeld hieronder, je ze ook 'op de juiste' volgorde weer moet sluiten. Bijvoorbeeld: <a><c>...</c></a>.
Voorbeeld

<vereniging>
 <leden>
  <lid>Dennis</lid>
 </vereniging>
</leden>

Dit is fout. Juiste syntax zou zijn:

<vereniging>
 <leden>
  <lid>Dennis</lid>
 </leden>
</vereniging>

Er moet een root-element zijn

In dit voorbeeld hieronder is het root-element <vereniging>. Dit houdt in dat alles wat met vereniging te maken heeft tussen <vereniging> en </vereniging> moet staan.
Voorbeeld

<vereniging>
 <leden>
  <lid>Dennis</lid>
 </leden>
</vereniging>
<controbutie>3,95</controbutie>

Dit is fout. Juiste syntax zou zijn:

<vereniging>
 <controbutie>3,95</controbutie>
 <leden>
  <lid>Dennis</lid>
 </leden>
</vereniging>

Alle attribuut-waarden moeten geciteerd worden

In het voorbeeld hieronder moet de attribuut waarde <lid geboortedatum="datum"> tussen "" gezet worden. Dus <x a="attribuut-waarde">.
Voorbeeld

<vereniging>
 <leden>
  <lid geboortedatum=3/31/2000>Laurens</lid>
 </leden>
</vereniging>

Dit is fout. Juiste syntax zou zijn:

<vereniging>
 <leden>
  <lid geboortedatum="11/11/2011">Laurens</lid>
 </leden>
</vereniging>

Niet te gebruiken symbolen

In XML zijn de symbolen: < kleiner dan, > groter dan, & en, ' apostrof, " citaat teken, gereserveerd voor XML zelf. Om tóch deze symbolen te kunnen gebruiken zijn ze gecodedeerd als volgt:

Symbolen

Code	symbool	betekenis
&lt;	<	kleiner dan
&gt;	>	groter dan
&amp;	&	en
'	'	apostrof
&qout;	"	citaat teken

Commentaar

Commentaar toevoegen in XML doe je als volgt:
<!-- Dit is commentaar! -->

Spaties blijven behouden

In HTML wordt Hello     World weergegeven als Hello World. De spaties worden dus niet behouden, er blijft er maar één over. In XML is dat niet. Dan wordt Hello     World gewoon Hello     World. De spaties worden dus behouden in XML.

Nieuwe regel wordt als line-feed opgeslagen

XML slaat een nieuwe regel op als line-feed (LF). In Windows wordt een nieuwe regel normaal gesproken opgeslagen als carriage return (CR) en LF. In Mac OS en Linux wordt een nieuwe regel standaard als line feed opgeslagen.

Regulier?

Om te bezwijzen dat XML geen reguliere taal is, maken we gebruik van het pomp-lemma voor reguliere talen. Stel dat XML wél regulier is, dan voldoet de taal aan het pomp-lemma en bestaat er een deterministische automaat met k states die de taal accepteert.

Neem nu het woord Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle w \equiv <lid><lid>...<lid></lid></lid>...</lid>} . Het moge duidelijk zijn dat Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle w \; \epsilon \; L} waarbij Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle L} in dit geval de taal XML is. Dit woord heeft k aantal keer <lid> en k aantal keer </lid>. Het pumping-lemma zegt dat we de 1e set, <lid>, kunnen oppompen. Voor elke <lid> moet er ook een </lid> volgens de XML syntax. Nu kunnen we duidelijk zien dat het woord niet meer in de taal zit, omdat er nu meer <lid> dan </lid> zijn. Hiermee hebben we bewezen dat de taal niet regulier is.

Contextvrij?

We kunnen met behulp van het pumping-lemma voor context-vrije talen bewijzen dat XML niet context-vrij is.

Stel dat XML (hierna L) wél context-vrij is. Dan is er een woord Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle w \; \epsilon \; L} waarvoor geldt dat je die kan splitsen in uvxyz. Laten we naar het woord Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle w \equiv <a^k b^k></a^k b^k>} kijken. Voor bijvoorbeeld k = 5 krijg je dan:

<aaaaabbbbb></aaaaabbbbb>

Dit is valide XML en zit dus in Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle L} . Let op, k weten we niet maar wordt door het pomping-lemma vastgesteld. Het pomping lemma zegt nu dat er een vxy combinatie is waarbij Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle |vxy| \leq k} en Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle uv^ixy^iz \epsilon L} met Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle i \geq 0} .

• Stel nu dat vxy volledig in de eerste tag zit. Dit zou betekenen dat je alleen maar de eerste tag oppompt en dus is het duidelijk dat dit niet meer in L zit.
• Stel dat vxy volledig in de sluittag zit. In dit geval zou je alleen de sluittag oppompen en is ook direct duidelijk dat dit woord niet in L zit.
• Stel dat vxy over de start/eind-tags heen zit, dan kunnen we het nog over verschillende gevallen verdelen:
  
  1. Stel y of v bevat een deel van "></", dan mag het duidelijk zijn dat er niet kan worden gepompt.
  2. Stel dat y een deel van de Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a^k} a's bevat uit de sluittag, dan kan v geen a's bevatten omdat Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle |vxy| \leq k} en dus zou dit pompen ook iets wat niet bestaat in XML creëren.
  3. v of y is leeg. In dit geval is het sowieso geen element van L want dan zou XML regulier zijn en we hebben net bewezen dat dit niet klopt.

XML is dus niet contextvrij.