History

The 3rd Generation is faster, more powerful and less complicated, both internally and externally. The 3rd Generation Evaluator benefits from the design lessons learned from the previous two generations.

Marpa is alpha software, and at this point is experimental, so hopefully no major or production applications depended on the 2nd Generation interface.

Ranking Parses

During the life of the 2nd Generation Evaluator, the default parse order varied. In the 3rd Generation Evaluator, it is ""none"". This means that the "ranking_method" named argument of the Marpa Recognizer must be set to a value other than ""none"", or all ranking actions will be silently ignored.

Aside from ""none"", the 2nd Generation Evaluator only had one documented parse order: ""numeric"". This name was somewhat misleading, and the ranking method which provides the same capabilities in the 3rd Generation Evaluator is called ""constant"".

In converting from the 2nd Generation Evaluator to the 3rd, the return values of the ranking actions will usually have to change. In the 2nd Generation, these returned a rank. In the 3rd Generation, these return a reference to a rank. This allows 3rd Generation to specify that, instead of being ranked, a choice should be ignored. If a 3rd Generation ranking closure returns a Perl "undef", the token or rule it corresponds to will be ignored.

Parse Order

Parses results are returned in an order determined by node rank. The rules are

"none"

When the parse order is "none", the node rank is arbitrary and the parse results will be iterated in arbitrary order. This is the most efficient alternative, and is the default.

"numeric"

The ""numeric"" parse order allows user control of the order in which the value method iterates through the parse results. Numeric parse order assigns a Perl numeric value to each leaf node and rule node of the parse. This numeric value becomes the node's rank. Negative values are allowed. The highest numeric value is the highest rank, the lowest numeric value is the lowest rank, and so forth.

By default,

• The rank of every leaf node is 0.
• The rank of every rule node is the sum of the ranks of its child nodes.

The defaults can be changed by assigning ranking actions. The ranking action of a token leaf node is specified using the token symbol's "ranking_action" property. The ranking action of a nulled leaf node is specified using the null node symbol's "ranking_action" property. The ranking action of a rule is specified using the rule's "ranking_action" property.

For the rank of a node to be calculated, the ranking action must first be resolved to a ranking Perl closure. Ranking actions are resolved to ranking Perl closures in the evaluator setup phase, using the same logic that resolves semantics actions to Perl semantic closures. The logic that resolves action names to closures is described in detail in the semantics document.

The ranking closures for token leaf nodes and the ranking closures for nulled leaf nodes are called in the bocage setup phase. The ranking closures for rule nodes are called during the parse setup phase.

Infinitely Ambiguous Grammars

    S ::= A
    A ::= B
    B ::= A
    B :: 'x'

Given the input 'x', this grammar will produce these parses

    S -> A -> B -> x
    S -> A -> B -> A -> B -> x
    S -> A -> B -> A -> B -> x -> A -> B -> x
    .
    .
    .

Because of the two rules "A ::= B" and "B ::= A", this list of parses could go on forever. The two rules "A ::= B" and "B ::= A" form what is called a cycle.

Typically, if a user has written an grammar with an infinite cycle, it was a mistake and he wants to rewrite it before proceeding. By default, an infinitely ambiguous grammar is a fatal error. This is the behavior most users will want.

If a user does want to parse with an infinitely ambiguous grammar, Marpa allows it. The details are described below.

new

    my $evaler = Marpa::Evaluator->new( { recce => $ambiguous_recce } );

The "new" method's arguments are one or more hashes of named arguments. On success, the "new" method returns a new evaluator object. If the "new" method finds that there is no parse of the input according to the grammar, it returns undefined. For other failures, the "new" method throws an exception.

A unsuccessful return from the "new" method means that there is no parse of the input according to the grammar, but the opposite is not necessarily true. It is possible that the "new" method will successfully return an evaluator object, only for the "value" method to return undefined the first time it is called, indicating that there are no parse results. The number of parse results, including whether there are any at all, is not known until they are iterated by the "value" method.

The "recognizer" named argument is required, and its value must be a recognizer object which has finished recognizing a text. The "recce" named argument is a synonym for the "recognizer" named argument. Other named arguments are described below.

set

    $evaler->set( { max_parses => 300 } );

The "set" allows Marpa named arguments to be specified for an evaluator object after its creation. The arguments to the "set" method are zero or more hashes of named arguments.

value

    my @values = ();
    if ($evaler) {
        while ( defined( my $ambiguous_value_ref = $evaler->value() ) ) {
            push @values, ${$ambiguous_value_ref};
        }
    }

Iterates the evaluator object, returning a reference to the value of the next parse result. A Perl "undef" is a valid parse result value, and is returned as a reference to an "undef".

If there are no more parse results, returns undefined. If the input did not match the grammar, the "value" method will return undefined the first time it is called. Failures are thrown as exceptions.

