L’implementazione dei parser viene generata automaticamente a partire da due file, uno contenente le specifiche del lexer, l’altro quelle del parser. Questi file ricordano quelli utilizzati da Flex [4] e Bison [5] ma con alcune differenze,
dovute in parte alla minore maturità del programma e in parte alla necessità di dover gestire il parallelismo.
5.3.1 Le espressioni regolari
Le espressioni regolari sono delle stringhe che descrivono un linguaggio, cioè un insieme di stringhe. Vengono utilizzate nella fase di generazione per la descrizione del lessico come si vedrà nella sezione 5.3.2. Durante la gene-razione del lexer vengono poi trasformate dapprima in degli automi a stati finiti nondeterministici mediante l’algoritmo di costruzione di Thompson [8], poi tali automi vengono decorati nei loro stati finali con i relativi token (o meglio, con le regole da applicare) e uniti a formare un solo automa, il quale infine viene convertito in uno equivalente deterministico secondo il metodo riportato in [9]. Questo automa rende possibile l’analisi lessicale mediante l’algoritmo 3.
Le espressioni regolari in GoPapageno accettano i seguenti operatori, con i significati descritti e in ordine decrescente di precedenza:
• x, dove x è un generico carattere non speciale, una occorrenza di x.
• \x, dove x è un generico carattere speciale, una occorrenza di x.
• [a-dz], una occorrenza di un carattere tra a e d oppure z (classe di caratteri).
• [^a-dz], una occorrenza di un carattere che non sia tra a e d oppure z (classe di caratteri negata).
• ., una occorrenza di un carattere qualsiasi eccetto \n (a capo).
• (reg), l’espressione regolare reg.
• reg*, zero o più occorrenze dell’espressione regolare reg.
• reg+, una o più occorrenze dell’espressione regolare reg.
• reg1reg2, il concatenamento delle espressioni regolari reg1 e reg2.
• reg1|reg2, l’unione delle espressioni regolari reg1 e reg2.
È presente anche un operatore non standard, aggiunto per far fronte ai
• %altstart%reg, dove reg è un espressione regolare, aggiunge come nuo-va condizione iniziale di riconoscimento lo stato iniziale dell’automa generato da reg, e le associa la sua -chiusura.
5.3.2 Il file di input per il lexer
Questo file ha convenzionalmente estensione .l ed è formato da tre sezioni:
Definizioni
%%
Regole
%%
Codice
Nella sezione Definizioni è possibile aggiungere, una per riga, delle espressioni regolari da associare a un identificatore, nel modo seguente:
Identifier Regex
Succesivamente, l’identificatore può essere usato una o più volte nelle espressioni regolari della sezione Regole usando {Identifier}, e verrà sostituito con l’espressione regolare corrispondente.
In questa sezione è possibile aggiungere anche il seguente comando speciale:
%cut Regex
Dove Regex è un’espressione regolare che verrà usata per individuare i punti in cui tagliare l’input. Ad esempio per un file XML un buon punto in cui tagliare è rappresentato dal carattere <, mentre per un file JSON è ragionevole un \n (a capo), come si è visto nella sezione 4.2. Se questa direttiva viene omessa l’input potrà essere tagliato in qualsiasi punto, il che può potenzialmente dare luogo ad errori (in quanto uno o più token potrebbero essere separati impedendone il riconoscimento) a meno che non venga utilizzato un solo thread oppure tutti i token siano composti da un solo carattere.
La sezione Regole contiene le regole lessicali, che devono avere questa forma:
Regex { Code }
Dove Regex è l’espressione regolare da riconoscere, e Code è il codice Go ad essa associato. Nel caso in cui possono essere attivate più regole verrà scelta quella che riconosce la stringa di caratteri più lunga o, a parità di lunghezza, quella definita prima nel file.
All’interno del codice della regola si possono usare due variabili speciali:
• text, di tipo string, che contiene la stringa riconosciuta
• genSym, di tipo *symbol, che contiene il nuovo simbolo che verrà aggiunto alla lista.
Inoltre va restituito uno dei seguenti valori:
• _ERROR se è avvenuto un errore.
• _SKIP se si vogliono ignorare i caratteri riconosciuti dalla regola.
• _LEX_CORRECT se si vuole aggiungere un token (contenuto in genSym) alla lista.
Infine, nella sezione Codice può essere inserito liberamente del codice, ad esempio funzioni e variabili globali, che possono anche essere richiamate dal codice delle regole. L’unica limitazione è che deve essere sempre definita in questa sezione una funzione con questa segnatura:
func lexerPreallocMem(inputSize int, numThreads int)
Questa funzione viene richiamata dal parser preliminarmente alla fase di lexing e dovrebbe contenere tutte le allocazioni di memoria necessarie, in modo da evitare serializzazioni durante l’esecuzione parallela.
Un esempio del contenuto di un file di questo tipo è presente
5.3.3 Il file di input per il parser
Questo file ha convenzionalmente estensione .g ed è formato da tre sezioni:
Codice
%%
Assioma
%%
Regole
Nella sezione Codice, può essere inserito liberamente del codice, allo stesso modo di quanto visto per il file del lexer, ma qui è necessario inserire una funzione con questa segnatura:
func parserPreallocMem(inputSize int, numThreads int)
Anche in questo caso essa viene richiamata preliminarmente e dovrebbe contenere tutte le allocazioni di memoria necessarie alla fase di parsing.
La sezione Assioma deve contenere unicamente la descrizione dell’assioma della grammatica, in questa forma:
%axiom Token
Dove Token è appunto il nonterminale assioma della grammatica.
Infine, la sezione Regole contiene le regole grammaticali, che devono avere questa forma:
Nonterminale : Token1 Token2 ... TokenN { Code
};
O in alternativa, per le regole che condividono la stessa parte sinistra:
Nonterminale : Token1 Token2 ... TokenN { Code
} | TokenA TokenB ... TokenZ {
Code } ...;
Come si può vedere, la parte sinistra di ogni regola deve contenere un singolo nonterminale, la parte destra invece un insieme di token separati da uno o più spazi. Per rispettare le regole delle grammatiche a operatori naturalmente non potranno essere presenti più nonterminali adiacenti.
All’interno del codice della regola possono essere utilizzati i simboli speciali $$ e $n; questi verranno poi sostuiti con le variabili di tipo *symbol che rappresentano rispettivamente il simbolo associato alla parte sinistra e i vari simboli (uno per token) associati alla parte destra. Ad esempio, per copiare il valore semantico del secondo token della parte destra nel nonterminale prodotto dalla riduzione, si può scrivere:
Nonterminale : Token1 Token2 ... TokenN {
$$.Value = $2.Value };
Un esempio del contenuto di questo file è presente nell’appendice B.