Come implementare i riferimenti avanzati in un compilatore?

Question

Sto creando un compilatore con Lex e YACC (in realtà Flex e Bison). La lingua consente illimitati riferimenti in avanti a qualsiasi simbolo (come C#). Il problema è che è impossibile analizzare la lingua senza sapere cosa sia 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, questo richiederebbe una grande quantità di memoria per i file di grandi dimensioni, e sarebbe difficile da gestire con YACC (dovrei creare grammatiche separate per ogni tipo di dichiarazione/corpo). Dovrei anche scrivere a mano il lexer (che non è un gran problema).

Non mi interessa un sacco di efficienza (anche se è ancora importante), perché ho intenzione di riscrivere il compilatore in sé una volta che l'ho finito, ma voglio che quella versione sia veloce (quindi se ci sono tecniche generali veloci che non possono essere fatte in Lex/YACC ma possono essere fatte a mano, per favore suggerirle anche). Quindi, al momento, la facilità di sviluppo è il fattore più importante.

Esistono buone soluzioni a questo problema? Come si fa di solito in compilatori per linguaggi come C# o Java?

Answer 1

È completamente possibile analizzarlo. Sebbene vi sia un'ambiguità tra identificatori e parole chiave, lex sarà felice di far fronte a ciò dando la priorità alle parole chiave.

Non vedo quali altri problemi ci siano. Non è necessario determinare se gli identificatori sono validi durante la fase di analisi. Stai costruendo un albero di analisi o un albero di sintassi astratto (la differenza è sottile, ma irrilevante ai fini di questa discussione) durante la tua analisi. Successivamente, si costruiscono le strutture delle tabelle dei simboli nidificate eseguendo un passaggio sull'AST generato durante l'analisi. Quindi esegui un altro passaggio su AST per verificare che gli identificatori utilizzati siano validi. Segui questo con una o più analisi aggiuntive su AST per generare il codice di output o qualche altra infrastruttura intermedia e il gioco è fatto!

MODIFICA: se vuoi vedere come è fatto, controlla il codice sorgente per il compilatore Mono C#. Questo in realtà è scritto in C# piuttosto che in C o C++, ma usa la porta .NET di Jay che è molto simile a yacc.

Answer 2

Un'opzione è quella di gestire i riferimenti in avanti semplicemente mediante i token di scansione e memorizzazione nella cache fino a quando non si colpisce qualcosa con cui si sa come realizzarsi (una specie di ripristino di errore "in modalità panico"). Una volta che hai eseguito il tuo pensiero sul file completo, torna indietro e prova a rielaborare i bit che non sono stati analizzati in precedenza.

Come dover scrivere a mano il lexer; non usare lex per generare un parser normale e basta leggerlo da uno shim scritto a mano che ti permette di tornare indietro e dare da mangiare al parser da una cache, oltre a 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