<commit_before># Copyright 2013 <NAME>
# This file is part of Marpa::R2.  Marpa::R2 is free software: you can
# redistribute it and/or modify it under the terms of the GNU Lesser
# General Public License as published by the Free Software Foundation,
# either version 3 of the License, or (at your option) any later version.
#
# Marpa::R2 is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
# Lesser General Public License for more details.
#
# You should have received a copy of the GNU Lesser
# General Public License along with Marpa::R2.  If not, see
# http://www.gnu.org/licenses/.

=head1 NAME

Marpa::R2::Semantics::Order - How the SLIF ranks ambiguous parses

=head1 Description

Marpa allows ambiguous parses.
While an unambiguous parse can produce at most one parse tree
and one parse result,
an ambiguous parse will produce a parse series.
A parse series is a sequence of parse trees,
each of which will have its own parse result.

This document describes ways of controlling
the order in which
the L<SLIF recognizer's C<value()> method|Marpa::R2::Scanless::R/"value()">
evaluates the parse
trees of an ambiguous parse.
It also describes ways to exclude selected parse trees
from the parse series.

=head2 Duplicate parses are eliminated

When evaluating the parse trees in a parse series,
Marpa never evaluates the same parse tree twice.
What this means probably matches the programmer's
intuition of what it should mean.
Marpa considers two parse trees to be the same if they are
B<semantic equivalents>.

Two parse trees are semantic equivalents if
and only if
a recursive, top-down evaluation of each
applies
the same rules
in the same order
at the same G1 locations.
If the semantics are deterministic,
and if two parse trees are
semantic equivalents according to this definition,
the two parse trees will always produce the same parse result.

The two parse trees are called semantic equivalents,
because from the point
of view of a deterministic semantics they are indistinguishable.
When the Marpa documentation refers to duplicate
parses,
unless otherwise stated,
it means that the two
are semantic equivalents.

=head2 Default parse order

By calling
the recognizer's
L<C<value()>|Marpa::R2::Scanless::R/"value()">
method
repeatedly,
Marpa can produce all the parse results
in the current parse series.
The default is for the parse results to be returned
in an B<arbitrary parse order>.
This corresponds to the "C<none>" value of
L<the recognizer's C<ranking_method>|Marpa::R2::Scanless::R/"ranking_method">
named argument.

Traversal of the parse trees in
arbitrary parse order
will be always be well-behaved
in the sense
that no two parse trees will be semantic duplicates,
and no unique (semantic non-duplicate)
parse tree will be omitted in it.
No other property of arbitrary parse order is guaranteed.
For example, the order may
change each time
the parse series is traversed.

=head2 Ranking methods

SLIF recognizer objects have a L<C<ranking_method> named
argument|Marpa::R2::Scanless::R/"ranking_method">,
whose value can be the name of a ranking method,
or "C<none>", indicating that the default ranking method is to
be used.

=head2 The C<rule> ranking method

The rule method ranks alternative parses according to their rule alternatives.
Every rule alternative has a B<numeric rank>.
A rule's rank can be specified using the
the C<rank> adverb
argument for that RHS alternative.
Rule ranks must be integers.
They may be negative.
If no numeric rank is specified, the numeric rank is 0.

=head2 The C<high_rule_only> ranking method

The C<high_rule_only> ranking method is similar to the
C<rule> ranking method, except that, at every choice point,
it discards all of the choices which
have a rank lower than that of the highest ranked choice.

The C<high_rule_only> ranking method 
can reduce the ambiguity of a parse,
but it does not necessarily do so.
This is because, at each choice point among the parse trees,
it is possible that several of the choices,
or all of them, will have the same rank
as the highest ranked choice.

=head2 Rule ranking

A parse series is kept in a structure called a B<parse bocage>.
The parse bocage is a tree-like structure, whose root node
is the common root of all the parse trees of the parse series.
In an unambiguous parse,
there will be only one parse tree,
and the parse bocage will be equivalent
to that parse tree.
In an ambiguous parse,
there will be B<choice points> in the parse bocage.
At the choice points, there will be two or more
B<alternatives> -- choices which
result in different parse trees.

When ranking, the logic traverses the parse bocage,
looking for choice points.
From the point of view of the individual parse trees,
this traversal will be top-down
and left-to-right.
At the choice points,
the choices
are ranked as follows:

=over

=item * B<Different numeric ranks>:

If the two choices have different numeric ranks,
they must also have different rule alternatives.
The choice whose rule alternative has the higher numeric rank
will rank high.

=item * B<Same rule alternative>:

If the two choices have the same rule alternative,
they rank as described
under L<"Null variant ranking">.

=item * B<Same numeric rank, different rule alternatives>:

Two different rule alternatives can have the same numeric rank.
If the two choices are for
different rule alternatives,
with the same numeric rank,
the relative order of the two choices is
arbitrary.

=back

Note that, in the above, the logic is the same regardless of the DSL rule
to which the rule alternatives belong.
Different rule alternatives can,
in the case of a prioritized rule,
belong to the same DSL rule.
But two rule alternatives may also be different because they are
from two different DSL rules.

=head2 Null variant ranking

Some rules have a RHS which contains
B<proper nullables>:
symbols
which may be nulled, but which are not nulling
symbols.
(Nulling symbols are symbols which are B<always> nulled.)

