The purpose of this section is to describe a concise notation in which the syntax of computer notations (languages) can be unambiguously defined or described.
Acomputer language is a collection of sequences of symbols that are formed according to certain well-defined rules. Such rules constitute the grammar of the notation, or language. In a sense, a computer program can be thought of as corresponding to a sentence in some spoken language, and the component parts of a program are roughly analogous to such language constructs as subject, predicate, and object or complement.
Spoken languages, though they express ideas with a finite number of sounds (phonemes) are capable of expressing an infinite number of such ideas. Likewise, a programming notation may have a finite number of symbols and rules for manipulating these, but be capable of expressing an infinite number of programs.
There are four rules which allow on to create all the syntax definitions for any programming language. They are similar to the basic programming abstractions noted in chapter one of this text and elaborated on in Modula-2 for the writing of programs.
If a language construction C uses two elements P and Q in succession, one expresses this as:
C = PQ
If a language construction C uses one or the other of two elements P or Q, one writes this rule as:
C = P | Q
If a language construction C may be either P or nothing at all (empty), then one writes the syntax rule as:
C = [ P ]
If a construction C consists of any number (including zero) of repetitions of P then one writes:
C = { P }
The notation described by the four rules of succession, alternatives, option, and repetition with the notation above is called Extended Backus-Naur Formalism or EBNF for short.
Before looking at the complete definition of Modula-2 in this notation, consider a few particular cases and see how EBNF can save space and gain some precision.
One of the earliest definitions was that of an identifier. It went as follows:
An identifier is a sequence of letters and numbers that starts with a letter.
The same rule can be written in EBNF as:
identifier = letter { letter | digit }
As indicated in the rules above, the braces signify a repetition of any number of the elements inside them, and this can be either a letter or a digit.
A further example of the use of the vertical bar to indicate alternatives is given in the following series of definitions:
octalDigit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" digit = octalDigit | "8" | "9" hexDigit = digit | "A" | "B" | "C" | "D" | "E" | "F"
Here, each definition is built up from the previous one in order to avoid needless repetition. Notice the use of quotes to surround elements which, if they are used, must appear exactly as given. That last line for instance tells us the rather familiar fact that a hexadecimal digit must be either a digit or a letter from "A" to "F".
The option notation is can be illustrated in the description of the import construction, where the FROM moduleName is an optional form. One could express this in EBNF as:
import = [FROM ident] IMPORT identList ";"
Notice how the EBNF shows clearly that the semicolon is required at the end of this construction.
The concrete syntax in this section is taken from ISO/IEC IS 10514, the international standard for Modula-2.
compilation module =
program module | definition module | implementation module ;
program module =
"MODULE", module identifier, [protection], semicolon,
import lists, module block, module identifier, period ;
module identifier =
identifier ;
protection =
left bracket, protection expression, right bracket ;
protection expression =
constant expression ;
definition module =
"DEFINITION", "MODULE", module identifier, semicolon,
import lists, definitions, "END", module identifier, period ;
implementation module =
"IMPLEMENTATION", "MODULE", module identifier, [protection],
semicolon, import lists, module block, module identifier, period ;
import lists =
{import list} ;
import list =
simple import | unqualified import ;
simple import =
"IMPORT", identifier list, semicolon ;
unqualified import =
"FROM", module identifier, "IMPORT", identifier list, semicolon ;
export list =
unqualified export | qualified export ;
unqualified export =
"EXPORT", identifier list, semicolon ;
qualified export =
"EXPORT", "QUALIFIED", identifier list, semicolon ;
qualified identifier =
{module identifier, period}, identifier ;
definitions =
{definition} ;
definition =
"CONST", {constant declaration, semicolon} |
"TYPE", {type definition, semicolon} |
"VAR", {variable declaration, semicolon} |
procedure heading, semicolon ;
procedure heading =
proper procedure heading | function procedure heading ;
type definition =
type declaration | opaque type definition ;
opaque type definition =
identifier ;
proper procedure heading =
"PROCEDURE", procedure identifier, [formal parameters] ;
formal parameters =
left parenthesis, [formal parameter list], right parenthesis ;
formal parameter list =
formal parameter, {semicolon, formal parameter} ;
function procedure heading =
"PROCEDURE", procedure identifier, formal parameters,
colon, function result type ;
function result type =
type identifier ;
formal parameter =
value parameter specification | variable parameter specification ;
value parameter specification =
identifier list, colon, formal type ;
variable parameter specification =
"VAR", identifier list, colon, formal type ;
declarations =
{declaration} ;
declaration =
"CONST", {constant declaration, semicolon} |
"TYPE", {type declaration, semicolon} |
"VAR", {variable declaration, semicolon} |
procedure declaration, semicolon |
local module declaration, semicolon ;
constant declaration =
identifier, equals, constant expression ;
type declaration =
identifier, equals, type denoter ;
variable declaration =
variable identifier list, colon, type denoter ;
variable identifier list =
identifier, [ machine address], {comma, identifier,
[machine address] } ;
machine address =
left bracket, value of address type, right bracket ;
value of address type =
constant expression ;
procedure declaration =
proper procedure declaration | function procedure declaration ;
proper procedure declaration =
proper procedure heading, semicolon, (proper procedure block,
procedure identifier | "FORWARD") ;
procedure identifier =
identifier ;
function procedure declaration =
function procedure heading, semicolon, (function procedure block,
procedure identifier | "FORWARD") ;
local module declaration =
"MODULE", module identifier, [protection], semicolon,
import lists, [export list], module block, module identifier ;
type denoter =
type identifier |new type ;
ordinal type denoter =
ordinal type identifier | new ordinal type ;
type identifier =
qualified identifier ;
ordinal type identifier =
type identifier ;
new type =
new ordinal type | set type | packedset type | pointer type |
procedure type | array type | record type ;
new ordinal type =
enumeration type | subrange type ;
enumeration type =
left parenthesis, identifier list, right parenthesis ;
identifier list =
identifier, {comma, identifier} ;
subrange type =
[range type], left bracket, constant expression, ellipsis,
constant expression, right bracket ;
range type =
ordinal type identifier ;
set type =
"SET", "OF", base type ;
base type =
ordinal type denoter ;
packedset type =
"PACKEDSET", "OF", base type ;
pointer type =
"POINTER", "TO", bound type ;
bound type =
type denoter ;
procedure type =
proper procedure type | function procedure type ;
proper procedure type =
"PROCEDURE", [left parenthesis, [formal parameter type list],
right parenthesis] ;
function procedure type =
"PROCEDURE", left parenthesis, [formal parameter type list],
right parenthesis, colon, function result type ;
formal parameter type list =
formal parameter type, {comma, formal parameter type} ;
formal parameter type =
variable formal type | value formal type ;
variable formal type =
"VAR", formal type ;
value formal type =
formal type ;
formal type =
type identifier | open array formal type ;
open array formal type =
"ARRAY", "OF", {"ARRAY", "OF"}, type identifier ;
array type =
"ARRAY", index type, {comma, index type}, "OF", component type ;
index type =
ordinal type denoter ;
component type =
type denoter ;
record type =
"RECORD", field list, "END" ;
field list =
fields, {semicolon, fields} ;
fields =
[fixed fields | variant fields] ;
fixed fields =
identifier list, colon, field type ;
field type =
type denoter ;
variant fields =
"CASE", [tag identifier], colon, tag type, "OF",
variant list, "END" ;
tag identifier =
identifier ;
tag type =
ordinal type identifier ;
variant list =
variant, {case separator, variant}, [variant else part] ;
variant else part =
"ELSE", field list ;
variant =
[variant label list, colon, field list] ;
variant label list =
variant label, {comma, variant label} ;
variant label =
constant expression, [ellipsis, constant expression] ;
proper procedure block =
declarations, [procedure body], "END" ;
procedure body =
"BEGIN", block body ;
function procedure block =
declarations, function body, "END" ;
function body =
"BEGIN", block body ;
module block =
declarations, [module body], "END" ;
module body =
initialization body, [finalization body], ;
initialization body =
"BEGIN", block body ;
finalization body =
"FINALLY", block body ;
block body =
normal part, ["EXCEPT", exceptional part] ;
normal part =
statement sequence ;
exceptional part =
statement sequence ;
statement =
empty statement | assignment statement | procedure call |
return statement |retry statement | with statement |
if statement | case statement |while statement |
repeat statement | loop statement |exit statement |for statement ;
statement sequence =
statement, {semicolon, statement} ;
empty statement =
;
assignment statement =
variable designator, assignment operator, expression ;
procedure call =
procedure designator, [actual parameters] ;
procedure designator =
value designator ;
return statement =
simple return statement | function return statement ;
simple return statement =
"RETURN" ;
function return statement =
"RETURN", expression ;
retry statement =
"RETRY" ;
with statement =
"WITH", record designator, "DO", statement sequence, "END" ;
record designator =
variable designator | value designator ;
if statement =
guarded statements, [if else part], "END" ;
guarded statements =
"IF", boolean expression, "THEN", statement sequence,
{"ELSIF", boolean expression, "THEN", statement sequence} ;
if else part =
"ELSE", statement sequence ;
boolean expression =
expression ;
case statement =
"CASE", case selector, "OF", case list, "END" ;
case selector =
ordinal expression ;
case list =
case alternative, {case separator, case alternative},
[case else part] ;
case else part =
"ELSE", statement sequence ;
case alternative =
[case label list, colon, statement sequence] ;
case label list =
case label, {comma, case label} ;
case label =
constant expression, [ellipsis, constant expression] ;
while statement =
"WHILE", boolean expression, "DO", statement sequence, "END" ;
repeat statement =
"REPEAT", statement sequence, "UNTIL", boolean expression ;
loop statement =
"LOOP", statement sequence, "END" ;
exit statement =
"EXIT" ;
for statement =
"FOR", control variable identifier, assignment operator,
initial value, "TO", final value, ["BY", step size], "DO",
statement sequence, "END" ;
control variable identifier =
identifier ;
initial value =
ordinal expression ;
final value =
ordinal expression ;
step size =
constant expression ;
variable designator =
entire designator | indexed designator |
selected designator | dereferenced designator ;
entire designator =
qualified identifier ;
indexed designator =
array variable designator, left bracket, index expression,
{comma, index expression}, right bracket ;
array variable designator =
variable designator ;
index expression =
ordinal expression ;
selected designator =
record variable designator, period, field identifier ;
record variable designator =
variable designator ;
field identifier =
identifier ;
dereferenced designator =
pointer variable designator, dereferencing operator ;
pointer variable designator =
variable designator ;
expression =
simple expression, [relational operator, simple expression] ;
simple expression =
[sign], term, {term operator, term} ;
term =
factor, {factor operator, factor} ;
factor =
left parenthesis, expression, right parenthesis |
logical negation operator, factor |
value designator | function call |
value constructor | constant literal ;
ordinal expression =
expression ;
relational operator =
equals operator | inequality operator | less than operator |
greater than operator | less than or equal operator |
subset operator | greater than or equal operator |
superset operator | set membership operator ;
term operator =
plus operator | set union operator | minus operator |
set difference operator | logical disjunction operator |
string catenate symbol ;
factor operator =
multiplication operator | set intersection operator |
division operator | symmetric set difference operator |
rem operator | div operator | mod operator |
logical conjunction operator ;
value designator =
entire value | indexed value | selected value | dereferenced value ;
entire value =
qualified identifier ;
indexed value =
array value, left bracket, index expression,
{comma, index expression}, right bracket ;
array value =
value designator ;
selected value =
record value, period, field identifier ;
record value =
value designator ;
dereferenced value =
pointer value, dereferencing operator ;
pointer value =
value designator ;
function call =
function designator, actual parameters ;
function designator =
value designator ;
value constructor =
array constructor | record constructor | set constructor ;
array constructor =
array type identifier, array constructed value ;
array type identifier =
type identifier ;
array constructed value =
left brace, repeated structure component,
{comma, repeated structure component}, right brace ;
repeated structure component =
structure component, ["BY", repetition factor] ;
repetition factor =
constant expression ;
structure component =
expression | array constructed value |
record constructed value | set constructed value ;
record constructor =
record type identifier, record constructed value ;
record type identifier =
type identifier ;
record constructed value =
left brace, [structure component, {comma, structure component}],
right brace ;
set constructor =
set type identifier, set constructed value ;
set type identifier =
type identifier ;
set constructed value =
left brace, [member, {comma, member}], right brace ;
member =
interval | singleton ;
interval =
ordinal expression, ellipsis, ordinal expression ;
singleton =
ordinal expression ;
constant literal =
whole number literal | real literal |
string literal | pointer literal ;
constant expression =
expression ;
actual parameters =
left parenthesis, [actual parameter list], right parenthesis ;
actual parameter list =
actual parameter, {comma, actual parameter} ;
actual parameter =
variable designator | expression | type parameter ;
type parameter =
type identifier ;