L’algoritmo 2 riceve in input una sequena di token β e il numero di thread k che si vogliono impiegare. Inizia dividendo la sequenza in k sottosequenze il più possibile bilanciate. Successivamente esegue k istanze dell’algoritmo 1, con un token di look-back posto nello stack e un altro token di look-ahead
Algoritmo 2: ParsingParallelo(β, k)
1 Dividi la stringa β in k sottostringhe #β1β2...βk#.
2 Esegui in modo concorrente k istanze dell’algoritmo 1, con i seguenti parametri per 1 ≤ i ≤ k: α = aβib, head = |β1β2...βi−1| + 1, end =
|β1β2...βi| + 1, S = (a, ⊥), dove a è l’ultimo simbolo di βi−1 e b è il primo di βi+1, e si pongono β0 = βk+1 = #.
3 Attendi il termine dell’esecuzione delle k istanze, ognuna delle quali fornirà come risultato il proprio stack S.
4 Unisci tutti gli stack per comporre l’input α della passata finale
5 Lancia un’ultima istanza dell’algoritmo 1 con head = 1, end = |α| e S = (#, ⊥)
6 Restituisci il primo nonterminale presente in S
posto alla fine della propria sottosequenza. Questi token condivisi tra thread adiacenti sono necessari per il parser per poter valutare correttamente le relazioni di precedenza anche in seguito alla divisione della sequenza originale.
Per il primo e l’ultimo thread essi saranno un token speciale #, che cede la precedenza a ogni altro token e su cui ogni altro token prende la precedenza.
In seguito attende il termine dell’esecuzione di ogni thread, dopodichè uni-sce tutti gli stack che contengono i risultati parziali tralasciando le relazioni di precedenza, costruendo la sequenza di input finale α. Infine processa α in modo sequenziale nuovamente tramite l’algoritmo 1 per ottenere il risultato finale.
È possibile migliorare l’algoritmo 2. Invece di eseguire un’unica passata finale in modo sequenziale, se ne possono eseguire k-1, ciascuna che prende come input l’output della precedente e lo divide tra lo stesso numero di thread meno uno. Tuttavia, dato che solitamente gli stack restituiti sono molto più piccoli dell’input di partenza, in genere è bene non effettuare più di un paio di passate parallele, per evitare che l’overhead dovuto alla creazione dei thread non superi il beneficio ottenuto dal parallelismo.
4 La fase di analisi lessicale
L’analisi lessicale, o lexing, consiste nella trasformazione di una stringa in una sequenza di simboli (token). Tradizionalmente viene considerata una fase poco dispendiosa rispetto a quella di parsing, ma questa assunzione non è valida se per quest’ultima fase si usano grammatiche a precedenza di ope-ratori. In questo contesto, grazie alla semplicità e all’efficienza dell’algoritmo di parsing, il tempo richiesto dalle due fasi è comparabile già in ambito pu-ramente sequenziale; parallelizzando poi la fase di parsing, quella di lexing diventa rapidamente il collo di bottiglia. Per questo motivo è necessario parallelizzare anche la fase di lexing.
Verrà mostrato innanzitutto un algoritmo sequenziale per effettuare il lexing di una stringa usando un automa a stati finiti nella sezione 4.1. Poi si discuteranno le problematiche del lexing parallelo e se ne mostrerà una possibile soluzione nella sezione 4.2
4.1 L’algoritmo per il lexing sequenziale
L’algoritmo 3 sfrutta un automa a stati finiti, decorato negli stati finali con i token da riconoscere, per effettuare il lexing di una stringa. La convenzione adottata è quella di cercare sempre il più lungo riconoscimento possibile, come da standard per questo tipo di analizzatori.
Il suo funzionamento è piuttosto semplice. Prende in input una stringa σ. Inizia generando una nuova lista L per contenere i token, e creando la variabile pos, inizializzata a 0, che punta al carattere corrente della stringa, la variabile stato, che contiene l’utlimo stato raggiunto dell’automa e vie-ne inizializzata con lo stato di partenza, e le variabili ultimoStatoFinale e posUltimoStatoFinale, che contengono rispettivamente l’ultimo stato finale raggiunto dall’automa e la relativa posizione e sono inizialmente nulle (righe 1-6).
Subito dopo inizia un ciclo che scorre tutti i caratteri della stringa σ tra-mite l’indice pos (riga 7). Ad ogni iterazione lo stato raggiunto dall’automa viene aggiornato tramite la sua lista di transizioni, sfruttando come indice il carattere corrente σ[pos] (riga 8).
Se lo stato raggiunto non è nullo, è sufficiente controllare se è finale, e in tal caso aggiornare la variabile ultimoStatoFinale e la relativa posizione posUltimoStatoFinale (righe 9-12).
Algoritmo 3: LexingSequenziale(σ)
1 L := nuovaLista()
2 pos := 0
3 //automaton contiene gli stati dell’automa deterministico usato per il lexing
4 stato := automaton[0]
5 ultimoStatoFinale := null
6 posUltimoStatoFinale := -1
7 Finchè pos < |σ|:
8 stato := stato.transizioni[σ[pos]]
9 Se stato != null:
10 Se stato.Finale:
11 ultimoStatoFinale = stato
12 posUltimoStatoFinale = pos
13 Altrimenti:
14 Se ultimoStatoFinale != null:
15 L.aggiungi(ultimoStatoFinale.tokenAssociato)
16 stato = automaton[0]
17 pos = posUltimoStatoFinale
18 Altrimenti:
19 Restituisci un errore
20 pos++
21 //Alla fine aggiungi l’ultimo token
22 Se stato == ultimoStatoFinale:
23 L.aggiungi(ultimoStatoFinale.tokenAssociato)
24 Altrimenti:
25 Restituisci un errore
26 Restituisci L
Se invece lo stato raggiunto è nullo, ciò significa che non è stata trovata una transizione per il carattere corrente nello stato attuale. In questo caso controlla se precedentemente è stato raggiunto uno stato finale; se è così, viene aggiunto alla lista il token associato a tale stato finale, lo stato dell’au-toma viene riportato a quello iniziale e la posizione corrente diventa quella dello stato finale. Se invece non è stato precedentemente raggiunto alcuno stato finale, viene restituito un errore, in quanto non è possibile riconoscere un token (righe 14-19).
L’ultima operazione all’interno del ciclo è l’incremento della posizione corrente (riga 20).
Infine, una volta raggiunto il termine della stringa è necessario aggiun-gere l’ultimo token nel caso in cui si sia raggiunto uno stato finale, oppure restituire un errore in caso contrario dato che ci sono dei caratteri che non sono stati riconosciuti (righe 22-25).
In output viene restituita la lista contenente i token generati.