/ 
Marpa-R2-2.053_003
River stage two • 39 direct dependents • 56 total dependents
/ Marpa::R2::Scanless::DSL

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

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

G0, G1 and lexemes

In reading this document, it is important to keep in mind the distinction, on one hand, between G0 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. G0 rules simply recognize symbols in the input. G0 rules do not have a semantics.

Top-level G0 rules correspond to a string in the input. The top-level G0 rules are seen by G1 as lexemes, and the string to which a top-level G0 rule corresponds becomes the default value of the lexeme. The G0 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 G0. 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). The angle brackets, if used, serve to "quote" the symbol name, and will not be part of the 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 of the 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 normalized form of that symbol name is <op comma>. The actual name of every symbol is its normalized form. Symbol names are often displayed between angle brackets, regardless of whether the symbol was originally specified in bracketed form.

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

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

Character classes

<vertical space char> ~ [\x{A}\x{B}\x{C}\x{D}\x{2028}\x{2029}]

A character class in square brackets ("[]") can be used in a RHS alternative of a prioritized rule, or on the RHS of a quantified rule or a discard 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 G0 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 G0 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.

Rules and statements

The BNF operator ("::=") indicates that the rule is a G1 rule. The match operator ("~") can be used between the LHS and RHS of a rule, instead of the BNF operator. Rules which use the match operator are G0 rules. The effect of a rule will sometimes vary, depending on its lexical position in the DSL source.

Statements are signified by the assignment operator ("="). Their effect is global, never lexical. The location of a statement in the DSL source will never affect the result.

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.

For each type of rule, the right side declaration is described in detail below. Among the things a right side declaration may contain are:

  • Zero or more RHS alernatives. 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.

  • An list of zero or more adverbs. Each adverb consists of a keyword, the adverb operator ("=>"), and the adverb's value.

Note that most rules are classified as "prioritized rules", although the prioritization may be trivial. For example, a rule like the following,

a ::= b c d

whose RHS consists only of a sequence of symbols, is a prioritized rule. The prioritization is trivial -- there is only one priority, and in fact only one alternative within that priority. In typical grammars, most rules will be prioritized rules, and many of them will be trivially prioritized.

Start rule

Every source string should have a start rule. The LHS of this rule is the :start pseudo-symbol. The RHS must be a single symbol name. The start rule does not accept any adverbs. Start rules must be G1 rules.

Empty rules

An empty rule is a rule with an empty RHS. An empty right hand side is what the name suggests: no symbols or punctuation. The action and bless adverbs are allowed with empty rules, but no others. A empty rule makes its LHS symbol a nullable symbol.

Quantified rules

A rule is quantified if its RHS consists of a single symbol name, followed by a "quantifier". The quantifer is either a star ("*"), or a plus sign ("+") indicating, respectively, that the sequence rule has a minimum length of 0 or 1. Quantified rules allow the action, bless, proper and separator adverbs.

Prioritized rules

Any rule that is not a start rule, and that is not empty or quantified, is considered prioritized. The prioritization is often trivial, consisting only of a single priority level.

Each prioritized right hand side consists of one or more right hand alternatives (called "alternatives" for brevity). An alternative is a series of one or more symbols, followed by zero or more adverbs. The action, assoc and bless adverbs are allowed.

The alternatives are separated by single or double "or" symbols. This means the 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.

Within an alternative, symbols may be enclosed in parentheses. A symbol enclosed in parentheses is hidden from Marpa's semantics. A set of parentheses may contain more than one symbol, in which case the entire sequence of symbols is hidden, as if they had been enclosed in parentheses individually.

Discard rules

:discard ~ whitespace

A discard rule is a rule whose LHS is the :discard pseudo-symbol, and whose RHS is a single symbol name, called the discarded symbol. These rules indicate that the discarded symbol is a top-level G0 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 rules must be G0 rules. No adverbs are allowed.

Default pseudo-rules

:default ::= action => [values] bless => ::lhs

The default pseudo-rule changes the defaults for rule adverbs. Default pseudo-rules do not affect the defaults for G0 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 defaults for 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, it is reset to its original default, the one it had before any default pseudo-rules were encountered.

Lexeme pseudo-rules

:lexeme ~ <say keyword> priority => 1

The :lexeme pseudo-rule allows adverbs to be used to change the treatment of a lexeme. The only adverbs allowed in a :lexeme rule are priority and pause.

As a side effect, a :lexeme pseudo-rules declares that a symbol is 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 G0 and G1 rules, the result will be a fatal error. Applications may find the ability to "declare" lexemes useful for debugging, and for documentating grammars.

Lexeme default statement

lexeme default = action => [start,length,value] bless => ::name

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 and bless adverbs can be specified in a lexeme default pseudo-rule. Only one lexeme default statement is allowed in a file.

Completion event statement

event subtext = completed <subtext>

The completion event statement sets up a symbol so that a named event occurs for all of its "symbol completions". A "symbol completion" 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".)

Note that, as a special case, a zero length or null rule is never considered "complete", As a consequence, it is never a symbol completion when a symbol is zero length, or "nulled".

Named events pause internal scanning, as described in Marpa::R2::Scanless::R. They may be queried using the Scanless recognizer's event() method.

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 specifies the semantics for a G1 rule or a lexeme, as described below. The action adverb may also appear in a default pseudo-rule.

The default value of a G1 rule is a Perl undef. The action adverb is not allowed for G0 rules, which have no default value. The possible values of actions are described in their own section.

The default value of a lexeme is its literal value in the input stream, as a string. This is called the token value of the lexeme.

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. The bless adverb is allowed for alternatives of prioritized G1 rules, quantified G1 rules, and lexemes. The bless adverb is also allowed for the default lexeme statement and the default pseudo-rule. A G0 rule cannot have a bless adverb.

