Ulteriori informazioni su Parsing

Question

Sono in programmazione dal 1999 per lavoro e divertimento. Voglio imparare nuove cose e ultimamente mi sono concentrato sull'analisi, poiché gran parte del mio lavoro è la lettura, l'integrazione e l'analisi dei dati. Ho anche un gran numero di compiti ripetitivi che penso potrei esprimere in linguaggi di dominio molto semplici se il sovraccarico era abbastanza basso. Ho alcune domande sull'argomento.

1. La maggior parte del mio codice di analisi corrente non definisce una grammatica formale. Di solito metto insieme qualcosa nel mio linguaggio preferito perché è facile, so come farlo e posso scrivere quel codice molto velocemente. È anche facile per le altre persone con cui collaboro. Quali sono i vantaggi e gli svantaggi di definire una grammatica e generare un parser reale (come si farebbe con ANTLR o YACC) per analizzare le cose rispetto agli hack che la maggior parte dei programmatori usava per scrivere i parser?
2. Quali sono i migliori strumenti di generazione di parser per la scrittura di parser basati su grammatica in C++, Perl e Ruby? Ho guardato allo ANTLR e non ho trovato molto sull'utilizzo di ANTLRv3 con un target C++, ma per il resto sembra interessante. Quali sono gli altri strumenti simili a ANTLR di cui dovrei leggere la lettura?
3. Quali sono i libri e gli articoli canonici che qualcuno è interessato a saperne di più sull'analisi? Sfortunatamente un corso in compilatori non faceva parte della mia educazione, quindi il materiale di base è molto gradito. Ho sentito grandi cose sullo Dragon Book, ma che altro c'è là fuori?

Answer 1

Su 1., direi che il vantaggio principale è manutenibilità - apportare un piccolo cambiamento alla lingua significa semplicemente apportare una modifica corrispondentemente piccola alla grammatica, piuttosto che hackerare minuziosamente attraverso i vari punti nel codice che potrebbe avere qualcosa a che fare con ciò che vuoi cambiare ... ordini di grandezza di migliore produttività e minori rischi di bug.

Su 2. e 3., non posso suggerire molto oltre quello che hai già trovato (utilizzo principalmente Python e pyparsing, e potrei commentare da esperienza su molti framework di analisi Python centrati, ma per C++ uso principalmente buona vecchio yacc o bison in ogni caso, e la mia vecchia copia nodosa del Libro del Drago - non l'ultima edizione, in realtà - è tutto ciò che tengo al mio fianco per lo scopo ...).

Answer 2

Let's Build A Compiler è un tutorial passo-passo su come scrivere un semplice compilatore. Il codice è scritto in Delphi (Pascal), ma è abbastanza semplice da poter essere tradotto facilmente nella maggior parte delle altre lingue.

Answer 3

In perl, i moduli Parse :: RecDescent sono il primo punto di partenza. Aggiungi tutorial al nome del modulo e Google dovrebbe essere in grado di trovare un sacco di tutorial per iniziare.

Answer 4

Ecco il mio prendere sul vostro (molto buono) domande:

1. Credo che un parser beneficia più da situazioni non banali in cui una grammatica esiste realmente. Devi sapere come funzionano i parser e le grammatiche per pensare a quella tecnica, e non tutti gli sviluppatori lo fanno.
2. lex/yacc sono vecchi strumenti Unix che potrebbero essere utilizzabili come sviluppatore C++. Forse anche Bison.
3. ANTRL e il suo libro di accompagnatori sono molto buoni. "Writing Compilers and Interpreters" ha esempi C++ che potrebbero piacerti.

Il pattern Interprete GoF è un'altra tecnica per scrivere "piccoli linguaggi". Dai un occhiata a questo.

Answer 5

Definire una grammatica utilizzando BNF, EBNF o qualcosa di simile è più semplice e in seguito si avrà un tempo migliore per mantenerlo. Inoltre, puoi trovare molti esempi di definizioni grammaticali. Ultimo ma non meno importante, se hai intenzione di parlare della tua grammatica a qualcun altro sul campo, è meglio che tu stia parlando la stessa lingua (BNF, EBNF ecc.).

Scrivere il proprio codice di analisi è come reinventare la ruota ed è soggetto a errori. È anche meno manutenibile. Certo, può essere più flessibile, e per i piccoli progetti potrebbe anche essere una buona scelta, ma l'uso di un generatore di parser esistente che prende una grammatica e sputa il codice dovrebbe coprire la maggior parte delle nostre esigenze.

Per C++ vorrei anche suggerire lex/yacc. Per Ruby sembra una scelta decente: Coco/R(uby)

Answer 6

Tempi divertenti: ho passato molte ore stamattina a chiedermi quali macchine e parser di stato e sto cercando di capire come potrei imparare di più su di loro.

Per 2, è possibile dare un'occhiata a Ragel (è utile per C++ e Ruby).

Answer 7

Vorrei analizzare seriamente l'analisi basata su un combinatore monadico (che spesso si occupa anche dell'analisi lessicale) in Haskell. L'ho trovato piuttosto un occhiolino; è sorprendente quanto facilmente sia possibile creare un parser da zero usando questo metodo. È così facile, infatti, che è spesso più veloce scrivere il proprio parser piuttosto che provare a utilizzare le librerie esistenti.

L'esempio più famoso è probabilmente Parsec che ha un buon user guide che spiega come utilizzarlo. Esiste un elenco di porte di questa libreria in altre lingue (tra cui C++ e Ruby) elencate nello Parsec page of the Haskell wiki, sebbene io non abbia familiarità con esse e quindi non posso dire quanto siano vicine all'utilizzo di Parsec in Haskell.

Se si desidera imparare come funzionano internamente e come scriverne di propri, è consigliabile iniziare dal Capitolo 8 ("Parser funzionali") da Graham Hutton Programming in Haskell. Una volta compreso bene il capitolo (che probabilmente richiederà diverse letture), verrai impostato.

Answer 8

Ecco un tutorial su un self-contained, completamente portatile generatore di parser che può essere usato per progettare e realizzare "basso overhead" DSL molto rapidamente (10 pagine!):

http://www.bayfronttechnologies.com/mc_tutorial.html

Questo il sito ti guida attraverso il documento del 1964 di Val Schorre su MetaII. Sì, 1964. Ed è sorprendente. È così che ho imparato a conoscere i compilatori nel 1970.