Provided by: libmarpa-r2-perl_2.086000~dfsg-8build5_amd64 bug

NAME

       Marpa::R2::NAIF::Grammar - NAIF grammars

Synopsis

           my $grammar = Marpa::R2::Grammar->new(
               {   start   => 'Expression',
                   actions => 'My_Actions',
                   default_action => 'first_arg',
                   rules   => [
                       { lhs => 'Expression', rhs => [qw/Term/] },
                       { lhs => 'Term', rhs => [qw/Factor/] },
                       { lhs => 'Factor', rhs => [qw/Number/] },
                       { lhs => 'Term', rhs => [qw/Term Add Term/], action => 'do_add' },
                       {   lhs    => 'Factor',
                           rhs    => [qw/Factor Multiply Factor/],
                           action => 'do_multiply'
                       },
                   ],
               }
           );

           $grammar->precompute();

Description

       This document describes grammars for Marpa's named argument interface (NAIF).  If you are
       a beginner, or are not sure which interface you are interested in, or do not know what the
       NAIF interfaces is, you probably are looking for the document on grammars for the SLIF
       interface.

       To create a Marpa grammar object, use the "new" method.  Rules and symbols may be
       specified when the grammar is created.

       To change a Marpa grammar object, use the "set" method.  New rules may be added until a
       grammar is precomputed.

       A grammar cannot be used for parsing until it is precomputed.  To precompute a Marpa
       grammar object, use the "precompute" method.  After precomputation, no new rules may added
       and most other changes are forbidden.

   Symbol names
       Marpa reserves, for its internal use, all symbol names ending with one of these four
       symbols: the right square bracket (""]""), the right parenthesis ("")""), the right angle
       bracket ("">""), and the right curly bracket (""}"").  Any other valid Perl string is an
       acceptable symbol name.

   Terminal symbols
       Marpa defines a terminal as a symbol which is valid as an input token symbol.  By default,
       the terminals are those symbols who do not appear on the LHS of any rule.

       Marpa will allow any non-nulling symbol to be a terminal, even those which appear on the
       LHS of one or more rules.  To allow (or disallow) use of a symbol as a terminal, the
       application can use the "terminals" named argument, and the "terminal" property.  An
       attempt to use a nulling symbol as a terminal is a fatal error.

   Sequence rules
       It is very common in a grammar for one symbol to produce a repeating sequence.  Marpa
       allows a shorthand for this: sequence rules.  The RHS of a sequence rule will be repeated,
       as specified by the "min" rule property.  In sequence rules the RHS must always be one
       symbol in length, and that symbol may not be a nullable symbol.

       A rule is a sequence rule if the "min" rule property is defined.  "min" can be 0 or 1, and
       specifies the minimum number of times that the sequence is allowed to repeat.  As of this
       writing, the maximum number of repetitions is always infinite.

           { lhs => 'sequence', rhs => ['item'], min => 0, action => 'do_sequence' }

       A "min" of zero indicates a sequence that repeats zero or more times.  This is the
       equivalent of using the star quantifier (""*"") in the standard regular expression
       notation.

           { lhs => 'sequence', rhs => ['item'], min => 1, action => 'do_sequence' }

       A "min" of one indicates a sequence that repeats one or more times.  This is the
       equivalent of using the plus quantifier (""+"") in the standard regular expression
       notation.

       Sequences can have a separator, specified with the "separator" rule property.  By default,
       separation is Perl-style: trailing separators are allowed.  In ""proper"" separation, a
       separator must actually separate two sequence items and therefore is not allowed after the
       last item of a sequence.  If you prefer ""proper"" separation, you can set the "proper"
       rule property.

       Advantages of sequence rules

       You are never forced to use sequence rules, but it's usually better if you do.  When a
       sequence is written as a sequence rule, Marpa optimizes it.

       When a sequence is written using non-sequence rules, the semantics typically wind up being
       spread over two or three Perl closures.  The semantic action for a sequence rule is a
       single Perl closure.  Putting the semantics into a single Perl closure often results in
       simpler and more natural code.  See the section on sequences in the semantics document.

       Caveats

       Marpa throws an exception if you try to use a nullable symbol as the right hand side of a
       sequence rule, or as the separator for a sequence rule.  The ban on nullables in sequences
       only applies to sequences when they are written using sequence rules.  Nothing prevents
       you from specifying a sequence of nullables using non-sequence rules.  But usually there
       is no good reason to do this, and sequences of nullables can be highly ambiguous which,
       for efficiency reasons, makes them a good thing to avoid.

       To keep things simple, the right hand side of a sequence rule must be a single symbol.  Of
       course, applications will often want to repeat sequences of multiple symbols.  That is
       easy to do indirectly:

           { lhs => 'sequence', rhs => [qw(item)], min => 0, action => 'do_sequence' },
           { lhs => 'item', rhs => [qw(part1 part2)], action => 'do_item' },