show_bocage

    my $show_bocage_output = $evaler->show_bocage(2);

Returns a multi-line string describing the bocage for an evaluator. The first line contains the count of the parse results produced up to this point from the bocage. The bocage follows in the form of a parse bocage grammar, listed in pre-order.

Parse bocage grammars are similar to parse forest grammars. Parse bocage grammars are described at length in a separate document, using an example output from "show_bocage".

The optional verbosity argument must be an integer greater than or equal to zero. For each parse bocage and-production, if verbosity is a number greater than zero, Marpa shows the LR(0) item corresponding to the and-production's and-node.

If verbosity is less than 2, Marpa shows only the and-productions. If verbosity is 2 or more, Marpa also shows the or-productions. Or-productions contain only redundant information, but the parse bocage grammar is not formally complete without them.

Marpa::location

Marpa::token_location

closure

Sources of action names include

• The "action" properties of rules
• The "default_action" named argument of grammars
• The "lhs" properties of rules
• The "ranking_action" properties of rules
• The "ranking_action" properties of symbols
• For its "new" method, the "action_object" named argument of grammars

When an action name is a key in the "closure" named argument, the usual action resolution mechanism of the semantics is bypassed. A common use of the "closure" named argument is to allow anonymous subroutines to be semantic actions. For more details, see the document on semantics.

end

infinite_rewrite

If the "infinite_rewrite" named argument is false, there will be no rewrite to eliminate infinite cycles. Instead, infinite cycles will be dealt with dynamically, as they arise in the parse setup phase during the calls to "Marpa::Evaluator::value". For more detail, see the section on infinitely ambiguous grammars.

max_parses

Marpa allows extremely ambiguous grammars. The user may write a highly ambiguous grammar by mistake, or as a deliberate choice of parsing strategy for an application. When the ambiguity is a mistake, specifying "max_parses" is useful to limit CPU usage and output length while the issue is being debugged. When ambiguity is a deliberate strategy, it is often the case that the user only wants to see the first few parse results.

parse_order

recce

recognizer

trace_actions

trace_evaluation

trace_file_handle

trace_values

Cycle Length

Cycle length is the number of times a parse derivation goes around a potentially infinite cycle. Above, a set of parses from an example of an infinitely ambiguous grammar was shown. Here are those parses again, this time labeled with their cycle length.

    Cycle length 1: S -> A -> B -> x
    Cycle length 2: S -> A -> B -> A -> B -> x
    Cycle length 3: S -> A -> B -> A -> B -> x -> A -> B -> x

Of the parse results in the above list, Marpa would return a value only for the first, the one whose cycle length is 1.

When iterating parse results for an infinitely ambiguous grammar, two strategies are available to the user. Which is used depends on the setting of the infinite_rewrite named argument. If the infinite_rewrite named argument is true, the rewrite strategy is used. If the infinite_rewrite named argument is false, the dynamic strategy is used. The rewrite strategy is the default.

The Rewrite Strategy

In the rewrite strategy, the parse bocage is rewritten during the evaluator setup phase, in the "Marpa::Evaluator::new" method. Potentially infinite cycles are eliminated in the rewrite, but all derivation paths for cycles of length one are preserved. This is the most powerful method and it works extremely well when the parse only contains a limited number of infinite cycles.

A disadvantage of the rewrite strategy is that the rewrite is done, and its full cost in CPU time incurred, before any parses are returned. Marpa typically tries to amortize the cost of ambiguity over the parse results.

Another disadvantage of the rewrite strategy is that there are grammars for which the rewrite is so CPU intensive that it is simply impractical for a parse of any size. These cases are probably only theoretical, but they are not very hard to create.

The extreme worst cases are plex grammars. In a plex grammar, every symbol directly produces every other symbol. That is, in a plex grammar, for every ordered pair of symbols X and Y, there is a rule of the form

     X ::= Y

I cannot think that anyone will be using plex grammars in a practical application. On the other hand, the same thing might be said of infinite ambiguity itself.

The Dynamic Strategy

The rewriting of infinite cycles can be turned off by setting the Multi-parse Evaluator's "infinite_rewrite" named argument to false. This totally eliminates the cost of the infinite cycle rewrite. The disadvantage of the dynamic strategy is that, in Marpa's current implementation, it skips some parse results which the rewrite strategy includes.

The rewrite strategy includes all the parse results that are possible when cycle length is limited to 1. Where there are multiple, connected cycles, the rewrite strategy will iterate every possible way of reaching every possible cycle.

When multiple cycles interconnect, many parse results will simply be different paths through the tangle of cycles. The dynamic strategy prunes some of these paths. If an application does not need a precise enumeration of all possible ways of reaching every cycle at every location, this pruning may be acceptable or even preferred.