XML/DTD: Kontextfreiheit?

Alles, was nicht direkt mit Python-Problemen zu tun hat. Dies ist auch der perfekte Platz für Jobangebote.
matott

XML/DTD: Kontextfreiheit?

Beitragvon 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.
Benutzeravatar
gerold
Python-Forum Veteran
Beiträge: 5554
Registriert: Samstag 28. Februar 2004, 22:04
Wohnort: Telfs (Tirol)
Kontaktdaten:

Beitragvon 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...
http://halvar.at | Kleiner Bascom AVR Kurs
Wissen hat eine wunderbare Eigenschaft: Es verdoppelt sich, wenn man es teilt.
Benutzeravatar
nkoehring
User
Beiträge: 543
Registriert: Mittwoch 7. Februar 2007, 17:37
Wohnort: naehe Halle/Saale
Kontaktdaten:

Beitragvon 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.
Benutzeravatar
Dill
User
Beiträge: 470
Registriert: Mittwoch 10. Januar 2007, 14:52
Wohnort: Köln

Beitragvon 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 ... :shock:
Benutzeravatar
nkoehring
User
Beiträge: 543
Registriert: Mittwoch 7. Februar 2007, 17:37
Wohnort: naehe Halle/Saale
Kontaktdaten:

Beitragvon 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 ... :shock:
Ja damit hast du auch wieder recht ...also ich bleib bei BeautifulSoup ;)
matott

Beitragvon 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

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

XML ist übrigens *nicht* kontextfrei. Das bringt dem OP natürlich auch nichts. :-)
Benutzeravatar
Dill
User
Beiträge: 470
Registriert: Mittwoch 10. Januar 2007, 14:52
Wohnort: Köln

Beitragvon 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

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

Was ist "erweitert kontextfrei"? Formal ist XML kontextsensitiv.
Benutzeravatar
Dill
User
Beiträge: 470
Registriert: Mittwoch 10. Januar 2007, 14:52
Wohnort: Köln

Beitragvon 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.
Benutzeravatar
nkoehring
User
Beiträge: 543
Registriert: Mittwoch 7. Februar 2007, 17:37
Wohnort: naehe Halle/Saale
Kontaktdaten:

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

Ich teile BlackJacks Aussage... Chomsky laesst gruessen ^^
Benutzeravatar
Dill
User
Beiträge: 470
Registriert: Mittwoch 10. Januar 2007, 14:52
Wohnort: Köln

Beitragvon 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 :wink:
matott

Beitragvon 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

Beitragvon 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
User
Beiträge: 1157
Registriert: Sonntag 3. September 2006, 12:52

Beitragvon 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.

Wer ist online?

Mitglieder in diesem Forum: Majestic-12 [Bot]