Constructor

   new()
           my $grammar = Marpa::R2::Grammar->new(
               {   start   => 'Expression',
                   actions => 'My_Actions',
                   default_action => 'first_arg',
                   rules   => [
                       { lhs => 'Expression', rhs => [qw/Term/] },
                       { lhs => 'Term', rhs => [qw/Factor/] },
                       { lhs => 'Factor', rhs => [qw/Number/] },
                       { lhs => 'Term', rhs => [qw/Term Add Term/], action => 'do_add' },
                       {   lhs    => 'Factor',
                           rhs    => [qw/Factor Multiply Factor/],
                           action => 'do_multiply'
                       },
                   ],
               }
           );

       "Marpa::R2::NAIF::Grammar::new" returns a new Marpa grammar object or throws an exception.
       The arguments to "Marpa::R2::NAIF::Grammar::new" are references to hashes of named
       arguments.  In each key/value pair of this hash, the hash key is the argument name and the
       hash value is the value of the named argument.  The available named arguments are
       described below.

Mutators

   precompute()
           $grammar->precompute();

       The "precompute" method compiles data structures that the recognizer will need.  It
       returns the grammar object or throws an exception.

   set()
           $grammar->set( { trace_file_handle => $trace_fh } );

       The arguments to the "set" method are references to hashes of named arguments.  The
       available named arguments are described below.  "set" either returns true or throws an
       exception.

Accessors

   check_terminal()
       Returns a Perl true when its argument is the name of a terminal symbol.  Otherwise,
       returns a Perl false.  Not often needed, but a lexer may find this the most convenient way
       to determine if a symbol is a terminal.

   rule()
           my ( $lhs, @rhs ) = $grammar->rule($rule_id);

       Given a rule ID as its argument, returns an array containing the symbols of the rule.  The
       rule() method returns a Perl false if no rule with that rule ID exists.  If the rule ID
       exists, the rule's LHS symbol is the first symbol in the array, and rest of the array
       contains the rule's RHS symbols in order.  Situations where Rule ID's are encountered
       include callbacks and use of the progress method.

   rule_ids()
           my @rule_ids = $grammar->rule_ids();

       Returns an array containing the valid rule IDs.  Situations where Rule ID's are
       encountered include callbacks and use of the progress method.

Trace accessors

   show_problems()
           print $grammar->show_problems()
               or die "print failed: $ERRNO";

       Usually the application does not call this method directly.  Returns a string describing
       any serious but non-fatal problems a grammar had in the precomputation phase.  A serious
       problem is one that will prevent parsing.  Warnings are not serious problems in this
       sense.  If there were no serious problems, returns a string saying so.  This method is not
       useful before precomputation.

       In Marpa, most serious grammar problems are not immediately thrown as exceptions.  This is
       because there can be a number of serious problems in a grammar, particularly one that is
       large or in an early draft.  If each serious problem caused an immediate exception, the
       user would have to fix them one at a time -- very tedious.

       The recognizer throws an exception when the user attempts to create a parse from a grammar
       with serious problems.  When that happens, the string returned by "show_problems" is part
       of the error message.

   show_rules()
           print $grammar->show_rules()
               or die "print failed: $ERRNO";

       Returns a string listing the rules.  Each rule is shown with comments which indicate rule
       properties.  "show_rules" is useful in debugging grammars.

       Marpa does extensive rewriting of its grammars, and both the original rules and the
       rewritten rules appear in the "show_rules" list.  When a rule is rewritten, the original
       rule is often not used.  In that case, ""!used"" will be one of the comments for the
       original rule.  The ""!used"" comment also marks rules not used for reasons other than
       rewrites.  For example, inaccessible and unproductive rules are also marked ""!used"".

       The ""discard_sep"" comment indicates that the rule discards separators This is only
       relevant in sequence rules.  Other comments indicate whether rules were nullable,
       unproductive, inaccessible, or empty.

   show_symbols()
           print $grammar->show_symbols()
               or die "print failed: $ERRNO";

       Returns a string listing the symbols, along with comments indicating whether they were
       terminal, nulling, nullable, unproductive or inaccessible.  Useful for debugging grammars.

