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