# 3 Context-Free Syntax

In this section, we give a context-free grammar for a superset of Oz programs. Any sequence of tokens that is not a member of the language described by this grammar, starting from the <statement> nonterminal, is considered erroneous.

Implementations may accept a larger language, e. g., something more than only a statement at top-level, or treat lexical syntax that has no assigned meaning in the report as compiler directives.

## 3.1 The Base Language

Statements

> <statement> | ::= | <statement> <statement>
> | | | `local` <in statement> `end`
> | | | "`(`" <in statement> "`)`"
> | | | `proc` { <atom> } "`{`" <expression> { <pattern> } "`}`"
> |  | <in phrase>
> |  | `end`
> | | | `fun` { <atom> } "`{`" <expression> { <pattern> } "`}`"
> |  | <in expression>
> |  | `end`
> | | | "`{`" <expression> { <expression> } "`}`"
> | | | `if` <expression> `then` <in statement>
> |  | [ <else statement> ]
> |  | `end`
> | | | `case` <expression> `of` <case statement clause>
> |  | { `[]` <case statement clause> }
> |  | [ <else statement> ]
> |  | `end`
> | | | `lock` <expression> `then` <in statement> `end`
> | | | `thread` <in statement> `end`
> | | | `try` <in statement>
> |  | [ `catch` <case statement clause> { "`[]`" <case statement clause> } ]
> |  | [ `finally` <in statement> ]
> |  | `end`
> | | | `raise` <in expression> `end`
> | | | <expression> "`=`" <expression>
> | | | <expression> "`:=`" <expression>
> | | | <expression> "`.`" <expression> "`:=`" <expression>
> | | | `skip`

Expressions

> <expression> | ::= | `local` <in expression> `end`
> | | | "`(`" <in expression> "`)`"
> | | | `proc` { <atom> } "`{`" "`$`" { <pattern> } "`}`"
> |  | <in phrase>
> |  | `end`
> | | | `fun` { <atom> } "`{`" "`$`" { <pattern> } "`}`"
> |  | <in expression>
> |  | `end`
> | | | "`{`" <expression> { <expression> } "`}`"
> | | | `if` <expression> `then` <in expression>
> |  | <else expression>
> |  | `end`
> | | | `case` <expression> `of` <case expression clause>
> |  | { `[]` <case expression clause> }
> |  | [ <else expression> ]
> |  | `end`
> | | | `lock` <expression> `then` <in expression> `end`
> | | | `thread` <in expression> `end`
> | | | `try` <in expression>
> |  | [ `catch` <case expression clause> { "`[]`" <case expression clause> } ]
> |  | [ `finally` <in statement> ]
> |  | `end`
> | | | `raise` <in expression> `end`
> | | | <expression> "`=`" <expression>
> | | | <expression> `orelse` <expression>
> | | | <expression> `andthen` <expression>
> | | | <monop> <expression>
> | | | <expression> <binop> <expression>
> | | | <expression> "`:=`" <expression>
> | | | <expression> "`.`" <expression> "`:=`" <expression>
> | | | <possibly escaped variable>
> | | | "`_`"
> | | | <atom> | <int> | <float>
> | | | `unit` | `true` | `false`
> | | | <label> "`(`" { <subtree> } [ "`...`" ] "`)`"
> | | | "`[`" { <expression> }+ "`]`"
> | | | <expression> "`|`" <expression>
> | | | <expression> { "`#`" <expression> }+
> | | | "`$`"

> <label> | ::= | <variable label> | <atom label>
> | | | <unit label> | <true label> | <false label>

> <feature> | ::= | <variable> | <atom> | <int>
> | | | `unit` | `true` | `false`

> <subtree> | ::= | [ <feature> "`:`" ] <expression>

Precedence

