Recursive ascent parsing : from Earley to Marcus

An overview is given of recursive ascent parsing, a new functional implementation technique for parsers for context-free grammars. The theory behind it unifies the treatment of hitherto virtually unrelated parsing methods, such as the Earley algorithm and LR parsing. This is effected by banning the distinguishing factors, such as stacks and parsing tables: stacks are replaced by recursive functions, parsing tables by function memoization. In addition to this unification, the theory provides a high-level view on parsing compared to the standard theory. Nevertheless, the functional implementations are as efficient as conventional ones, especially if the functions that constitute the parsers are formulated in low-level imperative languages with efficient function calls, like C. This means that they are important in practice, for parsing both artificial and natural languages. The recursive ascent treatment of LR(0) parsing has a natural generalization that leads to a new family of look-ahead parsers. This family is akin to the one proposed by Marcus a decade ago to model the processing of a natural language in the human mind