Il lexing parallelo

Parallelizzare l’analisi lessicale non è un compito facile come può inizialmen-te sembrare. Il problema risiede nella divisione della stringa di input che è necessaria per poter portare avanti più computazioni in parallelo. Questa operazione infatti può dividere i lessemi, cioè le porzioni dell’input che ven-gono assegnate ai token, tra le unità di computazione, risultando in un’analisi errata dal punto di vista sintattico (o possibilmente anche semantico) se non viene applicata la dovuta cura in fase di ricombinazione.

Alcuni casi sono più semplici da trattare di altri. Ad esempio nel linguag-gio XML il carattere < non può essere presente nè all’interno degli attributi di un tag, nè nel testo racchiuso tra due tag (in entrambi i case deve essere sostituito dalla sequenza &lt;), rimanendo quindi esclusivo dei token che rappresentano i tag di apertura e di chiusura. È perciò sufficiente tagliare l’input in corrispondenza del carattere < per avere la certezza di non separare un lessema.

Nel caso di JSON valgono considerazioni analoghe per quanto riguarda il carattere \n (a capo), che non può essere presente in alcun token del lin-guaggio. Tuttavia, tale carattere potrebbe non essere presente affatto nella stringa di input (specialmente se si tratta di informazioni che non devono risultare leggibili per un essere umano, ma solamente processabili da un cal-colatore). Se così fosse, e non si adottassero altre misure, sarebbe impossibile

individuare dei punti di taglio e quindi la fase di lexing tornerebbe ad essere sequenziale (e gravata dall’overhead dovuto al fatto di aver scandagliato a vuoto una parte consistente dell’input).

Infine, nel caso della maggior parte dei linguaggi di programmazione, esi-stono dei costrutti, come i commenti e le stringhe multilinea, che possono contenere al loro interno qualsiasi tipo di carattere e anche delle sequenze che normalmente verrebbero riconosciute come token del linguaggio (basti pensare al caso molto comune del codice commentato). Qui bisogna per forza abbandonare l’idea di poter dividere l’input senza separare i lessemi, e introdurre delle computazioni alternative per far fronte al nondeterminismo.

Per esporre l’approccio adottato si farà uso di un esempio semplice ma significativo. Si consideri un linguaggio costituito da un’alternanza di strin-ghe e invocazioni di funzioni senza parametri, il cui lessico è il seguente:

STRING -> "([^"\\]|\\.)*"

FUNCTION -> [a-zA-Z][a-zA-Z0-9_]*\(\)

Si supponga di voler effettuare l’analisi lessicale del seguente input func1()"func2()|func3()"func4() usando 2 thread, e dove | non fa parte dell’input ma denota solamente il punto di taglio. Se si utilizzasse il lessico così com’è verrebbe restituito un errore, in quanto il secondo thread leg-gerebbe func3() e successivamente "func4(), dopodichè fallirebbe avendo raggiunto la fine del file senza aver trovato la chiusura della stringa che stava riconoscendo.

Questa impasse si può superare portando avanti per ogni thread oltre il primo più computazioni concorrenti che partano ognuna da una diversa condizione iniziale. Nel caso dell’esempio, il secondo thread dovrebbe partire sia dalla condizione iniziale usuale (quella in cui deve ancora iniziare il rico-noscimento di un token), sia da una nuova condizione iniziale, in cui inizia il riconoscimento già dall’interno della stringa. In questo modo riconoscerà func3()” e successivamente func4(), portando a termine l’analisi nel modo corretto; chiaramente bisognerà poi effettuare la ricombinazione dei risultati parziali, ma questo si vedrà in seguito.

In figura 1 viene mostrato l’automa a stati finiti nondeterministico che viene generato dall’espressione regolare associata al token STRING, mentre in figura 2 è mostrato l’automa a stati finiti deterministico equivalente. La porzione

q₀

Figura 1: L’automa nondeterministico ottenuto dall’espressione regolare associata al token STRING

di automa associata al riconoscimento del token FUNCTION è stata tralasciata in quanto non significativa.

