Esiste un generatore di parser guidato da un esempio o uno sviluppo DSL ad-hoc?

7

Sono interessato a sapere se esiste uno strumento che ti consente di inserire esempi di documenti validi e ti consente quindi di generalizzare da quello a un parser riutilizzabile.

Posso immaginarlo, ma ogni volta che comincio a imparare i parser arriva alla granularità di qualcosa come lex e yacc e sembra più complicato di quanto dovrebbe essere il mio istinto.

Quindi mi chiedo se

  • a) è fondamentalmente così complicato e ho bisogno di vederlo o
  • b) c'è un modo per creare DSL ad-hoc per attività relativamente semplici che potrei imparare su

Aggiornamento: un semplice esempio di un dsl "ad hoc" che mi piacerebbe fare rapidamente.

Invece dell'XML

<foo>
  <item>bar</item>
  <item>bat</item>
</foo>

Potrei volere qualcosa come:

foo
  bar
  bat
    Le linee
  • contengono elementi di dati
  • il rientro produce relazioni padre-figlio

Il mio strumento immaginario mi consente di trasmettere le informazioni di cui sopra.

Quindi, nel mio strumento immaginario, potrei evidenziare "foo" in alto e fare clic con il tasto destro, a quel punto mi richiederebbe di limitare i valori a una lista di scelta ....

Quindi potrei estendere il primo a:

foo
  bar(5)
  bat
  • in una riga, '(' e ')' circondano un elemento secondario

Quanto sopra potrebbe essere qualificato con un valore booleano che specifica la ricorsione oppure no, se impostato su true allora bar (lala (4)) potrebbe funzionare ...

Questo è il tipo di pensiero che generalmente ho che mi ha portato a porre la domanda. È possibile che ora l'ho qualificato, la risposta cambia, in tal caso mi scuso in anticipo.

    
posta Aaron Anodide 10.11.2011 - 03:44
fonte

3 risposte

7

Non puoi praticamente costruire un parser per un vero linguaggio informatico (o DSL) semplicemente mostrandogli degli esempi. Imparare qualcosa solo con esempi positivi è piuttosto difficile (come è ben noto alla comunità di apprendimento automatico); hai bisogno di almeno alcuni esempi negativi. Praticamente vuoi che i parser siano in grado di accettare delle alternative. Se li consenti, una semplice generalizzazione disgiuntiva che accetta solo l'insieme di esempi positivi e rifiuta tutto il resto funziona bene ma non è utile (ad esempio, un "parser" per le stringhe "QA" "BZQ1" e "RQ" sarebbe be just "QA" | "BZQ1" | "RQ").

Questo articolo parla di machine learning per indurre la grammatica dai dati. Non dice molto sulla praticità. Nessuno strumento che abbia mai visto è stato efficace nel farlo in modo generale e le differenze tra "legale" e "non legale" possono essere incredibilmente sottili. Immagina di provare ad apprendere quali sono i programmi C ++ validi secondo lo standard C ++ e di rifiutare quelli che MS consente che non siano legali. Perfino i programmatori praticamente non possono farlo, e il comitato per gli standard C ++ discute incessantemente sui casi delicati.

Francamente, se hai EBNF, scrivere una grammatica per un DSL è in genere abbastanza semplice ... se sai che cosa dovrebbe consentire il DSL. Scrivere un grammer che funzioni per la maggior parte dei generatori di parser è relativamente difficile, perché accettano solo versioni limitate di EBNF (ad es., LL (k), LALR (1), ...). Puoi renderlo molto più semplice utilizzando un motore di analisi completo senza contesto come un parser GLR che non ha tali restrizioni.

Il nostro DMS Software Reengineering Toolkit ha un generatore di parser GLR e accetta facilmente grammatiche prive di contesto. Apparentemente sembra impossibile l'analisi del C ++ con un semplice BNF (i GNU hanno dovuto creare un parser LALR terribilmente compromesso per farlo per GCC); è possibile perché ci sono grammatiche context-free per C ++, basta guardare nello standard!.

Ma l'analisi è solo la parte facile. Non dovresti spendere le tue energie lì. Sono necessari più macchinari per elaborare il DSL: creazione di AST, ispezione di casi speciali, trasformazione in una lingua di destinazione, ottimizzazione del codice.

DMS è utile per creare DSL non solo perché può accettare le descrizioni dei DSL in modo relativamente semplice, ma perché ha la maggior parte di quella grande quantità di macchinari per l'elaborazione (analisi / trasformazione / ...) di quella DSL di cui avrai bisogno, dopo che avrai avuto successo nell'analisi.

    
risposta data 10.11.2011 - 05:16
fonte
0

DSL può essere diviso in 2 gruppi:

a) come (per lo più) scrivi Ira Baxter: build NEW parser etc ... implement semantico

b) internal: usa sottoinsieme / sovra-set (estensioni di libreria) del linguaggio reale. Quindi usa no-choice sulla sintassi, deve accettare la regola generale di sintassi della lingua di hosting.

Esempio di DSL interno in java. Copiato da un progetto più grande:

BackupService.open().setAdminEmail("[email protected]")
.setDatabase("xddasdas;user;pass").pefrorm().zip().transfer("sftp...).finish();

Leggi "evangelismo" nella comunità linguistica di Groovy.

link

e campionare a. Xml Builder, è molto vicino alla tua idea

link

    
risposta data 23.09.2015 - 20:32
fonte
0

Non nel caso generale, per le ragioni fornite da Ira Baxter. Tuttavia, questa è una descrizione abbastanza buona di come funziona docopt : fornisci esempi di quali validi argomenti della riga di comando per il tuo programma dovrebbero assomiglia, e genera un parser di argomenti da riga di comando da quegli esempi.

    
risposta data 23.09.2015 - 21:23
fonte

Leggi altre domande sui tag