The overall syntax of a grammar is as follows. We use the the Modified BNF Syntax as defined with ANSI-CL.
| grammar | := | {↓rule}* | ||
| rule | := |
( ↓non-terminal {->
↓rhs}+ )
|
||
| ↓option | ||||
| rhs | := |
{↓pattern}* [=>
↓action]
|
||
| pattern | := | ↓non-terminal | ||
| ↓token | ||||
(* ↓rhs)
|
||||
(+ ↓rhs)
|
||||
(? ↓rhs)
|
||||
(++ ↓pattern
↓rhs)
|
||||
(** ↓pattern
↓rhs)
|
||||
(or
{↓pattern}*)
|
||||
(and ↓rhs)
|
||||
| non-terminal | := | a symbol but not a keyword | ||
| token | := | a keyword or a string | ||
| action | := | a Lisp form | ||
| option | := |
(:precedence
{↓precedence}*)
|
||
| precedence | := |
({:left | :right |
:nonassoc}
{↓token}*)
|
Within an action symbols named $i
($1, $2, …) refer to the ith
semantic action. The package of these symbols is not important but the
symbols must appear lexically within the action.
As with loop the symbols ->, =>,
?, *, +, **,
++ are compared with string=, thus the package
is not important here.
Each rule looks like
(↓non-terminal
{-> ↓rhs}+)
That is a non-terminal name followed by a list of productions
right-hand-sides each preceeded by ->. Non-terminals are
named by symbols, which may not be keywords. Each such production may
include a semantic action preceeded by => which is
evaluated and becomes the semantic value of this production.
The RHS items are patterns. In the simplest case such a pattern is a symbol naming another non-terminal or a keyword naming a lexical category. As a convenience strings are accepted as lexical categories as well.
(sum -> sum "+" product
-> product)
This rule has two productions. The first says that a sum is
either a sum followed by the token "+" and a
product, the second says it may also be just a
product.
We may want to add a semantic action to the first production so that the
semantic value of the sum non-terminal when matched is
indeed the sum of the arguments. Like
(sum -> sum "+" product => (+ $1 $3)
-> product)
The Lisp form (+ $1 $3) is evaluated with $1
lexically defined to be the semantic value of the sum
mentioned in the RHS and $3 being the semantic value of the
third item in the RHS namely the product non-terminal. We
do not need an explicit semantic action for the second production
-> product because a semantic action returning just
$1 is the default.
(* ↓rhs)
Matches zero or more of rhs. The semantic value is a list of all the semantic value of rhs.
(+ ↓rhs)
Same as (* rhs), but matches
one or more of rhs.
(? ↓rhs)
Option. Matches zero or one rhs. The semantic value of this
pattern is either nil when rhs did not appear,
or the semantic value of rhs.
(** separator rhs)
A list of zero or more occurrences of rhs separated by the pattern separator. The semantic value of this pattern is a list of the rhs appeared.
(++ separator rhs)
Same as ** but at least one rhs must be
present.