La condizione iniziale classica dell’automa nondeterministico è rappresen-tata dallo stato iniziale q₀. Per consentire il riconoscimento di una stringa dal suo interno va aggiunta come nuova condizione iniziale lo stato q₁, in quanto sarebbe lo stato iniziale dell’automa che verrebbe generato dall’espressione regolare ([^"\\]|\\.)*". Questo non è sufficiente; alla nuova condizione iniziale va anche associata anche la sua -chiusura, costituita dall’insieme {q₁, q₂, q₃, q₅, q₉}.

Con la trasformazione dell’automa in uno equivalente deterministico, le nuove condizioni iniziali vengono mantenute osservando gli insiemi di stati dell’automa nondeterministico che costituiscono un singolo stato dell’automa deterministico. In questo caso la nuova condizione iniziale diventa lo stato d1 in quanto contiene lo stato q₁, e la chiusura associata diventa {d₁, d2, d4} in quanto ciascuno di questi stati contiene almeno uno stato dell’automa nondeterministico che fa parte della -chiusura di q₁.

Effettuare la ricombinazione dei risultati parziali a questo punto è rela-tivamente semplice. Il primo thread ha sempre una sola condizione iniziale, quella che parte dallo stato d₀, e quindi fornisce in output una sola sequenza

d₀|q₀

start

d₁|q₁, q₂, q₃, q₅, q₉ d₂|q₂, q₃, q₄, q₅, q₈, q₉

d₃|q₆ d₄|q₂, q₃, q₅, q₇, q₈, q₉

d₅|q₁₀

" [ˆ"\\]

\\

"

[ˆ"\\]

\\

"

.

[ˆ"\\]

\\ "

Figura 2: L’automa deterministico equivalente a quello in figura 1.

di token. Il secondo thread scorre le proprie computazioni alternative finchè non ne trova una tale che lo stato raggiunto dal thread precedente faccia parte della chiusura del proprio stato iniziale. Se la trova la sceglie come sequenza corretta da unire a quella del thread precedente, altrimenti resti-tuisce un errore. La stessa operazione viene effettuata da tutti gli eventuali thread successivi.

Nel caso dell’esempio al termine della computazione sono presenti queste sequenze:

• Thread 1, stato iniziale d₀: func1(), "func2(), stato raggiunto d2

• Thread 2, stato iniziale d₀: func3(), "func4(), stato raggiunto d2

La prima sequenza del secondo thread viene scartata perchè d₂, lo stato raggiunto dal primo thread, non fa parte della chiusura associata a d₀. La seconda sequenza invece viene accettata perchè d₂ fa parte della chiusura associata a d₁. A questo punto è sufficiente ricostruire il token mancante unendo la stringa finale del primo thread con la stringa iniziale del secondo, formando il lessema "func2()func3()".

Naturalmente per far funzionare il tutto vanno effettuate delle modifi-che all’algoritmo 3. Oltre alla lista di token vanno restituite in output le sottostringhe dei token parzialmente riconosciuti che possono trovarsi sia al-l’inizio che alla fine dell’input, e anche l’ultimo stato raggiunto, per consentire la successiva ricombinazione.

5 Design e implementazione dello strumento

5.1 Il linguaggio Go

Go [3] è un linguaggio open source sviluppato da Google e rilasciato nel 2009, e nasce dall’esigenza di costruire un linguaggio che faciliti la programmazione e che sia al tempo stesso efficiente nella compilazione e nell’esecuzione. Si tratta di un linguaggio compilato, con tipizzazione statica e gestione automa-tica della memoria tramite garbage collector. La sua sintassi ricorda quella del C, con alcune semplificazioni volte ad alleggerire il codice e renderlo me-no ripetitivo. Mantiene alcuni costrutti presenti in altri linguaggi, come le interfacce, ma ne tralascia altri, come l’ereditarietà e i tipi generici.

È stato scelto per programmare il generatore proprio in virtù della sua semplicità e del suo essere un linguaggio di alto livello senza sacrificare troppo in termini di performance [6]. Inoltre presenta dei thread a basso overhead, chiamati goroutine, e dei channel per la comunicazione e la sincronizzazione, primitive che si sono rivelate utili per gestire la concorrenza in modo efficace ed elegante. Infine, pur essendo un linguaggio ancora giovane ha visto la sua popolarità crescere nel corso degli anni [7], e attualmente dispone di una community ampia e attiva e di un buon numero di librerie di supporto.

Nonostante i numerosi aspetti positivi del linguaggio, non si possono tra-lasciare alcune criticità emerse in fase di implementazione. Per mantenere l’esecuzione parallela ed evitare serializzazioni è necessario preallocare buona parte delle strutture dati utili al parser e anche quelle definite dall’uten-te a supporto della semantica. In quest’ottica sarebbe stato comodo podall’uten-ter usare un’unica struttura dati generica per ogni tipo necessario, ma questo attualmente è impossibile dato che Go non supporta i tipi generici. Un altro problema è la mancanza della struttura dati set nella libreria standard; e per quanto sia facile crearne una a partire dai vettori estendibili presenti in Go, detti slice, nuovamente tale struttura sarà legata a un certo tipo e non generica.

Queste problematiche, sebbene meritevoli di attenzione, sono comunque poco influenti considerando la possibilità di poter scrivere dei parser in un linguaggio moderno e di alto livello. Inoltre potranno essere superate con gli sviluppi futuri del linguaggio, e presumibilmente quando esso raggiungerà la versione 2.0.

Specifiche

Figura 3: L’organizzazione di GoPapageno.