Seminario: "Operator precedence grammars are back again"
Prof. Dino Mandrioli
Preside della FacoltÓ di Ingegneria dell'Informazione

DEI - Sala Seminari
21/01/2010
Ore 11:00

Abstract
:
"Operator precedence grammars (OPGs) have been invented more than 40 years ago by Robert Floyd in a seminal paper which laid the foundations of determinitic parsing for context-free languages. They have also been proved to have interesting algebraic properties under the motivation of grammar inference. After that they have been forgotten for quite a while due to more powerful parsing techniques which emerged subsequently.
Recently, new classes of deterministic context-free languages, automata and grammars have been introduced under the main motivation of keeping the typical closure and decidability properties enjoied by regular languages; thanks to these properties in fact major breakthroughs in software and system modeling, analysis, and verification have been obtained; model checking is certainly the most striking example of such techniques.
Balanced languages (BLs) and Visual Pushdown Languages (VPLs) are the roots of such prolific geneaolgy of language families.
We argue that the old OPGs -that herewith we call Floyd grtammars (FGs) in honor of their inventor- deserve their own position within the new genealogy. In fact we show that their languages properly include several other families of the geneaolgy and enjoy closure under boolean operations, concatenation, Kleene star and practically all of the traditional language operations: to the best of our knowledge this old family of languages is the largest one that is closed under all such operations."