++ed by:

23 PAUSE users
17 non-PAUSE users.

Jeffrey Kegler


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



This document describes ways of controlling the order in which the SLIF 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.

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

Default parse order


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.

Ranking methods


The rule ranking method

The rule method ranks alternative parses according to their rule alternatives. Every rule alternative has a numeric rank. A rule's rank can be specified using the the 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.

The high_rule_only ranking method


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

Rule ranking



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

  • Same rule alternative:

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

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

Rule alternatives may be part of a single rule in the DSL -- for example, a prioritized rule. Placement with a DSL rule makes no difference when ranking rule alternatives. For example, it makes no difference if two rule alternatives come from the same prioritized rule; or from two different prioritized rules.

Null variant ranking


When a rule alternative contains proper nullables, each instance of that rule creates a nulling variant. A nulling variant is a specific pattern of null and non-null symbols in a rule instance's RHS. In many cases, this creates an ambiguity -- different nulling variants can match the same substring in the 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 adverb for RHS alternatives specifies which nulling variants are ranked high or low. If the null-ranking is "low", then the closer a nulling variant places its visible (non-null) symbols to the start of the rule instance, the higher it ranks. A null ranking of low 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 instance, the higher it ranks. In ranking nulling variants with more than one proper nullable, major-to-minor is left-to-right.

A general approach to sorting parses



A formal definition

This section is a restatement of earlier definition in more formal language. It is recorded here for those who find it helpful. Most readers will want to ignore this. Call the set of parse trees, T. Semantic equivalence is an equivalence relation on T. Call this relation ~. Call E, the quotient set of T by ~. In this document, the term arbitrary parse order is used to mean an arbitrary choice among the relations which are strict total orders of E.

Copyright and License

  Copyright 2015 Jeffrey Kegler
  General Public License as published by the Free Software Foundation,

  but WITHOUT ANY WARRANTY; without even the implied warranty of
  Lesser General Public License for more details.

  You should have received a copy of the GNU Lesser