XML/DTD: Kontextfreiheit?

matott · Sonntag 11. März 2007, 08:08

Edit (Leonidas): Vom Anfangsthread "Eigene "config" Dateien gescheid parsen." getrennt.

Sowieso würde ich mal überdenken, ob deine Sprache regular ist oder context-free. Denn normalerweise ist XML context-free und du brauchst sowas wie z.B. einen LR- oder LL-Parser (gibt auch noch andere Typen).

Edit (Leonidas): Vom Anfangsthread "Eigene "config" Dateien gescheid parsen." getrennt.

gerold · Sonntag 11. März 2007, 10:18

matott hat geschrieben:Sowieso würde ich mal überdenken, ob deine Sprache regular ist oder context-free. Denn normalerweise ist XML context-free und du brauchst sowas wie z.B. einen LR- oder LL-Parser (gibt auch noch andere Typen).

Hallo matott!

Nett dass du antwortest, aber was könnte dem Fragesteller deine Antwort bringen, außer zu verwirren?

mfg
Gerold

PS: Meine Antwort bringt dem Fragesteller natürlich auch nichts...

nkoehring · Sonntag 11. März 2007, 10:52

gerold hat geschrieben:
matott hat geschrieben:Sowieso würde ich mal überdenken, ob deine Sprache regular ist oder context-free. Denn normalerweise ist XML context-free und du brauchst sowas wie z.B. einen LR- oder LL-Parser (gibt auch noch andere Typen).
Hallo matott!

Nett dass du antwortest, aber was könnte dem Fragesteller deine Antwort bringen, außer zu verwirren?

mfg
Gerold

PS: Meine Antwort bringt dem Fragesteller natürlich auch nichts...

Ich empfinde seine Antwort als garnicht so unpassend. Es ist nunmal so, dass XML eigentlich Kontextfrei ist und man dementsprechend (eigentlich) nen speziellen Parser braeuchte...

Aber zum Glueck haben wir ja BeautifulStoneSoup

Damit kannst du ziemlich bequem XML parsen.

Dill · Sonntag 11. März 2007, 11:32

@akis.kapo, hat es einen hintergrund, warum du keinen fertigen parser nutzen möchtest?

@rest

Es ist nunmal so, dass XML eigentlich Kontextfrei ist und man dementsprechend (eigentlich) nen speziellen Parser braeuchte...

sicher, aber was bringt das jmd, der ganz offensichtlich noch nie was von formalen sprachen gehört hat.

btw ist xml exteded CF ...

nkoehring · Sonntag 11. März 2007, 11:44

Dill hat geschrieben:@akis.kapo, hat es einen hintergrund, warum du keinen fertigen parser nutzen möchtest?

@rest
Es ist nunmal so, dass XML eigentlich Kontextfrei ist und man dementsprechend (eigentlich) nen speziellen Parser braeuchte...
sicher, aber was bringt das jmd, der ganz offensichtlich noch nie was von formalen sprachen gehört hat.

btw ist xml exteded CF ...

Ja damit hast du auch wieder recht ...also ich bleib bei BeautifulSoup

matott · Sonntag 11. März 2007, 12:14

Na ja, ok, wenn ihr meint:
Formale Sprachen in a Nutshell
So, bezogen auf dein Beispiel akis.kapo:
Wenn du versuchsts z.B. die Elemente in einander zu "verschachteln",

Code: Alles auswählen

<item>
  <item>
  </item>
</item>

dann musst du das ja in deiner Regular Expression angeben, d.h. für jedes "Verschachtelungslevel" musst die RegEx erweitern, da RegEx nicht rekursiv sind.

Code: Alles auswählen

item[1]: text | (item[2])+;
item[2]: text | (item[3])+;
[..]
item[n]: text | (item[n+1])+;

Context-free sieht das dann so aus:

Code: Alles auswählen

item: text | item+;

Somit sind nur kann man die Sprache, die du für deine Config benutzt nur context-free ausdrücken.

Ich hoffe jetzt ist es klar, denn es ist wichtig ordentliches Parsing zu beherrschen. Zum Glück gibt es ja heute sehr viele Tools, die einem dabei helfen

.

