Problem mit Linksrekursion bei Parserkombinatoren

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
D@ve
User
Beiträge: 4
Registriert: Mittwoch 12. November 2008, 18:52
Kontaktdaten:

Mittwoch 26. November 2008, 09:53

Moin, bin neu hier. Mache Python eigentlich eher unfreiwillig für eine Vorlesung (hat aber einen gewissen Reiz muss ich zugeben).

Es geht darum mit folgendem Parserkombinator eine vereinfachte Grammatik bzw einen entsprechenden Parser für XML zu schreiben:
http://denkspuren.blogspot.com/2008/09/ ... toren.html

Das klappt bisher auch wunderprächtig. Bis auf den rekursiven Teil...

Code: Alles auswählen


#Tagblock (rekursiv)
tag_block = Delay()
content = Alternative("content", text, tag_block, empty_tag, comment_tag) 
tag_block.set(Sequence("tag_block", open_tag, ZeroOrMore(content), close_tag))
xml_document = Sequence("xml_document", xml_tag, tag_block)
Das Problem ist die Linksrekursion im letzten Block, was in einer Endlosschleife mündet.
Kennt sich jemand damit aus und kann mir das für Normalsterbliche verständlich erklären wie man die Linksrekursion auflöst? Aus dem Wikipedia-Artikel werde ich nicht wirklich schlau...

http://en.wikipedia.org/wiki/Left_recursion

Vielen Dank
Gruß, Dave
Zuletzt geändert von D@ve am Mittwoch 26. November 2008, 11:23, insgesamt 1-mal geändert.
There are only 10 types of people. Those who understand binary and those who don't.
D@ve
User
Beiträge: 4
Registriert: Mittwoch 12. November 2008, 18:52
Kontaktdaten:

Mittwoch 26. November 2008, 11:23

Manchmal ist die Lösung wirklich einfach....

Code: Alles auswählen

content = Alternative("content", text, comment_tag, empty_tag, tag_block ) 
tag_block.set(Sequence("tag_block", open_tag, content, close_tag))
xml_document = Sequence("xml_document", xml_tag, tag_block)
Trotzdem Danke...

Gruß, Dave
There are only 10 types of people. Those who understand binary and those who don't.
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Mittwoch 26. November 2008, 13:36

Oh, das ist ja ein interessanter Blogeintrag, Parserkombinatoren stehen schon seit Ewigkeit auf meiner Liste der Dinge mit denen ich spielen will, PLT Scheme bringt sogar eine eigene Lib dafür mit.

Und ich meine, wenn wir Python in der Vorlesung hätten, wäre es ja wunderbar, das Subset von Java mit dem ich mich rumschlagen muss ist einfach nur schmerzhaft.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Mittwoch 26. November 2008, 13:48

Dieses Paper vom Autoren von OMeta zeigt, wie PEG-Parser für Links-Rekursion nachgerüstet werden können: http://www.vpri.org/pdf/tr2007002_packrat.pdf .

Ich bin jedoch zu blöd, in deinem Beispiel die Linksrekursion zu erkennen. Du schreibst:

Code: Alles auswählen

content = tag_block | ...
tag_block = open_tag content* close_tag
Das ist keine Linksrekursion. Da gibt es kein Problem, wenn dein Parser-Kombinator richtig funktioniert. Ich erkenne allerdings auch keine Unterschied in der "Lösung", außer das du jetzt als Kind nur noch einmal content erlaubst, was sicherlich nicht so gedacht ist.

Linksrekursiv wäre diese Regel:

Code: Alles auswählen

list = list "," element | element
Stefan
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Mittwoch 26. November 2008, 14:06

Leonidas hat geschrieben:Oh, das ist ja ein interessanter Blogeintrag
OMG, der zitiert mich ja... ich bin berühmt! ;)

Habe ich denn hier nie meine verbesserte Version gepostet? Da benutze ich docstrings, um Aktionen mit Regeln zu annotieren. Liesst sich besser, wenn man mehr machen will, also nur etwas zu erkennen.

Stefan
D@ve
User
Beiträge: 4
Registriert: Mittwoch 12. November 2008, 18:52
Kontaktdaten:

Mittwoch 26. November 2008, 14:08

Naja Funktioniertd doch nicht... Zu früh gefreut...
Ich bin jedoch zu blöd, in deinem Beispiel die Linksrekursion zu erkennen.
Die Linksrekursion liegt imo bei ZeroOrMore(content). Ohne ZeroOrMore funktioniert's, aber dann ist entsprechen natürlich auch die Verschachtelung dahin... Kann natürlich auch sein, dass ich einfach zu übermüdet bin und einfach zu dämlich dazu bin... hab die Nacht durchgemacht um das noch fertig zu bekommen.

tag_block = Delay()
content = Alternative("content", text, tag_block, empty_tag, comment_tag)
tag_block.set(Sequence("tag_block", open_tag, ZeroOrMore(content), close_tag))
xml_document = Sequence("xml_document", xml_tag,tag_block)
Da gibt es kein Problem, wenn dein Parser-Kombinator richtig funktioniert
Der sollte im wesentlichen funktionieren der war Vorgegeben... Wir sollten dabei nur die Grammatik umsetzen.... Hier mal komplett soweit:

Code: Alles auswählen

#Terminal_Symbole
blank = Token(" ")
equals = Token("=")
single_quote = Token("'")
double_quote = Token("\"")
#whitespace = Token("\n")
whitespace = RegExp("\s","whitespace") 

#beliebiger Text außer "<" und ">"
text = RegExp("[a-zA-Z0-9=üöäÜÖÄß()\[\]\"\s\.,;\+\-]*","text") 
#text = RegExp("[a-z]*","test") 
 
