Scrittura parser ricorsivo con pyparsing

Question

Sto cercando di capire l'elemento Forward() da pyparsing. Supponiamo che io sono questo semplice BNF:

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

package_name = 
    identifier 
/(package_name "." identifier) 

e cerco di analizzare un semplice pacchetto come java.lang.String ricevo o solo java come risultato o non tornare da ricorsione. ho provato in questo modo:

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") 

stamperà [[ '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") 

raggiungerà limite di ricorsione

come funziona Forward segnaposto?

Answer 1

Il problema non è con Forward ma con la grammatica, che è intrinsecamente limitata troppo presto, o ricorsiva in un modo che è indecidibile con un parser di discesa ricorsivo ingenuo come Pyparsing.

avete questo:

package_name = identifier | (package_name "." identifier) 

Se corrispondono alla sinistra a destra, questo sarà sempre indicare un singolo identificativo e poi fermarsi, senza tentare di corrispondere a un periodo successivo. Se si passa il fine di corrispondere l'ultima identifier:

package_name = (package_name "." identifier) | identifier 

. . . quindi ricambierà all'infinito, perché per decidere se corrispondere a package_name, la prima cosa che deve fare è decidere se corrispondere a package_name. Questa è una grammatica left-recursive, che un semplice parser ricorsivo-discendente come Pyparsing non può gestire. Il Pyparsing non guarda avanti per vedere come una partita influenzerà le partite successive. Prova solo le partite da sinistra a destra.

è possibile ottenere un semplice esempio di come Forward opere cambiando il modo in cui il recurses grammaticali:

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'], {}) 

Qui, la ricorsione accade a destra, non a sinistra, in modo da Pyparsing può corrispondere incremenetally.

(L'utilizzo di ZeroOrMore è un'aringa rossa. Se hai una grammatica ricorsiva come questa, non vuoi usare ZeroOrMore, perché la definizione ricorsiva consente già alla tua sottoespressione di corrispondere più volte Come ho suggerito nel mio commento, tuttavia, è molto più semplice definire questo tipo di grammatica senza ricorsione comunque.)