schreibe rekursiven Parser mit pyparsing

Question

Ich versuche das Forward() Element aus Pyparsen zu verstehen. Angenommen, ich habe diese einfache BNF:

identifier = 
    "a..z,$,_" < "a..z,$,_,0..9" > 

package_name = 
    identifier 
/(package_name "." identifier) 

und ich versuche, ein einfaches Paket zu analysieren, wie java.lang.String ich entweder nur java als Ergebnis erhalten oder nie von Rekursion zurück. Ich habe versucht, es wie folgt aus:

from pyparsing import alphas,alphanums, Word, Forward, ZeroOrMore, Group, Literal 

identifier=Word(alphas+"$_",alphanums+"$_") 
dot=Literal(".") 

package_name = Forward() 
definition = package_name+dot+identifier 
package_name << Group(identifier+ZeroOrMore(definition)) 

package_name.parseString("java.lang.String") 

druckt [[ 'java']]

from pyparsing import alphas,alphanums, Word, Forward, ZeroOrMore, Group, Literal 

identifier=Word(alphas+"$_",alphanums+"$_") 
dot=Literal(".") 

package_name = Forward() 
definition = identifier^package_name+dot+identifier 
package_name << definition 

package_name.parseString("java.lang.String") 

wird Rekursion Grenze

wie funktioniert dieses Forward Platzhalter Arbeit erreichen?

Answer 1

Das Problem ist nicht mit Forward aber mit Grammatik, die von Natur aus entweder zu früh begrenzt ist, oder rekursiv in eine Weise, die mit einem naiven Rekursiver Abstieg wie Pyparsing unentscheidbar ist.

Sie haben dies:

package_name = identifier | (package_name "." identifier) 

Wenn Sie links nach rechts Spiel, das immer eine einzige Kennung übereinstimmen und dann stoppen, ohne zu versuchen, einen folgenden Zeitraum zu entsprechen. Wenn Sie die Reihenfolge so ändern, dass sie der identifier zuletzt entspricht:

. . . dann wird es unendlich rekursieren, denn um zu entscheiden, ob package_name übereinstimmt, ist das erste, was es tun muss, zu entscheiden, ob package_name übereinstimmt. Dies ist eine left-recursive Grammatik, die ein einfacher rekursiver-absteigender Parser wie Pyparsing nicht verarbeiten kann. Pyparsing schaut nicht voraus, um zu sehen, wie sich ein Match auf nachfolgende Matches auswirkt. Es versucht nur die Streichhölzer von links nach rechts.

Sie können ein einfaches Beispiel dafür, wie Forward Werke erhalten, indem die Art und Weise Ihre Grammatik rekursiv zu ändern:

identifier = pyp.Word(pyp.alphas+"$_", pyp.alphanums+"$_") 
package_name = pyp.Forward() 
package_name << ((identifier + '.' + package_name) | identifier) 

>>> package_name.parseString("java.lang.String") 
[u'java', u'.', u'lang', u'.', u'String'], {}) 

Hier geschieht die Rekursion auf der rechten Seite, nicht auf der linken Seite, so Pyparsing es incremenetally mithalten können.

(Ihre Verwendung von ZeroOrMore ist ein Ablenkungsmanöver. Wenn Sie eine rekursive Grammatik wie diese haben möchten, möchten Sie ZeroOrMore nicht verwenden, da die rekursive Definition bereits zu mehreren Übereinstimmungen mit Ihrem Unterausdruck führt Wie ich in meinem Kommentar vorgeschlagen habe, ist es jedoch viel einfacher, diese Art von Grammatik ohne Rekursion zu definieren.)