Google Groups

Re: Maximum parse count exceeded — necessarily fatal?

rns Sep 9, 2012 10:11 PM
Posted in group: marpa parser
It's clear now, thanks for explaining.

Limiting time/memory is the job of high_rule_only?

On Monday, September 10, 2012 3:23:14 AM UTC+3, Jeffrey Kegler wrote:
Actually the implementation of max_parses does nothing to limit time/memory usage in earlier phases, so it does not "add value" in that respect.

Why not?  Determining parse count before actually iterating the parse trees is actually fairly difficult.  Consider a parse with two "choice points" (points of ambiguity).  The one "choice point" has 2 alternatives and the other 3.  How ambiguous is the parse?

There are actually five possible answers: the parse count might be 1, 2, 3, 5 or 6.  Neither "choice point" may wind up in the any of the valid parses, so the parse might be unambiguous -- 1 parse tree.  Only one or the other choice point may be used, which would mean 2 parse trees or 3, depending on which "choice point" was used.  Or both "choice points" might be used, in which case the count depends on whether they are "parent-child" or "siblings".  If siblings the parse count is 5, if parent-child it is 6.  In addition, there are issues of external vs. internal representation.

So max_parses just avoids all these issues.  It's a straight increment-and-test, applied as the completed parse trees come out, and implemented in the highest-level of Perl wrappering.

-- jeffrey
On Saturday, September 8, 2012 7:54:55 PM UTC+3, Jeffrey Kegler wrote:
An application can simply count the number of parses, and take whatever
action is desired.  Why, in that case, have a max_parses named argument
at all?  max_parses is mainly intended as a fallback for testing and
debugging, to stop "run-away" parses.  In those contexts, where the
application's logic is in the formative stage, the Draconian solution is
the best way to deal with the "stop loss".  Production applications will
probably avoid max_parses.
Thanks for explaining. 

Fair enough, but a production application can count parses only when it can call value() (am I right, BTW?) and all parses are ready (time/memory had been spent) i.e. it effectively cannot limit time/memory usage by limiting the number of parses even if it uses eval

This, if true, can be a problem, e.g. when parsing natural language where, in my experience, there always can be a construction that would confuse the grammar.

-- jeffrey

rns wrote:
> If there any specific reason for "Maximum parse count (10) exceeded"
> to be fatal? I mean this is not always an error?
> If not, it would be fairly easy to patch by
> defining *Marpa::R2::warning = \&Carp::confess; and using it instead
> of Marpa::R2::exception. Or non-fatals are excluded?