The work presented here attempts to bring out some fundamental concepts that underlie some known parsing algorithms, usually called chart or dynamic programming parsers, in the hope of guiding the design of similar algorithms for other formalisms that could be considered for describing the “surface” syntax of languages. The key idea is that chart parsing is essentially equivalent to a simple construction of the intersection of the language (represented by its grammar) with a regular set containing only the input sentence to be parsed (represented by a finite state machine). The resulting grammar for that intersection is precisely what is usually called a shared forest: it represent all parses of a syntactically ambiguous sentence. Since most techniques for processing ill-formed input can be modeled by considering a non-singleton regular set of input sentences, we can expect to generalize these ill-formed input processing techniques to all parsers describable with our approach.
The Logic Push-Down Automaton (LPDA) is introduced as an abstract operational model for the evaluation of logic programs. The LPDA can be used to describe a significant number of evaluation strategies, ranging from the top-down OLD strategy to bottom-up strategies, with or without prediction. Two types of dynamic programming, i.e. tabular, interpretation are defined, one being more efficient but restricted to a subclass of LPDAs. We propose to evaluate a logic program by first compiling it into a LPDA according to some chosen evaluation strategy, and then applying a tabular interpreter to this LPDA. This approach offers great flexibility and generalizes the magic-set transformations. It explains in a more intuitive way some known magic-set variants and their limits, and also suggests new developments.