[DGD] RFC: dgd/doc/parser

[Felix A. Croes]

			Parser reference manual

1. Introduction

The parse_string() utility for DGD parses strings as follows: first, the
string is broken up into two types of smaller strings, called "tokens" and
"whitespace".  Next, the resulting array of tokens (whitespace is ignored) is
parsed as a sentence in the language defined by a formal grammar.  For any
valid parsings, LPC functions are called as appropriate, which may transform
the array of tokens, or indicate that a particular parsing of the string
is yet to be considered invalid.  Finally, the resultant array of tokens, if
any, is returned by the function.

Regular expressions are used to define tokens and whitespace, and the language
of those tokens is defined by a context-free grammar, which can be enhanced
with LPC function calls.  [insert reference to context-free grammars]
Token/whitespace definitions and language definition together are called
"the grammar".

Internally, DGD generates two partial automatons for each grammar, one to
match tokens and one to parse a sentence of tokens.  Only those parts of the
automatons are generated that are required to parse the sentences seen so far;
this effect is cumulative for successive calls in each object, ensuring that
the automatons are not needlessly generated more than once.  Each object can
handle only one grammar at a time.  If a grammar differs from the previous
one used by the same object, any existing generated automatons are wiped out
and constructed anew.


2. Grammar

A grammar consists of token rules and production rules, which may be given in
any order.  Each grammar must contain at least one token rule and one
production rule.


2.1 Token rules

A token rule has the following format:

    token = /regexp/

where "token" is an identifier name as in LPC, and "regexp" a regular
expression, with the following syntax:

    c	    a single character except `.', `[', `\', `*', `+', `(', `)'
    .	    any single character
    \c	    a single character c, including `.', `[', `\', `*', `+', `(', `)'
    [set]   a single character in the given set, which is constructed of
	    single characters such as `a' and/or character ranges such as
	    `a-z'.  `\' may be used to escape the characters `]', `^', `-'
    [^set]  a single character not in the given set

and, with regular expressions "a" and "b":

    a*      zero or more occurances of a	(highest precedence)
    a+      one or more occurances of a
    ab      the concatenation of a and b
    a|b     a or b
    (a)     a					(lowest precedence)

For any regular expression, the longest possible token will be matched.  The
name "whitespace" is reserved for defining a special token, which is simply
skipped.  More than one rule may be specified for each token, including
whitespace.

If a string matches more than token, the token for which the rule appears first
in the grammar is selected.  If a string does not match any token, it is
rejected and parsing fails.


2.2 Production rules

A production rule has the following format:

    symbol : rule

where "symbol" is an identifier name as in LPC for the production rule, and
"rule" consists of zero or more token symbols, production rule symbols, or
string constants delimited by single quotes.

A string constant in a production rule matches the given sequence of characters
directly, without reference to a token rule.  Since a token rule is implicitly
generated for such string constants, the string constant is also said to be a
token.  String constants take precedence over regular expressions, and any
token that matches both a string constant and a regular expression will always
match the string constant, only.  `\' may be used in a string constant to
escape the single quote.

More than one production rule may be given for the same symbol.  All
production rules taken together form a context-free grammar, for which the
start symbol is defined in the first rule.  Production rules that are
unreachable from the start symbol are ignored.  Any symbol used in a
production rule reachable from the start symbol must itself define a token
rule or a production rule.

Optionally, a rule can be followed by an LPC function name:

    symbol : rule ? function

where "function" is the name of an LPC function to be called in the current
object if the specified rule has been matched.


3. Parsing

Normally, parse_string() returns a flat array of token strings (if the input
string could be parsed as a sentence in the language defined by the grammar)
or 0 (if the input string could not be parsed).  However, the return value can
be modified to an array containing arbitrary other values, including
sub-arrays, by specifying LPC functions in the grammar that will be called
while parsing.  Moreover, if the grammar is ambiguous, sub-arrays for the
alternative may be automatically included in the result.


3.1 LPC functions

An LPC function called for a production rule will have a single argument,
an array with the parse tree that matches the production rule.  LPC functions
are called in bottom-up order, so any function calls for sub-parse trees in
the current parse tree will already have been made.

The LPC function can return its argument unchanged, or modify its argument
before returning it, or return a completely different value.  Whatever the
return value is, it is taken to be an array matching the current rule; if
it is not an array at all, the current parse tree (and all parse trees that
depend on it) are discarded altogether.

LPC functions are typically used to replace tokens in the parse tree by
their semantic value, or to add structure to a parse tree, which otherwise
would be represented as a flat array.


3.2 Ambiguous grammars

A grammar that allows more than one parse tree for the same input string is
said to be "ambiguous".  The string parser will sort alternative parse trees
by the order of the topmost different rule in the grammar, and by default
ignore all of them but the first one.

An optional third argument to parse_string() can be used to retain an
additional number of alternative parse trees, which will be merged with the
first one; the argument specifies the number of extra alternatives to keep at
each point where sub-parse trees are handled by different rules in the grammar.
Instead of incorporating the first alternative immediately in the array
returned, a sub-array containing all of the alternatives as separate elements
is included, sorted by the order of their topmost rule in the grammar.

LPC functions called for rules can be used to invalidate alternative parse
trees.  Invalidated alternatives will be removed from the overall result.


3.3 Writing grammars

Grammars can be parsed most efficiently if they are not ambiguous.  Generally,
ambiguous grammars can be rewritten to be non-ambiguous.  For example,
consider the following (partial) grammar, which is ambiguous:

    Expr: number
    Expr: Expr '+' Expr

It can be rewritten to be either left-recursive,

    SimpleExpr: number
    Expr: SimpleExpr
    Expr: Expr '+' SimpleExpr

or right-recursive:

    SimpleExpr: number
    Expr: SimpleExpr
    Expr: SimpleExpr '+' Expr

Neither rewritten grammar is ambiguous, and both explicitly specify the order
in which expressions are to be evaluated: from left to right, or from right to
left, respectively.