Named arguments

   action_object
       The "action_object" named argument specifies a Perl class name to be used in resolving
       action names to Perl closures.  A "new" constructor must be defined in the "action_object"
       package.  It will be used to create the per-parse-tree variables.  The per-parse-tree
       variable is passed to rule evaluation closures, as their first argument.  Details are in
       the document on semantics.

   actions
                   actions => 'My_Actions',

       The "actions" named argument specifies the Perl package that Marpa will use when resolving
       action names to Perl closures.  If both an "actions" named argument and an "action_object"
       named argument are specified, the package from the "actions" named argument is the only
       one used to resolve action names.  The "actions" package is treated only as a package, and
       not as a class.  Any "new" constructor in the "actions" package is ignored.  Details are
       given in the document on semantics.

   default_action
                   default_action => 'first_arg',

       The "default_action" named argument specifies the value action name for rules without an
       "action" property.  Details are given in the document on semantics.

   default_empty_action
       The "default_empty_action" named argument specifies the action for empty (zero length)
       rules which have no action specified explicitly.  Details are given in the document on
       semantics.

   inaccessible_ok
       The value must be a reference to an array of symbol names.  By default, Marpa warns if a
       symbol is inaccessible, but the warning is suppressed for any symbol named in the array.
       Setting the "inaccessible_ok" named argument after grammar precomputation is useless, and
       itself results in a warning.

       Inaccessible symbols are symbols which cannot be derived from the start symbol, and which
       therefore can never be part of a successful parse.  Inaccessible symbols often indicate
       errors in grammar design.  But a user may have plans for these symbols, may wish to keep
       them as notes, or may simply wish to deal with them later.

   infinite_action
       Takes as its value a string specifying what Marpa should do if it discovers that its
       grammar is infinitely ambiguous.  The value must be one of ""fatal"", ""warn"" or
       ""quiet"".  A grammar is infinitely ambiguous if there is some input for which it produces
       an endless number of parses.

       If the value is ""fatal"", Marpa throws an exception when it encounters an infinitely
       ambiguous grammar.  This is the default and will usually be what the user wants.  In most
       cases, an infinitely ambiguous grammar is simply a mistake.

       ""quiet"" indicates that the user wants to allow infinitely ambiguous grammars.  ""warn""
       indicates that the user wants to allow infinitely ambiguous grammars, but wants a warning
       message to be printed to the trace file handle.

   rules
       The value of the "rules" named argument is a reference to an array of rule descriptors.
       The "rules" named argument may be specified multiple times, adding new rules to the
       grammar each time.  New rules may be added until the grammar is precomputed.  The format
       of rule descriptors is explained below.

   source
       The value of the "source" named argument is a reference to string that contains a
       description of the grammar in BNF format.  The format of this string is described in the
       document on the BNF format.  The "source" named argument may only be specified once, and
       it cannot be used together with the "rules" named argument.

   start
           start => 'Expression',

       The value of the "start" named argument must be a symbol name.  It will be used as the
       start symbol for the grammar.  The "start" named argument is required.

   symbols
       The value of the "symbols" named arguments must be a reference to a hash.  In each
       key/value pair of this hash, the hash key is the symbol property name and the hash value
       is the symbol descriptor.  Symbol descriptors are described below.

       Note that the value of "symbols" named argument is a hash, but the value of the "rules"
       named argument is an array.  This is because symbol names make convenient hash keys.  For
       rules, there is no equally natural choice for a hash key.

   terminals
       The value of the "terminals" named argument must be a reference to an array of symbol
       names.  All the symbols in the array will be allowed as terminals.  See the discussion of
       terminals above.

   trace_file_handle
       The value is a file handle.  Trace output and warning messages go to the trace file
       handle.  By default the trace file handle is "STDERR".

   unproductive_ok
       The value must be a reference to an array of symbol names.  By default, Marpa warns if a
       symbol is unproductive, but the warning is suppressed for any symbol named in the array.
       Setting the "unproductive_ok" named argument after grammar precomputation is useless, and
       itself results in a warning.

       Unproductive symbols are symbols which can never derive a sentence.  (A sentence is a
       string of zero or more terminals.)  That means that unproductive symbols can never be part
       of a successful parse.  Unproductive symbols often indicate errors in grammar design.  But
       a user may have plans for these symbols, may wish to keep them as notes, or may simply
       wish to deal with them later.

   warnings
       The value is a boolean.  Warnings are written to the trace file handle.  By default,
       warnings are on.  Usually, an application will want to leave them on.  If warnings are
       turned off, turning them back on after grammar precomputation is useless, and itself
       results in a warning.

