1 Introduction

This report defines how Oz program text, which is a sequence of characters, is transformed into an Oz Core program. This transformation is performed in three steps.

Lexical Syntax

First, a given program text is transformed into a sequence of words. Each word represents a sequence of tokens. We call this process tokenizing.

Context-free Syntax

The resulting sequence of tokens is transformed into a parse tree. We call this process parsing, and the resulting parse tree program.

Core Programs

The program is translated to a Core program, eliminating a number of abbreviations and nesting.

At each step, errors may occur. A text represents an Oz program if it can be tokenized and parsed into a program which can be translated without error into a Core program.

Meta Notation

In a document like this one, it is helpful to make use of notational conventions in order to provide for concise and precise descriptions.

1.1 Fonts

We make use of fonts to distinguish the different kinds of symbols occurring in this document:



terminal or nonterminal symbol

<variable>, <statement>


local, skip

1.2 Regular Expressions and Context-Free Grammars

Regular expressions and context free grammars describe sets of words. We use the following notation to describe one such set in terms of others (in increasing order of precedence):




singleton containing the empty word


grouping of regular expressions

w ]

union of \epsilon with the set of words w

w }

set of words containing all concatenations of zero or more elements of w

w }+

set of words containing all concatenations of one or more elements of w

w_1 w_2

set of words containing all concatenations of an element of w_1 with an element of w_2

w_1 | w_2

union of w_1 and w_2

w_1 - w_2

difference of w_1 and w_2

Martin Henz and Leif Kornstaedt
Version 1.4.0 (20080702)