#Bezeichner von Attributen oder Tags
#identifier = RegExp("^[^\d][a-zA-Z0-9_\-\.]*","identifier") 
identifier = RegExp("[a-zA-Z][a-zA-Z0-9_\-]*","identifier") 
 
#Attribute
attribute_value = Alternative("attribute_value",Sequence("attribute_value", double_quote, text, double_quote), Sequence("attribute_value", single_quote, text, single_quote))
attribute = Sequence("attribute", OneOrMore(blank), identifier, equals, attribute_value)

#Spezialfälle encoding und version Attribute
version_string = RegExp("\d+\.\d+","float_value")
version_attribute_value = Alternative("version_attribute_value", Sequence("version_value", double_quote, version_string, double_quote), Sequence("version_value", single_quote, version_string, single_quote))
version_attribute = Sequence("version_attribute", OneOrMore(blank), Token("version"), equals, version_attribute_value) 

encoding_string = RegExp("[a-zA-Z0-9\.\-]*","encoding_string")
encoding_attribute_value = Alternative("encoding_attribute_value", Sequence("encoding_value", double_quote, encoding_string, double_quote), Sequence("encoding_value", single_quote, encoding_string, single_quote))
encoding_attribute = Sequence("encoding_attribute", OneOrMore(blank), Token("encoding"), equals, encoding_attribute_value)

#Tags
xml_tag = Sequence("xml_tag",ZeroOrMore(whitespace), Token("<?xml"), version_attribute, encoding_attribute, ZeroOrMore(attribute), ZeroOrMore(blank), Token("?>"),ZeroOrMore(whitespace))
open_tag = Sequence("open_tag",Token("<"), identifier, ZeroOrMore(attribute), Token(">"),ZeroOrMore(whitespace) )
close_tag = Sequence("close_tag",Token("</"), identifier, Token(">"),ZeroOrMore(whitespace))
empty_tag = Sequence("open_tag",Token("<"), identifier, ZeroOrMore(attribute), Token("/>"),ZeroOrMore(whitespace))
comment_tag = Sequence("comment_tag",Token("<!--"),text,Token("-->"),ZeroOrMore(whitespace))

#Tagblock (rekursiv)
tag_block = Delay()
content = Alternative("content", comment_tag, empty_tag, text, tag_block ) 
tag_block.set(Sequence("tag_block", open_tag, ZeroOrMore(content), close_tag))
xml_document = Sequence("xml_document", xml_tag, tag_block)
Und ich meine, wenn wir Python in der Vorlesung hätten, wäre es ja wunderbar, das Subset von Java mit dem ich mich rumschlagen muss ist einfach nur schmerzhaft
Yop Java ist bei uns auch Nummer 1. Wobei das gerade extrem ätzend ist, jeder Prof hat da so seine Präferenzen. Ich komme von PHP, Java ist die Hofsprache in der Fakkultät und ich muss mir dieses Semester Python, C++ und C# aneignen zusätzlich wurde mal kurz mit LISP gedroht (ich hoffe davon bleiben wir verschont)...
Von daher besteht kein Grund zur Eifersucht... Wobei das mit den Parserkombinatoren ein ziemlich interessantes Thema ist. Hat jedenfalls Spaß gemacht bis jetzt (nur blieb der Erfolg aus)...

Vielen Dank

Gruß, Dave
There are only 10 types of people. Those who understand binary and those who don't.
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Mittwoch 26. November 2008, 14:34

D@ve hat geschrieben:zusätzlich wurde mal kurz mit LISP gedroht (ich hoffe davon bleiben wir verschont)...
Wieso, Lisp macht viel Spaß, die Syntax ist angenehmer als Curly-Braces und die Features sind beachtlich (wobei, das hängt natürlich vom konkreten Lisp ab aber solange es nicht Emacs-Lisp ist, ist es super). Gerade in Lisp bekommt kann man durch die Makros einige Vorteile für Parserkombinatoren.

sma, PLY benutzt für seine Grammatikregeln auch Docstrings. Das ist zwar sehr einfach zu nutzen, aber wenn man bedenkt dass Docstrings bei ``python -OO`` verschwinden, nicht unbedingt optimal.

Und überhaupt, dieser Denkspuren-Blog hat ja eine Menge lesenswerter Beiträge.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Mittwoch 26. November 2008, 22:00

IMHO gibt es wenige Sprachen, die nicht besser sind als PHP. An Daves Stelle wäre ich also dankbar für jede Sprache, die ich zusätzlich lernen kann. Insbesondere Lisp-Wissen gehört IMHO zum Grundwissen eines jeden Informatikers, ähnlich wie Mediziner oder Geisteswissenschaftler Latein oder Griechisch kennen sollten. Neben der C/Pascal/Java-Soße sollte man IMHO auch Scheme, Forth, Smalltalk und ML oder Haskell gesehen haben.

Für eine moderne Mischung aus Java und Lisp empfehle ich einen Blick auf Clojure.

Zu der Grammatik kann ich nur sagen, dass ein oberflächlicher Blick keinen Fehler zeigt. Wie gesagt, an der (nicht vorhandenen) Linksrekursion liegt es IMHO nicht und ich tippe daher mutig auf einen Fehler in der Biliothek.

Stefan
D@ve
User
Beiträge: 4
Registriert: Mittwoch 12. November 2008, 18:52
Kontaktdaten:

Donnerstag 27. November 2008, 00:31

IMHO gibt es wenige Sprachen, die nicht besser sind als PHP.
Es ist immerhin Programmiersprache genug, als dass ich damit meinen Lebensunterhalt bestreiten kann...
There are only 10 types of people. Those who understand binary and those who don't.
audax
User
Beiträge: 830
Registriert: Mittwoch 19. Dezember 2007, 10:38

Donnerstag 27. November 2008, 07:24

Haha!


scnr...
Antworten