NAME

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

Description

       This document deals with Marpa's low-level NAIF 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 (NAIF) is, you probably want to look instead at the document on semantics for
       the SLIF interface.

       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 NAIF recognizer's
       "value" method evaluates the parse trees of an ambiguous parse; It also describes ways to
       exclude selected parse trees from the parse series.

       Almost all of what is said in this document also applies to the SLIF recognizer's "value"
       method.  Certain named arguments which control the parse order are present in the NAIF,
       but are not present in the SLIF, and this accounts for the differences between the two.

   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 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 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.

   Default parse order
       In this document, the term arbitrary parse order 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.

       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.

       By calling the recognizer's "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 arbitrary parse order.  This corresponds to the ""none"" value of the recognizer's
       "ranking_method" named argument.

   Ranking methods
       Marpa recognizer objects have a "ranking_method" named argument, whose value can be the
       name of a ranking method, or ""none"", indicating that the default ranking method is to be
       used.

   The "rule" ranking method
       The rule method ranks alternative parses according to their rules.  Every rule has a rule
       rank.  A rule's rank can be specified using the the "rank" named argument for that rule.
       Rule ranks must be integers.  If no rule rank is specified, the rule rank is 0.

   The "high_rule_only" ranking method
       The "high_rule_only" ranking method is similar to the "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 alternative.

       Since the "high_rule_only" 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.

   Rule ranking
       A parse series is kept in a structure called a 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 choice points
       in the parse bocage.  At the choice points, there will be two or more 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 alternatives are ranked (in the "rule" ranking method)
       or selected (in the "high_rule_only" ranking method), by comparing them as follows:

       •   Different ranks: If the two alternatives have different rule ranks, they must also
           have different rules.  The alternative with the higher rule rank will rank high.

       •   Same Rule: If the two alternatives have the same rule, they rank as described under
           "Null variant ranking".

       •   Same rank, different rules: 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.

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

       When a rule contains proper nullables, each application of that rule to a section of input
       creates a nulling variant -- 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.

       The "null_ranking" 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 "null_ranking" named argument.  Specifically, if the "null_ranking" is
       ""low"", then the closer a nulling variant places its visible (non-null) symbols to the
       start of the rule, the higher it ranks.  "low" null ranking is the default.  If the
       "null_ranking" is ""high"", then the closer a nulling variant places its null symbols to
       the start of the rule, the higher it ranks.

   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 "<rank, true_value>" duple.  The duples can then be sorted by "rank".  Once the
       resuls are sorted, the "rank" 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.)

       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.

Copyright and License

         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/.