Politecnico di Milano
Scuola di Ingegneria Industriale e dell’Informazione
Corso di Laurea Magistrale in Ingegneria Informatica Dipartimento di Elettronica, Informazione e Bioingegneria
GoPapageno: un generatore di analizzatori sintattici paralleli di nuova generazione
Relatore: Prof. Matteo Pradella Correlatore: Prof. Alessandro Barenghi
Tesi di Laurea di:
Simone Guidi 855155
Indice
1 English summary 3
2 Introduzione 4
3 La fase di analisi sintattica 5
3.1 Le grammatiche a precedenza di operatori . . . 5
3.1.1 Definizioni di base . . . 5
3.1.2 La proprietà di parsabilità locale . . . 6
3.2 L’algoritmo per il parsing sequenziale . . . 7
3.3 L’algoritmo per il parsing parallelo . . . 8
4 La fase di analisi lessicale 10 4.1 L’algoritmo per il lexing sequenziale . . . 10
4.2 Il lexing parallelo . . . 12
5 Design e implementazione dello strumento 17 5.1 Il linguaggio Go . . . 17
5.2 Architettura del programma . . . 18
5.3 Generazione dei parser . . . 18
5.3.1 Le espressioni regolari . . . 19
5.3.2 Il file di input per il lexer . . . 20
5.3.3 Il file di input per il parser . . . 22
5.4 Ottimizzazioni applicate . . . 23
5.5 Modalità d’uso . . . 24
6 Risultati ottenuti 26 6.1 Architettura e file di input . . . 26
6.2 Prestazioni della fase di lexing . . . 26
6.3 Prestazioni della fase di parsing . . . 29
6.4 Confronto con Flex-Bison . . . 31
7 Conclusioni 32
A Specifiche lessicali usate per i test 34
B Specifiche grammaticali usate per i test 36
Elenco delle figure
1 L’automa nondeterministico ottenuto dall’espressione regolare associata al token STRING . . . 14 2 L’automa deterministico equivalente a quello in figura 1. . . . 15 3 L’organizzazione di GoPapageno. . . 18 4 Tempo di esecuzione della fase di lexing all’aumentare del
numero di thread. . . 27 5 Speedup della fase di lexing all’aumentare del numero di th-
read. . . 28 6 Percentuale di codice parallelo nella fase di lexing all’aumen-
tare del numero di thread. . . 28 7 Tempo di esecuzione della fase di parsing all’aumentare del
numero di thread. . . 29 8 Speedup della fase di parsing all’aumentare del numero di
thread. . . 30 9 Percentuale di codice parallelo nella fase di parsing all’aumen-
tare del numero di thread. . . 30
Elenco degli algoritmi
1 OPParsingGeneralizzato(α, head, end, S) . . . . 7 2 ParsingParallelo(β, k) . . . . 9 3 LexingSequenziale(σ) . . . 11
1 English summary
Parsing algorithms are widely used in many fields of computer science, but struggle to keep pace with the recent fast growth of multiprocessor architec- tures, mainly because the formalism they adopt is intrinsically sequential.
In this thesis it is discussed a different approach that exploits the class of grammars called operator precedence grammars; these grammars, although theoretically less powerful than the usual LR grammars, have the property of local parsability, that allows the parallel parsing. Algorithms are also shown for both the sequential and the parallel cases.
It is also discussed a way to parallelize the lexical analysis that would otherwise quickly become the bottleneck of the parsing process. It basically works by adding new start conditions to the recognizer automaton to al- low the recognition of a token even when its lexem is split among different workers.
Then it is described GoPapageno, the tool built, that is a generator of parallel lexers/parsers exploiting the above considerations; it can generate fully functional parsers starting from two files, one containing the lexical specifications and the other the syntactical ones. The structure of these files is described thoroughly, together with a certain numbers of optimizations that were added to increase the performance of the tool.
Last but not least, experimental results are shown that highlight the good amount of scalability reached, and the comparison with a similar tool that generates sequential parsers is analyzed.
2 Introduzione
Gli algoritmi di analisi sintattica trovano largo impiego in svariati ambiti nell’informatica, per esempio nella navigazione web, nella compilazione dei programmi e nell’analisi dei linguaggi naturali. La stragrande maggioranza di essi tuttavia non supporta la computazione parallela, e questo sta diven- tando un problema. Circa un decennio fa è stato raggiunto un limite per la frequenza massima dei processori, portando di conseguenza negli ultimi anni ad architetture non più veloci, ma basate su un numero sempre crescente di unità di calcolo.
Una possibile soluzione a questo problema è stata individuata in una spe- cifica classe di grammatiche, denominate a precedenza di operatori e inven- tate da R. Floyd oltre cinquanta anni fa. Queste grammatiche, pur essendo meno potenti delle grammatiche context-free, hanno la proprietà della parsa- bilità locale, che consente di effettuare il parsing parallelo in modo semplice e deterministico, senza richiedere la presenza di strutture particolari all’interno del file di input nè una fase di scansione preliminare. Inoltre la minor po- tenza generativa è ininfluente in molti casi pratici, sebbene richieda qualche accortezza.
Il generatore di analizzatori lessicali/sintattici costruito, chiamato Go- Papageno [1] (Go Parallel Parser Generator), è uno strumento che sfrutta tale proprietà per generare dei parser paralleli a partire da due file di input, uno contenente le specifiche lessicali e l’altro quelle grammaticali. I parser così generati possono essere utilizzati immediatamente e hanno dimostrato nei test effettuati una buona scalabilità all’aumentare del numero di thread utilizzati. Inoltre, la sua implementazione in un linguaggio moderno quale è Go semplifica la generazione di nuovi parser oltre che l’estendibilità dello strumento stesso.
3 La fase di analisi sintattica
L’analisi sintattica, o parsing, consiste nel ridurre una sequenza di token a un assioma seguendo le regole di una grammatica. Verranno inizialmente analiz- zate le proprietà delle grammatiche a precedenza di operatori, il formalismo che rende possibile il parsing parallelo, nella sezione 3.1, successivamente l’al- goritmo di parsing sequenziale nella sezione 3.2 e infine l’algoritmo parallelo nella sezione 3.3. I risultati mostrati in questa sezione sono descritti con maggiore dettaglio in [2].
3.1 Le grammatiche a precedenza di operatori
3.1.1 Definizioni di base
Si consideri una grammatica context-free denotata dalla tupla (VT, VN, P, S) dove VT è l’alfabeto terminale, VN è l’alfabeto nonterminale, P è l’insieme delle regole grammaticali e S è l’assioma.
Definizione 3.1. Una grammatica è a operatori (OG) se contiene solamente regole la cui parte destra non contiene nonterminali adiacenti.
Per ogni grammatica context-free è possibile ottenere una grammatica a operatori equivalente.
Data una grammatica a operatori G e un nonterminale A, si possono definire i set di terminali sinistro e destro come:
LG(A) = {a ∈ VT | A⇒ Baα}∗ RG(A) = {a ∈ VT | A⇒ αaB}∗ dove B ∈ VN ∪ {}. Tramite questi set vengono definite delle relazioni di precedenza binarie tra terminali:
stessa precedenza: a .
= b ⇐⇒ ∃A → αaBbβ, B ∈ VN∪ {}
prende la precedenza: a m b ⇐⇒ ∃A → αDbβ, D ∈ VN e a ∈ RG(D) cede la precedenza: a l b ⇐⇒ ∃A → αaDβ, D ∈ VN e b ∈ LG(D) Queste relazioni non godono delle proprietà riflessiva, simmetrica e tran- sitiva. Viene detta matrice di precedenza la matrice |VT| × |VT| che contiene per ogni coppia ordinata (a, b) il set M delle relazioni di precedenza tra a
Definizione 3.2. Una grammatica è a precedenza di operatori (OPG) se e solo se la sua matrice di precedenza M non contiene conflitti, cioè se
∀a, b, |Mab| ≤ 1.
Le grammatiche OPG non hanno la stessa potenza generativa di quelle context-free; ad esempio non possono generare il linguaggio L = {anban |n ≥ 1} in quanto necessariamente |Maa| > 1. Nonostante questa limitazione teorica, nella pratica molti linguaggi di programmazioe e di markup possono essere generati da grammatiche OPG, ad esempio Lua, JSON e XML.
Per rimuovere le ambiguità senza perdita di generalità, rendendo più per- formante l’algoritmo di parsing, è conveniente effettuare un’ulteriore trasfor- mazione della grammatica nella forma normale di Fischer (FNF). Le gram- matiche FNF seguono queste regole:
- L’assioma S non è presente nella parte destra di nessuna regola
- Nessuna regola condivide la stessa parte destra con nessun’altra regola - Nessuna regola ad eccezione dell’assioma può avere la stringa vuota come parte destra
- Nessuna regola ad eccezione dell’assioma può avere un singolo nonterminale come parte destra
3.1.2 La proprietà di parsabilità locale
Sia G una grammatica context-free e h ≥ 1. G ha la proprietà di parsabilità locale con limite h se e solo se per ogni regola A → α contenuta in G, ogni volta che
#hS#h ⇒ ζ = βγAδη ⇒ βγαδη∗ ⇒ x∗
con |γ| = |δ| = h, ogni altra derivazione #hS#h ⇒ θγαδφ può essere∗ ottenuta esclusivamente utilizzando la stessa regola A → α per ottenere α.
Quindi h specifica la lunghezza dei dintorni sinistro e destro che sono ne- cessari per essere sicuri che la stringa α debba essere ridotta al nonterminale A. Floyd ha dimostrato che la proprietà di parsabilità locale implica che può essere effettuato il parsing di G in modo deterministico e non ambiguo.
È possibile dimostrare che ogni OPG in FNF gode della proprietà di par- sabilità locale con limite 1. Infatti, se si considera una derivazione βγAδη ⇒ βγαδη, con |γ| = |δ| = 1, allora necessariamente γ, δ ∈ VT ∪ {#}, γ cede la
precedenza al primo terminale in α, l’ultimo terminale in α prende la pre- cedenza su δ e solo terminali con la stessa precedenza sono contenuti in α.
Quindi, ogni volta che la stringa γαδ è presente in G, le relazioni di prece- denza tra i suoi terminali restano invariate, perchè la matrice di precedenza di G è senza conflitti. Dunque α è la parte destra di una regola e, dato che G è in FNF, nessun’altra regola può produrre α nel contesto (γ, δ).
Esistono alcuni linguaggi localmente parsabili con limite 1 che non posso- no essere generati da una grammatica OPG, come il già citato {αnbαn|n ≥ 1}, ma non sono rilevanti nella pratica.
3.2 L’algoritmo per il parsing sequenziale
Algoritmo 1: OPParsingGeneralizzato(α, head, end, S)
1 Sia X = α[head] e si consideri la relazione di precedenza tra il primo terminale in S, detto Y , e X.
2 Se X ∈ VN, aggiungi (X, ⊥) a S; head++
3 Se Y l X, aggiungi (X, l) a S; head++
4 Se Y .
= X, aggiungi (X, .
=) a S; head++
5 Se Y m X, considera S:
6 Se S non contiene nessun l allora aggiungi (X, m) a S; head++
7 Altrimenti sia S (X0, p0)...(Xi−1, pi−1)(Xi, l)...(Xn, pn) dove
∀j, i < j ≤ n, pj 6= l.
8 Se Xi−1 ∈ VN (e quindi pi−1 = ⊥) ed esiste una regola A → Xi−1Xi...XN, sostituisci (Xi−1, pi−1)(Xi, l)...(Xn, pn) in S con (A, ⊥);
9 Se Xi−1 ∈ VT ∪ {#} ed esiste una regola A → Xi...XN, sostituisci (Xi, l)...(Xn, pn) in S con (A, ⊥);
10 Altrimenti restituisci un errore.
11 Se (head < end) oppure (head = end e S 6= (a, ⊥)(B, ⊥)), per qualche B ∈ VN, ripeti dallo step 1
12 Restituisci S
L’algoritmo 1 è quello usato tradizionalmente per il parsing delle gramma- tiche a precedenza di operatori, ma generalizzato in modo che sia in grado di analizzare anche stringhe contenenti nonterminali. Questa generalizzazione
ci nonterminali nell’input di partenza, ma è necessaria in ambito parallelo per poter processare l’input che si ottiene con la ricombinazione dei risultati parziali.
In input prende una sequenza di token α, un intero head che punta alla posizione iniziale, un altro intero end che punta alla posizione finale, e uno stack S, che deve essere già inizializzato con almeno un terminale. Lo stack contiene delle coppie (X, p) dove X ∈ VT ∪ VN e p è una delle tre relazioni di precedenza l, .
=, m se X è un terminale ed è indefinito (⊥) se X è un nonterminale.
Ad ogni passo viene considerata la relazione di precedenza tra il primo terminale presente sullo stack (dove per primo si intende quello inserito più di recente, dato che lo stack segue la politica LIFO) e il token corrente, α[head] (riga 1). Se tale relazione è l, .
= o ⊥ il token corrente viene aggiunto allo stack con la relazione di precedenza corrispondente e si incrementa head (righe 2-4). Se invece la relazione di precedenza è m, bisogna distinguere due casi:
• Se nello stack non è presente nessun elemento (Xi, l), viene aggiunto allo stack il token corrente con relazione di precedenza m e si incrementa head (riga 6).
• Altrimenti, si considerano come maniglia di riduzione gli elementi com- presi tra Xi−1 e la cima dello stack se Xi−1 è un nonterminale o tra Xi e la cima dello stack se Xi−1 è un terminale. Se esiste una regola con parte sinistra A che ha tale maniglia come parte destra, la si sostituisce con (A, ⊥). Se invece non esiste si restituisce un errore, a significare che la sequenza di input non è valida (righe 7-10).
Queste operazioni vengono ripetute finchè non si raggiunge la fine della se- quenza di input oppure, avendola raggiunta, non si ha uno stack composto da un singolo terminale e un singolo nonterminale (riga 11).
3.3 L’algoritmo per il parsing parallelo
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.
4.2 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 <), 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
q0
start
q1 q2
q3 q4
q5 q6 q7
q8 q9
q10
"
[ˆ"\\]
\\ .
"
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 q0. Per consentire il riconoscimento di una stringa dal suo interno va aggiunta come nuova condizione iniziale lo stato q1, 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 {q1, q2, q3, q5, q9}.
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 q1, e la chiusura associata diventa {d1, d2, d4} in quanto ciascuno di questi stati contiene almeno uno stato dell’automa nondeterministico che fa parte della -chiusura di q1.
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 d0, e quindi fornisce in output una sola sequenza
d0|q0
start
d1|q1, q2, q3, q5, q9 d2|q2, q3, q4, q5, q8, q9
d3|q6 d4|q2, q3, q5, q7, q8, q9
d5|q10
" [ˆ"\\]
\\
"
[ˆ"\\]
\\
"
.
[ˆ"\\]
\\ "
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 d0: func1(), "func2(), stato raggiunto d2
• Thread 2, stato iniziale d0: func3(), "func4(), stato raggiunto d2
La prima sequenza del secondo thread viene scartata perchè d2, lo stato raggiunto dal primo thread, non fa parte della chiusura associata a d0. La seconda sequenza invece viene accettata perchè d2 fa parte della chiusura associata a d1. 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 poter 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 della grammatica
È a prece- denza di operatori?
Trasformazione in FNF
Generazione del parser
parallelo
Arricchimento dell’analisi
lessicale
Specifiche lessicali
Generazione del lexer parallelo
Analizzatore completo no
si
si
Figura 3: L’organizzazione di GoPapageno.
5.2 Architettura del programma
Il programma è costituito da due parti fondamentali e distinte, entrambe scritte in Go: il generatore e gli analizzatori generati.
Nella figura 3 è mostrato uno schema delle operazioni interne ed ester- ne che sono necessarie per portare a compimento la generazione dei parser.
In blu sono mostrati gli input, in arancione le operazioni effettuate auto- maticamente dal generatore e in verde quelle che devono essere effettuate esternamente e manualmente. Il generatore inizialmente si occupa di verifi- care che la grammatica fornita sia a precedenza di operatori. Se non è così vengono segnalate le coppie di terminali che presentano relazioni di preceden- za multiple, e la grammatica va modificata. Un metodo efficace per eliminare conflitti di precedenza consiste nell’arricchire l’analisi lessicale aggiungendo dei nuovi terminali. Se invece la grammatica è a operatori, procede con la sua trasformazione nella forma normale di Fischer e con la generazione di lexer e parser paralleli.
5.3 Generazione dei parser
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.
5.4 Ottimizzazioni applicate
GoPapageno punta a generare dei parser le cui prestazioni siano già buone nel caso in cui venga usata una singola unità di computazione, e scalino pres- sochè linearmente nel caso in cui vengano usate più unità di computazione.
Questi risultati sono stati raggiunti anche grazie alle ottimizzazioni di seguito descritte. Naturalmente tutte riguardano i parser generati e non la fase di generazione, in quanto essa non ne ha bisogno.
La struttura dati utilizzata sia per le sequenze di token che per gli stack è una lista di array. Essa combina la flessibilità delle liste, in quanto è sempre possibile aggiungere nuovi elementi finchè non si esaurisce la memoria, con la velocità dell’accesso sequenziale e il ridotto consumo di memoria degli array.
La memoria necessaria al parser viene interamente preallocata usando dei pool, in modo da evitarne la frammentazione e ridurre le serializzazioni dovute a nuove allocazioni. Un primo tentativo prevedeva un singolo pool condiviso tra tutti i thread, in modo da far fronte a situazioni in cui il consu- mo di memoria fosse sbilanciato tra i thread, ma questo approccio si è rivelato
mente perchè ne derivavano eventi di cache line stealing. Attualmente invece viene allocato un pool per ogni thread; sebbene sia più difficile garantire che non verranno effettuate nuove allocazioni, questo approccio si è rivelato vincente sotto il profilo delle prestazioni.
I token vengono salvati in memoria come interi senza segno a 16 bit, e il loro primo bit è riservato per indicare se sono terminali oppure nonterminali, in modo da salvare spazio senza inficiare le possibilità generative, dato che con questa impostazione è possibile generare 215, cioè 32678, terminali e altrettanti nonterminali, più che sufficienti per qualsiasi grammatica di uso pratico.
Effettuare le riduzioni nella fase di parsing è un compito computazional- mente non banale dato che va individuata la regola da applicare tramite la sua parte destra. Per migliorarne le prestazioni è stata usata una struttura dati chiamata trie compressa e descritta in [10].
La matrice di precedenza è stata compressa in un array a 64 bit in modo che ogni valore occupi 2 bit (infatti solo 4 valori di precedenza sono possibili, l, .
=, m e ⊥), consentendo un certo risparmio di memoria. Quest’ultima ottimizzazione non si è rivelata efficace in tutti i casi; sono necessarie infatti alcune computazioni per estrarre il valore di precedenza richiesto, e questo fattore può incrementare il tempo di esecuzione per matrici piccole. Tutta- via all’aumentare del numero di terminali la dimensione della matrice non compressa cresce rapidamente, e a un certo punto il beneficio di poter man- tenere in memoria (e soprattutto in cache) una matrice notevolmente più piccola dovrebbe superare il leggero overhead di computazione. GoPapageno comunque genera entrambe le matrici, in modo che per ogni parser generato si possano effettuare dei test e scegliere quella che si comporta meglio.
5.5 Modalità d’uso
Il generatore può essere eseguito in due modi:
• Compilando il file main.go presente nella root del repository, ed eseguendolo in questo modo:
main -lexicon lexiconfile -grammar grammarfile -outdir outdirpath
• Richiamando la funzione generator.Generate() con i suoi tre parametri all’interno di un programma Go:
generator.Generate(lexiconFilename, grammarFilename, outDir)
I parser così generati prendono in input una stringa oppure un file e il numero di thread che si desidera usare. Il loro package ha il nome della cartella in cui sono contenuti, quindi ad esempio sarà possibile richiamare un parser xml contenuto nella cartella omonima in uno di questi modi:
xml.ParseString(inputString, numThreads) xml.ParseFile(inputFilename, numThreads)
Entrambe queste funzioni restituiscono due variabili, una di tipo *symbol contenente la radice dell’albero sintattico e l’altra di tipo error, nulla nel caso in cui l’esecuzione sia andata a buon fine.
6 Risultati ottenuti
6.1 Architettura e file di input
Per eseguire i test è stato utilizzato un computer POWER7 con architettura PowerPC con 16 core divisi in due chip e 4 thread per core, con una frequenza di clock di 4.25GHz ed equipaggiato con 128MB di ram. Dispone inoltre di 32KB di memoria per i dati e 32KB di memoria per le istruzioni per ogni core come cache di primo livello, di 256KB di memoria per ogni core come cache di secondo livello, e 10MB di memoria condivisa da tutti i core come cache di terzo livello.
Il file utilizzato invece è un documento XML da 100MB ottenuto tramite replicazione da un file da 30MB chiamato lineitem.xml e scaricabile da [11] e viene processato tramite un parser creato con GoPapageno e compilato con la versione 1.7 di Go. Le specifiche lessicali e sintattiche di tale parser sono mostrate nelle appendici A, e B. Come si può vedere non si tratta di specifiche che seguono rigorosamente lo standard, ma sono comunque sufficienti allo scopo di mostrare le prestazioni ottenibili dallo strumento.
Inoltre non viene eseguita alcuna azione semantica al di là della costruzio- ne dell’albero sintattico. Generalmente le azioni semantiche sono più esose in termini di tempo di computazione rispetto alla costruzione dell’albero e, da- to che vengono parallelizzate anch’esse, la loro aggiunta dovrebbe migliorare ulteriormente la scalabilità del parser.
I test sono stati eseguiti tutti nella stessa sessione, variando il numero di thread da 1 a 64 ed effettuando 30 misurazioni per ogni iterazione; è stata poi calcolata la media aritmetica e la deviazione standard, che sono riportate nel grafico dei tempi rispettivamente come un puntino e una linea verticale che termina in due lineette orizzontali.
6.2 Prestazioni della fase di lexing
Le prestazioni della fase di lexing sono riportate in figura 4. Come si può notare il tempo di esecuzione si riduce almeno fino a che vengono utilizzati 32 thread, dopodichè rimane praticamente stazionario.
Questa informazione è ben visibile anche nel grafico seguente (figura 5), in cui è rappresentato lo speedup ottenuto usando un certo numero di thread rispetto all’esecuzione sequenziale. Come si può vedere, viene raggiunto il notevole risultato di un incremento di velocità di esecuzione di circa 18 volte
0 200 400 600 800 1000 1200 1400 1600 1800 2000
4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64
Tempo trascorso (ms)
Numero di thread utilizzati
Figura 4: Tempo di esecuzione della fase di lexing all’aumentare del numero di thread.
in corrispondenza dei 32 thread, che poi al netto di qualche oscillazione ri- mane pressochè invariato aumentando ancora il numero di thread. Infine, in figura 6 è mostrata la percentuale di codice che viene eseguito in parallelo, ottenuta tramite la metrica di Kharp-Flatt [12]. Essa rimane praticamente costante per qualunque numero di thread, e sempre sopra al 95%.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64
Speedup
Numero di thread utilizzati
Figura 5: Speedup della fase di lexing all’aumentare del numero di thread.
0 10 20 30 40 50 60 70 80 90 100
4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64
Codice parallelo (%)
Numero di thread utilizzati
Figura 6: Percentuale di codice parallelo nella fase di lexing all’aumentare del numero di thread.
6.3 Prestazioni della fase di parsing
0 500 1000 1500 2000 2500 3000
4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64
Tempo trascorso (ms)
Numero di thread utilizzati
Figura 7: Tempo di esecuzione della fase di parsing all’aumentare del numero di thread.
Le prestazioni della fase di parsing sono riportate in figura 7. In questo caso sono state prese due misurazioni: sia quella del tempo di esecuzione totale, riportata in blu nel grafico, sia quella del tempo di esecuzione al netto della ricombinazione e della passata finale. In questo modo è possibile vedere precisamente quanto influisce sui risultati tale esecuzione sequenziale.
In figura 8 è mostrato lo speedup ottenuto nei due casi, e qui si può vede- re chiaramente come il codice eseguito sequenzialmente, sebbene costituisca solo una frazione del tempo di esecuzione nel caso del singolo thread, vada a limitare notevolmente lo speedup ottenibile, che comunque raggiunge un buon incremento di circa 7 volte.
Infine, osservando la percentuale di codice parallelo nei due casi, si può vedere come esse procedano parallelamente e distanziate di circa il 10%, a significare che l’overhead di ricombinazione rimane costante e non aumenta.
Naturalmente questi risultati dipendono almeno in parte dalla struttura del file, che determina quanta parte possa essere ridotta in modo parallelo e quanta solamente in modo sequenziale, quindi il gap tra le due curve può
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64
Speedup
Numero di thread utilizzati
Figura 8: Speedup della fase di parsing all’aumentare del numero di thread.
0 10 20 30 40 50 60 70 80 90 100
4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64
Codice parallelo (%)
Numero di thread utilizzati
Figura 9: Percentuale di codice parallelo nella fase di parsing all’aumentare del numero di thread.
6.4 Confronto con Flex-Bison
Per effettuare questo confronto sono stati creati due file di specifica molto simili a quelli delle appendici, da cui sono stati prodotti il lexer e il parser mediante i già citati Flex e Bison. È stato poi creato un file C che all’interno della funzione main imposta semplicemente la variabile yyin con lo stesso file che è stato usato per i test delle sezioni precedenti e poi esegue la funzione yyparse(). Questo file è stato poi compilato con la versione 6.4.1 di gcc, con il flag di ottimizzazione più potente, ovvero -O3.
Il tempo è stato misurato tramite il comando linux perf stat con 30 ri- petizioni, e il risultato ottenuto è stato il seguente: 810ms, con deviazione standard trascurabile. È un risultato assai più basso di quello ottenuto da GoPapageno con un singolo thread (1909ms per la fase di lexing, 2687ms per la fase di parsing, per un totale di 4596ms), tuttavia, come si può notare dai grafici delle sezioni precedenti, il tempo di esecuzione di Flex e Bison vie- ne raggiunto all’incirca in corrispondenza degli 8 thread, e in seguito anche superato, raggiungendo un minimo di circa 500ms totali.
Bisogna poi tenere in considerazione il fatto che Go è di base un linguaggio meno performante del C essendo di più alto livello, e che il suo compilatore non ha la stessa maturità di gcc. Inoltre nel test effettuato con Flex e Bison non è stato materializzato l’albero sintattico, operazione invece presente nei test effettuati con GoPapageno.
7 Conclusioni
GoPapageno è uno strumento potente e flessibile, che può semplificare lo svi- luppo degli analizzatori sintattici e al contempo renderli performanti, special- mente se utilizzati con architetture multiprocessore. L’auspicio è che possa essere migliorato ed espanso in futuro, ad esempio amplificando la parte di diagnostica degli errori, ed utilizzato per generare dei parser completamente funzionali (quindi dotati anche di semantica) per i linguaggi più comuni, e specialmente per quelli maggiormente utilizzati in rete, come JSON e XML, dato che al momento è questo l’ambito principale in cui vengono utilizzati i programmi scritti in Go.
Inoltre, insieme alla precedente versione scritta in C [13], può fare da apripista per nuovi generatori di parser paralleli scritti in altri linguaggi, che possano sfruttare al meglio le architetture multiprocessore presenti ovunque al giorno d’oggi e riportare al passo coi tempi questa importante categoria di algoritmi.
Riferimenti bibliografici
[1] Simone Guidi, GoPapageno, github.com/simoneguidi94/gopapageno [2] A. Barenghi, S. Crespi Reghizzi, D. Mandrioli, F. Panella, M. Pradella,
Parallel Parsing Made Practical
[3] The Go Programming Language, golang.org [4] GNU Flex, www.gnu.org/software/flex/
[5] GNU Bison, www.gnu.org/software/bison/
[6] The Computer Language Benchmarks Game, benchmarksgame.alioth.
debian.org/u64q/which-programs-are-fastest.html
[7] The RedMonk Programming Language Rankings: June 2017, redmonk.
com/sogrady/2017/06/08/language-rankings-6-17/
[8] Algoritmo di Thompson, it.wikipedia.org/wiki/Algoritmo_di_
Thompson
[9] Converting an NFA to a DFA, http://web.cecs.pdx.edu/~harry/
compilers/slides/LexicalPart3.pdf
[10] Ulrich Germann, Eric Joanis, Samuel Larkin, Tightly packed tries: how to fit large models into memory, and make them load fast, too
[11] XMLData Repository, aiweb.cs.washington.edu/research/
projects/xmltk/xmldata/www/repository.html#treebank
[12] Kharp-Flatt metric, en.wikipedia.org/wiki/Karp\T1\
textendashFlatt_metric
[13] Papageno Developers, Papageno, github.com/PAPAGENO-devels/
papageno
A Specifiche lessicali usate per i test
%cut <
VALUE "([^"\\]|\\.)*"
IDENT [a-zA-Z0-9_\-:]+
INFOS [^<]+
SPACE [ \t]
NEWLINE [\r\n]
%%
<{IDENT}>
{
*genSym = symbol{openbracket, 0, nil, nil, nil}
return _LEX_CORRECT }
</{IDENT}>
{
*genSym = symbol{closebracket, 0, nil, nil, nil}
return _LEX_CORRECT }
<{IDENT}/>
{
*genSym = symbol{alternativeclose, 0, nil, nil, nil}
return _LEX_CORRECT }
<{IDENT}({SPACE}+{IDENT}={VALUE})+>
{
*genSym = symbol{openparams, 0, nil, nil, nil}
return _LEX_CORRECT }
<{IDENT}></{IDENT}>
{
*genSym = symbol{opencloseinfo, 0, nil, nil, nil}
return _LEX_CORRECT }
<{IDENT}({SPACE}+{IDENT}={VALUE})+></{IDENT}>
{
*genSym = symbol{opencloseparam, 0, nil, nil, nil}
return _LEX_CORRECT }
({SPACE}|{NEWLINE})+
{
return _SKIP }
<?[^?]+?>
{
return _SKIP }
<![^>]+>
{
return _SKIP }
{INFOS}
{
*genSym = symbol{infos, 0, nil, nil, nil}
return _LEX_CORRECT }
. {
return _ERROR }
%%
func lexerPreallocMem(inputSize int, numThreads int) { }
B Specifiche grammaticali usate per i test
func parserPreallocMem(inputSize int, numThreads int) { }
%%
%axiom ELEM
%%
ELEM : ELEM openbracket ELEM closebracket {
} | ELEM openparams ELEM closebracket {
} | ELEM opencloseinfo {
} | ELEM opencloseparam {
} | ELEM alternativeclose {
} | ELEM infos {
} | openbracket ELEM closebracket {
} | openparams ELEM closebracket {
} | opencloseinfo {
} | opencloseparam {
} | alternativeclose {
} | infos {
};
