ECMAScript 4 Netscape Proposal Formal Description Semantic Notation

Friday, June 13, 2003

The semantics of ECMAScript 4 are written in Algol-like pseudocode. The following sections define the notation used to write the semantics’ concepts, expressions, procedures, and actions.

Operators

The table below summarizes operators used in expressions in this document. The operators are listed in groups in order from the highest precedence (tightest-binding) to the lowest precedence (loosest-binding). Other than the relational operators, operators in the same group have the same precedence and associate left-to-right, so, for example, 7–3+2–1 means ((7–3)+2)–1 instead of 7–(3+(2–1)) or (7–(3+2))–1. As is traditional in mathematics, the relational operators cascade, so

a = b  c < d

means

a = b and b  c and c < d

Parentheses are used to override precedences or clarify expressions.

Expressions used in describing algorithms may perform side effects. Except for and, or, and ?:, the operators compute all of their operands left-to-right, and if computation of any operand throws an exception e, then the operator immediately propagates e without computing any following operands.

Semantic Domains

Semantic domains describe the possible values that a variable might take on in an algorithm. The algorithms are constructed in a way that ensures that these constraints are always met, regardless of any valid or invalid programmer or user input or actions.

A semantic domain can be intuitively thought of as a set of possible values, and, in fact, any set of values explicitly described in this document is also a semantic domain. Nevertheless, semantic domains have a more precise mathematical definition in domain theory (see for example [Schmidt86]) that allows one to define semantic domains recursively without encountering paradoxes such as trying to define a set A whose members include all functions mapping values from A to Integer. The problem with an ordinary definition of such a set A is that the cardinality of the set of all functions mapping A to Integer is always strictly greater than the cardinality of A, leading to a contradiction. Domain theory uses a least fixed point construction to allow A to be defined as a semantic domain without encountering problems.

Semantic domains have names in Capitalized Red Small Caps. Such a name is to be considered distinct from a tag or regular variable with the same name, so Undefined, undefined, and undefined are three different and independent entities.

A variable v is constrained using the notation

v: T

where T is a semantic domain. This constraint indicates that the value of v will always be a member of the semantic domain T. These declarations are informative (they may be dropped without affecting the semantics’ correctness) but useful in understanding the semantics. For example, when the semantics state that x: Integer then one does not have to worry about what happens when x has the value true or +_f64.

The constraints can be proven statically. The ECMAScript semantics have been machine-checked to ensure that every constraint holds.

Tags

Tags are computational tokens with no internal structure. Tags are written using a dark red font. Two tags are equal if and only if they have the same name.

Each tag that does not also name a tuple or a record is defined using the notation:

In the HTML version of the semantics, each use of a tag’s name is linked back to its definition.

Booleans

The tags true and false represent booleans. Boolean is the two-element semantic domain {true, false}.

Let a and b be booleans and x and y any values. In addition to = and , the following operations can be done on them:

Note that the and, or, and ?: operators short-circuit. These are the only operators that do not always compute all of their operands.

Sets

A set is an unordered, possibly infinite collection of elements. Each element may occur at most once in a set. There must be an equivalence relation = defined on all pairs of the set’s elements. Elements of a set may themselves be sets.

A set is denoted by enclosing a comma-separated list of values inside braces:

{element₁, element₂, ... , element_n}

The empty set is written as {}. Any duplicate elements are included only once in the set.

For example, the set {3, 0, 10, 11, 12, 13, –5} contains seven integers.

Sets of either integers or characters can be abbreviated using the ... range operator, which generates inclusive ranges of integers or character code points. For example, the above set can also be written as {0, –5, 3 ... 3, 10 ... 13}.

If the beginning of the range is equal to the end of the range, then the range consists of only one element: {7 ... 7} is the same as {7}. If the end of the range is one less than the beginning, then the range contains no elements: {7 ... 6} is the same as {}. The end of the range is never more than one less than the beginning.

A set can also be written using the set comprehension notation

{f(x) | x  A}

which denotes the set of the results of computing expression f on all elements x of set A. A predicate can be added:

{f(x) | x  A such that predicate(x)}

denotes the set of the results of computing expression f on all elements x of set A that satisfy the predicate expression. There can also be more than one free variable x and set A, in which case all combinations of free variables’ values are considered. For example,

