Come faccio a implementare in avanti riferimenti in un compilatore?

Question

Sto creando un compilatore con Lex e YACC (in realtà Flex e Bison). Il linguaggio permette riferimenti in avanti illimitate per qualsiasi simbolo (come C #). Il problema è che è impossibile per analizzare il linguaggio senza sapere che cosa è un identificatore.

L'unica soluzione che conosco è quello di lex l'intera sorgente, e poi fare un "breadth-first" analizzare, le cose di livello così alti come dichiarazioni di classe e le dichiarazioni di funzioni vengono analizzati prima che le funzioni che li utilizzano. Tuttavia, ciò avrebbe richiesto una grande quantità di memoria per file di grandi dimensioni, e sarebbe difficile da gestire con YACC (avrei dovuto creare grammatiche separati per ogni tipo di dichiarazione / corpo). Vorrei anche avere a portata di mano-scrivere il lexer (che non è che molto di un problema).

Non mi interessa molto a proposito di efficienza (anche se è ancora importante), perché ho intenzione di riscrivere il compilatore in se stesso una volta che ho finito, ma voglio che la versione per essere veloce (quindi se ci sono qualsiasi tecnica veloce generali che non possono essere fatte in Lex / YACC, ma può essere fatto a mano, si prega di suggerire anche loro). Così adesso, facilità di sviluppo è il fattore più importante.

Ci sono delle buone soluzioni a questo problema? Come è questo di solito fatto in compilatori per linguaggi come C # o Java?

Answer 1

E 'tutto possibile analizzarlo. Sebbene vi sia un'ambiguità tra identificatori e parole chiave, lex felicemente affrontare che dando priorità parole chiave.

Non vedo quale altro problemi ci sono. Non è necessario per determinare se identificatori sono validi durante la fase di analisi. Si sta costruendo sia un albero di analisi o di un albero di sintassi astratta (la differenza è sottile, ma irrilevante ai fini di questa discussione), come si analizza. Dopo di che si costruisce le vostre strutture della tabella dei simboli nidificati eseguendo un passaggio sulla AST generato durante il parsing. Poi si fa un altro passaggio sulla AST per verificare che gli identificatori utilizzati sono validi. Seguire questo con una o più analizza l'AST per generare il codice di uscita, o qualche altro datastructure intermedio e il gioco è fatto!

EDIT: Se volete vedere come è fatto, controllare il codice sorgente per il Mono compilatore C #. Questo in realtà è scritto in C # invece di C o C ++, ma utilizza la porta NET di Jay, che è molto simile a Yacc.

Answer 2

Una possibilità è quella di trattare con riferimenti in avanti da solo la scansione e la memorizzazione nella cache i token fino a colpire qualcosa che si sa come reale con (una specie di recupero di errore "panic-mode"). Una volta eseguito pensato il file completo, tornare indietro e provare a ri analizzare i bit che non analizzano prima.

Per quanto di avere a portata di mano scrivere il lexer; non, uso lex per generare un parser normale e basta leggere da esso tramite uno spessore scritta a mano che ti permette di tornare indietro e alimentare il parser da una cache così come quello che lex fa.

Per quanto riguarda facendo diverse grammatiche, un po 'di divertimento con un preprocessore sul file yacc e si dovrebbe essere in grado di farli tutti dalla stessa fonte originale