Note that in both <statement>s and <expression>s there is potential ambiguity between <expression> "`:=`" <expression> and <expression> "`.`" <expression> "`:=`" <expression>. In fact "`. :=`" is a ternary operator and has precedence. Parenthesis must be used for the alternate parse, that is, (<expression>"`.`"<expression>) "`:=`" <expression>.

The assignment operators "`. :=`" and "`:=`", when used in expression position, perform an atomic exchange, the result of the operation being the previous value of the stateful entity assigned to.

Operators

Expressions with operators need additional disambiguating rules introduced in Section 3.5.

> <monop> | ::= | "`~`" | "`!!`" | "`@`"

> <binop> | ::= | "`.`" | "`^`"
> | | | "`==`" | "`\=`" | "`<`" | "`<=`" | "`>`" | "`>=`"
> | | | "`+`" | "`-`" | "`*`" | "`/`" | `div` | `mod`

Declarations

A <declaration part> is a sequence of variables and statements. Singleton variables serve only for explicit declaration and are otherwise ignored. Variables within statements are implicitly declared if they occur at a pattern position. A prefixed escape (`!`) prevents implicit declaration.

> <declaration part> | ::= | <variable>
> | | | <statement>
> | | | <declaration part> <declaration part>

> <in statement> | ::= | [ <declaration part> `in` ] <statement>

> <in expression> | ::= | [ <declaration part> `in` ] [ <statement> ] <expression>

> <possibly escaped variable> | ::= | [ "`!`" ] <variable>

As procedure body either a statement or an expression may be possible, depending on whether the procedure's formal parameter patterns contain a nesting marker (`$`) or not.

> <in phrase> | ::= | <in statement>
> | | | <in expression>

Patterns

Pattern matching is performed as a top-down left-to-right sequence of tests. Record patterns test a value's constructor; constant patterns and escaped variable patterns test for equality with the given value; nonlinearities (variables occurring multiply in one pattern) test for equality of the corresponding subtrees. Equation patterns and non-escaped variables introduce variable bindings.

> <pattern> | ::= | <label> "`(`" { <subpattern> } [ "`...`" ] "`)`"
> | | | "`[`" { <pattern> }+ "`]`"
> | | | <pattern> "`|`" <pattern>
> | | | <pattern> { "`#`" <pattern> }+
> | | | <atom> | <int> | <float>
> | | | `unit` | `true` | `false`
> | | | <possibly escaped variable>
> | | | "`_`"
> | | | <pattern> "`=`" <pattern>
> | | | "`(`" <pattern> "`)`"

> <subpattern> | ::= | [ <feature> "`:`" ] <pattern>

Following the pattern an additional side condition can be given. It is only evaluated if the pattern matched, in the environment extended by the bindings introduced by the pattern. The variables introduced in the optional <declaration part> are also visible in the clause's body.

> <case statement clause> | ::= | <pattern> [ `andthen` [ <declaration part> `in` ] <expression> ]
> |  | `then` <in statement>

> <case expression clause> | ::= | <pattern> [ `andthen` [ <declaration part> `in` ] <expression> ]
> |  | `then` <in expression>

Else Clauses

If the `else` part to an `if` statement is omitted, it is taken to be `else skip`. The `else` part to an `if` expression is mandatory.

If the `else` part to a `case` statement or expression is omitted and no pattern matches, an error exception is raised.

> <else statement> | ::= | `elseif` <expression> `then` <in statement>
> |  | [ <else statement> ]
> | | | `elsecase` <expression> `of` <case statement clause>
> |  | { "`[]`" <case statement clause> }
> |  | [ <else statement> ]
> | | | `else` <in statement>

> <else expression> | ::= | `elseif` <expression> `then` <in expression>
> |  | <else expression>
> | | | `elsecase` <expression> `of` <case expression clause>
> |  | { "`[]`" <case expression clause> }
> |  | [ <else expression> ]
> | | | `else` <in expression>

## 3.2 Constraint Extensions and Combinators

Statements

