Memoization of Top Down Parsing

Abstract

This paper discusses the relationship between memoized top-down recognizers and chart parsers. It presents a version of memoization suitable for continuation-passing style programs. When applied to a simple formalization of a top-down recognizer it yields a terminating parser.

uuencoded, compressed postscript file

References in corpus (1)

• Principles and Implementation of Deductive Parsing

Cited by in corpus (6)

• Robust Probabilistic Predictive Syntactic Processing
• More declarative tabling in Prolog using multi-prompt delimited control
• Reimplementing the Wheel: Teaching Compilers with a Small Self-Contained One
• Linear Tabling Strategies and Optimizations
• Pattern matching in compilers
• Structured Grammars are Effective