Bidirectional Push DOwn Automata

摘要

We define a new model of automata for the description of bidirectional parsing strategies for context-free grammars and a tabulation mechanism that allow them to be executed in polynomial time. This new model of automata provides a modular way of defining bidirectional parses, separating the description of a strategy from its execution.