> <statement> | += | <fd compare>
> | | | <fd in>
> | | | `fail`
> | | | `not` <in statement> `end`
> | | | `cond` <cond statement clause>
> |  | { "`[]`" <cond statement clause> }
> |  | [ `else` <in statement> ]
> |  | `end`
> | | | `or` <dis statement clause> { "`[]`" <dis statement clause> }+ `end`
> | | | `dis` <dis statement clause> { "`[]`" <dis statement clause> }+ `end`
> | | | `choice` <in statement> { "`[]`" <in statement> } `end`

> <cond statement clause> | ::= | [ <declaration part> `in` ] <statement> `then` <in statement>

> <dis statement clause> | ::= | [ <declaration part> `in` ] <statement> [ `then` <in statement> ]

Expressions

> <expression> | += | <fd compare>
> | | | <fd in>
> | | | `fail`
> | | | `cond` <cond expression clause>
> |  | { "`[]`" <cond expression clause> }
> |  | [ `else` <in expression> ]
> |  | `end`
> | | | `or` <cond expression clause> { "`[]`" <cond expression clause> }+ `end`
> | | | `dis` <cond expression clause> { "`[]`" <cond expression clause> }+ `end`
> | | | `choice` <in expression> { "`[]`" <in expression> } `end`

> <cond expression clause> | ::= | [ <declaration part> `in` ] <statement> `then` <in expression>

> <fd compare> | ::= | <expression> ( "`=:`" | "`\=:`" | "`<:`" | "`=<:`" | "`>:`" | "`>=:`" ) <expression>

> <fd in> | ::= | <expression> ( "`::`" | "`:::`" ) <expression>

## 3.3 Class Extensions

Class Definitions

> <statement> | += | `class` <expression>
> |  | { <class descriptor> }
> |  | { <method> }
> |  | `end`

> <expression> | += | `class` [ "`$`" ]
> |  | { <class descriptor> }
> |  | { <method> }
> |  | `end`

> <class descriptor> | ::= | `from` { <expression> }+
> | | | `prop` { <expression> }+
> | | | `attr` { <attr or feat> }+
> | | | `feat` { <attr or feat> }+

Non-escaped variables are implicitly introduced with class scope, bound to new names. This allows to model private components.

> <attr or feat> | ::= | [ "`!`" ] <variable> | <atom> | <int>
> | | | `unit` | `true` | `false`

Methods

The first-class message used to invoke a method can be referenced by appending `=` <variable> to the method head. This message does not contain defaulted arguments (see below) if they have not been explicitly given.

> <method> | ::= | `meth` <method head> [ "`=`" <variable> ]
> |  | <in phrase>
> |  | `end`

If dots are given, any additional features are allowed in the first-class message; else, extraneous features cause an error exception to be raised.

> <method head> | ::= | [ "`!`" ] <variable> | <atom>
> | | | `unit` | `true` | `false`
> | | | <method head label> "`(`" { <method formal> } [ "`...`" ] "`)`"

> <method head label> | ::= | [ "`!`" ] <variable label> | <atom label>
> | | | <unit label> | <true label> | <false label>

A default `<=` after a formal argument allows for the corresponding actual argument to be omitted from a first-class method. In this case, the default expression will be evaluated (inside the method) and the formal argument variable bound to the result.

> <method formal> | ::= | [ <feature> "`:`" ] ( <variable> | "`_`" | "`$`" )
> |  | [ "`<=`" <expression> ]

Operations

To the following operators, `self` is an implicit operand. Their use is syntactically restricted to the body of method definitions.

> <statement> | += | `lock` <in statement> `end`
> | | | <expression> "`:=`" <expression>
> | | | <expression> "`<-`" <expression>
> | | | <expression> "`,`" <expression>

The assignment operators "`:=`", "`<-`", when used in an expression position, perform an atomic exchange, the result of the operation being the previous value of the attribute assigned to.

