componibili Grammatiche

Question

Ci sono così tanti linguaggi di programmazione che supportano l'inserimento di mini-lingue. PHP è incorporato in HTML. XML può essere incorporato in JavaScript. Linq può essere incorporato in C#. Le espressioni regolari possono essere incorporate in Perl.

// JavaScript example 
var a = <node><child/></node> 

Vieni a pensarci, la maggior parte dei linguaggi di programmazione può essere modellata come mini-lingue diverse. Java, per esempio, potrebbe essere suddiviso in un almeno quattro mini-lingue distinte:

• A langauge di dichiarazione del tipo (direttiva pacchetto, le direttive di importazione, dichiarazione della classe)
• Un linguaggio membro-dichiarazione (modificatori di accesso, dichiarazioni di metodo, membro vars)
• Un linguaggio economico (flusso di controllo, l'esecuzione sequenziale)
• Un linguaggio espressione (letterali, assegnazioni, confronti, aritmetica)

Potendo implementare quei quattro linguaggi concettuali come quattro grammatiche distinte certamente ridurrebbe il molto dello spaghettiism che vedo solitamente nelle implementazioni di parser e compilatori complessi.

Ho implementato parser per vari tipi di linguaggi (utilizzando ANTLR, JavaCC e parser di discesa ricorsivi personalizzati), e quando la lingua diventa davvero grande e complessa, di solito si finisce con una grammatica huuuuuuuge, e l'implementazione del parser diventa davvero brutta davvero veloce.

Idealmente, quando si scrive un parser per una di queste lingue, sarebbe bello per la sua attuazione come una raccolta di parser componibili, passando il controllo avanti e indietro tra di loro.

La cosa complicata è che spesso il langeuge di contenimento (ad es. Perl) definisce il proprio terminus sentinel per la lingua contenuta (ad es. Espressioni regolari). Ecco un buon esempio:

my $result ~= m|abc.*xyz|i; 

In questo codice, il codice Perl principale definisce un terminale non standard "|" per l'espressione regolare. Implementare il parser di espressioni regolari come completamente distinto dal parser perl sarebbe davvero difficile, perché il parser di espressioni regolari non saprebbe come trovare il terminale di espressione senza consultare il parser genitore.

Oppure, permette di dire che ho avuto una lingua che ha permesso l'inserimento di espressioni Linq, ma invece di terminare con un punto e virgola (come C# fa), ho voluto affidare le espressioni Linq appaiono tra parentesi quadre:

var linq_expression = [from n in numbers where n < 5 select n] 

Se ho definito la grammatica Linq all'interno della grammatica di lingua madre, ho potuto facilmente scrivere una produzione univoca per un "LinqExpression" utilizzando lookahead sintattica per trovare le recinzioni della staffa. Ma poi la mia grammatica genitoriale dovrebbe assorbire l'intera specifica Linq. E questa è una resistenza. D'altra parte, un parser Linq figlio separato avrebbe un tempo molto difficile capire dove fermarsi, perché avrebbe bisogno di implementare lookahead per i tipi di token stranieri.

E questo praticamente escluderebbe l'utilizzo di fasi separate di lexing/parsing, poiché il parser Linq definirà un intero insieme di regole di tokenizzazione diverso dal parser padre. Se stai effettuando la scansione di un token alla volta, come fai a sapere quando passare il controllo all'analizzatore lessicale della lingua madre?

Cosa ne pensate?Quali sono le migliori tecniche oggi disponibili per l'implementazione di grammatiche linguistiche distinte, disaccoppiate e componibili per l'inclusione di mini-lingue all'interno di lingue madri più grandi?

Answer 1

L'analisi è un aspetto del problema, ma sospetto che l'interazione tra i vari interpreti eseguibili che si riferiscono a ogni mini-lingua sia probabilmente molto più difficile da risolvere. Per essere utile, ogni blocco di sintassi indipendente deve lavorare coerentemente con il contesto generale (o il comportamento finale sarà imprevedibile e quindi inutilizzabile).

Non che io capisca cosa stanno realmente facendo, ma un posto molto interessante per cercare più ispirazione è FoNC. Sembrano (sto indovinando) di essere diretti verso una direzione che consente a tutti i tipi di diversi motori computazionali di interagire senza problemi.

Answer 2

Sto lavorando su questo problema esatto. Condividerò i miei pensieri:

I grammatic sono difficili da eseguire il debug. Ho effettuato il debug di alcuni in Bison e ANTLR e non era carino. Se vuoi che l'utente inserisca le DSL come grammatica nel tuo parser, devi trovare un modo per farlo in modo che non esploda. Il mio approccio è di non permettere DSL arbitrari, ma per consentire solo quelli che seguono due regole:

• I tipi di token (identificatori, stringhe, numeri) sono gli stessi tra tutti DSL in un file.
• sbilanciati parentesi, o staffe non sono consentiti

La ragione per la prima restrizione è perché parser moderni delle interruzioni l'analisi in una fase lessicale e quindi applicare le regole grammaticali tradizionali. Fortunatamente, credo che un singolo tokenizzatore universale sia sufficiente per il 90% dei DSL che si desidera creare, anche se non è in grado di contenere i DSL che si sono già creati e che si desidera incorporare.

La seconda restrizione consente alle grammatiche di essere più separate l'una dall'altra. È possibile analizzare in due fasi raggruppando le parentesi (parentesi graffe, parentesi) e quindi analizzando in modo ricorsivo ogni gruppo. La grammatica del tuo DSL incorporato non può sfuggire attraverso le parentesi in cui è contenuta.

Un'altra parte della soluzione è consentire macro. Ad esempio, regex("abc*/[^.]") mi sembra soddisfacente. In questo modo la macro "regex" può analizzare la regex invece di costruire un regex grammer nella lingua principale. Non puoi usare delimitatori diversi per la tua regex, certo, ma ottieni una misura di coerenza nella mia mente.

Answer 3

Se ci pensi, questo è davvero il modo in cui l'analisi della discesa ricorsiva funziona. Ogni regola e tutte le regole da cui dipende formano una mini grammatica. Qualunque cosa sia più in alto non ha importanza. Ad esempio, potresti scrivere una grammatica Java con ANTLR e separare tutte le diverse "mini-lingue" in diverse parti del file.

Questo non è molto comune semplicemente per il motivo che queste "mini-lingue" condividono spesso molte regole. Tuttavia, sarebbe sicuramente bello se strumenti come ANTLR ti permettessero di includere grammatiche separate da file diversi. Questo ti permetterebbe di separarli logicamente. Il motivo per cui probabilmente non è implementato è probabilmente che si tratta di un problema "cosmetico", è puramente correlato ai file di grammatica stessi, non a un'analisi in sé. Inoltre, non renderà il tuo codice più breve (anche se potrebbe essere leggermente più semplice da seguire). L'unico problema tecnico che risolverebbe è il nome collisioni.

Answer 4

È possibile ascoltare il podcast this.L'analisi senza scanner è stata "inventata" per aiutare a risolvere il problema della composizione di grammatiche diverse (il problema è che si scopre subito che non è possibile scrivere un tokenizer/scanner "universale").

Answer 5

Dai un'occhiata a SGLR, analisi LR Scannerless generalizzato. Ecco alcuni riferimenti e URL. Questa tecnica di parsing rende la composizione delle tabelle di analisi molto semplice. Soprattutto in combinazione con SDF.

Martin Bravenboer e Eelco Visser. Progettazione di embeddings e assimilazioni di sintassi per librerie di lingue. In Modelli in Software Engineering: workshop e simposi a modelli 2007, il volume di 5002 LNCS, 2008.

MetaBorg e MetaBorg in action

Answer 6

Perl 6 può essere visto come un insieme di DSL specificamente realizzati per i programmi di scrittura.

In effetti l'implementazione Rakudo è costruita esattamente in questo modo.

Anche le stringhe sono un DSL con opzioni che è possibile abilitare o disabilitare.

Q 
:closure 
:backslash 
:scalar 
:array 
:hash 
"{ 1 + 3 } \n $a @a<> %a<>" 

qq"{1+2}" eq ｢3｣ 

qq:!closure"{1+2}" eq ｢{1+2}｣ 

Ha sostanzialmente quella di essere costituito da grammatiche componibili per questo lavoro:

sub circumfix:«:-) :-)» (@_) { say @_ } 

:-) 1,2,3 :-) 

---

In Perl 6 grammatiche sono solo un tipo di classe, e gettoni sono un tipo di metodo.

role General-tokens { 
    token start-of-line { ^^ } 
    token end-of-line { $$ } 
} 
grammar Example does General-tokens { 
    token TOP { 
    <start-of-line> <stuff> <end-of-line> 
    } 
    token stuff { \N+ } 
} 

role Other { 
    token start-of-line { <alpha> ** 5 } 
} 
grammar Composed-in is Example does Other { 
    token alpha { .. } 
} 

say Composed-in.parse: 'abcdefghijklmnopqrstuvwxyz'; 

｢abcdefghijklmnopqrstuvwxyz｣ 
start-of-line => ｢abcdefghij｣ 
    alpha => ｢ab｣ 
    alpha => ｢cd｣ 
    alpha => ｢ef｣ 
    alpha => ｢gh｣ 
    alpha => ｢ij｣ 
stuff => ｢klmnopqrstuvwxyz｣ 
end-of-line => ｢｣ 

Si noti che non ha mostrato una classe azioni, che è utile per trasformare il parse-albero come è costruito.