Problem mit Linksrekursion bei Parserkombinatoren

[D@ve]

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

[D@ve]

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

[Leonidas]

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.

[sma]

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]

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]

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

[Leonidas]

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.

[sma]

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]

IMHO gibt es wenige Sprachen, die nicht besser sind als PHP.

Es ist immerhin Programmiersprache genug, als dass ich damit meinen Lebensunterhalt bestreiten kann...

[audax]

Haha!


scnr...