Esiste un’alternativa per flex / bison utilizzabile su sistemi embedded a 8 bit?

Sto scrivendo un piccolo interprete per un semplice linguaggio BASIC come un esercizio su un microcontrollore AVR in C usando la toolchain avr-gcc. Tuttavia, mi chiedo se ci siano strumenti open source che potrebbero aiutarmi a scrivere il lexer e il parser.

Se scrivessi questo per funzionare sulla mia macchina Linux, potrei usare flex / bison. Ora che mi sono limitato a una piattaforma a 8 bit devo fare tutto a mano o no?

Ho implementato un parser per una semplice lingua di comando destinata all’ATmega328p . Questo chip ha 32k ROM e solo 2k di RAM. La RAM è sicuramente la limitazione più importante: se non sei ancora legato a un particolare chip, sceglierne uno con la RAM più grande ansible. Questo renderà la tua vita molto più facile.

All’inizio ho considerato l’utilizzo di flex / bisonte. Ho deciso contro questa opzione per due motivi principali:

  • Per impostazione predefinita, Flex & Bison dipende da alcune funzioni di libreria standard (specialmente per I / O) che non sono disponibili o che non funzionano nello stesso modo in avr-libc. Sono abbastanza sicuro che ci sono soluzioni alternative supportate, ma questo è uno sforzo extra che è necessario prendere in considerazione.
  • AVR ha un’architettura di Harvard . C non è progettato per tener conto di ciò, quindi anche le variabili costanti vengono caricate nella RAM di default . È necessario utilizzare macro / funzioni speciali per archiviare e accedere ai dati in flash ed EEPROM . Flex & Bison crea alcune tabelle di ricerca relativamente grandi, che mangeranno la RAM abbastanza velocemente. A meno che non mi sbagli (il che è del tutto ansible) dovrai modificare la sorgente di output per sfruttare le speciali interfacce Flash ed EEPROM.

Dopo aver respinto Flex & Bison, sono andato alla ricerca di altri strumenti di generazione. Ecco alcuni che ho considerato:

  • LIMONE
  • Ragel
  • re2c

Si potrebbe anche voler dare un’occhiata al confronto di Wikipedia .

Alla fine, ho finito per codificare a mano sia il lexer che il parser.

Per l’analisi ho usato un parser di discesa ricorsivo. Penso che Ira Baxter abbia già fatto un lavoro adeguato per coprire questo argomento, e ci sono un sacco di tutorial online.

Per il mio lexer, ho scritto delle espressioni regolari per tutti i miei terminali, ho disegnato la macchina a stati equivalente e l’ho implementata come una gigantesca funzione usando goto ‘s per saltare tra gli stati. Questo è stato noioso, ma i risultati hanno funzionato alla grande. Per inciso, goto è un ottimo strumento per implementare macchine a stati: tutti i tuoi stati possono avere etichette chiare proprio accanto al codice pertinente, non ci sono overhead di chiamate a funzioni o variabili di stato, ed è più veloce che puoi ottenere. C in realtà non ha un costrutto migliore per build macchine a stati statici.

Qualcosa su cui riflettere: i lexer sono in realtà solo una specializzazione dei parser. La più grande differenza è che le grammatiche regolari sono in genere sufficienti per l’analisi lessicale, mentre la maggior parte dei linguaggi di programmazione ha (per lo più) grammatiche senza contesto. Quindi non c’è davvero nulla che ti impedisca di implementare un lexer come un parser di discesa ricorsivo o usare un generatore di parser per scrivere un lexer. Di solito non è così comodo come usare uno strumento più specializzato.

Se si desidera un metodo semplice per codificare i parser o se si dispone di spazio limitato, è necessario codificare manualmente un parser di discesa ricorsivo; questi sono essenzialmente parser LL (1). Ciò è particolarmente efficace per le lingue che sono “semplici” come di base. (Ne ho fatti parecchi negli anni ’70!). La buona notizia è che questi non contengono alcun codice di libreria; solo quello che scrivi

Sono abbastanza facili da programmare, se hai già una grammatica. Per prima cosa, devi eliminare le regole ricorsive di sinistra (ad es. X = XY). Questo è generalmente abbastanza facile da fare, quindi lo lascio come un esercizio. (Non devi farlo per le regole di formazione delle liste, vedi la discussione di seguito).

Quindi se hai la regola BNF del modulo:

  X = ABC ; 

