Perché i parser online sembrano fermarsi a regexps?

Question

Mi chiedo a lungo perché non sembra esserci alcun parser per, diciamo, BNF , che si comportano come regexps in varie librerie.

Certo, ci sono cose come ANTLR , Yacc e molti altri che generano codice che, a loro volta, possono analizzare un CFG , ma non sembra esserci una libreria in grado di farlo senza il passaggio intermedio.

Sono interessato a scrivere un Packrat parser , per avviare tutti quelli nidificati -parenthesis-stranezze associate a regexps (e, forse ancora di più, per lo sport di esso), ma in qualche modo ho la sensazione che sto solo entrando in un'altra classe di paludi simile a un problema di arresto.

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

Answer 1

Penso che sia più una cosa culturale. L'uso di grammatiche senza contesto è per lo più limitato ai compilatori, che in genere hanno un codice associato a ciascuna regola di produzione. In alcune lingue, è più semplice emettere codice che simulare i callback. In altri, vedrai librerie di parser: combinatori di parser in Haskell, per esempio. D'altro canto, le espressioni regolari sono ampiamente utilizzate in strumenti come grep, dove è scomodo eseguire il compilatore C ogni volta che l'utente fornisce una nuova espressione regolare.

Answer 2

Boost.Spirit sembra quello che stai cercando.

Se stai cercando di crearne uno tuo, ho usato BNFC per il mio ultimo progetto di compilatore e fornisce la grammatica utilizzata nella propria implementazione . Questo potrebbe essere un buon punto di partenza ...

Answer 3

Non ci sono limiti tecnici / teorici in agguato nell'ombra. Non posso dire perché non siano più popolari, ma conosco almeno una libreria che fornisce questo tipo di "quotazione online". analizzando quello che cerchi.

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

Ecco un piccolo esempio dalla parte superiore della mia testa:

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

Le librerie del combinatore parser per Haskell e Scala consentono anche di esprimere la tua grammatica per il tuo parser nello stesso pezzo di codice che lo utilizza. Tuttavia, ad esempio, non puoi lasciare che l'utente digiti una grammatica in fase di esecuzione (che potrebbe essere di interesse solo per le persone che creano software per aiutare le persone a capire comunque le grammatiche).

Answer 4

Pyparsing ( http://pyparsing.wikispaces.com ) ha un supporto integrato per l'analisi packrat e è puro Python, quindi puoi vedere l'implementazione effettiva.

Answer 5

Perché le grammatiche complete senza contesto sono abbastanza confuse quanto lo sono senza una sintassi cripticamente densa e incomprensibile per renderle ancora più confuse?

È difficile sapere cosa stai chiedendo. Stai cercando di creare qualcosa di simile a un'espressione regolare, ma per grammatiche senza contesto? Ad esempio, usando $ var = ~ / expr = expr + expr / (in Perl) e avendo 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 circa tre regole renderà la tua "espressione grammaticale" ancora più illeggibile di qualsiasi espressione regolare dei giorni nostri.

Answer 6

Gli effetti collaterali sono l'unica cosa che vedo che ti conquisterà. La maggior parte dei generatori di parser include codice incorporato per l'elaborazione e sarebbe necessario un valutazione per farlo funzionare.

Un modo per aggirare il problema sarebbe quello di nominare le azioni e poi fare un'azione "quot". funzione che accetta il nome dell'azione da eseguire e gli arg con cui eseguirla.

Answer 7

Teoricamente potresti farlo con Boost Spirit in C ++, ma è principalmente per grammatiche statiche. Penso che il motivo per cui questo non sia comune sia che i CFG non siano così comunemente usati come regex. Non ho mai dovuto usare una grammatica tranne che per la costruzione di compilatori, ma ho usato regexs molte volte. I CFG sono generalmente molto più complessi dei regex, quindi ha senso generare staticamente codice con uno strumento come YACC o ANTLR.

Answer 8

tcllib ha qualcosa del genere, se puoi sopportare Parse Expression Grammars e anche TCL. Se Perl fa per te CPAN ha Parse :: Earley . Ecco una pura variazione Perl che sembra promettente. PLY sembra essere una soluzione plausibile per Python