Serve una panoramica dei concetti e degli strumenti per tradurre una DSL in espressioni regolari

5

Sto cercando una piccola guida. Fino a stamattina, questo era tutto sulla mia testa. Dopo aver passato oggi ricerche su Wikipedia, StackOverflow, ecc., Direi che ho il naso fuori dall'acqua. Ho il compito di ricercare un progetto che, a quanto ho capito, implicherebbe il reverse engineering di un linguaggio specifico del dominio che è fondamentalmente un tipo di sintassi di espressioni regolari e che lo traduce in espressioni regolari convenzionali (nel senso di Perl). Spero che qualcuno possa colmare le lacune nella mia comprensione, quindi lascia che ti spieghi quello che ho e la mia comprensione, finora.

Riguardo al DSL, ha fondamentalmente due componenti. Uno è espressioni regolari simili a grep, più o meno. L'altro componente è costituito da ciò che è possibile chiamare macro. Queste macro vengono utilizzate quando si desidera trovare numeri di previdenza sociale, numeri di carta di credito e così via nel testo analizzato. Il DSL è un modo più semplice per l'utente finale di specificare testo ed eccezioni corrispondenti. (Onestamente, è ancora piuttosto complicato da usare - ma più semplice delle espressioni regolari.)

Il DSL viene utilizzato per scrivere "regole", una regola come un'istruzione a riga singola che descrive il testo di destinazione.

Quello che voglio fare è prendere una regola come input, tradurre quella regola in un'espressione regolare convenzionale laddove possibile. Se una macro non si scompone in una singola espressione regolare, tradurrò la macro in uno o più RE o qualsiasi tipo di codice di elaborazione del testo necessario.

Il mio più grande punto di ignoranza è il "tradurre". Ecco la mia prima domanda: coinvolgerà quello che viene chiamato "parsing"? (Come puoi immaginare, sono un programmatore autodidatta.) Utilizzerei uno strumento come ANTLR o PyParsing o qualcosa del genere? (Ho appena scoperto di questi strumenti oggi, durante le mie ricerche.) Sto indovinando sì, ma apprezzerei la conferma.

Quanto devo imparare? Non ho bisogno di prendere il "libro del drago", giusto? Non sto scrivendo una DSL, ma se sono reverse-engineering, allora immagino che avrò più o meno bisogno di imparare come creare una DSL in primo luogo (dato che altrimenti avrei saputo come fare parsing). Sì?

Che cosa ho bisogno di ottenere sotto la mia cintura? Questo è quello che sto cercando di capire. Ho analizzato i file di configurazione; Ho scritto un semplice generatore di codice YAML in Java Bean; Ho scritto un semplice estrattore HTML; Conosco un po 'le espressioni regolari e l'elaborazione del testo; ma questo particolare sforzo è più sofisticato di qualsiasi altra cosa abbia fatto prima. Sembra fattibile, ma come controllo di integrità per favore dimmi se, nella mia ignoranza, ho sbagliato i calcoli e quello che sto descrivendo in realtà ha bisogno di 4 anni di essere un importante informatico da portare a termine.

Qualcuno può indicarmi la giusta direzione o darmi qualche suggerimento? Grazie.

    
posta Mario 20.06.2014 - 22:24
fonte

2 risposte

2

Non ho mai scritto un compilatore, quindi sono fuori dalla mia profondità qui, ma qui c'è un tentativo:

Vorrei iniziare scrivendo un lexer e un parser per la lingua. Ci sono molti strumenti per questo. ANTLR è uno di loro; può gestire sia lexing che analisi. In alternativa, puoi usare Lex o GNU Flex per creare un lexer e creare un albero di analisi con Yacc e la sua implementazione Bison sono altri. Sono sicuro che ci sono molti altri generatori di lexer e parser che non ho trattato qui.

Per quanto riguarda la generazione del codice, non so davvero quale sia il modo migliore per farlo. Tuttavia, ci sono molte risorse sull'argomento.

La risposta principale a questa domanda elenca molte risorse che è possibile utilizzare per entrambi il lexing / parsing e la generazione del codice.

Se conosci un linguaggio funzionale (come OCaml), questo sarebbe un buon linguaggio per implementare il tuo compilatore, poiché credo (mai fatto) che rendano relativamente facile lavorare con gli alberi.

    
risposta data 22.07.2014 - 18:22
fonte
2

Raccomando di familiarizzare con diversi linguaggi di programmazione (inclusi Scheme o CommonLisp e Ocaml o Haskell).

È probabile che implementare il tuo traduttore in tali lingue sarebbe un bene per te.

Quindi ti suggerisco di leggere Programming Language Pragmatics (di M.Scott) e Lisp In Small Pieces (di C.Queinnec).

Ovviamente, dovrai leggere un buon libro di testo del compilatore.

Il lexing & la fase di parsing è probabilmente la più semplice. La maggior parte dei problemi sono altrove.

Ovviamente potresti voler utilizzare un generatore di parser come menhir o antlr . Potresti anche evitarli e scrivere il tuo parser a mano ( questa risposta sta spiegando perché vorresti farlo ). Ma l'analisi è abbastanza "facile" (ma molto lavoro!). La maggior parte dei problemi sono altrove.

BTW, tu stai ri-implementando un DSL. Potresti provare a (compatibilmente) migliorarlo. Ed è una quantità significativa di lavoro (mesi, non giorni).

Ovviamente il tuo traduttore implicherà la creazione di un albero di sintassi astratto interno del codice DSL analizzato (e il male è in i dettagli) e trasformandoli in qualche altro AST che rappresenta il codice di uscita.

Il mio documento DSL2011 su MELT potrebbe essere rilevante per te.

Anche la lettura del Manuale della raccolta dei rifiuti dovrebbe essere utile.

    
risposta data 22.07.2014 - 18:37
fonte

Leggi altre domande sui tag