The SCP parsing algorithm : computational framework and formal properties

Abstract

This paper presents a new parsing algorithm for unrestricted context-free grammars. Basically, it may be described as a bidirectional bottom-up parser that is driven by an event generation strategy and is based on a sophisticated Syntactic Constraint Propagation (SCP) technique which uses strong top-down predictions. First, we motivate the new algorithm by discussing the notion of overparsing. Next, we present the formal kernel of the algorithm (based on the relations of partial derivability and adjacency) and a detailed description of the algorithm. Finally, the paper presents some important results from three perspectives: linguistic, computational and formal.