This paper presents a thorough discussion of generalized LR parsing with simultaneous attribute evaluation. Nondeterministic parsers and combined parser/evaluators are presented for the LL(0) , LR(0) , and SKLR(0) strategies. SKLR(0) parsing occurs as an intermediate strategy between the first two. Particularly in the context of simultaneous attribute evaluation, generalized SKLR(0) parsing is a sensible alternative for generalized LR(0) parsing.
Head-Corner (HC) parsing has come up in computational linguistics a few years ago, motivated by linguistic arguments. This idea is a heuristic, rather than a fail-safe principle, hence it is relevant indeed to consider the worst-case behaviour of the HC parser. We define a novel predictive head-corner chart parser of cubic time complexity. We start with a left-corner (LC) chart parser, which is easier to understand. Subsequently, the LC chart parser is generalized to an HC chart parser. It is briefly sketched how the parser can be enhanced with feature structures.
The Primordial Soup Algorithm A Systematic Approach to the Specification of Parallel Parsers
Wil Janssen | Mannes Poel | Klaas Sikkel | Job Zwiers
COLING 1992 Volume 1: The 14th International Conference on Computational Linguistics
A connectionist network is defined that parses a grammar in Chomsky Normal Form in logarithmic time, based on a modification of Rytter’s recognition algorithm. A similar parsing network can be defined for an arbitrary context-free grammar. Such networks can be integrated into a connectionist parsing environment for interactive distributed processing of syntactic, semantic and pragmatic information.