EBNF:

The Meta-Notation For Syntax Definition

The syntax of CAOPLE language is defined in EBNF, which is an extension to BNF, or Backus Naur Form.

Syntax Rules

In EBNF, the syntax definition of a language consists of a number of syntax rules. Each syntax rule is in the form of

A ::=Exp,

which defines a non-terminal symbol A by the syntax formula Exp.

A non-terminal symbol is represented in the form of a string of letters.

A syntax formula is an expression that constructed from terminal and non-terminal symbols combined by using meta-symbols.

Terminal Symbols

A terminal symbol represents a sequence of characters that may appear in the syntactically valid sentences of the language, i.e. the programs of the language that are syntactically correct.

In the definition of CAOPLE, a terminal symbol can be i one of the following two forms:

  • literals: in the form of "chars" , which means the characters between the double quotes are what to appear in valid sentences;

  • lexical tokens: in the form of ⟨TokenName⟩, which means any of the particular sequence of characters for the TokenName as defined in the Lexical Elements section are valid.

Non-Terminal Symbols

Each non-terminal symbol represents a syntax entity or grammar concept of the language. It must be defined by one and only one syntax rule. The syntax formula on the right hand side of the definition specifies how the syntax entity is formed from other syntax entities and terminal symbols.

Meta-Symbols

In a syntax rule, the non-terminal symbol to be defined occurs on the left-hand side of the meta-symbol ::=, which reads ‘is defined as’, while its definition is an EBNF formula on the right-hand side, which is a concatenation of terms formed from terminal and non-terminal symbols using the meta-symbols | for alternative, [ ] for option, and { } or { }+ for repetitions.

In addition to these traditional EBNF meta-symbols, we introduce two new ones: ∼ for negation, and = for naming.

A syntax expression in the form of X = Exp within in an EBNF formula means that the syntax entity Exp occurs is named as X, and the name X can be referred to in other syntax rule as a non-terminal symbol.


Note: The naming meta-notation fundamentally changes the BNF’s context-free nature to be context sensitive. In the definition of CAOPLE, we have used this facility to classify identifiers into variable names, type names, caste names, action names, and parameters, etc.

The meta-symbols of EBNF used in the the definition of CAOPLE are listed in Table 1.1 below.

Table 1.1. EBNF Meta-Symbols

Example

For example, the following are some syntax rules in the EBNF meta-notation.

In the above example, the first rule, on lines 1 and 2, defines a non-terminal symbol DefPackage. It is a syntax entity that consists of (a) an optional syntax entity Imports (which is also a non-terminal) followed by (b) a terminal symbol ⟨DEFINITION⟩, (c) a non-terminal symbol Identifier, which is named as PackageName, and then, (d) a terminal symbol "{" , (e) a non-terminal symbol Definitions and finishes with (f) a terminal symbol "}" .

The 3rd line defines the non-terminal Imports, which starts with a terminal symbol ⟨IMPORT⟩ followed by a non-empty sequence of PackageNames separated by a terminal symbol comma "," . PackageName is an identifier that occurred in a DefPackage.

The 4th line defines the non-terminal Definitions, which is a syntax entity that consists of a non-empty sequence of either a TypeDef or ConstDef.

The 5th line defines the non-terminal TypeDef, which stars with the terminal symbol ⟨TYPE⟩, followed by an identifier that is classified as TypeName, the terminal "=" and a type expression TypeExpr.

Finally, on line 6, an Identifier is defined as a non-empty string of letters and digits that starts with a letter, but it must not be a Keyword.