NAME
Marpa::Grammar - Marpa Grammar Objects
SYNOPSIS
my $grammar = Marpa::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
Marpa's grammar objects are created with the new method. Rules and other named arguments may be specified when the grammar is created, or later using the set method.
The precompute method adds data structures that the recognizer will need to the grammar object. After precomputation a grammar is "frozen". The set method and some tracing accessors may be called after precomputation, but no new rules may added and most other named arguments are no longer valid.
Symbol Names
Symbol names that end in right square brackets are reserved for Marpa's internal use. Any other valid Perl string is an acceptable symbol name.
Terminals
If a Marpa grammar has no empty rules, the default is that every valid symbol is also valid as a terminal. A terminal is a symbol that is valid as input. More formally, a symbol is a terminal if it is allowed as a token symbol. Unlike most parser generators, Marpa allows terminals to appear on the left hand side of rules.
A grammar has the option of explicitly marking its terminals. Terminals can be explicitly marked using the terminals named argument, or the terminal property of the symbols named argument.
If a Marpa grammar has no empty rules and no terminals are explicitly marked, all symbols are valid as terminals. If a Marpa grammar has no empty rules, but some terminals are explicitly marked, only explicitly marked terminals are valid as terminals.
If a Marpa grammar has empty rules, only explicitly marked terminals are valid as terminals. When a Marpa grammar has empty rules but there are no explicitly marked terminals, an exception is thrown at precomputation time.
Marpa requires that all token names be valid terminals. Explicitly marking terminals allows the recognizer to check the input more strictly. Additionally, precomputation can be more efficient for grammars which explicitly mark their terminals.
Sequence Rules
It is very common in a grammar for one symbol to derive a sequence of other symbols. Marpa has a shorthand for this: sequence rules.
A rule is a sequence rule if the min rule property is defined. min can be 0 or 1, and indicates the minimum length of the sequence. As of this writing, the maximum length is always infinite.
{ lhs => 'sequence', rhs => ['sequence_item'], min => 0 }A min of zero indicates a sequence of 0 or more symbols. This is the equivalent of using the star quantifier ("sequence_item*") in the standard regular expression notation.
{ lhs => 'sequence', rhs => ['sequence_item'], min => 1 }A min of one indicates a sequence of 1 or more symbols. This is the equivalent of using the plus quantifier ("sequence_item+") in the standard regular expression notation.
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(sequence_item)], min => 0 },
{ lhs => 'sequence_item', rhs => [qw(part1 part2)], },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" separaration, you can set the proper rule property.
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.
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 for efficiency reasons, it is a good thing to avoid.
CONSTRUCTOR
new
my $grammar = Marpa::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::Grammar::new returns a new Marpa grammar object or throws an exception. The arguments to Marpa::Grammar::new are references to hashes of named arguments. In the key/value pairs 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
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 usually needed, but in unusual sitations a lexer may find this the easiest way to determine if a symbol is a terminal.
TRACE ACCESSORS
show_AHFA
print $grammar->show_AHFA()
or Carp::croak "print failed: $OS_ERROR";Returns a multi-line string listing the states of the AHFA with the LR(0) items, LR(0) NFA states, and transitions for each. Not useful before the grammar is precomputed. Useful in debugging, but requires knowledge of Marpa internals.
show_problems
print $grammar->show_problems()
or Carp::croak "print failed: $OS_ERROR";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.
Usually the application does not call this method directly. 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 Carp::croak "print failed: $OS_ERROR";Returns a string listing the rules. Each rule is shown with comments which indicate either rule properties or internal settings. show_rules is often useful in debugging grammars. Much of its information requires no knowledge of the Marpa internals to interpret.
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, empty, or had a non-zero priority.
The vlhs, vrhs and real comments show rule settings relevant in tracking "virtual" internal symbols. Details on virtual symbols can be found in the implementation document.
show_symbols
print $grammar->show_symbols()
or Carp::croak "print failed: $OS_ERROR";Returns a string listing the symbols, along with comments indicating whether they were terminal, nulling, nullable, unproductive or inaccessible. Also shown is a list of rules with that symbol on the left hand side, and a list of rules which have that symbol anywhere on the right hand side. Often useful and much of the information requires no knowledge of the Marpa internals to interpret.
NAMED ARGUMENTS
action_object
The action_object named argument expresses semantics. Its standard use is as a class name to be used in resolving action names to Perl closures. If a new constructor is defined in the action_object package, that constructor is used to create the per-parse variables. Details are in the document on semantics.
actions
actions => 'My_Actions',The actions named argument expresses semantics. Its standard use is to specify 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 expresses semantics. Its standard use is to specify the semantic action for rules without an action property. Details are given in the document on semantics.
default_null_value
The default_null_value named argument expresses semantics. Its standard use is to specify the null value for symbols without a null_value property. 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 ambigious. 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.
The setting of the infinite_action property and the choice of evaluators are independent of each other. The Single Parse Evaluator will detect attempts to use it with an infinitely ambiguous grammar and throw an exception at evaluator setup time.
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.
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.
strip
The value is a Boolean. If true, after precomputation Marpa "strips" the grammar of all data structures not needed for further processing. This saves space and time. Stripping is the default behavior.
If strip is set to false, the grammar object is not stripped. The data that would have been stripped remains available for tracing and debugging.
symbols
The value of the symbols named arguments must be a reference to a hash. In the key/value pairs 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. Specifying symbols in a terminals named argument is one way of explicitly marking them as terminals. Explicit marking of terminals is not necessary unless a grammar has empty rules. 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.
trace_rules
Traces rules as they are added to the grammar. Useful, but you may prefer the show_rules method. Does not require knowledge of Marpa internals.
A trace_rules setting becomes effective within the named argument hash which sets it. A trace message warns the user if he turns on rule tracing when rules have already been added.
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 the key/value pairs 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 expresses semantics. Its standard use is as the name of the rule's semantic action. The action name resolves to a Perl closure. For details, see the document on semantics.
The semantics of nulling symbols are dealt with on a per-symbol basis, rather than per rule. 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.
The lhs plays a role in the standard semantics. If no action rule property is defined, Marpa looks in either the grammar's actions package or the grammar's action_object for a Perl closure that has the name of the lhs symbol. For details, see the document on semantics.
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, non-sequence 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.
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.
ranking_action
The ranking_action rule property expresses semantics. Its standard use is to control the order of the parses. The Single Parse Evaluator ignores it. For its semantics in the Multi-parse Evaluator, see that evaluator's documentation
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, the action property and the priority property. The last three 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. For non-sequence rules, a rule is considered a duplicate if it has the same left hand side symbol, and the same symbols in the same order on the right hand side. For sequences, a rule is considered a duplicate if it has the same left hand symbol, the same right hand side symbol, and the same separator.
SYMBOL DESCRIPTORS
symbols => {
L => { null_value => 'null L' },
R => { null_value => 'null R' },
A => { null_value => 'null A' },
B => { null_value => 'null B' },
X => { null_value => 'null X', terminal => 1 },
Y => { null_value => 'null Y', 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:
null_value
The null_value symbol property expresses semantics. Its standard use is as the null value of its symbol. Details are given in the document on semantics.
terminal
A boolean. If true, it marks the symbol as a terminal. If false, it unmarks the symbol as a terminal. For details, see the section on terminals.
LICENSE AND COPYRIGHT
Copyright 2007-2010 Jeffrey Kegler, all rights reserved. Marpa is free software under the Perl license. For details see the LICENSE file in the Marpa distribution.