5.3 Rules

A standard way of describing rules is Backus-Naur Form, or BNF. In one common way of writing BNF, a rule looks like this:

    Expression ::= Term Factor

In the rule above, Expression, Term and Factor are symbols. A rule consists of a left hand side and a right hand side. In a context-free grammar, like those Marpa parses, the left hand side of a rule is always a symbol string of length 1. The right hand side of a rule is a symbol string of zero or more symbols. In the example, Expression is the left hand side, and Term and Factor are right hand side symbols.

Left hand side and right hand side are often abbreviated as RHS and LHS. If the RHS of a rule has no symbols, the rule is called an empty rule or an empty rule.

The length of a rule is the length of its RHS string. This implies that the length of an empty rule is zero.

In a standard grammar, all rules are BNF rules, as just described. Marpa grammars differ from standard grammars in allowing a second kind of rule: a sequence rule. The RHS of a sequence rule is a single symbol, which is repeated zero or more times. Libmarpa allows the application to specify other parameters for sequence rules, including a separator symbol. See Sequence rules.