BlackJack · Sonntag 11. März 2007, 13:10

XML ist übrigens *nicht* kontextfrei. Das bringt dem OP natürlich auch nichts.

Dill · Sonntag 11. März 2007, 13:18

XML ist übrigens *nicht* kontextfrei. Das bringt dem OP natürlich auch nichts.

XML ist (erweitert) kontextfrei. alles andere wäre mir neu.

was soll es denn sonst sein?

BlackJack · Sonntag 11. März 2007, 13:29

Was ist "erweitert kontextfrei"? Formal ist XML kontextsensitiv.

Dill · Sonntag 11. März 2007, 13:40

ich bin in dem thema nicht sondernlich fit, aber die Grammatik eines XML-doc ist eine DTD.
Und eine DTD ist kontextfrei.
genauer, sie ist erweitert kontextfrei, da auf der rechten seite RE stehen können.

nkoehring · Sonntag 11. März 2007, 13:40

Ich teile BlackJacks Aussage... Chomsky laesst gruessen ^^

Dill · Sonntag 11. März 2007, 13:47

so, jetzt habe ich mal etwas rumgesucht:

http://coding.derkeiler.com/Archive/Gen ... /0159.html

http://lrb.cs.uni-dortmund.de/~tick/Talks/xmld.pdf

das schöne ist, irgendwie haben wir alle recht

matott · Sonntag 11. März 2007, 13:52

Du kannst XML, aber auch mit YACC o.ä. parsen, wenn du dir den Context "merkst", dann ist es aber auch wieder irgendwie kontextsensitiv. Aber wenn man so argumentiert kann man auch per Stack unendlich viele Reguläre Parser in einer verschachteln, wenn sie sich beim Abstieg immer weiter aufrufen und verschachteln.
Siehe: http://laramies.com/ragel/json/
Für ECF siehe: http://tack.sourceforge.net/doc/LLgen.html

BlackJack · Sonntag 11. März 2007, 15:21

@Dill: Ich bleibe dabei das XML nicht kontextfrei ist.

Die Hinzunahme einer DTD hilft dagegen nicht, also eine neue Sprache deren Worte XML *und* der DTD genügen, ist auch nicht kontextfrei.

Da gibt es immer noch Entities und Refrenzen. Zum Beispiel müssen Entities deklariert werden, bevor man sie benutzt und rekursive Entities sind nicht erlaubt.

Wenn ein Attribut vom Typ `ID` ist, darf der Wert nur einmal im Dokument vorkommen. Wenn ein Attribut vom Typ `IDREF` ist, muss der Wert im Dokument als `ID` vorkommen. Diese beiden Regeln kommen erst durch DTDs oder ähnliche Spezifizierungen hinzu!

Zu "erweitert kontextfrei": Das ist auf die Sprache bezogen das gleiche wie "kontextfrei", denn es geht sowohl in dem PDF-Dokument, als auch in der LLgen-Dokumentation um die *Notation* der kontextfreien Grammatik, nicht um die *Sprache* die davon erkannt werden kann. Der Satz "XML ist erweitert kontextfrei" ergibt vor dem Hintergrund keinen Sinn.

sape · Sonntag 11. März 2007, 15:44

BlackJack hat geschrieben:Was ist "erweitert kontextfrei"? Formal ist XML kontextsensitiv.

Erstmal vorweg, ich stecke in dem Thema nicht genug drin, aber soviel hab ich mir schon angelesen und stimme daher mit BlackJack überein.

1. Erstmal gibt es sowas wie erweitert kontextfrei nicht in der Chomsky-Hierarchie.

2. XML, HTML und ähnliches ist nicht vollständig Type-2 (kontextfrei Grammatiken) aber lässt sich mit auch nicht vollständig mit Type-3 (reguläre Grammatiken) beschreiben (Bestimmte Verschachtelungen sind für regExp "nicht" zu lösen (wie man es z.B. bei BBCode hat), wo bestimmte Verschachtelungen von Typen nicht erlaubt sind.)

