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.
XML/DTD: Kontextfreiheit?
- gerold
- Python-Forum Veteran
- Beiträge: 5555
- Registriert: Samstag 28. Februar 2004, 22:04
- Wohnort: Oberhofen im Inntal (Tirol)
- Kontaktdaten:
Hallo matott!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).
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.
Wissen hat eine wunderbare Eigenschaft: Es verdoppelt sich, wenn man es teilt.
- nkoehring
- User
- Beiträge: 543
- Registriert: Mittwoch 7. Februar 2007, 17:37
- Wohnort: naehe Halle/Saale
- Kontaktdaten:
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...gerold hat geschrieben:Hallo matott!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).
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...
Aber zum Glueck haben wir ja BeautifulStoneSoup
Damit kannst du ziemlich bequem XML parsen.
[url=http://www.python-forum.de/post-86552.html]~ Wahnsinn ist auch nur eine andere Form der Intelligenz ~[/url]
hackerkey://v4sw6CYUShw5pr7Uck3ma3/4u7LNw2/3TXGm5l6+GSOarch/i2e6+t2b9GOen7g5RAPa2XsMr2
hackerkey://v4sw6CYUShw5pr7Uck3ma3/4u7LNw2/3TXGm5l6+GSOarch/i2e6+t2b9GOen7g5RAPa2XsMr2
@akis.kapo, hat es einen hintergrund, warum du keinen fertigen parser nutzen möchtest?
@rest
btw ist xml exteded CF ...
@rest
sicher, aber was bringt das jmd, der ganz offensichtlich noch nie was von formalen sprachen gehört hat.Es ist nunmal so, dass XML eigentlich Kontextfrei ist und man dementsprechend (eigentlich) nen speziellen Parser braeuchte...
btw ist xml exteded CF ...
- nkoehring
- User
- Beiträge: 543
- Registriert: Mittwoch 7. Februar 2007, 17:37
- Wohnort: naehe Halle/Saale
- Kontaktdaten:
Ja damit hast du auch wieder recht ...also ich bleib bei BeautifulSoupDill hat geschrieben:@akis.kapo, hat es einen hintergrund, warum du keinen fertigen parser nutzen möchtest?
@restsicher, aber was bringt das jmd, der ganz offensichtlich noch nie was von formalen sprachen gehört hat.Es ist nunmal so, dass XML eigentlich Kontextfrei ist und man dementsprechend (eigentlich) nen speziellen Parser braeuchte...
btw ist xml exteded CF ...
[url=http://www.python-forum.de/post-86552.html]~ Wahnsinn ist auch nur eine andere Form der Intelligenz ~[/url]
hackerkey://v4sw6CYUShw5pr7Uck3ma3/4u7LNw2/3TXGm5l6+GSOarch/i2e6+t2b9GOen7g5RAPa2XsMr2
hackerkey://v4sw6CYUShw5pr7Uck3ma3/4u7LNw2/3TXGm5l6+GSOarch/i2e6+t2b9GOen7g5RAPa2XsMr2
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",
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.
Context-free sieht das dann so aus:
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 .
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>
Code: Alles auswählen
item[1]: text | (item[2])+;
item[2]: text | (item[3])+;
[..]
item[n]: text | (item[n+1])+;
Code: Alles auswählen
item: text | item+;
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 .
- nkoehring
- User
- Beiträge: 543
- Registriert: Mittwoch 7. Februar 2007, 17:37
- Wohnort: naehe Halle/Saale
- Kontaktdaten:
Ich teile BlackJacks Aussage... Chomsky laesst gruessen ^^
[url=http://www.python-forum.de/post-86552.html]~ Wahnsinn ist auch nur eine andere Form der Intelligenz ~[/url]
hackerkey://v4sw6CYUShw5pr7Uck3ma3/4u7LNw2/3TXGm5l6+GSOarch/i2e6+t2b9GOen7g5RAPa2XsMr2
hackerkey://v4sw6CYUShw5pr7Uck3ma3/4u7LNw2/3TXGm5l6+GSOarch/i2e6+t2b9GOen7g5RAPa2XsMr2
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
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
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
Siehe: http://laramies.com/ragel/json/
Für ECF siehe: http://tack.sourceforge.net/doc/LLgen.html
@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.
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.
Erstmal vorweg, ich stecke in dem Thema nicht genug drin, aber soviel hab ich mir schon angelesen und stimme daher mit BlackJack überein.BlackJack hat geschrieben:Was ist "erweitert kontextfrei"? Formal ist XML kontextsensitiv.
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.
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: 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.)
Guter Argumentationsleitfaden.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.
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.
Ich auch nicht, aber ich bin auch noch schlecht im Beweisen .sape hat geschrieben: BTW: Bin kein Informatiker. Wenn etwas nicht stimmt in meinem Post, dan stellt das bitte klar.
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.
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.
wird in ebenen über dem parser behandelt.
siehe hier:
http://coding.derkeiler.com/Archive/Gen ... /0169.html
XML wurde designed mit dem vorsatz, es im gegensatz zu SGML vernünftig parsen zu können.
Aus sicht des parsers ist XML kontextfrei.
das zb interessiert den parser nicht.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.
wird in ebenen über dem parser behandelt.
siehe hier:
http://coding.derkeiler.com/Archive/Gen ... /0169.html
@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.
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.
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
daher ist es absolut in ordnung sprachen aus der sicht des parsers zu bewerten.
so habe ich es jedenfalls gelernt und bleibe dabei
es gibt einige leute die das anders sehen, zb solche die nicht (nur) auf/für unixen arbeiten.Welchen Sinn hat denn XML für deine Konfig-Datei?
Zum menschlichen Editieren finde ich traditionelle unixmäßige Dateien wesentlich entspannter.