Prev Up Next
Go backward to Prerequisites
Go up to Top
Go forward to Running a Parser

Grammars

Context-free grammars are at the heart of parser generation. Essence allows specifying so-called S-attributed grammars with evaluation rules for synthesized attributes. The assumption is that each node in the parse tree carries an instance of exactly one synthesized attribute, and an Essence grammar provides an expression describing how to compute the attribute along with each production.

The structure grammar provides a defining form for grammars. (It also provides numerous accessors and algorithms over grammars. However, these are not relevant for using Essence.)

An Essence grammar consists of two data objects: a representation of the grammar itself, and an enumeration (see doc/big-scheme.txt in the Scheme 48 distribution for a description of the enumeration facility in Scheme 48) which is needed to symbolically encode the input to the parser. The macro define-grammar from the grammar structure form defines both:

 

(define-grammar  <variable1> <variable2>
<nonterminals> <terminals> <start-symbol> <rules>) syntax

Syntax:

<Nonterminals> has the form 

  (<nonterminal> ...)

where each <nonterminal> is an <identifier>. <Terminals> is similarly of the form 

  (<terminal> ...)

with <terminal> an <identifier>. <Terminal> and <nonterminal> must be disjoint. <Start-symbol> must be a <nonterminal>. <Rules> has the form: 

  (<rule> ...)

where each indivial <rule> has the form 

  ((<nonterminal> <grammar-symbol> ...) <attribution>)

where each <grammar-symbol> is either a <nonterminal>, a <terminal>, or $error. (The latter is for directing error recovery <Attribution> is a Scheme expression.

Semantics:

Define-grammar defines a context-free grammar along with an enumeration type for its symbols. Define-grammar binds a data object representing the grammar to its first argument, and an enumeration type for its symbols to its second argument.

The third argument to define-grammar is a list of nonterminals, the fourth a list of terminals. The fifth argument is the start symbol (which must be one of the nonterminals), then comes a list of the grammar rules.

A grammar rules consist of a production--a list with a nonterminal as its first element, and the right-hand side as its rest--and an attribution.

The attribution is a Scheme expression, which may have free variables $i, where i ranges from 1 to the number of symbols on the right-hand side of the production. During parsing, the Essence parser binds $i to the attribute instance of the ith symbol on the right-hand-side when evaluating the attribution.

Here is a simple example grammar for arithmetic expressions: 

(define-grammar g10 g10-symbol
  (E T P)
  (+ - * / l r n)
  E
  (((E T) $1)
   ((E T + E) (+ $1 $3))
   ((E T - E) (- $1 $3))
   ((T P) $1)
   ((T P * T) (* $1 $3))
   ((T P / T) (/ $1 $3))
   ((P n) $1)
   ((P l E r) $2)))
This definition establishes an enumeration type g10-symbol with components (in that order):  
Mike Sperber, Peter Thiemann

Prev Up Next