{x | x  Integer such that x² < 10} = {–3, –2, –1, 0, 1, 2, 3};
{x² | x  {–5, –1, 1, 2, 4}} = {1, 4, 16, 25};
{x10 + y | x  {1, 2, 4}, y  {3, 5}} = {13, 15, 23, 25, 43, 45}.

The same notation is used for operations on sets and on semantic domains. Let A and B be sets (or semantic domains) and x and y be values. The following operations can be done on them:

If T is a semantic domain, then T{} is the semantic domain of all sets whose elements are members of T. For example, if T = {1,2,3}, then T{} = {{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}. The empty set {} is a member of T{} for any semantic domain T.

In addition to the above, the some and every quantifiers can be used on sets (see also lists). The quantifier

some x  A satisfies predicate(x)

returns true if there exists at least one element x in set A such that predicate(x) computes to true. If there is no such element x, then the some quantifier’s result is false. If the some quantifier returns true, then variable x is left bound to any element of A for which predicate(x) computes to true; if there is more than one such element x, then one of them is chosen arbitrarily. For example,

some x  {3, 16, 19, 26} satisfies x mod 10 = 6

evaluates to true and leaves x set to either 16 or 26. Other examples include:

(some x  {3, 16, 19, 26} satisfies x mod 10 = 7) = false;
(some x  {} satisfies x mod 10 = 7) = false;
(some x  {“Hello”} satisfies true) = true and leaves x set to the string “Hello”;
(some x  {} satisfies true) = false.

The quantifier

every x  A satisfies predicate(x)

returns true if there exists no element x in set A such that predicate(x) computes to false. If there is at least one such element x, then the every quantifier’s result is false. As a degenerate case, the every quantifier is always true if the set A is empty. For example,

(every x  {3, 16, 19, 26} satisfies x mod 10 = 6) = false;
(every x  {6, 26, 96, 106} satisfies x mod 10 = 6) = true;
(every x  {} satisfies x mod 10 = 6) = true.

Real Numbers

Numbers written in plain font are exact mathematical real numbers. Numbers can be written with or without a decimal point. Integers preceded with “0x” are hexadecimal (base 16). 4294967296, 4294967296.000, 0x100000000, and 2³² are all the same number. 0.1 is the exact value 1/10.

Integer is the semantic domain of all integers {... –3, –2, –1, 0, 1, 2, 3 ...}. 3.0, 3, 0xFF, and –10¹⁰⁰ are all integers.

Rational is the semantic domain of all rational numbers. Every integer is also a rational number: Integer  Rational. 3, 1/3, 7.5, –12/7, and 2^–5 are examples of rational numbers.

Real is the semantic domain of all real numbers. Every rational number is also a real number: Rational  Real. is an example of a real number slightly larger than 3.14.

Let x and y be real numbers. The following operations can be done on them and always produce exact results:

Real numbers can be compared using =, , <, , >, and . The result is either true or false.

Bitwise Integer Operators

The four procedures below perform bitwise operations on integers. The integers are treated as though they were written in infinite-precision two’s complement binary notation, with each 1 bit representing true and 0 bit representing false.

More precisely, any integer x can be represented as an infinite sequence of bits a_i where the index i ranges over the nonnegative integers and every a_i  {0, 1}. The sequence is traditionally written in reverse order:

..., a₄, a₃, a₂, a₁, a₀

The unique sequence corresponding to an integer x is generated by the formula

a_i = x / 2ⁱ mod 2

If x is zero or positive, then its sequence will have infinitely many consecutive leading 0’s, while a negative integer x will generate a sequence with infinitely many consecutive leading 1’s. For example, 6 generates the sequence ...0...0000110, while –6 generates ...1...1111010.

The logical and, or, and xor operations below operate on corresponding elements of the sequences a_i and b_i generated by the two parameters x and y. The result is another infinite sequence of bits c_i. The result of the operation is the unique integer z that generates the sequence c_i. For example, anding corresponding elements of the sequences generated by 6 and –6 yields the sequence ...0...0000010, which is the sequence generated by the integer 2. Thus, bitwiseAnd(6, –6) = 2.

Characters

Characters enclosed in single quotes ‘ and ’ represent Unicode characters with code points ranging from 0000 to 10FFFF hexadecimal. Even though Unicode does not define characters for some of these code points, in this specification any of these 1114112 code points is considered to be a valid character. Examples of characters include ‘A’, ‘b’, ‘«LF»’, ‘«uFFFF»’, ‘«U00010000»’ and , ‘«U0010FFFF»’ (see also the notation for non-ASCII characters).

Unicode has the notion of code points, which are numerical indices of characters in the Unicode character table, as well as code units, which are numerical values for storing characters in a particular representation. ECMAScript is designed to make it appear that strings are represented in the UTF-16 representation, which means that a code unit is a 16-bit value (an implementation may store strings in other formats such as UTF-8, but it must make it appear for indexing and character extraction purposes as if strings were sequences of 16-bit code units). For convenience this specification does not distinguish between code units and code points in the range from 0000 to FFFF hexadecimal.

Char16 is the semantic domain of the 65536 Unicode characters in the set {‘«u0000»’ ... ‘«uFFFF»’}. These characters form Unicode’s Basic Multilingual Plane. These characters have code points between 0000 and FFFF hexadecimal. Code units are also represented by values in the Char16 semantic domain.

SupplementaryChar is the semantic domain of the 1048576 Unicode characters in the set {‘«U00010000»’ ... ‘«U0010FFFF»’}. These are Unicode’s supplementary characters with code points between 10000 and 10FFFF hexadecimal. Since these characters are not members of the Char16 domain, they cannot be stored directly in strings of Char16 code units. Instead, whereever necessary the semantic algorithms convert supplementary characters into pairs of surrogate code units before storing them into strings. The first surrogate code unit h is in the set {‘«uD800»’ ... ‘«uDBFF»’} and the second surrogate code unit l is in the set {‘«uDC00»’ ... ‘«uDFFF»’}; together they encode the supplementary character with the code point value 0x10000 + (char16ToInteger(h) – 0xD800)0x400 + char16ToInteger(l) – 0xDC00.

Char21 is the semantic domain of all 1114112 Unicode characters {‘«u0000»’ ... ‘«U0010FFFF»’}.

Characters can be compared using =, , <, , >, and . These operators compare code point values, so ‘A’ = ‘A’, ‘A’ < ‘B’, ‘A’ < ‘a’, and ‘«uFFFF»’ < ‘«U00010000»’ are all true.

Character Conversions

The following procedures convert between characters and integers:

The procedure digitValue is defined as follows:

Lists

A finite ordered list of zero or more elements is written by listing the elements inside bold brackets:

[element₀, element₁, ... , element_n–1]

For example, the following list contains four strings:

[“parsley”, “sage”, “rosemary”, “thyme”]

The empty list is written as [].

Unlike a set, the elements of a list are indexed by integers starting from 0. A list can contain duplicate elements.

A list can also be written using the list comprehension notation

[f(x) | x  u]

which denotes the list [f(u[0]), f(u[1]), ... , f(u[|u|–1])] whose elements consist of the results of applying expression f to each corresponding element of list u. x is the name of the parameter in expression f. A predicate can be added:

[f(x) | x  u such that predicate(x)]

denotes the list of the results of computing expression f on all elements x of list u that satisfy the predicate expression. The results are listed in the same order as the elements x of list u. For example,

[x² | x  [–1, 1, 2, 3, 4, 2, 5]] = [1, 1, 4, 9, 16, 4, 25]
[x+1 | x  [–1, 1, 2, 3, 4, 5, 3, 10] such that x mod 2 = 1] = [0, 2, 4, 6, 4]

Let u = [e₀, e₁, ... , e_n–1] and v = [f₀, f₁, ... , f_m–1] be lists, e be an element, i and j be integers, and x be a value. The operations below can be done on lists. The operations are meaningful only when their preconditions are met; the semantics never use the operations below without meeting their preconditions.

Lists are functional — there is no notation for modifying a list in place.

If T is a semantic domain, then T[] is the semantic domain of all lists whose elements are members of T. The empty list [] is a member of T[] for any semantic domain T.

In addition to the above, the some and every quantifiers can be used on lists just as on sets:

some x  u satisfies predicate(x)
every x  u satisfies predicate(x)

These quantifiers’ behavior on lists is analogous to that on sets, except that, if the some quantifier returns true then it leaves variable x set to the first element of list u that satisfies condition predicate(x). For example,

some x  [3, 36, 19, 26] satisfies x mod 10 = 6

evaluates to true and leaves x set to 36.

Strings

A list of Char16 code units is called a string. In addition to the normal list notation, for notational convenience a string can also be written as zero or more characters enclosed in double quotes (see also the notation for non-ASCII characters). Thus,

“Wonder«LF»”

is equivalent to:

[‘W’, ‘o’, ‘n’, ‘d’, ‘e’, ‘r’, ‘«LF»’]

The empty string is written as “”.

A string holds code units, not code points. Supplementary Unicode characters are represented as pairs of surrogate code units when stored in strings.

In addition to all of the other list operations, <, , >, and are defined on strings. A string x is less than string y when y is not the empty string and either x is the empty string, the first code unit of x is less than the first code unit of y, or the first code unit of x is equal to the first code unit of y and the rest of string x is less than the rest of string y.

Note that these relations compare code units, not code points, which can produce unexpected effects if a string contains supplementary characters expanded into a pairs of surrogates. For example, even though ‘«uFFFF»’ < ‘«U00010000»’, the supplementary character ‘«U00010000»’ is represented in a string as “«uD800»«uDC00»”, and, by the above rules, “«uFFFF»” > “«uD800»«uDC00»”.

String is the semantic domain of all strings. String = Char16[].

Tuples

A tuple is an immutable aggregate of values comprised of a name and zero or more labeled fields.

The pseudocode defines each tuple and describes its fields. A tuple definition has the form

and defines tuples with name Name to have n fields with semantic domains T₁ through T_n respectively. In the HTML version of the semantics, each use of a tuple’s Name is linked back to its definition.

After Name is defined, the notation

Namelabel₁: v₁, ... , label_n: v_n

represents a tuple with name Name and values v₁ through v_n for fields labeled label₁ through label_n respectively. Each value v_i is a member of the corresponding semantic domain T_i. When most of the fields are copied from an existing tuple a, this notation can be abbreviated as

Namelabel_i1: v_i1, ... , label_ik: v_ik, other fields from a

which represents a tuple with name Name and values v_i1 through v_ik for fields labeled label_i1 through label_ik respectively and the values of correspondingly labeled fields from a for all other fields.

If a is the tuple Namelabel₁: v₁, ... , label_n: v_n, then

a.label_i

returns the i^th field’s value v_i. Tuples are functional — there is no notation for modifying a tuple in place. In the HTML version of the semantics, each use of label_i is linked back to a’s type.

The equality operators = and may be used to compare tuples. Tuples are equal when they have the same name and their corresponding fields’ values are equal.

The notation

Name

represents the semantic domain of all tuples with name Name.

Records

A record is a mutable aggregate of values similar to a tuple but with different equality behavior.

A record is comprised of a name and an address. The address points to a mutable data structure comprised of zero or more labeled fields. The address acts as the record’s serial number — every record allocated by new (see below) gets a different address, including records created by identical expressions or even the same expression used twice.

The pseudocode defines each record and describes its fields. A record definition has the form

and defines records with name Name to have n fields with semantic domains T₁ through T_n respectively. In the HTML version of the semantics, each use of a record’s Name is linked back to its definition.

After Name is defined, the expression

new Namelabel₁: v₁, ... , label_n: v_n

creates a record with name Name and a new address . The fields labeled label₁ through label_n at address are initialized with values v₁ through v_n respectively. Each value v_i is a member of the corresponding semantic domain T_i. A label_k: v_k pair may be omitted from a new expression, which indicates that the initial value of field label_k does not matter because the semantics will always explicitly write a value into that field before reading it.

When most of the fields are copied from an existing record a, the new expression can be abbreviated as

new Namelabel_i1: v_i1, ... , label_ik: v_ik, other fields from a

which represents a record b with name Name and a new address . The fields labeled label_i1 through label_ik at address are initialized with values v_i1 through v_ik respectively; the other fields at address are initialized with the values of correspondingly labeled fields from a’s address.

If a is a record with name Name and address , then

a.label_i

returns the current value v of the i^th field at address . That field may be set to a new value w, which must be a member of the semantic domain T_i, using the assignment

a.label_i  w

after which a.label_i will evaluate to w. Any record with a different address is unaffected by the assignment. In the HTML version of the semantics, each use of label_i is linked back to a’s type.

The equality operators = and may be used to compare records. Records are equal if and only if they have the same address.

The notation

Name

represents the infinite semantic domain of all records that have name Name and all addresses.

ECMAScript Numeric Types

ECMAScript does not support exact real numbers as one of the programmer-visible data types. Instead, ECMAScript numbers have finite range and precision. The semantic domain of all programmer-visible numbers representable in ECMAScript is GeneralNumber, defined as the union of four basic numeric semantic domains Long, ULong, Float32, and Float64:

The four basic numeric semantic domains are all disjoint from each other and from the semantic domains Integer, Rational, and Real.

The semantic domain FiniteGeneralNumber is the subtype of all finite values in GeneralNumber:

Signed Long Integers

Programmer-visible signed 64-bit long integers are represented by the semantic domain Long. These are wrapped in a tuple to keep them disjoint from members of the semantic domains ULong, Float32, and Float64.

Shorthand Notation

In this specification, when i is an integer between –2⁶³ and 2⁶³ – 1, the notation i_long indicates the result of Longvalue: i, which is the integer i wrapped in a Long tuple.

Unsigned Long Integers

Programmer-visible unsigned 64-bit long integers are represented by the semantic domain ULong. These are wrapped in a tuple to keep them disjoint from members of the semantic domains Long, Float32, and Float64.

Shorthand Notation

In this specification, when i is an integer between 0 and 2⁶⁴ – 1, the notation i_ulong indicates the result of ULongvalue: i, which is the integer i wrapped in a ULong tuple.

Single-Precision Floating-Point Numbers

Float32 is the semantic domain of all representable single-precision floating-point IEEE 754 values, with all not-a-number values considered indistinguishable from each other. Float32 is the union of the following semantic domains:

The non-zero finite values are wrapped in a tuple to keep them disjoint from members of the semantic domains Long, ULong, and Float64. The remaining values are the tags +zero_f32 (positive zero), –zero_f32 (negative zero), +_f32 (positive infinity), –_f32 (negative infinity), and NaN_f32 (not a number).

There are 4261412864 (that is, 2³²–2²⁵) normalized values:

m is called the significand.

There are also 16777214 (that is, 2²⁴–2) denormalized non-zero values:

m is called the significand.

Members of the semantic domain NonzeroFiniteFloat32 with value greater than zero are called positive finite. The remaining members of NonzeroFiniteFloat32 are called negative finite.

Since floating-point numbers are either tags or tuples wrapping rational numbers, the notation = and may be used to compare them. Note that = is false for different tags, so +zero_f32  –zero_f32 but NaN_f32 = NaN_f32. The ECMAScript x == y and x === y operators have different behavior for Float32 values, defined by isEqual and isStrictlyEqual.

Shorthand Notation

In this specification, when x is a real number, the notation x_f32 indicates the result of realToFloat32(x), which is the “closest” Float32 value as defined below. Thus, 3.4 is a Real number, while 3.4_f32 is a Float32 value (whose exact value is actually 3.400000095367431640625). The positive finite Float32 values range from 10^–45_f32 to (3.4028235  10³⁸)_f32.

Conversion

The procedure realToFloat32 converts a real number x into the applicable element of Float32 as follows:

This procedure corresponds exactly to the behavior of the IEEE 754 “round to nearest” mode.

The procedure truncateFiniteFloat32 truncates a FiniteFloat32 value to an integer, rounding towards zero:

Arithmetic

The following table defines negation of Float32 values using IEEE 754 rules. Note that expr_f32 indicates the result of realToFloat32(expr).

Double-Precision Floating-Point Numbers

Float64 is the semantic domain of all representable double-precision floating-point IEEE 754 values, with all not-a-number values considered indistinguishable from each other. Float64 is the union of the following semantic domains:

The non-zero finite values are wrapped in a tuple to keep them disjoint from members of the semantic domains Long, ULong, and Float32. The remaining values are the tags +zero_f64 (positive zero), –zero_f64 (negative zero), +_f64 (positive infinity), –_f64 (negative infinity), and NaN_f64 (not a number).

There are 18428729675200069632 (that is, 2⁶⁴–2⁵⁴) normalized values:

m is called the significand.

There are also 9007199254740990 (that is, 2⁵³–2) denormalized non-zero values:

m is called the significand.

Members of the semantic domain NonzeroFiniteFloat64 with value greater than zero are called positive finite. The remaining members of NonzeroFiniteFloat64 are called negative finite.

Since floating-point numbers are either tags or tuples wrapping rational numbers, the notation = and may be used to compare them. Note that = is false for different tags, so +zero_f64  –zero_f64 but NaN_f64 = NaN_f64. The ECMAScript x == y and x === y operators have different behavior for Float64 values, defined by isEqual and isStrictlyEqual.

Shorthand Notation

In this specification, when x is a real number, the notation x_f64 indicates the result of realToFloat64(x), which is the “closest” Float64 value as defined below. Thus, 3.4 is a Real number, while 3.4_f64 is a Float64 value (whose exact value is actually 3.399999999999999911182158029987476766109466552734375). The positive finite Float64 values range from (5  10^–324)_f64 to (1.7976931348623157  10³⁰⁸)_f64.

Conversion

The procedure realToFloat64 converts a real number x into the applicable element of Float64 as follows:

This procedure corresponds exactly to the behavior of the IEEE 754 “round to nearest” mode.

The procedure float32ToFloat64 converts a Float32 number x into the corresponding Float64 number as defined by the following table:

The procedure truncateFiniteFloat64 truncates a FiniteFloat64 value to an integer, rounding towards zero:

Arithmetic

The following tables define procedures that perform common arithmetic on Float64 values using IEEE 754 rules. Note that expr_f64 indicates the result of realToFloat64(expr).

Note that float64Remainder(float64Negate(x), y) always produces the same result as float64Negate(float64Remainder(x, y)). Also, float64Remainder(x, float64Negate(y)) always produces the same result as float64Remainder(x, y).

Procedures

A procedure is a function that receives zero or more arguments, performs computations, and optionally returns a result. Procedures may perform side effects. In this document the word procedure is used to refer to internal algorithms; the word function is used to refer to the programmer-visible function ECMAScript construct.

A procedure is denoted as:

If the procedure does not return a value, the : T on the first line is omitted.

f is the procedure’s name, param₁ through param_n are the procedure’s parameters, T₁ through T_n are the parameters’ respective semantic domains, T is the semantic domain of the procedure’s result, and step₁ through step_m describe the procedure’s computation steps, which may produce side effects and/or return a result. If T is omitted, the procedure does not return a result. When the procedure is called with argument values v₁ through v_n, the procedure’s steps are performed and the result, if any, returned to the caller.

A procedure’s steps can refer to the parameters param₁ through param_n; each reference to a parameter param_i evaluates to the corresponding argument value v_i. Procedure parameters are statically scoped. Arguments are passed by value.

Operations

The only operation done on a procedure f is calling it using the f(arg₁, ..., arg_n) syntax. f is computed first, followed by the argument expressions arg₁ through arg_n, in left-to-right order. If the result of computing f or any of the argument expressions throws an exception e, then the call immediately propagates e without computing any following argument expressions. Otherwise, f is invoked using the provided arguments and the resulting value, if any, returned to the caller.

Procedures are never compared using =, , or any of the other comparison operators.

Semantic Domains of Procedures

The semantic domain of procedures that take n parameters in semantic domains T₁ through T_n respectively and produce a result in semantic domain T is written as T₁  T₂  ...  T_n  T. If n = 0, this semantic domain is written as ()  T. If the procedure does not produce a result, the semantic domain of procedures is written either as T₁  T₂  ...  T_n  () or as ()  ().

Computation Steps

Computation steps in procedures are described using a mixture of English and formal notation. The various kinds of formal steps are described in this section. Multiple steps are separated by semicolons and performed in order unless an earlier step exits via a return or propagates an exception.

Informal steps state invariants and provide comments.

A nothing step performs no operation.

A note step performs no operation. It provides an informative comment about the algorithm. If Comment is an expression, then the note step is an informative comment that asserts that the expression, if evaluated at this point, would be guaranteed to evaluate to true.

A computation step may consist of an expression. The expression is computed and its value, if any, ignored.

An assignment step is indicated using the assignment operator . This step computes the value of expression and assigns the result to the temporary variable or mutable global v. If this is the first time the temporary variable is referenced in a procedure, the variable’s semantic domain T is listed; any value stored in v is guaranteed to be a member of the semantic domain T.

This step declares v to be a temporary variable with semantic domain T without assigning anything to the variable. v will not be read unless some other step first assigns a value to it.

Inside an action, the assignment operator can also be used to define the result of another action Action[nonterminal_i] applied to the current expansion of nonterminal_i, which must appear on the current production’s left or right side. Such an assignment is done only when the value of Action[nonterminal_i] is not defined explicitly via an action. The value of Action[nonterminal_i] is set at most once and never modified afterwards. If the same nonterminal is expanded several times while parsing a source program, all such expansions are treated independently.

Temporary variables are local to the procedures that define them (including any nested procedures). Each time a procedure is called it gets a new set of temporary variables.

This form of assignment sets the value of field label of record a to the value of expression.

An if step computes expression₁, which will evaluate to either true or false. If it is true, the first list of steps is performed. Otherwise, expression₂ is computed and tested, and so on. If no expression evaluates to true, the list of steps following the else is performed. The else clause may be omitted, in which case no action is taken when no expression evaluates to true.

A case step computes expression, which will evaluate to a value v. If v  T₁, then the first list of steps is performed. Otherwise, if v  T₂, then the second list of steps is performed, and so on. If v is not a member of any T_i, the list of steps following the else is performed. The else clause may be omitted, in which case v will always be a member of some T_i.

A while step computes expression, which will evaluate to either true or false. If it is false, no action is taken. If it is true, the list of steps is performed and then expression is computed and tested again. This repeats until expression returns true (or until the procedure exits via a return or an exception is propagated out).

A for each step computes expression, which will evaluate to either a set or a list A. The list of steps is performed repeatedly with variable x bound to each element of A. If A is a list, x is bound to each of its elements in order; if A is a set, the order in which x is bound to its elements is arbitrary. The repetition ends after x has been bound to all elements of A (or when either the procedure exits via a return or an exception is propagated out).

A return step computes expression to obtain a value v and returns from the enclosing procedure with the result v. No further steps in the enclosing procedure are performed. The expression may be omitted, in which case the enclosing procedure returns with no result.

Exceptions

A throw step computes expression to obtain a value v and begins propagating exception v outwards, exiting partially performed steps and procedure calls until the exception is caught by a catch step. Unless the enclosing procedure catches this exception, no further steps in the enclosing procedure are performed.

A try step performs the first list of steps. If they complete normally (or if they return), then the try step is done. If any of the steps propagates out an exception e, then if e  T, then exception e stops propagating, variable v is bound to the value e, and the second list of steps is performed. If e  T, then exception e keeps propagating out.

A try step does not intercept exceptions that may be propagated out of its second list of steps.

Nested Procedures

An inner proc may be nested as a step inside an outer proc. In this case the inner procedure is a closure and can access the parameters and temporaries of the outer procedure.

Semantic Actions

Semantic actions tie the grammar and the semantics together. A semantic action ascribes semantic meaning to a grammar production.

To illustrate the use of semantic actions, we shall look at an example, followed by a description of the notation for specifying semantic actions.

Example

Consider the following grammar, with the start nonterminal Numeral:

This grammar defines the syntax of an acceptable input: “37”, “33#4” and “30#2” are acceptable syntactically, while “1a” is not. However, the grammar does not indicate what these various inputs mean. That is the job of the semantics, which are defined in terms of actions on the parse tree of grammar rule expansions. Consider the following sample set of actions defined on this grammar, with a starting Numeral action called (in this example) Value:

Action names are written in violet cursive type. The definition

states that the action Value can be applied to any expansion of the nonterminal Numeral, and the result is an Integer. This action either maps an input to an integer or throws an exception. The code above throws the exception syntaxError when presented with the input “30#2”.

There are two definitions of the Value action on Numeral, one for each grammar production that expands Numeral:

Each definition of an action is allowed to perform actions on the terminals and nonterminals on the right side of the expansion. For example, Value applied to the first Numeral production (the one that expands Numeral into Digits) simply applies the DecimalValue action to the expansion of the nonterminal Digits and returns the result. On the other hand, Value applied to the second Numeral production (the one that expands Numeral into Digits # Digits) performs a computation using the results of the DecimalValue and BaseValue applied to the two expansions of the Digits nonterminals. In this case there are two identical nonterminals Digits on the right side of the expansion, so subscripts are used to indicate on which the actions DecimalValue and BaseValue are performed.

The definition

states that the action BaseValue can be applied to any expansion of the nonterminal Digits, and the result is a procedure that takes one Integer argument base and returns an Integer. The procedure’s body is comprised of independent cases for each production that expands Digits. When the procedure is called, the case corresponding to the expansion of the nonterminal Digits is evaluated.

The Value action on Digit illustrates the direct use of a nonterminal in a semantic expression: digitValue(Digit). Using the nonterminal Digit in this way refers to the character into which the Digit grammar rule expands.

We can fully evaluate the semantics on our sample inputs to get the following results:

Abbreviated Actions

In some cases the all actions named A for a nonterminal N’s rule are repetitive, merely calling A on the nonterminals on the right side of the expansions of N in the grammar. In these cases the semantics of action A are abbreviated, as illustrated by the example below.

Given the grammar rule

the notation

is an abbreviation for the following:

Note that:

• The expanded calls to Validate get the same arguments cxt and env passed in to the call to Validate on Expression.
• When an expansion of Expression has more than one nonterminal on its right side, Validate is called on all of the nonterminals in left-to-right order.
• When an expansion of Expression has no nonterminals on its right side, Validate does nothing.

The propagation notation is also used in when the actions return a value. In this case each expansion must have exactly one nonterminal. For example, given the grammar rule

the notation

is an abbreviation for the following:

Semantic Definition Summary

The following notation is used to define top-level semantic entities:

This notation defines Name to be a shorthand for the semantic domain expression. In the HTML version of the semantics, each use of Name is linked back to this definition.

This notation defines name to be a constant value given by the result of computing expression. The value is guaranteed to be a member of the semantic domain T. In the HTML version of the semantics, each use of name is linked back to this definition.

This notation defines name to be a mutable global value. Its initial value is the result of computing expression, but it may be subsequently altered using an assignment. The value is guaranteed to be a member of the semantic domain T. In the HTML version of the semantics, each use of name is linked back to this definition.

This notation defines f to be a procedure.

This notation defines a tag.

This notation defines a tuple.

This notation defines a record.

This notation states that action Action can be performed on nonterminal nonterminal and returns a value that is a member of the semantic domain T. The action’s value is either defined using the notation Action[nonterminal  expansion] = expression below or set as a side effect of computing another action via an action assignment.

This notation specifies the value that action Action on nonterminal nonterminal computes in the case where nonterminal nonterminal expands to the given expansion. expansion can contain zero or more terminals and nonterminals (as well as other notations allowed on the right side of a grammar production). Furthermore, the terminals and nonterminals of expansion can be subscripted to allow them to be unambiguously referenced by action references or nonterminal references inside expression.

This notation combines the above two — it specifies the semantic domain of the action as well as its value.

This notation is used when the computation of the action is too complex for an expression. Here the steps to compute the action are listed as step₁ through step_m. A return step produces the value of the action.

This notation is used only when Action returns a procedure when applied to nonterminal nonterminal with a single expansion expansion. Here the steps of the procedure are listed as step₁ through step_m.

This notation is used only when Action returns a procedure when applied to nonterminal nonterminal with several expansions expansion₁ through expansion_n. The procedure is comprised of a series of cases, one for each expansion. Only the steps corresponding to the expansion found by the grammar parser used are evaluated.

This notation is an abbreviation stating that calling Action on nonterminal causes Action to be called with the same arguments on every nonterminal on the right side of the appropriate expansion of nonterminal.

Waldemar Horwat Last modified Friday, June 13, 2003