From visibly push-down machines to input-driven language families

Stefano Crespi Reghizzi

Professore emerito del Dipartimento di Elettronica, Informazione e Bioingegneria del Politecnico di Milano

The context-free languages, especially the deterministic ones (DCF) are the successful formal model for all kinds of designed languages (programming, data-definition, domain-specific, etc). But they fail to meet two new requirements that come from the growing complexity of systems and the availability of low-cost multi-core computers. First, the system verification methods in use rely on model checking, which is not possible for DCF and their abstract push-down automata, because the language inclusion problem is undecidable. Second, the existing LR(1) or LL(1) parsers of DCF languages are serial and cannot exploit machine parallelism to shorten time and save energy, because they must scan the text from left to right. Though the two requirements are quite disparate, they are met by related language types that have been intensively investigated in recent years. VPD or visibly-pushdown, as called by Alur & Madhusudan in 2004, are the Input-Driven (ID) languages of Mehlhorn [1980], so called because the choice of the machine move, pushing/popping/staying, is determined by the current input character, which acts as a left/right bracket or as a stack-neutral symbol. They are attractive because they have the essential closure and decidability properties of regular languages. But the same properties hold also for an older language family (Floyd's [1963]) Operator-Precedence OP grammars, recently studied by our group. OP languages strictly include the ID languages; their automata are driven by pairs of adjacent input characters, or rather by the precedence relation of the pairs.Their generative power suffices to define programming languages and to generate efficient parallel parsers. The survey terminates with a glanceat on-going research.