Come dovrei specificare una grammatica per un parser?

Dai file di esempio dovrai prendere decisioni in base a quanto vuoi generalizzare da questi esempi. Supponiamo di avere i seguenti tre esempi: (ognuno è un file separato)

f() {}
f(a,b) {b+a}
int x = 5;

Potresti banalmente specificare due grammatiche che accettano questi esempi:

Trivial Grammar One:

start ::= f() {} | f(a,b) {b+a} | int x = 5;

Trivial Grammar Two:

start ::= tokens
tokens ::= token tokens | <empty>
token ::= identifier | literal | { | } | ( | ) | , | + | = | ;

Il primo è banale perché accetta solo i tre campioni. Il secondo è banale perché accetta tutto che potrebbe eventualmente usare quei tipi di token. [Per questa discussione presumo che non ti preoccupi molto del design del tokenizer: è semplice assumere identificatori, numeri e punteggiatura come token e puoi prendere in prestito qualsiasi token set da qualsiasi linguaggio di scripting che come comunque.]

Quindi, la procedura che devi seguire è iniziare dal livello più alto e decidere "quante di ciascuna istanza voglio consentire?" Se un costrutto sintattico può avere senso ripetere un numero qualsiasi di volte, come method s in una classe, ti conviene una regola con questo modulo:

methods ::= method methods | empty

Che è meglio indicato in EBNF come:

methods ::= {method}

Sarà probabilmente ovvio quando vuoi zero o una istanza (il che significa che il costrutto è facoltativo, come con la clausola extends per una classe Java), o quando vuoi consentire una o più istanze (come con un inizializzatore variabile in una dichiarazione). Dovrai essere consapevole di problemi come richiedere un separatore tra elementi (come con , in un elenco di argomenti), richiedendo un terminatore dopo ogni elemento (come con ; per istruzioni separate), o senza bisogno di separatori o terminatore (come nel caso dei metodi in una classe).

Se la tua lingua utilizza espressioni aritmetiche, sarebbe facile per te copiare dalle regole di precedenza della lingua esistente. È meglio attenersi a qualcosa ben noto, come le regole delle espressioni di C, piuttosto che cercare qualcosa di esotico, ma solo a condizione che tutto il resto sia uguale.

Oltre ai problemi di precedenza (cosa viene analizzato l'un l'altro) e ai problemi di ripetizione (quanti di questi elementi dovrebbero verificarsi, come sono separati?), dovrai anche pensare all'ordine: deve sempre comparire qualcosa prima di un altro cosa? Se una cosa è inclusa, dovrebbe essere esclusa un'altra?

A questo punto, potresti essere tentato di applicare alcune regole in modo grammaticale, una regola come se l'età di Person è specificata e non vuoi che sia specificata anche la loro data di nascita. Mentre puoi costruire la tua grammatica per farlo, potresti trovare più facile imporla con un passaggio di "controllo semantico" dopo che tutto è stato analizzato. Ciò semplifica la grammatica e, a mio avviso, rende migliori i messaggi di errore per quando la regola viene violata.

Where can I learn how to specify the grammar for a parser?

Per la maggior parte dei generatori di parser, di solito è una variante di Backus-Naur % s co_de % formato. Vado sul presupposto che stai usando qualcosa del genere e non provando a costruire i tuoi parser a mano. Se puoi produrre un parser per un formato in cui ti è stata data la sintassi (ho incluso un esempio di problema di seguito), specificare grammatiche non è un tuo problema.

Quello che penso tu stia combattendo è la sintassi divinatoria di una serie di campioni, che è molto più un riconoscimento di pattern che un'analisi. Se devi ricorrere a ciò, significa che chiunque stia fornendo i tuoi dati non può darti la sua sintassi perché non hanno una buona padronanza del suo formato. Se hai la possibilità di respingere e dire loro di darti una definizione formale, fallo. Non è giusto per loro darti un vago problema se potresti essere ritenuto responsabile per le conseguenze di un parser basato su una sintassi dedotta che accetta un input errato o rifiuta un buon input.

...I'm never sure that the grammar I've come up which is good (by any reasonable measure of "good").

