Perché i parser in linea sembrano fermarsi alle espressioni regolari?

Question

Mi sono chiesto a lungo perché non sembrano esserci parser per, ad esempio, BNF, che si comportano come espressioni regolari in varie librerie.

Certo, ci sono cose come ANTLR, Yacc e molti altri che generare il codice, che, a sua volta, può analizzare un CFG, ma non sembra essere una libreria che può farlo senza il passaggio intermedio.

Sono interessato a scrivere uno Packrat parser, per avviare tutte quelle parentele nidificate-quirks associati alle espressioni regolari (e, forse ancor più, per lo sport di esso), ma in qualche modo ho la sensazione che io sia semplicemente camminando in un altro ostacolo, come la classe delle paludi.

Esiste un limite tecnico/teorico per questi parser o mi manca qualcosa?

Answer 1

Penso che sia più di una cosa culturale. L'uso di grammatiche context-free è per lo più limitato ai compilatori, che in genere hanno un codice associato a ciascuna regola di produzione. In alcune lingue, è più facile generare codice che simulare i callback. In altri, vedrai le librerie di parser: i combinatori di parser in Haskell, per esempio. D'altra parte, le espressioni regolari vedono un largo uso in strumenti come grep, dove è scomodo eseguire il compilatore C ogni volta che l'utente dà una nuova espressione regolare.

Answer 2

Perché le grammatiche complete e prive di contesto sono abbastanza confuse come sono senza una sintassi criptica densa e incomprensibile per renderle ancora più confuse?

È difficile sapere cosa stai chiedendo. Stai cercando di creare qualcosa come un'espressione regolare, ma per grammatiche context-free? Ad esempio, utilizzando $var =~ /expr = expr + expr/ (in Perl) e con quella corrispondenza "1 + 1" o "1 + 1 + 1" o "1 + 1 + 1 + 1 + 1 + ..."? Penso che uno dei limiti di questo sarà la sintassi: avere più di tre regole renderà la tua "espressione grammaticale" ancora più illeggibile di qualsiasi espressione regolare dei giorni nostri.

Answer 3

L'effetto collaterale è l'unica cosa che vedo che ti porterà. La maggior parte dei generatori di parser include il codice incorporato per l'elaborazione e sarà necessario un avviso per farlo funzionare.

Un modo per aggirare questo è nominare le azioni e quindi creare una funzione di "azione" che prende il nome dell'azione da eseguire e gli argomenti con cui farlo.

Answer 4

Si potrebbe teoricamente farlo con Boost Spirit in C++, ma è principalmente fatto per grammatiche statiche. Penso che la ragione per cui questo non è comune è che i CFG non sono così comunemente usati come regex. Non ho mai dovuto usare una grammatica ad eccezione della costruzione del compilatore, ma ho usato regex molte volte. I CFG sono generalmente molto più complessi delle regex, quindi ha senso generare codice in modo statico con uno strumento come YACC o ANTLR.

Answer 5

tcllib ha qualcosa del genere, se si può sopportare con Parse Expression Grammars e anche TCL. Se Perl è la tua cosa CPAN ha Parse::Earley. Here è una variazione di Perl pura che sembra promettente. PLY sembra essere una soluzione plausibile per Python

Answer 6

Boost.Spirit sembra quello che stai dopo.

Se stai cercando di crearne uno, ho usato BNFC per il mio ultimo progetto di compilatore e fornisce the grammar used in its own implementation. Questo potrebbe essere un buon punto di partenza ...

Answer 7

Non c'è limitazione tecnica/teorica in agguato nell'ombra. Non posso dire perché non siano più popolari, ma conosco almeno una biblioteca che fornisce questo tipo di parsing "on-line" che cerchi.

SimpleParse è una libreria python che consente di incollare semplicemente la grammatica EBNF pelosa nel programma e utilizzarla per analizzare le cose subito, senza passaggi intermedi. L'ho usato per diversi progetti in cui volevo un linguaggio di input personalizzato, ma in realtà non volevo impegnarmi in alcun processo di compilazione formale.

Ecco un piccolo esempio la parte superiore della mia testa:

librerie Combinator

decl = r""" 
    root := expr 
    expr := term, ("|", term)* 
    term := factor+ 
    factor := ("(" expr ")")/[a-z] 
""" 
parser = Parser(decl) 
success, trees, next = parser.parse("(a(b|def)|c)def") 

il parser per Haskell e Scala lasciare che anche la vostra esprimere la vostra la grammatica per il parser nello stesso pezzo di codice che lo utilizza. Tuttavia, non è possibile, ad esempio, consentire all'utente di digitare una grammatica in fase di esecuzione (il che potrebbe interessare solo le persone che fanno software per aiutare le persone a capire comunque le grammatiche).

Answer 8

Pyparsing (http://pyparsing.wikispaces.com) ha il supporto integrato per il parsing packrat ed è puro Python, quindi è possibile vedere l'effettiva implementazione.