Rule descriptors

           rules => [
               { lhs => 'Expression', rhs => [qw/Term/] },
               { lhs => 'Term',       rhs => [qw/Factor/] },
               { lhs => 'Factor',     rhs => [qw/Number/] },
               { lhs => 'Term', rhs => [qw/Term Add Term/], action => 'do_add' },
               {   lhs    => 'Factor',
                   rhs    => [qw/Factor Multiply Factor/],
                   action => 'do_multiply'
               },
           ],

   Rule descriptors as hashes
       The long form descriptor of a rule is a reference to a hash of rule properties.  In each
       key/value pair of this hash, the hash key is the rule property name and the hash value is
       the value of that property.

   action
       The value of the "action" rule property is a string which specifies the semantics for the
       rule.  For details, see the document on semantics.

       The semantics of nulling symbols are dealt with on a per-symbol basis, rather than a per-
       rule basis.  For this reason the "action" rule property is useless for empty rules.  An
       exception is thrown if an "action" property is defined for an empty rule.

   keep
       Separators in sequence rules are usually not semantically significant.  By default, Marpa
       throws away separators during parse tree traversal and before node evaluation time, so
       that the semantic actions do not see the separators.

       If the value of the "keep" rule property is a Perl true, Marpa keeps separators.  This
       allows the semantic actions to examine them.  The downside is that the work of
       distinguishing sequence separators from sequence items is pushed into the semantic
       actions.  For details about the semantics, see the document on semantics.

   lhs
       The value of the "lhs" rule property must be a string containing the name of the rule's
       left hand side symbol.  Every Marpa rule must have a left hand side symbol.

   min
       "min" must be 0, 1, or undefined.  If "min" is 0 or 1, the rule is a sequence rule.  If
       "min" is undefined, the rule is an ordinary BNF rule.

       Only one symbol, called the sequence item, is allowed on the right hand side of a sequence
       rule.  The sequence item may not be a nullable symbol.  The input will be required to
       match the sequence item at least "min" times and will be allowed to match the sequence
       item an unlimited number of times.

   null_ranking
       "null_ranking" is ignored unless the recognizer's "ranking_method" named argument is set
       to something other than its default.  The "null_ranking" named argument allows the
       application to control the order in which rules with nullable symbols are returned by the
       "value" method.  Such rules can match the same input in several ways depending on which
       symbols are nulled.  These different ways of nulling symbols in a rule are called its null
       variants.

       If "null_ranking" is undefined, the order of the null variants will be arbitrary.  This is
       the default, and is acceptable to most applications.  For details on using the
       "null_ranking" named argument, see the document on parse order.

   proper
       By default, sequence rules with separators allow trailing separators, Perl-style.  If the
       "proper" rule property is a Perl true, ""proper"" separation is enforced.  In proper
       separation, separation must actually separate sequence items, and trailing separators are
       not allowed.

   rank
       "rank" is ignored unless the recognizer's "ranking_method" named argument is set to
       something other than its default.  The range allowed for "rank" is implementation-defined,
       but numbers in the range between -134,217,727 and 134,217,727 will always be allowed.
       "rank" is 0 by default.  For details on using the "rank" named argument, see the document
       on parse order.

   rhs
       The value of the "rhs" property is a reference to an array of strings containing the names
       of the rule's right hand symbols, in order.  This array may be zero length, in which case
       this is an empty rule -- a rule with no symbols on the right hand side.  A rule is also
       empty if there is no "rhs" specifier in its descriptor.

   separator
       Any sequence rule may have a "separator" defined.  The value must be a symbol name.  By
       default, Marpa allows trailing separators.  This is the usual style in Perl.  The
       separator must not be a nullable symbol.

   Rule descriptors as arrays
           rules => [
               [ 'E', [qw/E Add E/],      'do_add' ],
               [ 'E', [qw/E Multiply E/], 'do_multiply' ],
               [ 'E', [qw/Number/], ],
           ],

       Rule descriptors may be given in "short form" -- as a reference to an array.  The elements
       of the array, in order, are the "lhs" property, the "rhs" property, and the "action"
       property.  The last two are optional.  Omission of an optional property in a short form
       descriptor has the same effect that omitting the same optional property would have in the
       long form.

   Duplicate rules
       Marpa throws an exception if a duplicate rule is added.  Two BNF rules are considered
       duplicates if

       •   Both rules have the same left hand symbol.

       •   Both rules have the same right hand symbols in the same order.

       Sequence rules are even more restricted.  The LHS of a sequence rule may not be the LHS of
       another sequence rule.  The LHS of a sequence rule also may not be the LHS of any BNF
       rule.

       This restriction on the LHS of sequence rules is intended to make the definition of
       duplicate rules intuitive and their detection easy.  It does not limit the expressiveness
       of Marpa grammars, because it is very easy to work around.  One workaround to create an
       intermediate rule of length one, whose RHS is the sequence LHS symbol.  The LHS of the
       intermediate rule can then be used, without restriction, as the LHS of other rules.

Symbol descriptors

           symbols => {
               MinusMinus => { terminal => 1 },
               Minus      => { terminal => 1 },
               Number     => { terminal => 1 },
           },

       A symbol descriptor is a hash.  In the key/value pairs of this hash, the hash key is the
       symbol property name and the hash value is the value of that property.  The available
       symbol properties are as follows:

   terminal
       A boolean.  If true, it allows the symbol to be used as a terminal.  If false, it
       disallows use of the symbol as a terminal.  For details, see the section on terminals.

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