"Buono" nella tua situazione dovrebbe significare "analizza i positivi e rifiuta i negativi". Senza altre specifiche formali della sintassi del tuo file di input, i campioni sono i tuoi unici casi di test e non puoi fare di meglio. Potresti mettere il piede in basso e dire che solo gli esempi positivi sono buoni e rifiutare qualsiasi altra cosa, ma probabilmente non è nello spirito di ciò che stai cercando di realizzare.

In circostanze più sicure, testare una grammatica è come testare qualsiasi altra cosa: devi trovare un numero sufficiente di casi di test per esercitare tutte le varianti dei non terminali (e terminali, se vengono generati da un lexer).

Problema di esempio

Scrivi una grammatica che analizzerà i file di testo contenenti un elenco come definito dalle seguenti regole:

• Un elenco consiste di zero o più cose .
• Una cosa consiste in un identificatore , una parentesi aperta, una lista di elementi e una parentesi di chiusura.
• Un _item_list_ consiste di zero o più elementi .
• Un elemento constsis di un identificatore , un segno di uguale, un altro identificatore e un punto e virgola.
• Un identificatore è una sequenza di uno o più caratteri A-Z, a-z, 0-9 o il carattere di sottolineatura.
• Gli spazi bianchi vengono ignorati.

Esempio di input (tutti validi):

clank { foo = bar; baz = bear; }
clunk {
    quux =bletch;
    281_apple = OU812;
    He_Eats=Asparagus ; }

Le risposte di Macneil e Blrfl sono fantastiche. Voglio solo aggiungere alcuni commenti sull'inizio del processo.

Una sintassi è solo un modo per rappresentare un programma . Quindi la sintassi della tua lingua dovrebbe essere determinata dalla tua risposta a questa domanda: Che cos'è un programma?

Potresti dire che un programma è una raccolta di classi. Ok, questo ci dà

program ::= class*

come punto di partenza. O potresti doverlo scrivere

program ::= ε
         |  class program

Ora, che cos'è una classe? Ha un nome; una specifica superclasse opzionale; e un mucchio di costruttore, metodo e dichiarazioni di campo. Inoltre, è necessario un modo per raggruppare una classe in una singola unità (non ambigua) e ciò dovrebbe comportare alcune concessioni all'usabilità (ad esempio, taggarla con la parola riservata class ). Va bene:

class ::= "class" identifier extends-clause? "{" class-member-decl * "}"

Questa è una notazione ("sintassi concreta") che puoi scegliere. Oppure puoi decidere altrettanto facilmente:

class ::= "(" "class" identifier extends-clause "(" class-member-decl* ")" ")"

o

class ::= "class" identifier "=" "CLASS" extends-clause? class-member-decl* "END"

Probabilmente hai già preso questa decisione implicitamente, specialmente se hai degli esempi, ma voglio solo rafforzare il punto: La struttura della sintassi è determinata dalla struttura dei programmi che rappresenta. Ecco cosa ti fa superare le "grammatiche banali" dalla risposta di Macneil. Programmi di esempio sono ancora molto importanti, però. Servono a due scopi. In primo luogo, ti aiutano a capire, a livello astratto, che cos'è un programma. Secondo, ti aiutano a decidere quale sintassi concreta dovresti usare per rappresentare la struttura della tua lingua.

Una volta che hai ridotto la struttura, dovresti tornare indietro e affrontare problemi come consentire spazi bianchi e commenti, correggere ambiguità, ecc. Questi sono importanti, ma sono secondari rispetto alla progettazione generale e sono altamente dipende dalla tecnologia di analisi che stai utilizzando.

Infine, non cercare di rappresentare tutto ciò che riguarda la tua lingua nella grammatica. Ad esempio, potresti voler proibire determinati tipi di codice non raggiungibile (ad esempio, un'istruzione dopo un return , come in Java). Probabilmente non dovresti provare a inserirli nella grammatica, perché perderai le cose (whoops, e se return è in parentesi graffe, o cosa succederebbe se entrambi i rami di un'istruzione if ritornassero?) Oppure rendere la tua grammatica troppo complicata da gestire. È un vincolo sensibile al contesto ; scrivilo come un pass separato. Un altro esempio molto comune di un vincolo sensibile al contesto è un sistema di tipi. Potresti rifiutare espressioni come 1 + "a" nella grammatica, se hai lavorato abbastanza duramente, ma non puoi rifiutare 1 + x (dove x ha tipo stringa). Quindi evita le restrizioni semicongelate nella grammatica e fallo correttamente come passaggio separato.