Operator precedence languages: theory and applications

Operator Precedence Languages (OPLs) were introduced in the 1960s by Robert Floyd to support deterministic and efficient parsing of context-free languages. Recently, interest in this class of languages has been renewed thanks to a few distinguishing properties that make them attractive for exploiting various modern technologies in two main contexts: automatic software verification techniques, as model checking, and parallel and incremental parsing of programming and data-description languages. This thesis provides a complete theory of OPLs and investigates the properties that allow for their application in these different fields. Along a first line of research, we complement the results on this class of languages that have been proved in the last half a century, which characterized them in terms of equivalent classes of grammars, recognizing automata and a Monadic second-order logic; the study of their algebraic properties, furthermore, has qualified them as the largest class of deterministic context-free languages enjoying closure under all main language operations (Boolean ones, concatenation, Kleene * and others), strictly including renowned families of formalisms as parentheses languages and Visibly Pushdown Languages (VPLs). In this dissertation we extend research on OPLs to the field of omega-languages, i.e., languages consisting of strings of infinite length, which can model the behavior of systems with never-ending computations (such as operating systems, control systems, web services). We introduce an automata and Monadic second-order logic-based characterization for this class of languages and we prove their closure properties and the decidability of the emptiness problem, showing that they admit a decidable model checking problem. Furthermore, we study logic formalisms simpler than Monadic second-order logic to define suitable subclasses of OPLs. On a second line of investigation, this dissertation deals with a further property enjoyed by OPLs that is not exhibited by other families of deterministic context-free languages such as LR and LL, namely their local parsability. Local parsability means that parsing of any substring of a string according to a grammar depends only on information that can be obtained from a local analysis of the portion of the substring under processing and hence is not influenced by parsing of other substrings. The lack of this property implies that parsing algorithms for, e.g., LR and LL languages are inherently sequential and cannot exploit the speedup achievable by a parallel execution on modern multi-core computing platforms: in fact, if an input string is split into several parts, analyzed in parallel by different processing nodes, the parsing actions may require communication among the different processors, with considerable additional overhead. This thesis studies and exploits the local parsability property of OPLs to enable efficient parallel parsing of data description languages (such as, e.g., the JSON standard data format) and programming languages (as, e.g., Lua and JavaScript) and presents a schema for parallelizing also the lexical analysis phase. The algorithms for parallel parsing and lexing have been implemented in a prototype tool (PAPAGENO), which we validated with an extensive experimental campaign, showing that they achieve significant, near-linear speedups on modern multicore architectures, overcoming state of the art sequential parsers and lexers generated by, e.g., Bison and Flex. We exploit the local parsability property enjoyed by OPLs also for efficient parallel querying of large structured and semistructured documents: we examine, as a case study, an extension of the parallel OP parsing algorithm allowing parallel XPath querying of XML documents on multicore machines.

