Marpa, A practical general parser: the recognizer
This work addresses parsing efficiency and flexibility for developers and researchers in computational linguistics and compiler design, representing an incremental improvement by integrating existing advancements.
The paper tackles the problem of practical general parsing by introducing the Marpa recognizer, which unites improvements from Leo (1991) and Aycock and Horspool (2002) to Earley's algorithm, resulting in enhanced error detection and enabling event-driven parsing techniques like 'Ruby Slippers'.
The Marpa recognizer is described. Marpa is a practical and fully implemented algorithm for the recognition, parsing and evaluation of context-free grammars. The Marpa recognizer is the first to unite the improvements to Earley's algorithm found in Joop Leo's 1991 paper to those in Aycock and Horspool's 2002 paper. Marpa tracks the full state of the parse, at it proceeds, in a form convenient for the application. This greatly improves error detection and enables event-driven parsing. One such technique is "Ruby Slippers" parsing, in which the input is altered in response to the parser's expectations.