8 Exhaustion

A parse is exhausted when it cannot accept any further input. A parse is active iff it is not exhausted. For a parse to be exhausted, the furthest earleme and the current earleme must be equal. However, the converse is not always the case: if more tokens can be read at the current earleme, then it is possible for the furthest earleme and the current earleme to be equal in an active parse.

Parse exhaustion always has a location. That is, if a parse is exhausted it is exhausted at some earleme location X. If a parse is exhausted at location X, then

• There may be valid parses at X.
• The parse was active at all locations earlier than X.
• There may be valid parses at locations before X.
• There will be no valid parses at locations after X.
• No tokens can start at location X.
• No tokens can end at a location after X.
• No tokens can start at any location after X.
• No tokens will be accepted by an exhausted parser. It is an irrecoverable hard failure to call marpa_r_alternative() after a parser has become exhausted.
• No Earley sets will be at any location after X.
• No earlemes are completed by, and no Earley sets are created by, an exhausted parser. It is an irrecoverable hard failure to call marpa_r_earleme_complete() after a parser has become exhausted.

Users sometimes assume that parse exhaustion means parse failure. But other users sometimes assume that parse exhaustion means parse success. For many grammars, there are strong associations between parse exhaustion and parse success, but the strong association can go either way, Both exhaustion-loving and exhaustion-hating grammars are very common in practical application.

In an exhaustion-hating application, parse exhaustion typically means parse failure. C programs, Perl scripts and most programming languages are exhaustion-hating applications. If a C program is well-formed, it is always possible to read more input. The same is true of a Perl program that does not have a __DATA__ section.

In an exhaustion-loving application parse exhaustion means parse success. A toy example of an exhaustion-loving application is the language consisting of balanced parentheses. When the parentheses come into perfect balance the parse is exhausted, because any further input would unbalance the brackets. And the parse succeeds when the parentheses come into perfect balance. Exhaustion means success. Any language that balances start and end indicators will tend to be exhaustion-loving. HTML and XML, with their start and end tags, can be seen as exhaustion-loving languages.

One common form of exhaustion-loving parsing occurs in lexers that look for longest matches. Exhaustion will indicate that the longest match has been found.

It is possible for a language to be exhaustion-loving at some points and exhaustion-hating at others. We mentioned Perl’s __DATA__ as a complication in a basically exhaustion-hating language.

marpa_r_earleme_complete() and marpa_r_start_input are the only methods that may encounter parse exhaustion. See marpa_r_earleme_complete(), and marpa_r_start_input(). When the marpa_r_start_input or marpa_r_earleme_complete() methods exhaust the parse, they trigger a MARPA_EVENT_EXHAUSTED event. Applications can also query parse exhaustion status directly with the marpa_r_is_exhausted() method. See marpa_r_is_exhausted().

Parse exhaustion can be triggered on method success by either the marpa_r_earleme_complete() or the marpa_r_start_input method. Parse exhaustion can be triggered on method failure by the marpa_r_earleme_complete() method. Parse exhaustion triggered on method success is called parse exhaustion on success or exhaustion on success. Parse exhaustion triggered on method failure is called parse exhaustion on failure or exhaustion on failure.