I linguaggi Operator Precedence (OPL) furono introdotti da Robert Floyd nel 1963 con l’obiettivo di definire algoritmi deterministici ed efficienti per il parsing di linguaggi di programmazione, ma furono abbandonati pochi anni dopo in seguito all’introduzione di tecniche più generali di parsing, basate sulla classe dei linguaggi LR, che consentono l’analisi dell’intera famiglia dei linguaggi deterministici context-free. L’interesse nella classe dei linguaggi Operator Precedence è ripreso solo di recente con la scoperta di alcune interessanti proprietà di cui essi godono, che rendono possibile l’applicazione di questo formalismo in due principali contesti, naturalmente distanti fra loro: per la specifica e verifica automatica di sistemi software tramite model-checking e per l’elaborazione in parallelo (parsing e interrogazione) di linguaggi di programmazione e descrizione di dati. Questa tesi studia i fondamenti teorici degli OPL ed in particolare le proprietà che li rendono un formalismo promettente in questi campi applicativi. In primo luogo, viene proseguita l’attività di ricerca su questa classe di linguaggi risalente agli ultimi decenni, che ha sviluppato una caratterizzazione degli OPL in termini di classi di grammatiche, automi e una logica monadica del secondo ordine. Lo studio delle proprietà algebriche degli OPL, inoltre, ha dimostrato che essi rappresentano la più ampia classe di linguaggi deterministici context-free che gode delle proprietà di chiusura rispetto alle principali operazioni su linguaggi (Booleane, concatenazione, stella di Kleene e altre), includendo strettamente famiglie di linguaggi come linguaggi a parentesi o i linguaggi Visibly Pushdown (VPL). In questa tesi viene presentata una teoria completa degli OPL, estendendo lo stato dell’arte della ricerca su questo formalismo al campo dei linguaggi omega, i.e., linguaggi che consistono di stringhe infinite di simboli e che rappresentano un modello adatto a descrivere il comportamento di sistemi che eseguono le loro computazioni ininterrottamente, come nell’ambito di sistemi operativi, sistemi di controllo, web service. Viene introdotta una caratterizzazione per la classe degli OPL di stringhe infinite basata sulla definizione di opportune famiglie di automi e una logica monadica del secondo ordine, che estende la logica definita per le classi di OPL di parole di lunghezza finita. Inoltre, si dimostra la validità delle proprietà di chiusura e la decidibilità del problema della emptiness per questa classe di linguaggi, mostrando che essi ammettono un problema di model checking decidibile. Vengono quindi analizzate logiche più semplici della logica monadica del secondo ordine per definire opportune sottoclassi degli OPL. Questa tesi affronta inoltre una seconda linea di ricerca, che si fonda sullo studio della proprietà di local parsability degli OPL. La proprietà di local parsability implica che, nel parsing di una stringa di un linguaggio Operator Precedence, le azioni di shift o di riduzione da eseguire dipendono solo da una analisi locale della posizione corrente della stringa da elaborare e non sono influenzate dal parsing di altri fattori distanti della parola stessa. Le azioni di parsing possono essere quindi compiute con la certezza che non saranno mai condizionate né invalidate da operazioni di backtracking dovute all’elaborazione di altre porzioni dell’intera stringa. Questa proprietà rende i linguaggi Operator Precedence ideali per il parsing parallelo su architetture multicore, a differenza dei più generali, classici, linguaggi LR per i quali la proprietà di parsabilità locale invece non sussiste. Una stringa di un linguaggio Operator Precedence può essere infatti suddivisa in diversi segmenti, ciascuno dei quali può essere elaborato in parallelo da un diverso processore. La divisione in segmenti può essere completamente arbitraria perché le azioni di parsing di una stringa sono locali e non dipendono dal contesto precedente. La possibilità di scegliere in modo arbitrario i punti di suddivisione della stringa è una differenza fondamentale che distingue questo approccio di parsing parallelo dai tentativi proposti storicamente in letteratura come per i parser LR, che sono inerentemente sequenziali: suddividendo arbitrariamente la stringa in diversi segmenti, il parsing LR di un segmento da parte di un processore può dipendere da informazioni deducibili solo dall’analisi di altri fattori della parola e che non sono quindi disponibili. Nel parsing parallelo si rende di conseguenza necessaria o una comunicazione tra i processori, con una aggravio sulle performance, o l’assunzione di ipotesi sulle azioni di parsing da compiere con conseguente successivo invalidamento dell’elaborazione compiuta in caso si renda necessario backtracking. Gli approcci al parsing parallelo proposti storicamente in letteratura richiedono quindi, per motivi di performance, che le sottostringhe elaborate dai diversi processori corrispondano ad opportune e ben definite unità sintattiche del linguaggio: ad esempio blocchi di istruzioni o cicli while per una stringa di codice di un linguaggio di programmazione di cui eseguire il parsing in parallelo. Il vincolo di non poter suddividere il testo in modo arbitrario ha però il significativo svantaggio rispetto al parsing Operator Precedence di rendere la suddivisione dipendente dal particolare linguaggio e soprattutto di impedire una distribuzione equa dei segmenti di stringa da processare, e quindi del carico, sui diversi processori. Questa tesi studia la proprietà di local parsability degli OPL e ne analizza l'applicazione per il parsing efficiente in parallelo di linguaggi di descrizione di dati, come JSON, e di linguaggi di programmazione, come Lua e JavaScript; inoltre presenta uno schema per parallelizzare anche la fase di analisi lessicale. Gli algoritmi per l’analisi parallela sintattica e lessicale sono stati implementati in un prototipo (chiamato PAPAGENO), e sono stati validati con un’estesa campagna sperimentale, che ha mostrato come essi siano in grado di raggiungere speedup notevoli, quasi lineari, sulle moderne architetture multicore, ottenendo prestazioni significativamente migliori rispetto ai parser LR o ai lexer sequenziali generati da strumenti classici quali Bison e Flex. Inoltre, questa tesi analizza l’applicazione della proprietà di local parsability di cui godono gli OPL per consentire l’interrogazione efficiente in parallelo di documenti strutturati o semistrutturati di grandi dimensioni: si presenta, come caso di studio, un’estensione dell’algoritmo di parsing in parallelo per gli OPL per l’elaborazione in parallelo di query XPath su documenti XML su architetture multiprocessore.