Name¶
Marpa::R2::Scanless::DSL - The DSL for the Scanless interface
Synopsis¶
use Marpa::R2;
my $grammar = Marpa::R2::Scanless::G->new(
{ bless_package => 'My_Nodes',
source => \(<<'END_OF_SOURCE'),
:default ::= action => [values] bless => ::lhs
lexeme default = action => [ start, length, value ]
bless => ::name latm => 1
:start ::= Script
Script ::= Expression+ separator => comma
comma ~ [,]
Expression ::=
Number bless => primary
| '(' Expression ')' bless => paren assoc => group
|| Expression '**' Expression bless => exponentiate assoc => right
|| Expression '*' Expression bless => multiply
| Expression '/' Expression bless => divide
|| Expression '+' Expression bless => add
| Expression '-' Expression bless => subtract
Number ~ [\d]+
:discard ~ whitespace
whitespace ~ [\s]+
# allow comments
:discard ~ <hash comment>
<hash comment> ~ <terminated hash comment> | <unterminated
final hash comment>
<terminated hash comment> ~ '#' <hash comment body> <vertical space char>
<unterminated final hash comment> ~ '#' <hash comment body>
<hash comment body> ~ <hash comment char>*
<vertical space char> ~ [\x{A}\x{B}\x{C}\x{D}\x{2028}\x{2029}]
<hash comment char> ~ [^\x{A}\x{B}\x{C}\x{D}\x{2028}\x{2029}]
END_OF_SOURCE
}
);
About this document¶
This is the reference document for the domain-specific language (DSL) of Marpa's
Scanless interface (SLIF). The SLIF's DSL is an extension of BNF. The SLIF DSL
is used to specify other DSL's, and is therefore a "meta-DSL".
The structure of SLIF source strings¶
The SLIF source string consists of a series of rules, pseudo-rules and
statements. These are made up of tokens, as described below. Whitespace
separates tokens, but is otherwise ignored.
A hash (""#"") character starts a comment, which continues
to the end of the line. Comments are equivalent to whitespace.
L0, G1 and lexemes¶
In reading this document, it is important to keep in mind the distinction, on
one hand, between L0 and G1 rules and, on the other hand, between rules and
lexemes. G1 rules have a semantics, which can be specified as described in
this document. L0 rules simply recognize symbols in the input. L0 rules do not
have a semantics.
Top-level L0 rules correspond to a string in the input. The top-level L0 rules
are seen by G1 as lexemes, and the string to which a top-level L0 rule
corresponds becomes the default value of the lexeme. The L0 grammar can be
thought of as similar in behavior to a set of regular expressions with the
lexemes being seen as similar to named captures.
Lexemes are the symbols which form the interface between G1 and L0. Lexemes,
like G1 rules, have a semantics. The semantics of lexemes is specified
separately from the semantics of G1 rules, as described below.
Symbol names¶
Symbol names can be either "bare" or enclosed in angle brackets. Bare
symbol names must consist entirely of Perl word characters (alphanumerics,
plus the underscore). Symbol names are case-sensitive.
The angle brackets, if used, serve to "quote" the symbol name, and
will not be part of the explicit symbol name.
If angle brackets are used, symbol names may also contain whitespace, as in
<op comma>
A whitespace sequence inside angle brackets can include any whitespace character
that is legal in Perl, including newlines. This allows very long symbol names
to be line wrapped, if necessary.
Unlike the angle brackets, the whitespace in a bracketed symbol token
does become part of the explicit symbol name, but it does so in a
"normalized" form. Leading and trailing whitespace in the name is
discarded, and all other whitespace sequences are converted to a single ASCII
space character. This means that
< op comma >
<op comma>
< op comma>
and even
<op
comma>
will all be regarded as the same symbol name. The explicit form of that symbol
name is "<op comma>", except that, again, the angle brackets
are for clarity, and are not part of the explicit name.
Explicit, reserved and internal symbol names are often displayed between angle
brackets, regardless of whether the symbol was originally specified in
bracketed form.
When a SLIF symbol needs to be referred to by name in Perl code, it is the
symbol's explicit name that is used.
Single-quoted strings¶
Expression ::=
Number bless => primary
| '(' Expression ')' bless => paren assoc => group
|| Expression '**' Expression bless => exponentiate assoc => right
|| Expression '*' Expression bless => multiply
| Expression '/' Expression bless => divide
|| Expression '+' Expression bless => add
| Expression '-' Expression bless => subtract
Child ~ 'cHILd':i
Single quotes can be used in prioritized rules to indicate character strings.
The characters inside the single quote will be matched in the input, literally
and one-for-one. Single-quoted strings can contain any characters with the
exception of single quotes and vertical whitespace.
Single-quoted strings do not allow "escaped" characters. A backslash
(""\"") represents itself and has no effect on the
interpretation of the next character. If a rule needs to match one of the
forbidden characters (single quote or vertical whitespace), it must use a
character class.
Single-quoted strings are always interpreted at the L0 level, but they may be
used in either structural or lexical rules. When a single quoted string is
used in a structural rule, Marpa creates a virtual L0 rule on behalf of the
application. This is handy, but it does have a real disadvantage -- the name
of the virtual rule's LHS will be one assigned automatically by Marpa. When
tracing and debugging parses and grammars, these virtual LHS's can be harder
for a programmer to interpret.
A modifier can appear after the string. It must appear immediately after the
string, with no intervening whitespace. Currently only the
"":ic"" and "":i"" modifier are
availables. These have exactly the same effect -- they make the string match
case-insensitive.
Character classes¶
<vertical space char> ~ [\x{A}\x{B}\x{C}\x{D}\x{2028}\x{2029}]
word ~ [\w]:ic +
A character class in square brackets (""[]"") can be used in
a RHS alternative of a prioritized rule, a quantified rule or a discard
pseudo-rule. Marpa character classes may contain anything acceptable to Perl,
and follow the same escaping conventions as Perl's character classes.
Character classes are always interpreted at the L0 level, but they may be used
in either structural or lexical rules. When a character class is used in a
structural rule, Marpa creates a virtual L0 rule on behalf of the application.
This is handy, but it does have a real disadvantage -- the name of the virtual
rule's LHS will be one assigned automatically by Marpa. When tracing and
debugging parses and grammars, these virtual LHS's can be harder for a
programmer to interpret.
An implementation note: character classes are interpreted by Perl, but this
involves minimal overhead when the parse is of any length. Each character
class is passed to Perl to interpret exactly once and the result is memoized
in a C language structure for future use.
The modifiers allowed after single quoted strings are also allowed allowed after
character classes. Modifiers must appear immediately after the closing square
bracket, with no intervening whitespace. For more details, see the section on
single-quoted strings.
Statements¶
The SLIF DSL consists of a series of statements. The statements are of three
kinds, as indicated by their declarator:
- •
- G1 rules
The BNF operator (""::=""), coming between the LHS and
the first RHS alternative of a rule, indicates that the rule is a G1
rule.
- •
- L0 rules
The match operator (""~""), coming between the LHS and
the first RHS alternative of a rule, indicates a L0 rule.
- •
- Global statements
Global statements are signified by the assignment operator
(""=""). The location of a statement in the DSL source
will never affect the result.
Rules differ from statements in that the effect of a rule is sometimes lexical
-- that is, the effect may vary depending on the position of the rule in the
DSL source. Some rules are called pseudo-rules. Pseudo-rules do not correspond
to BNF rules, but instead use the rule format as a convenient way to express
other information.
The structure of rules¶
Every rule declaration consists of, in order:
- •
- A left hand side (LHS). This will be a symbol or a pseudo-symbol.
- •
- A declaration operator (""::="" or
""~"").
- •
- A right side declaration, which contains one or more RHS alternatives.
Details of the right side declaration vary by the type of rule. For each
type of rule, the right side declaration is described in detail
below.
RHS alternatives¶
The right side declaration of a rule will often contain one or more RHS
alternatives. A RHS alternative is a series of RHS primaries, where a RHS
primary may be a symbol name, a character class, or a single quoted string. A
list of one or more adverbs is often associated with the RHS alternatives.
Each adverb consists of a keyword, the adverb operator
(""=>""), and the adverb's value.
Within an alternative, primaries may be enclosed in parentheses. A primary
enclosed in parentheses is hidden from Marpa's semantics. A set of parentheses
may contain more than one primary, in which case the entire sequence of
primaries is hidden, as if they had been enclosed in parentheses individually.
"Hiding" primaries in this way can be convenient for primaries whose
values the semantics will ignore, perhaps because the value is constant.
For example, in the following rule
a ::= b (',' c) d action => ::first
there is
- •
- A LHS, in this case the symbol ""a"".
- •
- A declarator, ""::="", which indicates this is a G1
rule.
- •
- A RHS alternative consisting of four RHS primaries. The first RHS primary
is the symbol ""b"". The second RHS primary is a short
single-quoted string ','. The third and fourth RHS primaries are symbols:
""c"" and ""d"". The parentheses
around the second and third RHS primaries "hide" them from the
semantics. Marpa's semantics will see this as a rule with only two RHS
values.
- •
- The adverb list associated with the RHS alternative, consisting of a
single adverb. The adverb consists of its keyword
""action"", followed by the adverb operator
(""=>""), and the adverb's value
""::first"".
The rule in the above example is one of a very common type: a trivial
prioritized rule. A prioritized rule is one that contains one or more
prioritized RHS alternatives. Prioritized rules are the only rules which may
contain more than one RHS alternative, but even prioritized rules usually have
only one RHS alternative. If there is only one RHS alternative, as in this
case, the prioritization is
trivial -- there is only one priority.
Start rule¶
:start ::= Script
By default, the start symbol of the grammar is the LHS of the first G1 rule.
This default can be make explicit or overriden by using an explicit start
rule. The LHS of this rule is the ":start" pseudo-symbol. Only one
RHS alternative is allowed. This RHS alternative must contain only one symbol
name, and that symbol will be the start symbol of the G1 grammar. No adverbs
should be associated with the RHS alternative. Start rules must be G1 rules.
Empty rules¶
An empty rule is a rule with an empty RHS. The empty RHS, technically, is a RHS
alternative, one with zero RHS primaries. The "action" and
"bless" adverbs are allowed for the empty RHS alternative, but no
others. A empty rule makes its LHS symbol a nullable symbol.
Quantified rules¶
Script ::= Expression+ separator => comma
A quantified rule has only one RHS alternative, which is followed by a
quantifier. The RHS alternative must consist of a single RHS primary. This RHS
primary must be a symbol name or a character class. The quantifer is either a
star (""*""), or a plus sign (""+"")
indicating, respectively, that the sequence rule has a minimum length of 0 or
1.
Adverbs may be associated with the RHS alternative. The adverb list must follow
the quantifier. The adverbs allowed are "action", "bless",
"proper" and "separator".
Prioritized rules¶
Expression ::=
Number bless => primary
| '(' Expression ')' bless => paren assoc => group
|| Expression '**' Expression bless => exponentiate assoc => right
|| Expression '*' Expression bless => multiply
| Expression '/' Expression bless => divide
|| Expression '+' Expression bless => add
| Expression '-' Expression bless => subtract
A prioritized rule contains a series of one or more RHS alternatives, separated
by either the alternation operator (""|"") or the loosen
operators (""||""). In a typical grammar, most rules are
prioritized rules, but they are often trivially prioritized, consisting of
only one RHS alternative. For brevity, RHS alternatives are often called
alternatives.
Each alternative may be followed by a list of associated adverbs. The
"action", "assoc" and "bless" adverbs are
allowed.
The RHS alternatives in a prioritized right hand side proceed from tightest
(highest) priority to loosest. The double "or" symbol
(""||"") is the "loosen" operator -- the
alternatives after it have a looser (lower) priority than the alternatives
before it. The single "or" symbol (""|"") is the
ordinary "alternative" operator -- alternatives on each side of it
have the same priority. Associativity is specified using adverbs, as described
below.
Discard pseudo-rules¶
:discard ~ whitespace
A discard pseudo-rule is a rule whose LHS is the ":discard"
pseudo-symbol, and which has only one RHS alternative. The RHS alternative
must contain exactly one symbol name, called the
discarded symbol.
Discard pseudo-rules indicate that the discarded symbol is a top-level L0
symbol, but one which is not a lexeme. When a discarded symbol is recognized,
it is not passed as a lexeme to the G1 parser, but is (as the name suggests)
discarded. Discard pseudo-rules must be L0 rules. No adverbs are allowed.
Default pseudo-rules¶
:default ::= action => [values] bless => ::lhs
:default ::= action => [lhs, values ]
The purpose of the default pseudo-rule is to change the defaults for rule
adverbs. Technically, it has one RHS alternative, but this must always contain
zero RHS primaries. Default pseudo-rules do not affect the defaults for L0
rules or for lexemes. There may be more than one default pseudo-rule. The
scope of default pseudo-rules is lexical, applying only to rules that appear
afterwards in the DSL source.
Currently only the "action" and "bless" adverbs can be
specified in a default pseudo-rule. Each default pseudo-rule creates a
completely new set of defaults -- if an adverb is not specified, the default
is reset to its implicit value, the value which it had prior to any explicit
settings.
Lexeme pseudo-rules¶
:lexeme ~ <say keyword> priority => 1
The purpose of the ":lexeme" pseudo-rule is to allow adverbs to change
the treatment of a lexeme. This pseudo-rule always has exactly one RHS
alternative, and that RHS alternative must contain exactly one symbol. This
RHS symbol identifies the lexeme which the adverbs will affect. The only
adverbs allowed in a ":lexeme" rule are "event",
"pause", and "priority".
As a side effect, a ":lexeme" pseudo-rule declares that its RHS symbol
is expected to be a lexeme. This declaration does not "force" lexeme
status -- if the symbol does not meet the criteria for a lexeme based on its
use in L0 and G1 rules, the result will be a fatal error. Applications may
find this ability to "declare" lexemes useful for debugging, and for
documenting grammars.
Lexeme default statement¶
lexeme default = action => [ start, length, value ]
bless => ::name latm =>
lexeme default = action => [ lhs, value ]
The lexeme default statement changes the defaults for lexeme adverbs. It only
changes the defaults for lexemes, and does not affect rules. Only the defaults
for the "action", "bless", and "latm" adverbs
can be specified in a lexeme default statement. Only one lexeme default
statement is allowed in a grammar.
Named event statement¶
event subtext = completed <subtext>
event 'A[]' = nulled <A>
event '^a' = predicted A
The named event statement sets up a symbol so that a named event is triggered
when some condition occurs at a location. Named events can be defined to occur
when a symbol is predicted, when a symbol is completed, or when a symbol is
nulled.
A "completed" event occurs whenever a rule with that symbol on its LHS
is fully recognized in the parse. (The idea is that "symbol
completion" occurs when the rule, and therefore its LHS, is
"complete".) For the purpose of "completed" events, a
nulled symbol is not considered "complete", and
"completed" events will not be triggered for a zero-length instance
of a symbol.
A "nulled" event occurs whenever a zero-length symbol instance is
recognized. Null symbols may derive other null symbols, and these derivations
may be ambiguous. Ambiguous or not, all such derivations cause
"nulled" events. Again, nulled events and completed events are
mutually exclusive -- a nulled, or zero-length, symbol is not considered
"complete" for this purpose.
A "predicted" event occurs at any location where a non-zero length
symbol would be accepted by the recognizer. It can be thought of as occurring
when a symbol is "expected". The expectation may or may not come
true, depending on future input. Because there is no physical distinction
between expecting a zero-length symbol, and actually seeing one,
"predicted" events are not generated for symbols which are only
expected in zero-length form.
Completed and nulled events may not be defined for symbols that are lexemes, but
lexemes are allowed to be predicted events. A predicted event which is a
lexeme is different from a lexeme pause. The lexeme pause will not occur
unless that the lexeme is actually found in the input. A predicted event, on
the other hand, is as the name suggests, only a prediction. The predicted
symbol may or not actually be found in the input.
The name of an event may be either a bare name, or enclosed in single quotes. A
bare event name must be one or more word characters, starting with an
alphabetic character. A single quoted event name may contain any character
except a single quote or vertical space. The whitespace in single quoted event
names is normalized in similar fashion to the normalization of symbol names --
leading and trailing whitespace is removed, and all sequences of internal
whitespace are changed to a single ASCII space character. Names containing
single quotes (which, in any case, are impossible to add using current syntax)
are reserved.
Named completion events can occur during the the Scanless recognizer's
read(),
resume(),
lexeme_complete(), and
lexeme_read() methods. When they occur in the Scanless recognizer's
read(), and
resume() methods, they pause internal scanning.
Named events may be queried using the Scanless recognizer's
event()
method.
Inaccessible symbol statement¶
inaccessible is ok by default
inaccessible is fatal by default
Inaccessible symbols are symbols which cannot be reached from the start symbol.
Often, they are the result of an error in grammar writing. But inaccessible
symbols can also occur for legitimate reasons -- for example, you may have
rules and symbols in grammar intended for future use.
The default can be specified or changed with a statement of the form:
inaccessible is TREATMENT by default
where "TREATMENT" is one of "warn", "ok", or
"fatal".
"fatal" indicates that an inaccessible symbol should be a fatal error.
"warn" indicates that Marpa should print a warning message, but
proceed with the parse. "warn" is the default. "ok"
indicates that the parse should proceed without warning messages.
Ambiguity¶
Marpa parses ambiguous grammars and the design of the SLIF exploits this. A
flexible, but potentially ambiguous, syntax is used. Actual ambiguities are
obvious to the human eye, and users will create them, so that the techniques
of this section will rarely be needed.
If and when an actual ambiguity does occur, an error message reports the
ambiguity and its exact location. It will always be possible to disambiguate a
SLIF DSL, and there will always be more than one way to do this.
Separating statements with semicolons¶
:default ::= action => ::array
quartet ::= a a a a;
inaccessible is warn by default
a ~ 'a'
A statement may be terminated with a semicolon ("";"").
Grouping statements in curly braces¶
{
:default ::= action => ::array
quartet ::= a a a a
}
inaccessible is warn by default
a ~ 'a'
Statements can be grouped, using curly braces. These do
not create scopes
-- the curly braces serve merely to group and to separate groups of
statements.
Other ways to disambiguate¶
There are many other ways to disambiguate SLIF statements. If the ambiguity is
between keywords and symbol names, enclosing a symbol name in angle brackets
will force it to be treated only as a symbol name. And while it is never
necessary, statements can be re-ordered.
Adverbs¶
Adverbs consist of a keyword, the adverb operator
(""=>""), and the adverb's value. The keyword must be
one of those described in this section. The adverb's value must be as
described for each keyword.
action¶
The "action" adverb is allowed for
- •
- An RHS alternative, in which the action is for the alternative.
- •
- The default pseudo-rule, in which case the action is for all rules which
do not have their own action explicitly specified.
- •
- The lexeme default statement, in which case the action is for all
lexemes.
The "action" adverb is not allowed for L0 rules. The possible values
of actions are described, along with other details of the semantics, in a
separate document.
assoc¶
The "assoc" adverb is only valid in a prioritized rule. Its value must
be one of "left", "right" or "group". Its effect
will be as described below.
bless¶
The "bless" adverb causes the result of the semantics to be blessed
into the class indicated by the value of the adverb. Details of its use may be
found in the semantics document.
event¶
:lexeme ~ <a> pause => before event => 'before a'
:lexeme ~ <b> pause => after event => 'after b'
:lexeme ~ <c> pause => before event => 'before c'
:lexeme ~ <d> pause => after event => 'after d'
The "event" adverb applies only to lexemes and is only allowed in a
":lexeme" pseudo-rule. It turns a lexeme's pause into a named event,
using the name specified as its value. Applications are encouraged to turn all
lexeme pause's into named events, using the "event" adverb. The
allowed event names are as described for the named event statement.
It is a fatal error to specify the "event" adverb if the
"pause" adverb is not also specified.
forgiving¶
:lexeme ~ <name> forgiving => 1
The forgiving adverb is a synonym for the "latm" adverb.
latm¶
:lexeme ~ value latm => 1
The "latm" adverb applies only to lexemes and is only allowed in a
":lexeme" pseudo-rule and a "lexeme default" statement.
Its value is a boolean. If the boolean is set it indicates that a token is
LATM. A value of 1 is recommended, which indicates that a token is LATM. The
default value is 0, for reasons of backward compatibility.
LATM means "longest acceptable tokens match". In this, the lexer find
those tokens that are the longest that would be accepted by the G1 grammar.
There may be more than one such "longest" acceptable token, in which
case, the lexing will be ambiguous, and the parse will use all of the matching
tokens.
The alternative to LATM, and the default, is the "longest tokens
match" (LTM) discipline. LTM is similar to LATM, except that it takes no
account of whether a token would be acceptable to the G1 grammar. This makes
it possible that LTM will find one or more lexemes that are a longest match,
and none of them will be acceptable to G1. When that happens, the parse fails
with an error message. This failure occurs even if shorter lexemes would have
been found using LATM, lexemes which would have been acceptable to the G1
grammar. This means that matching succeeds more often under LATM than under
LTM.
Intuitively, LATM is a longest tokens match that considers context, while LTM is
a longest tokens match that ignores context. LATM is usually preferable.
Usually if LATM is chosen, a parse will want to use the a "lexeme
default" statement and use LATM globally. It is possible to use LATM
adverb on a lexeme by lexeme basis. When that is done, the lexemes marked LATM
will match only if acceptable to the G1 grammar, and the lexemes not marked
LATM will match regardless of their acceptability to the G1 grammar.
Whichever token discipline is chosen, all tokens matched will be of the same
length. Shorter tokens will not be considered.
LTM is the default for historical reasons. LTM was the SLIF's original token
matching discipline because it more closely models traditional lexing. Also
for historical reasons, LATM lexemes are sometimes called
"forgiving" -- in the original implementation, an LTM search was
always done for all lexemes, and LATM was implemented by "forgiving"
rejection by the G1 grammar, and backing up over the input to find acceptable
lexemes. Marpa now does LATM far more efficiently -- the G1 grammar indicates
to the lexer, in advance, which lexemes are acceptable, and the lexer searches
only for those.
name¶
start ::= number1 number2 name => top
number1 ::= <forty two> name => 'number 1'
number2 ::= <forty three> name => 'number 2'
The "name" adverb applies only to rules and rule alternatives. When
specified, it defines a name for that rule alternative.
null-ranking¶
S ::= A A A A null-ranking => high
The "null-ranking" adverb applies only to G1 rules (L0 rules do not
have a semantics) and is ignored unless the SLIF recognizer's
"ranking_method" named argument is set to something other than its
default. Some rule alternatives 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. The "null-ranking" named
argument allows the application to control the order in which null variants
are returned by the "value()" method.
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" adverb, see the document on
parse order.
pause¶
:lexeme ~ <a> pause => before event => 'before a'
:lexeme ~ <b> pause => after event => 'after b'
:lexeme ~ <c> pause => before event => 'before c'
:lexeme ~ <d> pause => after event => 'after d'
The "pause" adverb applies only to lexemes and is only allowed in a
":lexeme" pseudo-rule. Pauses take effect during the Scanless
recognizer's
read() and
resume() methods. They cause internal
scanning to be suspended, or "paused", before or after the specified
lexeme. Internal scanning can be resumed with the Scanless recognizer's
resume() method.
Applications are encouraged to name every lexeme pause using the event adverb.
If this is done, lexeme pauses can be queried using the SLIF recognizer's
events() method. Unnamed lexeme pauses must be queried using the SLIF
recognizer's
pause_lexeme() method.
If the value of pause is "before", Marpa will "pause"
internal scanning before that lexeme. No lexemes will be read at that
position.
If the value of pause is "after", all applicable lexemes at that
position will be read by G1, and internal scanning will pause immediately
afterwards.
A lexeme pause event does not occur, and has no effect, if
- •
- It is deactivated. Deactivation and reactivation of events is done with
the SLIF recognizer's activate() method
- •
- The G1 grammar would reject that lexeme at that location.
- •
- It has a lexeme priority lower than the highest lexeme priority.
- •
- At the same priority, it has a pause value of "after", when
another lexeme pause occurs which has a pause value of "before".
In other words, pausing before a lexeme prevents Marpa from pausing after
another lexeme at the same location.
Even with the above restrictions, there can be more than one lexeme pause event
at a location. The
pause_lexeme() method will return only one of them,
chosen arbitrarily, whereas the
events() method will return all of the
named events. This is one of the reasons that applications are strongly
encouraged to specify a name for every lexeme pause event using the
"event" adverb.
priority¶
The "priority" adverb is only allowed in a ":lexeme"
pseudo-rule. It sets the lexeme priority for the lexeme. The priority must be
an integer, but it may be negative. An increase in numerical value means a
higher priority. For example, a priority of 1 is greater than a priority of 0.
A priority of 0, in turn, is greater than a priority of -1. The default
priority is zero.
Where more than one lexeme can be accepted at a location, the lexeme priority
limits the lexemes that will be considered. Only lexemes with the highest
priority are considered. If several lexemes have the same priority, all of
them will be accepted.
The only effect of the lexeme priority is on the choice of lexemes when
- •
- all of them would be accepted;
- •
- all started at the same string location;
- •
- all end at the same string location; and therefore
- •
- all have the same length.
Lexeme priorities only have an effect when lexemes are accepted. The intent of
this scheme is to avoid situations where a lexeme with a high priority is
rejected, and causes a parse to fail, even though another lower priority
lexeme is acceptable and would allow the parse to continue.
For example, suppose that ""say"" can be both a keyword
("<say keyword>"), and a variable name
("<variable>"). Suppose further that the grammar specifies
that "<say keyword>" has a priority of 1, and
"<variable>" is left at the default priority of 0. When L0
finds a occurrence of ""say"", where both the
"say" keyword and a variable name would be accepted by G1, then only
the "say" keyword is read by G1, because of the priorities.
But, suppose instead that the parse is at a location where G1 is not accepting
the "<say keyword>". Since only lexeme priorites of acceptable
lexemes are considered, "<variable>" lexeme has the highest
priority, and the literal string ""say"" will be read as a
"<variable>" token.
proper¶
The "proper" keyword is only valid for a quantified right side, and
its value must be a boolean, in the form of a binary digit (0 or 1). It is
only relevant is a separator is defined and is 1 if proper separation is
required, and 0 if Perl separation is allowed. "Perl separation"
allows a final separator. "Proper separation" is so called, because
it requires that separators be "proper" in the sense that they must
actually separate sequence items.
rank¶
unspecial ::= ('I' 'am' 'special') words ('--' 'NOT!' ';') rank => 1
special ::= words (';') rank => -1
"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.
separator¶
The "separator" keyword is only valid for a quantified right side, and
its value must be a single symbol -- either a single symbol name, or a
character class. If specified, the separator must separate items of the
sequence. A separator may not be nullable.
Precedence¶
Marpa's precedence is a generalization beyond the traditional ideas of
precedence. Traditional precedence parsing required the classification of
operators as postfix, infix, etc. Marpa's precedence parsing is NOT based on
the special treatment of operators.
For the purpose of precedence, an operand is an occurrence in a RHS alternative
of the LHS symbol. An operator is considered to be anything that is not an
operand. The arity of an alternative is the number of operands that it
contains. All arities are allowed, from zero to the arbitrary number imposed
by system limits such as memory and file size.
For example, in the synopsis, the LHS symbol is "Expression". The
alternative
(<op lparen>) Expression (<op rparen>)
contains one occurrence of "Expression" and therefore has an arity of
one. The "<op lparen>" and "<op rparen>" are
considered operators.
In the RHS alternative
Expression (<op pow>) Expression
"Expression" occurs twice, and therefore the arity is 2. "<op
pow>" is considered to be an operator.
Because for this purpose an operator is defined as anything that is not an
operand, Marpa treats some symbols as operators that would not be considered
operators in the traditional approach. For example, in the RHS alternative
Number
there are no occurrences of "Expression", so that the alternative has
an arity of zero -- it is nullary. The symbol "Number" is considered
to be an operator.
An alternative with arity 0 is nullary. Precedence and associativity are
meaningless in this case and will be ignored.
An alternative with arity 1 is unary. Precedence will have effect, but left and
right associativity will not.
An alternative with arity 2 is binary. Precedence will have effect, and left and
right associativity will behave in the traditional way. The traditional
behavior for binary alternatives is exactly as described next for the
N-ary case.
An alternative with an arity of
N, where
N is 2 or greater, is
N-ary. Precedence will have effect. For left associativity, only the
leftmost operand of an
N-ary alternative associates -- operands after
the first will have the next-tightest priority level. For right associativity,
only the rightmost operand of an
N-ary alternative associates -- all
operands except the last will have the next-tightest priority level.
Marpa also allows "group" associativity. In "group"
associativity, all operands associate at the loosest (lowest) priority. That
is, in an alternative with group associativity, each operand may be a full
expression of the kind defined by the prioritized rule. "Group"
associativity is used, for example, in implementing the traditional function
of parentheses in Marpa. Group associativity is meaningless for nullary
alternatives, and is ignored.
Precedence and ambiguous grammars¶
Marpa's generalization of precedence works for all grammars that can be defined
by prioritized rules. It is efficient (linear) for all grammars that could be
parsed by the traditional precedence parsing methods. Marpa also allows you to
define alternatives not allowed by traditional methods. Many of these are
useful, and most of the useful ones can be parsed efficiently.
Because of the many forms of recursion allowed, it is possible to define highly
ambiguous grammars using the precedence mechanism. This can occur even by
accident.
The user should especially be careful with right hand side alternatives in which
all the symbols are operands. These can be useful. For example, an implicit
operation can be defined using a binary alternative with no non-operands, and
this could implement, for example, the standard notation for concatenation or
multiplication. But to do this efficiently requires either avoiding ambiguity,
or controlling its use carefully.
Marpa does catch the case where an alternative consists only of a single operand
-- a "unit rule". This causes a fatal error. Unit rules are easy to
define by accident in the SLIF. The author knows of no practical use for them,
and their presence in a grammar is usually unintentional. Note that, in the
event an application does find a use for a grammar with unit rules, the NAIF
and the Thin interface can parse it.
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/.