Symbol Names

Terminal Symbols

Marpa allows direct marking of terminals using the "terminals" named argument, and the "terminal" property. If any terminal is directly marked, only directly marked symbols will be terminals.

Marpa's behavior can be changed by unsetting the "lhs_terminals" named argument. When the "lhs_terminals" named argument is unset, only symbols which do not appear on the LHS of a rule can be terminals. If no symbols are directly marked, Marpa will implicitly mark all the non-LHS symbols as terminals.

Marpa is stricter for grammars with empty rules -- it does not allow them to take the default. There is an efficiency hit whenever the LHS of an empty rule is a terminal as well, so Marpa does not allow this to happen by default -- the user has to be explicitly indicate that that is what she wants. If a grammar has any empty rules, it must either directly mark its terminals, or must unset the "lhs_terminals" named argument.

One advantage of not taking the default is efficiency. Precomputation is faster for grammars which mark their terminals. Also, the recognizer checks that input tokens are terminals, so that being selective about which symbols are terminals and which are not can allow better input checking.

Summary

The following summarizes the logic which determines whether a symbol "S" is terminal. As a reminder, a symbol is said to be directly marked as a terminal if it is one of the symbols in the "terminals" named argument, or if the symbol has the "terminal" property set.

• If any symbol is directly marked as a terminal, then a symbol "S" is a terminal if and only if it is also directly marked as a terminal.
• If no symbol is directly marked as a terminal, and the "lhs_terminals" named argument is unset, then all non-LHS symbols are terminals.
• If the grammar contains no empty rules, no symbol is directly marked as a terminal, and the "lhs_terminals" named argument is set or left at its default, then all symbols are terminals.
• The only case not covered above is that in which a grammar contains one or more empty rules, no symbol is directly marked as a terminal, and the "lhs_terminals" named argument is set or left at its default. This is a fatal error.

Sequence Rules

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 }

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 }

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 nullable can be highly ambiguous, which makes them a good thing to avoid for efficiency reasons.

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 },
    { lhs => 'item', rhs => [qw(part1 part2)], },

new

    my $grammar = Marpa::PP::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::PP::Grammar::new" returns a new Marpa grammar object or throws an exception. The arguments to "Marpa::PP::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.

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.

check_terminal

show_AHFA

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

Not of interest to most users. Returns a multi-line string listing the states of an internal data structure called the Aycock-Horspool Finite Automaton. Not useful before the grammar is precomputed.

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 either rule properties or internal settings. "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.

The "vlhs", "vrhs" and "real" comments show rule settings relevant in tracking "virtual" internal symbols. These are used internally, to optimize evaluation.

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. 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. Useful for debugging grammars.

action_object

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_null_value

inaccessible_ok

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

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.

lhs_terminals

If "lhs_terminals" is unset and no symbols are directly marked as terminals, Marpa will mark all non-LHS symbols as terminals. If any symbol is directly marked, all terminals must be directly marked. If "lhs_terminals" is unset, but some symbols are directly marked, it is a fatal error for a terminal to appear on the LHS of a rule. For more, see the discussion of terminals above.

rules

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

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

trace_file_handle

trace_rules

unproductive_ok

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

Rule Descriptors as Hashes

action

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

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 "lhs" plays a role in the 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

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

ranking_action

rhs

separator

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

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

This definition applies to sequence rules, as well as to ordinary rules. As a consequence, sequence rules can be considered duplicates even when they have different separators and/or different minimum counts.

null_value

terminal