When a rule alternative contains proper nullables,
each instance<commit_msg>Github Issue #21<commit_after># Copyright 2013 <NAME>
# This file is part of Marpa::R2.  Marpa::R2 is free software: you can
# redistribute it and/or modify it under the terms of the GNU Lesser
# General Public License as published by the Free Software Foundation,
# either version 3 of the License, or (at your option) any later version.
#
# Marpa::R2 is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
# Lesser General Public License for more details.
#
# You should have received a copy of the GNU Lesser
# General Public License along with Marpa::R2.  If not, see
# http://www.gnu.org/licenses/.

=head1 NAME

Marpa::R2::Semantics::Order - How the SLIF ranks ambiguous parses

=head1 Description

Marpa allows ambiguous parses.
While an unambiguous parse can produce at most one parse tree
and one parse result,
an ambiguous parse will produce a parse series.
A parse series is a sequence of parse trees,
each of which will have its own parse result.

This document describes ways of controlling
the order in which
the L<SLIF recognizer's C<value()> method|Marpa::R2::Scanless::R/"value()">
evaluates the parse
trees of an ambiguous parse.
It also describes ways to exclude selected parse trees
from the parse series.

=head2 Duplicate parses are eliminated

When evaluating the parse trees in a parse series,
Marpa never evaluates the same parse tree twice.
What this means probably matches the programmer's
intuition of what it should mean.
Marpa considers two parse trees to be the same if they are
B<semantic equivalents>.

Two parse trees are semantic equivalents if
and only if
a recursive, top-down evaluation of each
applies
the same rules
in the same order
at the same G1 locations.
If the semantics are deterministic,
and if two parse trees are
semantic equivalents according to this definition,
the two parse trees will always produce the same parse result.

The two parse trees are called semantic equivalents,
because from the point
of view of a deterministic semantics they are indistinguishable.
When the Marpa documentation refers to duplicate
parses,
unless otherwise stated,
it means that the two
are semantic equivalents.

=head2 Default parse order

By calling
the recognizer's
L<C<value()>|Marpa::R2::Scanless::R/"value()">
method
repeatedly,
Marpa can produce all the parse results
in the current parse series.
The default is for the parse results to be returned
in an B<arbitrary parse order>.
This corresponds to the "C<none>" value of
L<the recognizer's C<ranking_method>|Marpa::R2::Scanless::R/"ranking_method">
named argument.

Traversal of the parse trees in
arbitrary parse order
will be always be well-behaved
in the sense
that no two parse trees will be semantic duplicates,
and no unique (semantic non-duplicate)
parse tree will be omitted in it.
No other property of arbitrary parse order is guaranteed.
For example, the order may
change each time
the parse series is traversed.

=head2 Ranking methods

SLIF recognizer objects have a L<C<ranking_method> named
argument|Marpa::R2::Scanless::R/"ranking_method">,
whose value can be the name of a ranking method,
or "C<none>", indicating that the default ranking method is to
be used.

=head2 The C<rule> ranking method

The rule method ranks alternative parses according to their rule alternatives.
Every rule alternative has a B<numeric rank>.
A rule's rank can be specified using the
the C<rank> adverb
argument for that RHS alternative.
Rule ranks must be integers.
They may be negative.
If no numeric rank is specified, the numeric rank is 0.

=head2 The C<high_rule_only> ranking method

The C<high_rule_only> ranking method is similar to the
C<rule> ranking method, except that, at every choice point,
it discards all of the choices which
have a rank lower than that of the highest ranked choice.

The C<high_rule_only> ranking method 
can reduce the ambiguity of a parse,
but it does not necessarily do so.
This is because, at each choice point among the parse trees,
it is possible that several of the choices,
or all of them, will have the same rank
as the highest ranked choice.

=head2 Rule ranking

A parse series is kept in a structure called a B<parse bocage>.
The parse bocage is a tree-like structure, whose root node
is the common root of all the parse trees of the parse series.
In an unambiguous parse,
there will be only one parse tree,
and the parse bocage will be equivalent
to that parse tree.
In an ambiguous parse,
there will be B<choice points> in the parse bocage.
At the choice points, there will be two or more
B<alternatives> -- choices which
result in different parse trees.

When ranking, the logic traverses the parse bocage,
looking for choice points.
From the point of view of the individual parse trees,
this traversal will be top-down
and left-to-right.
At the choice points,
the choices
are ranked as follows:

=over

=item * B<Different numeric ranks>:

If the two choices have different numeric ranks,
they must also have different rule alternatives.
The choice whose rule alternative has the higher numeric rank
will rank high.

=item * B<Same rule alternative>:

If the two choices have the same rule alternative,
they rank as described
under L<"Null variant ranking">.

=item * B<Same numeric rank, different rule alternatives>:

Two different rule alternatives can have the same numeric rank.
If the two choices are for
rule alternatives that are different,
but that have the same numeric rank,
the relative order of the two choices is
arbitrary.

=back

Note that, in the above, the logic is the same regardless of the DSL rule
to which the rule alternatives belong.
Different rule alternatives can,
in the case of a prioritized rule,
belong to the same DSL rule.
But two rule alternatives may also be different because they are
from two different DSL rules.

=head2 Null variant ranking

Some rules have a RHS which contains
B<proper nullables>:
symbols
which may be nulled, but which are not nulling
symbols.
(Nulling symbols are symbols which are B<always> nulled.)

When a rule alternative contains proper nullables,
each instance
{'fraction_non_alphanumeric': 0.047757575757575756, 'fraction_numerical': 0.004202020202020202, 'mean_word_length': 4.674461256304448, 'pattern_counts': {'":': 0, '<': 61, '<?xml version=': 0, '>': 61, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7121815', 'n_tokens_mistral': 3349, 'n_tokens_neox': 3188, 'n_words': 1925}