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.