Le regole di analisi - come rendere bello giocare insieme

Question

Così sto facendo un Parser, dove io sono a favore della flessibilità eccesso di velocità, e voglio che sia facile scrivere grammatiche, per esempio, adnon difficile soluzione regole (falso regole per risolvere i conflitti, ecc, come si deve fare in yacc/bison etc.)

C'è una mano-coded Lexer con un set di simboli (ad es.PIÙ, DECIMALE, STRING_LIT, NOME, e così via) adesso ci sono tre tipi di regole:

• TokenRule:corrisponde a un particolare token
• SequenceRule:corrisponde a un elenco ordinato di regole
• GroupRule:corrisponde a qualsiasi regola da un elenco

Per esempio, supponiamo di avere il TokenRule 'varAccess', che corrisponde al NOME del token (circa /[A-Za-z][A-Za-z0-9_]*/), e il SequenceRule 'assegnazione', che corrisponde [espressione, TokenRule(PLUS), espressione].

L'espressione è un GroupRule corrispondenti o 'assegnazione' o 'varAccess' (l'attuale schema di gioco sto provando con un po ' più completo, ma che farò per esempio)

Ma ora diciamo che voglio analizzare

var1 = var2

E diciamo che il Parser inizia con l'Espressione della regola (l'ordine in cui sono definiti non importa - la priorità sarà risolto in seguito).E diciamo che il GroupRule espressione primo incarico'.Poi dal 'espressione' è la prima regola per essere abbinati in 'assegnazione', si cercherà di analizzare un'espressione di nuovo, e così via fino a quando la pila è piena e il computer - come previsto - dà semplicemente in una frizzante segfault.

Quindi cosa ho fatto - SequenceRules aggiungere se stessi come 'foglie' per la loro prima regola, e non roôt regole.Radice le regole sono regole che il parser del primo tentativo.Quando uno di questi viene applicato e corrisponde, cerca di subapply ciascuna delle sue foglie, uno per uno, fino a quando uno le partite.Poi cerca le foglie della corrispondenza foglia, e così via, finché non corrisponde più.

In modo che è possibile analizzare le espressioni come

var1 = var2 = var3 = var4

Giusto =) Ora la roba interessante.Questo codice:

var1 = (var2 + var3)

Non analizzare.Quello che succede è che var1 ottenere analizzato (varAccess), assegnare i sub-applicato, è in cerca di un'espressione, cerca 'parentesi', inizia, cerca un'espressione dopo l' '(', trova var2, e poi soffoca sul '+', perché si aspettava un ')'.

Perche 'non e' partita la 'var2 + var3' ?(e sì, c'è un 'aggiungere' SequenceRule, prima di chiedere).Perche 'aggiungere' non è una radice regola (per evitare la ricorsione infinita con l'analisi-espressione-inizio-con-espressione-ecc.) e che le foglie non sono testati in SequenceRules altrimenti sarebbe analizzare le cose come

reader readLine() println()

come

reader (readLine() println())

(ad es.'1 = 3' è l'espressione previsto da aggiungere, la foglia di varAccess a)

considerando che ci piacerebbe che fosse associatività da sinistra a destra, es.l'analisi di come

(reader readLine()) println()

Comunque, ora abbiamo questo problema che ci si dovrebbe essere in grado di analizzare espressione come '1 + 2' interno SequenceRules.Cosa fare?Aggiungi un caso speciale, che quando SequenceRules iniziare con un TokenRule, quindi il GroupRules contiene sono testati per le foglie?Vorrei che anche dare un senso al di fuori di quel particolare esempio?Oppure si dovrebbe essere in grado di specificare in ogni elemento di un SequenceRule se si dovrebbe essere testato per foglie o no?Ditemi cosa ne pensate (altro che buttare via tutto il sistema, che sarà probabilmente accadrà in un paio di mesi comunque)

P. S:Per favore, piuttosto, per favore, non rispondere qualcosa del tipo "andate a leggere questo 400pages libro o anche non meritano il nostro tempo" Se si sente il bisogno - solo superarla e andare bash su reddit.Va bene?Grazie in anticipo.

Answer 1

LL(k) parser top-down ricorsiva, se automatico o scritto a mano) richiedono refactoring della propria grammatica per evitare la ricorsione sinistra, e spesso richiedono capitolato speciale di lookahead (ad es.ANTLR) per essere in grado di gestire k-token di lookahead.Dal momento che le grammatiche sono complessi, si arriva a scoprire k attraverso la sperimentazione, che è esattamente la cosa che si desidera evitare.

YACC/LALR(1) le grammatiche di evitare il problema della ricorsione sinistra, che è un grande passo in avanti.La cattiva notizia è che non ci sono veri e propri programmi lingue (oltre Wirth originale PASCAL) che sono LALR(1).Quindi si arriva a incidere il vostro grammatica a cambiare la LR(k) LALR(1), ancora una volta, costringendo a subire gli esperimenti che espongono i casi strani, e hacking, la grammatica riduzione logica per provare a gestire il K-lookaheads quando i generatori di parser (YACC, BISON, ...si è produrre 1-lookahead parser.

GLR parser (http://en.wikipedia.org/wiki/GLR_parser consentono di evitare quasi tutte queste sciocchezze.Se è possibile scrivere un contesto libero parser, in più circostanze concrete, un GLR parser analizza senza un ulteriore sforzo.Questo è un enorme sollievo quando si tenta di scrivere arbitrario grammatiche.E davvero un buon GLR parser produce direttamente un albero.

BISON è stato migliorato per fare GLR di analisi, una sorta di.È ancora da scrivere complicato logica di produrre il desiderato AST, e si deve preoccupare di come gestire fallito parser e pulizia/eliminare i loro corrispondenti (fallito) di alberi.Il DMS Software Reengineering Tookit fornisce standard di GLR parser per qualsiasi grammatica libera dal contesto, e crea automaticamente ASTs, senza alcuno sforzo supplementare da parte vostra;ambiguo alberi sono automaticamente costruito e può essere pulito dal post-analisi semantica analisi.Abbiamo usato questo per fare definire 30+ lingua grammatiche, tra cui C, C++ (che è ampiamente pensato per essere difficile da analizzare [ed è quasi impossibile analizzare con YACC] ma è semplice con reale GLR);vedere C+++ front end parser e AST builder basato su DMS.

Linea di fondo:se si desidera scrivere le regole di grammatica in modo semplice, e ottenere un parser per il loro trattamento, l'uso GLR l'analisi di tecnologia.Bison quasi opere.DMs davvero opere.

Answer 2

Il mio preferito di analisi tecnica è quello di creare ricorsiva-discesa (RD) parser da un PEG di grammatica specifica.Essi sono di solito molto veloce, semplice e flessibile.Un bel vantaggio è che non dovrete preoccuparvi di separare la suddivisione in token passa, e preoccuparsi di spremere la grammatica in alcuni LALR forma è inesistente.Alcuni PEG librerie sono elencati di [qui][1].

Scusate, so che questo rientra nel buttare via il sistema, ma si sono appena fuori dalla porta con il tuo problema e di commutazione a un PEG RD parser, sarebbe giusto eliminare il mal di testa ora.