3. XML, HTML sind nicht Turingtauglich. Type-2 sind Turingtauglich bzw. mit Kellerautomaten mit zwei Kellerspeichern (Was gleich mächtig mit einer Turingmaschine ist). Z.B. gibt es keine Kontrollstrukturen in Markup-/Beschreibungssprachen und auch keine schleifen. Alles Voraussetzungen um sich Type-2 auf der Chomsky-Hierarchie schimpfen zu lassen.

BTW: Bin kein Informatiker. Wenn etwas nicht stimmt in meinem Post, dan stellt das bitte klar.

matott · Sonntag 11. März 2007, 16:47

sape hat geschrieben: 2. XML, HTML und ähnliches ist nicht vollständig Type-2 (kontextfrei Grammatiken) aber lässt sich mit auch nicht vollständig mit Type-3 (reguläre Grammatiken) beschreiben (Bestimmte Verschachtelungen sind für regExp "nicht" zu lösen (wie man es z.B. bei BBCode hat), wo bestimmte Verschachtelungen von Typen nicht erlaubt sind.)

Ich glaube die Leute unterhalten sich eher über DTDs, als XML. Aber deine Argumentation habe ich ja auch schon so ähnlich vorgetragen.

sape hat geschrieben: 3. XML, HTML sind nicht Turingtauglich. Type-2 sind Turingtauglich bzw. mit Kellerautomaten mit zwei Kellerspeichern (Was gleich mächtig mit einer Turingmaschine ist). Z.B. gibt es keine Kontrollstrukturen in Markup-/Beschreibungssprachen und auch keine schleifen. Alles Voraussetzungen um sich Type-2 auf der Chomsky-Hierarchie schimpfen zu lassen.

Guter Argumentationsleitfaden.

Vielleicht könnte das was bringen: http://en.wikipedia.org/wiki/Pumping_lemma
Dieser eine Typ (http://coding.derkeiler.com/Archive/Gen ... /0159.html) zeigt es damit ja auch.

sape hat geschrieben: BTW: Bin kein Informatiker. Wenn etwas nicht stimmt in meinem Post, dan stellt das bitte klar.

Ich auch nicht, aber ich bin auch noch schlecht im Beweisen

.

BlackJack · Sonntag 11. März 2007, 18:54

Der Beweis, der davon ausgeht, dass man schon bewiesen hat, dass Sprachen der Form `wⁿxwⁿ` nicht kontextfrei sind, ist etwas einfacher als das Pumping-Lemma.

Dill · Montag 12. März 2007, 13:17

Es geht hier doch ums parsen.
XML wurde designed mit dem vorsatz, es im gegensatz zu SGML vernünftig parsen zu können.
Aus sicht des parsers ist XML kontextfrei.

Wenn ein Attribut vom Typ `ID` ist, darf der Wert nur einmal im Dokument vorkommen. Wenn ein Attribut vom Typ `IDREF` ist, muss der Wert im Dokument als `ID` vorkommen.

das zb interessiert den parser nicht.
wird in ebenen über dem parser behandelt.

siehe hier:
http://coding.derkeiler.com/Archive/Gen ... /0169.html

BlackJack · Montag 12. März 2007, 14:20

@Dill: Das ist alles schön und gut, macht aber die Aussage XML sei kontextfrei nicht wahr. Man kann für XML keine kontextfreie Grammatik angeben.

Man kann natürlich eine syntaktische Analyse auf Basis einer kontextfreien Grammatik, die eine Obermenge von XML-Dokumenten erkennt, in die Analysephase einbetten. Wie man das bei den meisten Programmiersprachen auch macht. Bekannteste/verbreiteste Ausnahme ist wohl Perl.

Dill · Montag 12. März 2007, 14:43

formale sprachen dienen der informatik nicht, weil sie so wunderschöne theoretische konstrukte sind, sondern weil sie den bau von parsern und damit compilern enorm erleichtern.

daher ist es absolut in ordnung sprachen aus der sicht des parsers zu bewerten.
so habe ich es jedenfalls gelernt und bleibe dabei

Welchen Sinn hat denn XML für deine Konfig-Datei?
Zum menschlichen Editieren finde ich traditionelle unixmäßige Dateien wesentlich entspannter.

es gibt einige leute die das anders sehen, zb solche die nicht (nur) auf/für unixen arbeiten.