A syntax directed approach to exploit parallelism in XML query languages

The syntax analysis is a fundamental process to perform translation and parsing of a written text, determining the structure by the definition of a formal grammar and the generation of a syntax tree, which exhibits the rules used during the recognition of the input. The parser can perform other tasks (more or less complicated) other than the generation of the syntax tree by the use of semantic action, depending on the grammar that describes the target language under analysis, for example retrieving precise informations from a written text, taking into account its structure. PAPAGENO is a parallel parser generator written in Python that produces the C code necessary to execute parallel parsing on a text whose grammar satisfies the Operator Precedence Grammar (OPG) rules, also known as Floyd's Grammar. This grammar allows the split of a text in same dimension chunks and the parallel execution of the semantic analysis, granting each processor one of the chunks, without altering the final results, even with an out of order execution. The simultaneous use of more than one processor allows a speedup gain depending on the kind of semantic actions that has to be executed. The purpose of this thesis is to describe an extension of PAPAGENO through the implementation of all the semantic actions that allows the identification of the XML language while at the same moment some kind of information are retrieved from the input file, by means of a query described using the XPath language. All of this is done by exploiting the parallelism resulting from describing the input XML file using the OPG. Moreover, it follows a detailed description of how the program is implemented, the algorithm that handles all the special cases, the design and the implementation of a custom parallel lexer to further enhance the application and to exploit parallelism and the available computing power. Also, are shown the results obtained by intensive and close to reality test cases, and how performance can be improved albeit maintaining a general purpose approach against special purpose examples.

L'analisi sintattica è un processo di analisi fondamentale per svolgere operazioni di riconoscimento e traduzione di un testo scritto, determinandone la struttura tramite la definizione di una grammatica formale e la generazione di un albero sintattico, il quale mostra le regole utilizzate durante il riconoscimento dell'input. Il parser, programma atto ad eseguire questo compito, può svolgere altre azioni più o meno complesse oltre alla generazione dell'albero sintattico, tramite azioni semantiche, a seconda del tipo di grammatica che descrive il linguaggio in esame, come ad esempio recuperare delle informazioni precise da un testo scritto a seconda di come esso è strutturato. PAPAGENO è un generatore di parser paralleli scritto in Python che è in grado di produrre il codice C necessario per eseguire parallelamente l'operazione di parsing su un testo la cui grammatica soddisfi le regole della Grammatica a Precedenza di Operatori. Quest'ultima permette la separazione del testo in parti uguali e l'esecuzione dell'analisi semantica in parallelo, affidando ad ogni processore una parte del testo, senza per questo alterarne il risultato finale, anche con un'esecuzione fuori ordine. L'utilizzo di più processori in contemporanea permette quindi di ricavare uno speedup più o meno elevato a seconda delle azioni semantiche da eseguire. La tesi in esame descrive l'estensione di PAPAGENO tramite l'implementazione di azioni semantiche che permettano il riconoscimento del linguaggio XML mentre se ne esegue un'analisi alla ricerca di informazioni richieste da una query descritta tramite il linguaggio XPath, il tutto sfruttando il parallelismo fornito dalla Grammatica a Precedenza di Operatori. In particolare, la tesi descrive in dettaglio l'algoritmo utilizzato per poter ritrovare le informazioni richieste e come gestire tutti i possibili casi particolari, oltre che il sottoinsieme della grammatica XML modificata per poter soddisfare le regole della grammatica. Inoltre, segue una descrizione dettagliata dell'implementazione del programma per l'esecuzione parallela dell'analisi lessicale (lexer) e delle strutture dati che contengono tutte le informazioni raccolte durante l'analisi semantica, la cui progettazione accurata permette di sfruttare al meglio la potenza di calcolo a disposizione. Si mostrano inoltre i risultati ottenuti con applicazioni concrete attinenti alla realtà, e di come si possano mantenere prestazioni ragguardevoli seppur mantenendo un approccio generico.