The value of a bless adverb is called a blessing. If the blessing is a Perl word (a string of alphanumerics or underscores), the name of the class will be formed by prepending the value of the bless_package named argument, followed by a double colon ("::").

If the blessing begins with a double colon ("::"), it is a reserved blessing. A blessing of ::undef means that the rule or lexeme will not be blessed. By default, both rules and lexemes are not blessed. If any rule or lexeme of a SLIF grammar has a blessing other than ::undef, a bless_package is required, and failure to specify one results in a fatal error.

The bless adverb for rules allows one additional reserved blessing: ::lhs. A blessing of ::lhs causes the result to be blessed into a class whose name is based on the LHS of the rule. The class will be the name of the LHS with whitespace changed to an underscore. (As a reminder, the whitespace in symbol names will have been normalized, with leading and trailing whitespace removed, and all other whitespace sequences changed to a single ASCII space.) When a ::lhs blessing value applies to a rule, it is a fatal error if the LHS contains anything other than alphanumerics and whitespace. In particular, the LHS cannot already contain an underscore ("_"). The ::lhs blessing is most useful in a default rule.

The bless adverb for lexemes allows only one reserved value: ::name. A reserved value of ::name causes the value of the lexeme to be blessed into a class whose name is based on the name of the lexeme. The class is derived from the symbol name in the same way, and subject to the same restrictions, as described above for deriving a class name from the LHS of a rule. The ::name reserved blessing is most useful in the lexeme default rule.

pause

The pause adverb applies only to lexemes. 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 appicable lexemes at that position will be read by G1, and internal scanning will pause immediately afterwards. (Note that, as of this writing, the after pause value is untested.)

A pause value has no effect if G1 would reject that lexeme at that location. A pause value also has no effect if its lexeme has a lexeme priority lower than the highest lexeme priority.

At the same priority, an pause value of before overrides any pause values of after at the same location. If pause values of both before and <after> could apply at a at a location, only "before" pause will take effect.

priority

The priority adverb is only allowed in a :lexeme pseudo-rule. It sets the lexeme priority for the lexeme. Priority must be an integer. It may be negative. 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 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 G0 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 indicates proper or Perl separation, as described for sequence rules.

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.

separator

The separator keyword is only valid for a quantified right side, and its value must be a symbol of the grammar. It will be used as the separator, as described for sequence rules.

Actions

Word actions

If the action value is a Perl word (a string of alphanumerics or underscores), it will be interpreted as the action name, as described for the action named argument of rule descriptors. Word actions are not allowed for lexemes.

Typically, a word action is resolved to a Perl closure, called the semantic closure. Ordinarily, the arguments to the semantic closure are the per-parse-tree variable, followed by values of the rule's child nodes, in the order in which they occurred in the input stream.

However, if a rule with a word action is blessed, in order to allow the blessing to take effect, the arguments to a semantic closure are formed differently. If the rule is blessed, its semantic closure will always have exactly two arguments. The first will be the per-parse-tree variable. The second will be a blessed array that contains the child values in input-stream order.

Reserved actions

If the action value begins with a double colon ("::"), it is a reserved action. The following are recognized:

  • ::array

    The value of the rule or lexeme is an array. For a rule, the array will contain the values of each of its children, in left-to-right order. If the rule has no children, the array will be empty. For a lexeme, the array will be of length one, and will contain the token value.

  • ::first

    The value of the rule is that of the rule's first child. If there is no such child, the value is a Perl undef.

    It is a fatal error if a blessing is applied to a rule with a ::first action. This is the case even when either or both adverbs are the result of a default. It is also a fatal error to use a ::first action with a lexeme.

  • ::undef

    The value of the rule or lexeme is a Perl undef. It is a fatal error if a blessing is applied to a rule with a ::undef action. This is the case even when either or both adverbs are the result of a default.

Array descriptor actions

lexeme default = action => [start,length,value] bless => ::name

An array descriptor is a comma separated list of zero or more array descriptor items, inside a pair of matching square brackets. The value of the lexeme or rule will be an array. The contents of the array will be a series of lists, as specified by the array descriptor items. These lists will occur in the array in the order specified. If no array descriptor items are specified, the value of the lexeme or rule will be an empty array.

The start array descriptor item will put the start location of the rule or lexeme into the array. The length array descriptor item will put the length (in parse locations) of the rule or lexeme into the array. Length in locations is defined such that the end location is always start location plus length.

For a rule, the values array descriptor item indicates a list containing the values of the rule's children, in left-to-right order. For a lexeme, the value array descriptor item indicates a list containing a single element, the token value of the lexeme.

::array is equivalent to [values]. The value and values array descriptor items are synonyms, and may be used interchangeably for both rules and lexemes. This means that, for both lexemes and rules, the actions [values], [value] and ::array will do exactly the same thing.

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.

Caveats

Symbol names

The SLIF may rewrite its symbol names internally. Here we call the name by which a symbol is specified in the SLIF source string its "external symbol name", and its name as rewritten, its "internal symbol name". In many cases, Marpa::R2 makes sure the user sees only the external names of symbols. For example, the rule() Grammar method returns external symbol names.

However, for some purposes, such as tracing grammars, the use of internal names may sometimes be appropriate. Marpa::R2's use of external and internal symbol names is evolving. When the SLIF is used, except as documented in this section, the user may see either the internal or external form of a symbol's name. Additionally, the exact form of the internal name is subject to change.

Precedence: the good news

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.

Precedence and ambiguous grammars

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 an 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 Stuifzand interface. 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, Marpa's standard interface can parse it.

Copyright and License

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