XML/DTD: Kontextfreiheit?

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

Beitragvon 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/General/comp.theory/2004-03/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

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

Beitragvon 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

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

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

Beitragvon BlackJack » Montag 12. März 2007, 15:50

Das formale Sprachen praktischen Nutzen haben, hat niemand bestritten.

Trotzdem ist XML, egal aus welcher Sicht, nicht kontextfrei. Auch aus der Sicht eines Parsers nicht. :roll:

Sonst könnte man ja, ganz praktisch, einen Parser schreiben, der die syntaktische Analyse durchführt, ohne sich Kontext zu merken. Dat jeht nich.
Benutzeravatar
Dill
User
Beiträge: 470
Registriert: Mittwoch 10. Januar 2007, 14:52
Wohnort: Köln

Beitragvon Dill » Montag 12. März 2007, 16:16

Sonst könnte man ja, ganz praktisch, einen Parser schreiben, der die syntaktische Analyse durchführt, ohne sich Kontext zu merken. Dat jeht nich.


doch das geht, kontext wird ausserhalb des parsers gespiechert, zb symboltabelle...

wie gut, dass es die (compiler-)compiler-coder nicht so genau nehmen wie du, sonst hätten wir heute noch keinen funktionierenden compiler. :wink:

edit
wenn du mir eine kontextsensitive grammatik für eine streng typisierte imperative sprache angibst, mit der der compiler ohne symboltabelle auskommt bin ich überzeugt. :twisted:
BlackJack

Beitragvon BlackJack » Montag 12. März 2007, 17:01

Okay, jetzt bin ich platt. Ein Parser der auf Kontext in einer Symboltabelle zugreift, merkt sich keinen Kontext. Das ist also Deine Aussage!?

Warum es keine funktionierenden Compiler(-Compiler) geben sollte, wenn die Programmierer das auch so genau nehmen wie ich, verstehe ich nicht. Das eine hat mit dem anderen nichts zu tun. Und ich gehe davon aus, dass die meisten von denen nicht der Meinung sind XML sei kontextfrei.

Dein Nachtrag (edit) ist dann ja nur noch wirr. Ich soll also etwas angeben, was es nicht geben kann und mit der eigentlichen Frage nichts zu tun hat, damit Du glaubst das XML nicht kontextfrei ist!? :shock:

Eine (Programmier)Sprache muss nicht kontextfrei sein, damit man einen Parser/Compiler dafür schreiben kann. Kaum eine Programmiersprache ist kontextfrei.
Benutzeravatar
Dill
User
Beiträge: 470
Registriert: Mittwoch 10. Januar 2007, 14:52
Wohnort: Köln

Beitragvon Dill » Montag 12. März 2007, 17:33

Okay, jetzt bin ich platt. Ein Parser der auf Kontext in einer Symboltabelle zugreift, merkt sich keinen Kontext. Das ist also Deine Aussage!?


Ja, ich gehe eben davon aus, dass es die aufgabe des parsers ist, einen syntaxbaum für eine eingabe zu liefern.
dabei arbeitet er mit einer kontextfreien grammatik.
die symboltablle liegt ausserhalb des parsers (auch wenn sie natürlich mit ihm zusammenarbeitet)

wenn du sagst, eine sprache sein kontextsensitiv, hast du natürlich recht, aber das ist doch praktisch irrelevant, da die probleme und aufgaben die das nach sich zieht, nicht durch techniken gelöst werden, die aus chomskys hierarchie abgeleitet sind. (wie eben die LL(k) parser).

Also, die sprache ist CS (gebe ich ja zu :) ), die grammatik CF, daher ist die sprache aus sicht des parsers CF.

Dein Nachtrag (edit) ist dann ja nur noch wirr. Ich soll also etwas angeben, was es nicht geben kann und mit der eigentlichen Frage nichts zu tun hat, damit Du glaubst das XML nicht kontextfrei ist!?


jetzt klar was ich damit sagen wollte?
BlackJack

Beitragvon BlackJack » Montag 12. März 2007, 18:30

Wenn der Parser auf die Symboltabelle zugreift, dann benutzt er Kontextinformation. Und wenn er Kontextinformation benutzt, dann ist ganz logischerweise auch für den Parser die Sprache nicht kontextfrei.

Man könnte unter Umständen argumentieren, dass eine Sprache aus Sicht eines Parsers kontextfrei ist, wenn er nicht auf die Symboltabelle zugreift und einen Syntaxbaum aufbaut, der erst danach von einer separaten semantischen Analyse auf die kontextsensitiven Eigenschaften geprüft wird. Aber das würde man in der Praxis wohl kaum machen, weil es effizienter ist diese Überprüfung schon beim Durchlauf des Parsers durch den Baum zu machen.

Dazu arbeiten Parser nicht mit kontextfreien Grammatiken, sondern mit attributierten Grammatiken, d.h. die Symbole bekommen Attribute und die Produktionen semantische Regeln oder Aktionen, die unter anderem diese Attribute berechnen und somit Kontextinformationen im Baum "herumreichen" können. Das war's dann mit der Kontextfreiheit des Parsers.

Und nein, mir ist nicht klar was Du mit dem Nachtrag sagen wolltest.

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder