Scrittura di un compilatore Compilatore - Analisi dell'uso e delle caratteristiche

Questa è una domanda eccellente.

Di recente ho lavorato su parecchie analisi e IMHO alcune delle caratteristiche principali sono:

• un'API programmatica - quindi può essere utilizzata all'interno di un linguaggio di programmazione, idealmente semplicemente importando una libreria. Può avere un'interfaccia GUI o BNF, ma quella programmatica è la chiave, perché puoi riutilizzare i tuoi strumenti, IDE, analisi statica, test, strutture per l'astrazione del linguaggio, familiarità del programmatore, generatore di documentazione, processo di costruzione, ecc. Inoltre, puoi giocare interattivamente con piccoli parser, che riduce drasticamente la curva di apprendimento. Questi motivi lo collocano nella parte superiore del mio elenco di "funzioni importanti".

• segnalazione degli errori, come menzionato da @guysherman. Quando viene rilevato un errore, voglio sapere dove si trovava l'errore e cosa stava succedendo quando è successo. Sfortunatamente, non sono stato in grado di trovare buone risorse per spiegare come generare errori decenti quando il backtracking entra in gioco. (Anche se il commento della nota @ Sk-logic sotto).

• risultati parziali. Quando l'analisi non riesce, voglio essere in grado di vedere ciò che è stato analizzato correttamente dalla parte dell'input che era prima della posizione dell'errore.

• astrazione. Non puoi mai costruire abbastanza funzioni e l'utente avrà sempre bisogno di più, quindi cercare di capire tutte le possibili funzioni in anticipo è destinato a fallire. È questo che intendi per modelli?

• Sono d'accordo con il tuo n. 2 (previsione anticipata). Penso che aiuti a generare buoni report di errore. È utile per qualcos'altro?

• supporto per la costruzione di un albero di analisi in caso di parsing, forse:

  • un albero di sintassi concreto, per il quale la struttura dell'albero corrisponde direttamente alla grammatica e include le informazioni di layout per la segnalazione degli errori delle fasi successive. In questo caso, il client non dovrebbe fare qualsiasi cosa per ottenere la struttura ad albero corretta - dovrebbe dipendere direttamente dalla grammatica.
  • un albero di sintassi astratto. In questo caso, l'utente è in grado di giocherellare con tutti gli alberi di analisi

• un tipo di registrazione. Non sono sicuro di questo; forse per mostrare una traccia delle regole che il parser ha provato, o per tenere traccia dei token spazzatura come spazi bianchi o commenti, nel caso (per esempio) si vogliono usare i token per generare documentazione HTML.

• capacità di gestire i linguaggi sensibili al contesto. Non è sicuro quanto sia importante questo, o - in pratica, sembra più pulito analizzare un superset di una lingua con una grammatica context-free, quindi controllare i vincoli sensibili al contesto in ulteriori passaggi successivi.

• messaggi di errore personalizzati, in modo da poter ottimizzare i rapporti di errore in situazioni specifiche e forse comprendere e risolvere più rapidamente i problemi.

D'altra parte, non ritengo che la correzione degli errori sia particolarmente importante, anche se non sono aggiornato sui progressi attuali. I problemi che ho notato sono che le potenziali correzioni che gli strumenti forniscono sono: 1) troppo numerose, e 2) non corrispondono agli errori reali fatti, e quindi non sono così utili. Speriamo che questa situazione migliorerà (o forse lo ha già fatto).

Non ho esperienza nella progettazione della lingua, ma ho provato a scrivere un parser una volta, mentre stavo creando e IDE per un motore di gioco.

Qualcosa che è importante per i tuoi utenti finali, a mio avviso, sono messaggi di errore che hanno senso. Non è un punto particolarmente sconvolgente, lo so, ma dopo averlo fatto indietro, una delle principali implicazioni di questo è che devi essere in grado di evitare i falsi positivi. Da dove vengono i falsi positivi? Vengono dal parser che cade al primo errore e non si riprende mai del tutto. C / C ++ è noto per questo (anche se i nuovi compilatori sono un po 'più intelligenti).

Quindi cosa ti serve invece? Penso che piuttosto che sapere cosa è / non è valido in un punto, è necessario sapere come prendere ciò che non è valido e apportare una modifica minima per renderlo valido - in modo che si possa continuare l'analisi senza generare errori falsi relativi alla tua discesa ricorsiva che si confonde. Essere in grado di creare un parser in grado di generare queste informazioni non solo ti dà un parser molto robusto, ma apre alcune fantastiche funzionalità per il software che utilizza il parser.

Capisco che potrei suggerire qualcosa di veramente difficile, o stupidamente ovvio, mi dispiace se è così. Se questo non è il tipo di cosa che stai cercando, cancellerò felicemente la mia risposta.

La grammatica non deve avere restrizioni come "non avere regole ricorsive lasciate". È ridicolo che gli strumenti oggi ampiamente utilizzati abbiano questo e possano capire solo le grammatiche LL di successo - quasi 50 anni dopo che yacc ha funzionato correttamente.

Un esempio per la ricorsione a destra (usando la sintassi yacc):

list: 
      elem                  { $$ = singleton($1); }
    | elem ',' list         { $$ = cons($1, $2);  }
    ;

Un esempio per la ricorsione a sinistra (usando la sintassi yacc):

funapp:
    term                    { $$ = $1; }
    | funapp term           { $$ = application($1, $2); }
    ;

Ora, questo potrebbe forse essere "refactored" a qualcos'altro, ma in entrambi i casi, il tipo specifico di ricorsione è solo il modo "giusto" per scrivere questo, poiché gli elenchi (nella lingua di esempio) sono corretti ricorsivi mentre l'applicazione della funzione è lasciato ricorsivo.

Ci si può aspettare dagli strumenti avanzati che supportano il modo naturale di scrivere cose, invece di richiedere a un "refactoring" di essere tutto ciò che è ricorsivo sinistro / destro su cui lo strumento si impone.