crea una subroutine per ogni elemento della regola (X, A, B, C) che restituisce un booleano che dice “Ho visto il costrutto syntax corrispondente”. Per X, codice:

 subroutine X() if ~(A()) return false; if ~(B()) { error(); return false; } if ~(C()) { error(); return false; } // insert semantic action here: generate code, do the work, .... return true; end X; 

Allo stesso modo per A, B, C.

Se un token è un terminale, scrivere il codice che controlla il stream di input per la stringa di caratteri che costituisce il terminale. Ad esempio, per un numero, controllare che il stream di input contenga cifre e avanzare il cursore del stream di input oltre le cifre. Questo è particolarmente facile se si esegue il parsing di un buffer (per BASIC si tende a ottenere una riga alla volta) semplicemente avanzando o non facendo avanzare un puntatore di scansione del buffer. Questo codice è essenzialmente la parte lessicale del parser.

Se la tua regola BNF è ricorsiva … non preoccuparti. Basta codificare la chiamata ricorsiva. Questo gestisce le regole grammaticali come:

 T = '(' T ')' ; 

Questo può essere codificato come:

 subroutine T() if ~(left_paren()) return false; if ~(T()) { error(); return false; } if ~(right_paren()) { error(); return false; } // insert semantic action here: generate code, do the work, .... return true; end T; 

Se hai una regola BNF con un’alternativa:

  P = Q | R ; 

quindi codice P con scelte alternative:

 subroutine P() if ~(Q()) {if ~(R()) return false; return true; } return true; end P; 

A volte incontrerai delle regole per la formazione di liste. Questi tendono ad essere lasciati ricorsivi e questo caso è facilmente gestibile. Esempio:

 L = A | LA ; 

Puoi codificarlo come:

 subroutine L() if ~(A()) then return false; while (A()) do // loop return true; end L; 

Puoi codificare diverse centinaia di regole di grammatica in un giorno o due in questo modo. Ci sono altri dettagli da completare, ma le basi qui dovrebbero essere più che sufficienti.

Se si è veramente stretti nello spazio, è ansible build una macchina virtuale che implementa queste idee. Questo è quello che ho fatto negli anni ’70, quando le parole 8K a 16 bit erano ciò che si poteva ottenere.


Se non vuoi codificarlo a mano, puoi automatizzarlo con un metacompiler ( Meta II ) che produce essenzialmente la stessa cosa. Questi sono un divertimento tecnico strabiliante e ci tengono davvero tutto il lavoro fuori da questo, anche per grandi grammatiche.

Agosto 2014:

Ricevo molte richieste per “come build un AST con un parser”. Per i dettagli su questo, che essenzialmente elabora questa risposta, vedi la mia altra risposta SO su https://stackoverflow.com/a/25106688/120163

Luglio 2015:

Ci sono molte persone che vogliono scrivere un semplice valutatore di espressioni. Puoi farlo facendo lo stesso tipo di cose che suggerisce il link “Builder AST” sopra; basta fare aritmetica invece di build nodes ad albero. Ecco un valutatore di espressioni fatto in questo modo .

È ansible utilizzare flex / bison su Linux con il suo gcc nativo per generare il codice che verrà quindi cross-compilato con AVR gcc per il target incorporato.

GCC può eseguire una compilazione incrociata su una varietà di piattaforms, ma si esegue flex e bison sulla piattaforma su cui si sta eseguendo il compilatore. Sputano solo il codice C che il compilatore quindi costruisce. Provalo per vedere quanto è veramente grande l’eseguibile risultante. Nota che hanno librerie temporali di esecuzione ( libfl.a ecc.) Che dovrai anche compilare per compilare il tuo objective.

Prova Boost :: Spirit. È una libreria di sola intestazione che puoi rilasciare e creare un parser molto veloce e pulito completamente in C ++. Gli operatori sovraccaricati in C ++ vengono utilizzati al posto di un file di grammatica speciale.

Invece di reinventare la ruota, dai un’occhiata a LUA: http://www.lua.org . È un linguaggio interpretativo pensato per essere incorporato in altri software e utilizzato su sistemi su piccola scala, come i sistemi embedded. Albero di analisi syntax procedurale incorporato, logica di controllo, supporto matematico e variabile: non è necessario reinventare qualcosa che migliaia di altri hanno già eseguito il debug e l’utilizzo. Ed è estensibile, il che significa che puoi aggiungere alla grammatica aggiungendo le tue funzioni C.