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.

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.

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