GRAIL: GRAmmars In Lisp

CMPT 384 Lecture Notes
Robert D. Cameron
September 15, 1999

Grammars and Symbolic Notation

Grammars are formalisms for defining the syntactic structure of languages and other notation systems. For example, BNF (Backus-Naur Form) is a widely-used formalism for describing the syntax of programming languages.

Typically, a grammar is defined in terms of production rules that describe the legal string syntax of the various syntactic classes in the language. The language itself is considered to be the set of all possible strings that can be produced for the top-level syntactic construct.

Beyond the string syntax of the language, however, grammars are also useful for describing the structure of the language. This is often referred to as the abstract syntax of the language in contrast to the concrete syntax represented by the detailed string representation.

Often, symbolic computing systems may be supported by grammatical formalisms that define both the abstract and concrete syntax of the language. This gives a basis for defining both the string representation of the symbolic data objects and the abstract data type for processing those objects as instances of appropriate symbolic data domains. One example of such a formalism is GRAIL, for defining GRAmmars in Lisp.

GRAIL

GRAIL grammars have 3 goals:

to concisely define the Lisp representation for a given notation system (symbolic data domain).
to specify all the necessary data access functions for manipulating objects of the data domain.
to serve as complete documentation for the symbolic data domain as an abstract data type (ADT).

GRAIL grammars are defined using 4 types of production rule.

Alternation rules.
Construction rules.
List rules.
Lexical rules.

Algebraic Expressions in GRAIL

<expr>	::=	<constant> \| <variable> \| <negation> \| <product> \| <sum>
<negation>	::=	`(` `-` <operand:expr> `)`
<product>	::=	`(` <operand1:expr> `*` <operand2:expr> `)`
<sum>	::=	`(` <operand1:expr> `+` <operand2:expr> `)`
<constant>	::=	<const-val:numeric-atom>
<variable>	::=	<var-name:symbolic-atom>

Alternation Rules

Alternation rules define a symbolic data domain as one of several alternatives.

<expr>

::=

Specification: Alternation rules specify that recognizers must be defined, e.g., constant-p, variable-p, negation-p, etc.

Implementation: How are these recognizers to be implemented?

Restriction: Each alternative must be a nonterminal. Why?

Relationship to BNF?

Construction Rules

Construction rules define a structured symbolic data domain represented as a Lisp list.

<negation>	::=	`(` `-` <operand:expr> `)`
<product>	::=	`(` <operand1:expr> `*` <operand2:expr> `)`
<sum>	::=	`(` <operand1:expr> `+` <operand2:expr> `)`

Form: A BNF rule with augmented nonterminals. How? Why?

Specification: Construction rules specify selector and constructor functions, e.g., operand, operand1, operand2, make-negation, make-product, make-sum.

Implementation?

Overloading: the same selectors can appear in more than one rule.

Restrictions?

List Rules

List rules define objects that are lists of entities.

<item-list> ::= ( <item^*> )

List rules specify that the standard list processing operations cons, first, rest, endp apply to the defined domain.

Why not specify separate list processing operations for each list domain, e.g., cons-item, first-item, rest-items, end-item-list-p?

Tedious.

We treat the standard list processing operations as generic, i.e., they can be used with any list domain.

The ^* notation means a list of zero or elements; we can restrict lists to have at least one element with the ⁺ notation.

Lexical Rules

Lexical rules define atomic domains.

::=

<const-val:numeric-atom>

Lexical rules specify converter functions, e.g., const-val and make-constant.

Why is this not a construction rule?

Lexical rules may also specify a single element domain

<asterisk> ::= *

This gives a data access ``constant:'';

asterisk = "*"

Matrices in GRAIL

Here is a GRAIL grammar for 2 by 2 matrices:

<matrix> ::= ( ( <x11:value> <x12:value> ) ( <x21:value> <x22:value> ) )

The corresponding data access functions deal with two levels of list structure.

x11[matrix] = first[first[matrix]]
x12[matrix] = second[first[matrix]]
x21[matrix] = first[second[matrix]]
x22[matrix] = second[second[matrix]]
make-matrix[x11; x12; x21; x22] =
  list2[list2[x11; x12]; list2[x21; x22]]

Sublist Components in GRAIL

Lists may be components in GRAIL construction rules:

<series-sum>	::=	`(` `SIGMA` <summands:expr-list> `)`
<expr-list>	::=	`(` <expr⁺> `)`

Instead, use sublist nonterminals:

<series-sum> ::= ( SIGMA ( <summands:expr⁺> ) )

The DAFs:

summands[series] = second[series]
make-series-sum[summands] = 
  list2["SIGMA"; summands]

Examples:

(SIGMA (X Y 5))
(SIGMA ((Z TIMES 2) 1))

But we might want a flatter representation:

(SIGMA X Y 5)
(SIGMA (Z TIMES 2) 1)

This can be done by using the sublist non-terminal as the last component of the top-level list structure:

<series-sum> ::= ( SIGMA <summands:expr⁺> )

The new DAFs:

summands[series] = rest[series]
make-series-sum[summands] = 
  cons["SIGMA"; summands]

The Metasyntax of GRAIL

GRAIL is itself a notation system. Here is the EBNF:

<alt-rule>	::=	<nonterm> `::=` <nonterm> {`\|` <nonterm>}
<nonterm>	::=	`<` <identifier> `>`
<list-rule>	::=	<nonterm> `::=` `(` <list-nonterm> `)`
<list-nonterm>	::=	`<` <identifier> <rep-symbol> `>`
<rep-symbol>	::=	^* \| ⁺
<cons-rule>	::=	<nonterm> `::=` <list-phrase>
<list-phrase>	::=	`(` {<list-item>} [<sublist-NT>] `)`
<list-item>	::=	<atom> \| <augmented-NT> \| <list-phrase>
<augmented-NT>	::=	`<` <identifier> `:` <identifier> `>`
<sublist-NT>	::=	`<` <identifier> `:` <identifier> <rep-symbol> `>`
<lexical-rule>	::=	<nonterm> `::=` <augmented-NT> \| <nonterm> `::=` <atom>

Exercise: consider the representation of GRAIL grammars as Lisp data objects (GRAIL in GRAIL)!