> <expression> | += | `lock` <in expression> `end`
> | | | "`@`"<expression>
> | | | <expression> "`:=`" <expression>
> | | | <expression> "`<-`" <expression>
> | | | <expression> "`,`" <expression>
> | | | `self`

## 3.4 Functor Extensions

A functor definition creates a chunk with (at least) features `'import'` and `'export'` describing its interface and a feature `apply` containing a procedure mapping an import record to an export module.

> <statement> | += | `functor` <expression> { <functor descriptor> } `end`

> <expression> | += | `functor` [ "`$`" ] { <functor descriptor> } `end`

Import Specification

The import specification names values (usually modules) to be made available to the body. They represent formal arguments to the body abstraction. The additional `at` clause allows to specify where the actual argument is to come from. This must be an atom (interpreted as a relative URL) so that a functor creating the referenced module may be located at compile time.

> <functor descriptor> | ::= | `import` { <import clause> }+

> <import clause> | ::= | <variable> [ `at` <atom> ]
> | | | <variable label> <import features> [ `at` <atom> ]

If the expected structure of an imported value is partially specified, occurrences of the module name are restricted to a single syntactic context: the first operand in applications of the dot operator, where the second operand is one of the features mentioned in the import specification.

> <import features> | ::= | "`(`" { <module feature> <import alias> }+ "`)`"

> <module feature> | ::= | <atom> | <int>

An import alias introduces a variable bound to one of the imported module's subtrees.

> <import alias> | ::= | [ "`:`" <variable> ]

Functor Body

The body of the functor is a statement (usually a sequence of definitions that compute the exported values). This statement is a pattern position. Note the difference between this abbreviated declaration and the <in statement> rule: The <statement> following the `in` keyword is optional, not the <declaration part> preceding it.

> <functor descriptor> | += | `define` <declaration part> [ `in` <statement> ]

Export Specification

The export specification specifies the structure the modules created by applications of this functor will have.

> <functor descriptor> | += | `export` { [ <module feature> "`:`" ] <variable> }+

The value of the variables mentioned in the export declaration are made available under the given features. If a feature is omitted, then it is computed from the corresponding variable's print name by changing its initial capital letter into a lower-case letter (unless it's a backquote variable, in which case the print name is taken as-is).

All variables introduced in the import and the body are visible in the export declaration.

Computed Functors

A functor that contains one of the following additional functor descriptors is called a computed functor. The `require` and `prepare` clauses correspond to the `import` and `define` clauses respectively, only they are executed upon functor definition instead of functor application. The variables introduced by these clauses are visible in the `define` and `export` clauses.

> <functor descriptor> | += | `require` { <import clause> }+
> | | | `prepare` <declaration part> [ `in` <statement> ]

## 3.5 Operator Associativity and Precedence

The grammar given above is ambiguous. Some ambiguities do not affect the semantics (such as associativity of <statement>s and <declaration part>s). Those that do are resolved according to the following table stating the associativity of operators in increasing order of precedence:

Operators | Associativity
--- | ---
`X=Y` | right
`X<-Y` `X:=Y` `X.Y:=Z` | right
`X orelse Y` | right
`X andthen Y` | right
`X==Y` `X\=Y` `X<Y` `X=<Y` `X>Y` `X>=Y`
`X=:Y` `X\=:Y` `X<:Y` `X=<:Y` `X>:Y` `X>=:Y` | none
`X::Y` `X:::Y` | none
`X|Y` | right
`X#Y` | mixfix
`X+Y` `X-Y` | left
`X*Y` `X/Y` `X div Y` `X mod Y` | left
`X,Y` | right
`~X` | prefix
`X.Y` `X^Y` | left
`@X` `!!X` | prefix

``Having higher precedence'' means ``binding tighter''; e. g., the expression `c#X.g = Y` is parsed as `(c#(X.g)) = Y`.

Attempts to exploit associativity of non-associative operators (without using parentheses to make the intention clear), as in `X < Y < Z`, are considered erroneous.