Multi-Directional Pattern Notation
==================================
Final - Sep 6 1999
* * * * *
Introduction
------------
MDPN is an extension to EBNF, which attributes it for the purposes of
scanning and parsing input files which assume a non-unidirectional form.
A familiarity with EBNF is assumed for the remainder of this document.
MDPN was developed by Chris Pressey in late 1998, built on an earlier,
less successful attempt at a "2D EBNF" devised to fill a void that the
mainstream literature on parsing seemed to rarely if ever approach, with
much help provided by John Colagioia throughout 1998.
MDPN has possible uses in the construction of parsers and subsequently
compilers for multi-directional and multi-dimensional languages such as
Orthogonal, Befunge, Wierd, Blank, Plankalkül, and even less contrived
notations like structured Flowchart and Object models of systems.
As the name indicates, MDPN provides a notation for describing
multidimensional patterns by extending the concept of linear scanning
and matching with geometric attributes in a given number of dimensions.
Preconditions for Multidirectional Parsing
------------------------------------------
The multidirectional parsing that MDPN concerns itself with assumes that
any portion of the input file is accessable at any time. Concepts such
as LL(1) are fairly meaningless in a non-unidirectional parsing system
of this sort. The unidirectional input devices such as paper tape and
punch cards that were the concern of original parsing methods have been
superceded by modern devices such as hard disk drives and ample, cheap
RAM.
In addition, MDPN is limited to an orthogonal representation of the
input file, and this document is generally less concerned about forms of
four or higher dimensions, to reduce unnecessary complexity.
Notation from EBNF
------------------
Syntax is drawn from EBNF. It is slightly modified, but should not
surprise anyone who is familiar with EBNF.
A freely-chosen unadorned ('bareword') alphabetic multicharacter
identifier indicates the name of a nonterminal (named pattern) in the
grammar. e.g. `foo`. (Single characters have special meaning as
operators.) Case matters: `foo` is not the same name as `Foo` or `FOO`.
Double quotes begin and end literal terminals (symbols.) e.g. `"bar"`.
A double-colon-equals-sign (`::=`) describes a production (pattern
match) by associating a single nonterminal on the left with a pattern on
the right, terminated with a period. e.g. `foo ::= "bar".`
A pattern is a series of terminals, nonterminals, operators, and
parenthetics.
The `|` operator denotes alternatives. e.g. `"foo" | "bar"`
The `(` and `)` parentheses denote precedence and grouping.
The `[` and `]` brackets denote that the contents may be omitted, that
is, they may occur zero or one times. e.g. `"bar" ["baz"]`
The `{` and `}` braces denote that the contents may be omitted or may be
repeated any number of times. e.g. `"bar" {baz "quuz"}`
Deviations from EBNF
--------------------
The input file is spatially related to a coordinate system and it is
useful to think of the input mapped to an orthogonally distributed
(Cartesian) form with no arbitrary limit imposed on its size,
hereinafter referred to as *scan-space*.
The input file is mapped to scan-space. The first printable character in
the input file always maps to the *origin* of scan-space regardless of
the number of dimensions. The origin is enumerated with coordinates (0)
in one dimension, (0,0) in two dimensions, (0,0,0) in three dimensions,
etc.
Scan-space follows the 'computer storage' co-ordinate system so that *x*
coordinates increase to the 'east' (rightwards), *y* coordinates
increase to the 'south' (downwards), and *z* coordinates increase on
each successive 'page'.
Successive characters in the input file indicate successive coordinate
(*x*) values in scan-space. For two and three dimensions, end-of-line
markers are assumed to indicate "reset the *x* dimension and increment
the *y* dimension", and end-of-page markers indicate "reset the *y*
dimension and increment the *z* dimension", thus following the
commonplace mapping of computer text printouts.
Whitespace in the input file are **not** ignored. The terminal `" "`,
however, will match any whitespace (including tabs, which are **not**
expanded.) The pattern `{" "}` may be used to indicate any number of
whitespaces; `" " {" "}` may be used to indicate one or more
whitespaces. Areas of scan-space beyond the bounds of the input file are
considered to be filled with whitespaces.
Therefore, `"hello"` as a terminal is exactly the same as
`"h" "e" "l" "l" "o"` as an pattern of terminals.
A `}` closing brace can be followed by a `^` (*constraint*) operator,
which is followed by an expression in parentheses.
This expression is actually in a subnotation which supports a very
simple form of algebra. The expression (built with terms connected by
infix `+-*/%` operators with their C language meanings) can either
reduce to
- a constant value, as in `{"X"} ^ (5)`, which would match five `X`
terminals in a line; or
- an unknown value, which can involve any single lowercase letters,
which indicate variables local to the production, as in
`{"+"}^(x) {"-"}^(x*2)`, which would match only twice as many minus
signs as plus signs.
Complex algebraic expressions in constraints can and probably should be
avoided when constructing a MDPN grammar for a real (non-contrived)
compiler. MDPN-based compiler-compilers aren't expected to support more
than one or two unknowns per expression, for example. There is no such
restriction, of course, when using MDPN as a guide for hand-coding a
multidimensional parser, or otherwise using it as a more sophisticated
pattern-matching tool.
The Scan Pointer
----------------
It is useful to imagine a *scan pointer* (SP, not to be confused with a
*stack pointer*, which is not the concern of this document) which is
analogous to the current token in a single-dimensional parser, but
exists in MDPN as a free spatial relationship to the input file, and
thus also has associated geometric attributes such as direction.
The SP's *location* is advanced through scan-space by its *heading* as
terminals in the productions are successfully matched with symbols in
the input buffer.
The following geometric attribution operators modify the properties of
the SP. Note that injudicious use of any of these operators *can* result
in an infinite loop during scanning. There is no built-in contingency
measure to escape from an infinite parsing loop in MDPN (but see
exclusivity, below, for a possible way to overcome this.)
`t` is the relative translation operator. It is followed by a vector, in
parentheses, which is added to the location of the SP. This does not
change its heading.
For example, `t (0,-1)` moves the SP one symbol above the current symbol
(the symbol which was *about* to be matched.)
As a more realistic example of how this works, consider that the pattern
`"." t(-1,1) "!" t(0,-1)` will match a period with an exclamation point
directly below it, like:
.
!
`r` is the relative rotation operator. It is followed by an axis
identifier (optional: see below) and an orthogonal angle (an angle *a*
such that |*a*| **mod** 90 degrees = 0) assumed to be measured in
degrees, both in parentheses. The angle is added to the SP's heading.
Negative angle arguments are allowed.
Described in two dimensions, the (default) heading 0 denotes 'east,'
that is, parsing character by character in a rightward direction, where
the SP's *x* axis coordinate increases and all other axes coordinates
stay the same. Increasing angles ascend counterclockwise (90 = 'north',
180 = 'west', 270 = 'south'.)
For example, `">" r(-90) "+^"` would match
>+
^
The axis identifier indicates which axis this rotation occurs around. If
the axis identifier is omitted, the *z* axis is to be assumed, since
this is certainly the most common axis to rotate about, in two
dimensions.
If the axis identifier is present, it may be a single letter in the set
`xyz` (these unsurprisingly indicate the *x*, *y*, and *z* dimensions
respectively), or it may be a non-negative integer value, where 0
corresponds to the *x* dimension, 1 corresponds to the *y* dimension,
etc. (Implementation note: in more than two dimensions, the SP's heading
property should probably be broken up internally into theta, rho, &c
components as appropriate.)
For example, `r(z,180)` rotates the SP's heading 180 degrees about the
*z* (dimension \#2) axis, as does `r(2,180)` or even just `r(180)`.
`<` and `>` are the push and pop state-stack operators, respectively.
Alternately, they can be viewed as lookahead-assertion parenthetics,
since the stack is generally assumed to be local to the production.
(Compiler-compilers should probably notify the user, but not necessarily
panic, if they find unbalanced `<>`'s.)
All properties of the SP (including location and heading, and scale
factor if supported) are pushed as a group onto the stack during `<` and
popped as a group off the stack during `>`.
Advanced SP Features
--------------------
These features are not absolutely necessary for most non-contrived
multi-directional grammars. MDPN compiler-compilers are not expected to
support them.
`T` is the absolute translation operator. It is followed by a vector
which is assigned to the location of the SP. e.g. `T (0,0)` will 'home'
the scan.
`R` is the absolute rotation operator. It is followed by an optional
axis identifier, and an orthogonal angle assumed to be measured in
degrees. The SP's heading is set to this angle. e.g. `R(270)` sets the
SP scanning line after line down the input text, downwards. See the `r`
operator, above, for how the axis identifier functions.
`S` is the absolute scale operator. It is followed by an orthogonal
*scaling factor* (a scalar *s* such that *s* = **int**(*s*) and *s* \>=
1). The SP's scale factor is set to this value. The finest possible
scale, 1, indicates a 1:1 map with the input file; for each one input
symbol matched, the SP advances one symbol in its path. When the scale
factor is two, then for each one input symbol matched, the SP advances
two symbols, skipping over an interim symbol. Etc.
`s` is the relative scale operator. It is followed by a scalar integer
which is added to the SP's scaling factor (so long as it does not cause
the scaling factor to be zero or negative.)
Scale operators may also take an optional axis identifier (as in
`S(y,2)`), but when the axis identifier is omitted, all axes are assumed
(non-distortional scaling).
`!>` is a state-assertion alternative to `>`, for the purpose of
determining that the SP successfully and completely reverted to a
previous state that was pushed onto the stack ('came full circle'). This
operator is something of a luxury; a grammar which uses constraints
correctly should never *need* it, but it can come in handy.
Other Advanced Features: Exclusivity
------------------------------------
Lastly, in the specification of a production, the *exclusivity* applying
to that production can be given between a hyphen following the name of
the nonterminal, and the `::=` operator.
Exclusivity is a list of productions, named by their nonterminals, and
comes into play at any particular *instance* of the production (i.e.
when the production successfully matches specific symbols at specific
points in scan-space during a parse, called the *domain*.) The
exclusivity describes how the domain of each instance is protected from
being the domain of any further instances. The domain of any subsequent
instances of any productions listed in the exclusivity is restricted
from sharing points in scan-space with the established domain.
Exclusivity is a measure to prevent so-called *crossword grammars* -
that is, where instances of productions can *overlap* and share common
symbols - if desired. Internally it's generally considered a list of
'used-by-this-production' references associated with each point in
scan-space. An example of the syntax to specify exclusivity is
`bar - bar quuz ::= foo {"a"} baz`. Note that the domain of an instance
of `bar` is the sum of the domains `foo`, `baz` and the chain of "`a`"
terminals, and that neither a subsequent instance of `quuz` nor `bar`
again can overlap it.
Examples of MDPN-described Grammars
-----------------------------------
**Example 1.** A grammar for describing boxes.
The task of writing a translator to recognize a two-dimensional
construct such as a box can easily be realized using a tool such as
MDPN.
An input file might contain a of box drawn in ASCII characters, such as
+------+
| |
| |
+------+
Let's also say that boxes have a minimum height of four (they must
contain at least two rows), but no minimum width. Also, edge characters
must match up with which edge they are on. So, the following forms are
both illegal inputs:
+-+
+-+
+-|-+
| |
*
| |
+-|-+
The MDPN production used to describe this box might be
Box ::= "+" {"-"}^(w) r(-90) "+" "||" {"|"}^(h) r(-90)
"+" {"-"}^(w) r(-90) "+" "||" {"|"}^(h) r(-90).
**Example 2.** A simplified grammar for Plankalkül's assignments.
An input file might contain an ASCII approximation of something Zuse
might have jotted down on paper:
|Z + Z => Z
V|1 2 3
S|1.n 1.n 1.n
Simplified MDPN productions used to describe this might be
Staff ::= Spaces "|" TempVar AddOp TempVar Assign TempVar.
TempVar ::= "Z" t(-1,1) Index t(-1,1) Structure t(0,-2) Spaces.
Index ::= <Digit {Digit}>.
Digit ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9".
Structure ::= <Digit ".n">.
AddOp ::= ("+" | "-") Spaces.
Assign ::= "=>" Spaces.
Spaces ::= {" "}.