.\" Automatically generated by Pod::Man 4.14 (Pod::Simple 3.40)
.\"
.\" Standard preamble:
.\" ========================================================================
.de Sp \" Vertical space (when we can't use .PP)
.if t .sp .5v
.if n .sp
..
.de Vb \" Begin verbatim text
.ft CW
.nf
.ne \\$1
..
.de Ve \" End verbatim text
.ft R
.fi
..
.\" Set up some character translations and predefined strings.  \*(-- will
.\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left
.\" double quote, and \*(R" will give a right double quote.  \*(C+ will
.\" give a nicer C++.  Capital omega is used to do unbreakable dashes and
.\" therefore won't be available.  \*(C` and \*(C' expand to `' in nroff,
.\" nothing in troff, for use with C<>.
.tr \(*W-
.ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p'
.ie n \{\
.    ds -- \(*W-
.    ds PI pi
.    if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch
.    if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\"  diablo 12 pitch
.    ds L" ""
.    ds R" ""
.    ds C` ""
.    ds C' ""
'br\}
.el\{\
.    ds -- \|\(em\|
.    ds PI \(*p
.    ds L" ``
.    ds R" ''
.    ds C`
.    ds C'
'br\}
.\"
.\" Escape single quotes in literal strings from groff's Unicode transform.
.ie \n(.g .ds Aq \(aq
.el       .ds Aq '
.\"
.\" If the F register is >0, we'll generate index entries on stderr for
.\" titles (.TH), headers (.SH), subsections (.SS), items (.Ip), and index
.\" entries marked with X<> in POD.  Of course, you'll have to process the
.\" output yourself in some meaningful fashion.
.\"
.\" Avoid warning from groff about undefined register 'F'.
.de IX
..
.nr rF 0
.if \n(.g .if rF .nr rF 1
.if (\n(rF:(\n(.g==0)) \{\
.    if \nF \{\
.        de IX
.        tm Index:\\$1\t\\n%\t"\\$2"
..
.        if !\nF==2 \{\
.            nr % 0
.            nr F 2
.        \}
.    \}
.\}
.rr rF
.\"
.\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2).
.\" Fear.  Run.  Save yourself.  No user-serviceable parts.
.    \" fudge factors for nroff and troff
.if n \{\
.    ds #H 0
.    ds #V .8m
.    ds #F .3m
.    ds #[ \f1
.    ds #] \fP
.\}
.if t \{\
.    ds #H ((1u-(\\\\n(.fu%2u))*.13m)
.    ds #V .6m
.    ds #F 0
.    ds #[ \&
.    ds #] \&
.\}
.    \" simple accents for nroff and troff
.if n \{\
.    ds ' \&
.    ds ` \&
.    ds ^ \&
.    ds , \&
.    ds ~ ~
.    ds /
.\}
.if t \{\
.    ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u"
.    ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u'
.    ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u'
.    ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u'
.    ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u'
.    ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u'
.\}
.    \" troff and (daisy-wheel) nroff accents
.ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V'
.ds 8 \h'\*(#H'\(*b\h'-\*(#H'
.ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#]
.ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H'
.ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u'
.ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#]
.ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#]
.ds ae a\h'-(\w'a'u*4/10)'e
.ds Ae A\h'-(\w'A'u*4/10)'E
.    \" corrections for vroff
.if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u'
.if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u'
.    \" for low resolution devices (crt and lpr)
.if \n(.H>23 .if \n(.V>19 \
\{\
.    ds : e
.    ds 8 ss
.    ds o a
.    ds d- d\h'-1'\(ga
.    ds D- D\h'-1'\(hy
.    ds th \o'bp'
.    ds Th \o'LP'
.    ds ae ae
.    ds Ae AE
.\}
.rm #[ #] #H #V #F C
.\" ========================================================================
.\"
.IX Title "Marpa::R2::NAIF::Semantics::Order 3pm"
.TH Marpa::R2::NAIF::Semantics::Order 3pm "2021-01-22" "perl v5.32.0" "User Contributed Perl Documentation"
.\" For nroff, turn off justification.  Always turn off hyphenation; it makes
.\" way too many mistakes in technical documents.
.if n .ad l
.nh
.SH "NAME"
Marpa::R2::NAIF::Semantics::Order \- How the NAIF ranks ambiguous parses
.SH "Description"
.IX Header "Description"
This document deals with Marpa's low-level \s-1NAIF\s0 interface.
If you are new to Marpa,
or are not sure which interface you are interested in,
or do not know what the Named Argment InterFace (\s-1NAIF\s0) is,
you probably want to look instead at
the document on semantics for the \s-1SLIF\s0
interface.
.PP
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.
.PP
This document describes ways of controlling
the order in which
the \s-1NAIF\s0 recognizer's \f(CW\*(C`value\*(C'\fR method
evaluates the parse
trees of an ambiguous parse;
It also describes ways to exclude selected parse trees
from the parse series.
.PP
Almost all 
of what is said in this document
also applies to the \s-1SLIF\s0 recognizer's \f(CW\*(C`value\*(C'\fR method.
Certain named arguments which control the parse order are present in the \s-1NAIF,\s0
but are not present in the \s-1SLIF,\s0
and this accounts for the differences between the two.
.SS "Duplicate parses are eliminated"
.IX Subsection "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
intuition of what it should mean.
Marpa considers two parse trees to be the same if they are
\&\fBsemantic equivalents\fR.
.PP
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 earleme locations.
This definition implies that,
given any deterministic semantics,
two parse trees which are
semantic equivalents
will always produce the same parse result \*(--
hence the term.
When the Marpa documentation refers to duplicate
parses, it will mean that the two
are semantic equivalents, unless otherwise
stated.
.SS "Default parse order"
.IX Subsection "Default parse order"
In this document, the term
\&\fBarbitrary parse order\fR
is used to mean an
arbitrary choice among
the strict total orders of
the equivalence classes
that contain the semantically equivalent parse trees.
This set of equivalence classes is finite.
.PP
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.
.PP
By calling
the recognizer's
\&\f(CW\*(C`value\*(C'\fR
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 \fBarbitrary parse order\fR.
This corresponds to the "\f(CW\*(C`none\*(C'\fR" value of
the recognizer's \f(CW\*(C`ranking_method\*(C'\fR
named argument.
.SS "Ranking methods"
.IX Subsection "Ranking methods"
Marpa recognizer objects have a \f(CW\*(C`ranking_method\*(C'\fR named
argument,
whose value can be the name of a ranking method,
or "\f(CW\*(C`none\*(C'\fR", indicating that the default ranking method is to
be used.
.ie n .SS "The ""rule"" ranking method"
.el .SS "The \f(CWrule\fP ranking method"
.IX Subsection "The rule ranking method"
The rule method ranks alternative parses according to their rules.
Every rule has a \fBrule rank\fR.
A rule's rank can be specified using the
the \f(CW\*(C`rank\*(C'\fR named
argument for that rule.
Rule ranks must be integers.
If no rule rank is specified, the rule rank is 0.
.ie n .SS "The ""high_rule_only"" ranking method"
.el .SS "The \f(CWhigh_rule_only\fP ranking method"
.IX Subsection "The high_rule_only ranking method"
The \f(CW\*(C`high_rule_only\*(C'\fR ranking method is similar to the
\&\f(CW\*(C`rule\*(C'\fR 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 alternative.
.PP
Since the \f(CW\*(C`high_rule_only\*(C'\fR ranking method eliminates some
parse trees, it can reduce or eliminate the ambiguity of a parse,
but it does not necessarily do either.
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 alternative.
.SS "Rule ranking"
.IX Subsection "Rule ranking"
A parse series is kept in a structure called a \fBparse bocage\fR.
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 \fBchoice points\fR in the parse bocage.
At the choice points, there will be two or more
\&\fBalternatives\fR \*(-- choices which
result in different parse trees.
.PP
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 alternatives
are ranked (in the \f(CW\*(C`rule\*(C'\fR ranking method)
or selected
(in the \f(CW\*(C`high_rule_only\*(C'\fR ranking method),
by comparing them as follows:
.IP "\(bu" 4
\&\fBDifferent ranks\fR:
If the two alternatives have different rule ranks,
they must also have different rules.
The alternative with the higher rule rank
will rank high.
.IP "\(bu" 4
\&\fBSame Rule\fR:
If the two alternatives have the same rule,
they rank as described
under \*(L"Null variant ranking\*(R".
.IP "\(bu" 4
\&\fBSame rank, different rules\fR:
Two different rules can have the same rank.
If the two alternatives are for
different rules,
but the two rules have the same rank,
the relative order of the two alternatives is
arbitrary.
.SS "Null variant ranking"
.IX Subsection "Null variant ranking"
Some rules have a \s-1RHS\s0 which contains
\&\fBproper nullables\fR:
symbols
which may be nulled, but which are not nulling
symbols.
(Nulling symbols are symbols which are \fBalways\fR nulled.)
.PP
When a rule contains proper nullables, each application
of that rule to a section of input creates a \fBnulling variant\fR \*(--
that rule with a specific pattern of
null and non-null symbols.
In many cases, this creates an ambiguity \*(-- different
nulling variants could apply to the same substring of input.
In ambiguous parsings of this kind,
some applications may want to rank nulling variants that start
with non-null symbols higher.
Other applications may want to do the opposite \*(--
to rank nulling variants that start
with null symbols higher.
.PP
The
\&\f(CW\*(C`null_ranking\*(C'\fR named
argument for rules
specifies which nulling variants are ranked high or low.
Ranking of nulling variants is done left-to-right,
with the null preference as indicated by the \f(CW\*(C`null_ranking\*(C'\fR
named argument.
Specifically, if the \f(CW\*(C`null_ranking\*(C'\fR is "\f(CW\*(C`low\*(C'\fR",
then the closer a nulling variant
places its \fBvisible\fR (non-null) symbols to the start of the rule,
the higher it ranks.
\&\f(CW\*(C`low\*(C'\fR null ranking is the default.
If the \f(CW\*(C`null_ranking\*(C'\fR is "\f(CW\*(C`high\*(C'\fR",
then the closer a nulling variant
places its \fBnull\fR symbols to the start of the rule,
the higher it ranks.
.SS "A general approach to sorting parses"
.IX Subsection "A general approach to sorting parses"
The most general way to sort Marpa parses is for the application
to take control.
The application can set up the Marpa semantic actions
so that the parse result of every parse tree is a
\&\f(CW\*(C`<rank, true_value>\*(C'\fR duple.
The duples can then be sorted by \f(CW\*(C`rank\*(C'\fR.
Once the resuls are sorted,
the \f(CW\*(C`rank\*(C'\fR element of the duple can be discarded.
(Those familiar with the Schwartzian transform
may note a resemblance.
In Perl,
duples can be implemented as references to arrays of 2 elements.)
.PP
The user needs to be careful.
In theory, ambiguity can cause an exponential explosion in the number of results.
In practice, ambiguity tends to get out of hand very easily.
Producing and sorting all the parses can take a very
long time.
.SH "Copyright and License"
.IX Header "Copyright and License"
.Vb 5
\&  Copyright 2014 Jeffrey Kegler
\&  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/.
.Ve