Da quando sono state inventate, descrivere ogni linguaggio con una grammatica è diventata prassi comune. La grammatica non è soltanto un formalismo matematico per descrivere la sintassi di un linguaggio di programmazione: è anche un concreto aiuto per implementare l'analizzatore sintattico, detto anche parser.

Lex e Yacc, solitamente usati in coppia, sono due strumenti che consentono di generare automaticamente il parser data la grammatica di un linguaggio e le espressioni regolari dei token. Lex è l'abbreviazione di Lexer (ovvero analizzatore lessicale). Yacc è l'acronimo di una esclamazione: “Yet Another Compiler Compiler!” ("Ancora un altro compilatore di compilatori!"), a testimoniare che al tempo del suo primo sviluppo, strumenti automatici per la costruzione di compilatori dovevano essere abbastanza comuni. Lex e Yacc fanno parte del set di comandi standard di Unix, e da allora hanno dettato una forma di standardizzazione di questi strumenti. Ne esistono infatti varie implementazioni: oltre a quelle incluse nelle versioni di Unix, ci sono prodotti freeware come GNU Flex e Bison (usati per il codice sviluppato per questo articolo) e prodotti commerciali come MKS Lex e Yacc o Abraxas PCLex e PCYacc.

Lex e Yacc non sono in grado di generare un compilatore completo: richiedono codice C/C++ di supporto per le parti non strettamente sintattiche. Entrambi sono dei generatori di codice ad alto livello: normalmente generano codice C che poi deve essere compilato insieme al codice di supporto scritto esplicitamente. Che io sappia, esistono implementazioni di Yacc in grado di generare Pascal, Perl e Java.

Compilatori prodotti con Lex e Yacc vengono spesso chiamati compilatori guidati dalla sintassi, in quanto l'analisi sintattica è alla base di tutto il processo di compilazione; in questo caso viene effettuata per prima l'analisi sintattica, e si utilizzano i risultati di questa fase come guida per le fasi successive, più "semantiche". Tutto il processo può essere visto come una serie di trasformazioni a partire dalla struttura sintattica del sorgente. Comunque in questo articolo tratteremo in dettaglio solo l'analisi sintattica: infatti il traduttore che implementiamo non necessita di complesse operazioni ulteriori una volta che è stata ricostruita la struttura sintattica.