Software Design and Development
Home > Software Design and Development > Core > Software Development Cycle > Metalanguages
Metalanguages
Outcomes addressed:
H1.2 differentiates between various methods used to construct software solutions
H4.2 applies appropriate development methods to solve software problems
If metadata is data that describes data, it follows that metalanguages are languages that describe language. Metalanguages are used to represent the syntax of a programming language. In other words, they are used to describe the rules of programming languages.
The syntax of a programming language refers to the rules which govern the way that the elements of the language can be joined together to form valid statements.
A computer language needs to be defined precisely because unlike the language we speak, it must be unambiguous. This means statements in a language can only have one possible meaning.
As computer languages have become more complex, metalanguages have be devised to describe the syntax of programming languages. These syntax description methods are used by programmers
- to set out the syntax of a new language they are developing
- to help them when they are writing code, to see how the syntax of a language is written
The SDD syllabus lists three metalanguages you must be able to use. They are
- Backus-Naur form (BNF)
- Extended Backus-Naur form (EBNF)
- Syntax diagram (or Railroad diagram)
There are various industry standards for writing each metalanguage. The NSW Board of Studies in the Software and Course Specification document provides a summary of how you can represent these metalanguages.
Backus-Naur form (BNF)
Wikipedia provides some interesting history of BNF at http://en.wikipedia.org/wiki/Backus-Naur_form 
.
A summary of the BNF symbols are
| Components | Symbol | Meaning |
|---|---|---|
| Production rule | ::= | You could read this as “is defined as”. |
| Non-terminal symbol | < > | Any characters written between these symbols make up a non-terminal. A non-terminal is a language element that is defined elsewhere |
| Alternatives | | | Gives choice. You can read this as “or”. |
| Terminal symbol | Any set of characters not enclosed by symbols is a Terminal, e.g, +, A, IF. These symbols can be put into quotes, e.g. “A” |
Note: BNF does not have symbols for optional, or repetition. It uses recursion to represent repetition.
BNF Example
<letter> ::= a | b | c | d | e | f
<word> ::= <letter> | <letter> <word>
You would read these two lines as a letter is defined as one symbol a, b, c, d, e or f. A word is defined as either letter or letter followed by word. This pair of statements is simple but requires you to get your head around the concept of recursion. The word is defined within itself, using recursion to create a repetition, so a word can be of any length of letters.
To determine if face is a word you need to check that it matches the syntax of a word
- face f <letter> yes. Check that ace is a <word>
- ace a <letter> yes. Check that ce is a <word>
- ce c <letter> yes. Check that e is a <word>
- e e <letter> true – which means that e is a <word>. Thus each of the above steps is true, therefore face is a “word”.
The following table shows whether a range of example elements have the correct syntax.
| Example | Legal/illegal | Reason |
|---|---|---|
| b | legal | b is defined as a letter |
| g | illegal | g not defined as a letter |
| bead | legal | b, e, a and d all legally defined letters, so make up a word |
| Bead | illegal | upper case B not defined as a letter |
| 2 | illegal | 2 not defined as a letter |
| fed cab | illegal | space character not defined as a letter |
BNF Exercise
The data types of a new programming language are described in BNF as:
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<letter> ::= A | B | C | D | E | F
<integer> ::= <digit> | <digit> <integer>
<signed_integer> ::= + <integer> | -<integer>
<address> ::= <letter> <integer>
| Example | Data type | Legal or illegal | Reason |
|---|---|---|---|
| A | letter | ||
| 7 | integer | ||
| 77 | integer | ||
| 77 | signed integer | ||
| -77 | integer | ||
| -77 | signed integer | ||
| a1 | address | ||
| AB6 | address | ||
| C108 | address | ||
| D | address | ||
| D-1 | address |
- As the designer of this new language, you want to add the ability to represent an address with more than one letter, followed by more than one digit, e.g. CD33, C3, DA1. Modify the syntax above to write the BNF statements that would enable this to be done.
Extended Backus-Naur form (EBNF)
EBNF is not more powerful than BNF in terms of what languages it can define, just more convenient. Any EBNF production can be translated into an equivalent set of BNF productions. EBNF includes symbols to represent optional and repeated parts of a definition as well as a way of grouping elements. Unfortunately, most of the symbols used are written differently to BNF.
A summary of the EBNF symbols are
| Component | Symbol | Meaning |
|---|---|---|
| Production rule | = | “is defined as” |
| Non-terminal symbol | Non-terminals do not require < > as in BNF | |
| Alternatives | | | "or”, same as BNF |
| Terminal symbol | “ “ ‘ ‘ |
Symbols written exactly as they are to be represented. Terminals in EBNF must be surrounded by quotes, e.g. “IF”, “?”, “3” |
| Optional | [ ] | Definitions written between these symbols are optional |
| Repetition | { } | Definitions written between these symbols may be repeated, 0 or more times |
| Grouped | ( ) | Definitions may be grouped using these symbols |
These extra symbols allow you to define some concepts that are very long-winded in BNF. EBNF statements can be shorter and easier on the brain.
EBNF example 1
<letter> ::= “a“ |“ b“ |“ c“ |“ d“ |“ e“ |“ f“
<word> ::= <letter> { <letter> }
You would read these two lines as a “letter” is defined as one symbol a, b, c, d, e or f. A “word” is defined as one “letter” followed by zero or more “letter”.
EBNF example 2
digit = “0” | “1” | “2’ | “3” | “4” | “5” | “6” | “7“ | “8” | “9”
integer = [“+” |”-“ ] digit {digit}
In just two lines we have defined an integer as optionally beginning with a sign (+ or -) and consisting of one or more digits. You can do this in BNF, but it would harder to create.
EBNF Exercise
- The data types of a programming language are defined by EBNF as:
digit = “1” |” 2” |” 3”
letter = “a” |” b” |”c”
operator = “+” |” –“
identifier = letter {letter | digit}
number = [“-“] digit {digit} [“.”digit { digit } ]
expression =identifier “:=” (identifier | number) {operator (identifier| number)}
Fill in the following table to check whether each example has the correct syntax
| Example | Data type | Legal or illegal | Reason |
|---|---|---|---|
| a | letter | ||
| t | letter | ||
| b222 | |||
| -22 | |||
| -12.33 | |||
| 21. | |||
| a:=a2+3 | |||
| b1:=22+12-3 | |||
| b2:=14+2 |
- Consider the EBNF below.
Outline whether the above ENBF is equivalent to the syntax defined in the EBNF example 2 abovedigit = “0” | “1” | “2’ | “3” | “4” | “5” | “6” | “7“ | “8” | “9”
sign = “+”|”-“
integer = sign digit {digit} - Construct EBNF to define an integer in base 2, allowing for a possible sign (+ or -). For example, 1 and 0 are digits, 10, 001, 101, +10, -1111 are all binary integers
- The following EBNF is defined. CALLA and CALLB are non-terminal symbols defined elsewhere
digit = “0” | “1” | “2’ | “3” | “4” | “5” | “6” | “7“ | “8” | “9”
integer = digit{digit}
letter = “a“ | “b“ | “c“ | “d“ | “e“ | “f“ | “g“ | “h“ | “i“ | “j“ | “k“ | “l“ | “m“ | “n“ | “o“ | “p“
address = letter integer
logical_operator = “>“ | “<“ | “>=“ | “<=“ | “<>“
selection = “IF (“address logical_operator (address|integer) “,” CALLA “,” CALLB”)”
Fill in the following table to check whether each selection example has the correct syntax
| Selection | Legal or Illegal | Reason |
|---|---|---|
| IF(p13>177, CALLA, CALLB) | ||
| IF(a0=p3, CALLA , CALLB) | ||
| If(p13<p12, CALLA CALLB) |
Syntax diagrams or Railroad diagrams
Syntax diagrams also describe a language’s syntax, but in a graphical form. Definitions are made by starting on the left and following a “railway” line. You may loop around but may not reverse direction. Repeated and optional elements are easily represented by branching.
| Component | Symbol Examples | Meaning |
|---|---|---|
| Non-terminal symbol |  |
A non-terminal language element that is defined elsewhere. |
| Terminal symbol |   |
Symbols written exactly as they are to be represented. |
| Alternatives |  |
Either 0 or 1 |
| Optional |  |
Either Word or nothing |
| Repetition |  |
0 or more letters |
Syntax diagram examples
The diagrams above show that a digit is defined as 0, 1, 2, 3 or 4 and a letter as a, b, c, d or e. A word may have one or more letters followed by zero or more digits.
The following table shows whether a range of example elements have the correct syntax.
| Example | Element | Legal or Illegal | Reason |
|---|---|---|---|
| a | letter | Legal | It is a letter |
| bade | word | Legal | All characters are defined letters |
| 2 | digit | Legal | It is a digit |
| ab44 | word | Legal | One or more letters followed by one or more digits |
| a4b4 | Word | Illegal | You may not reverse direction. Once a digit is in the word, only digits may follow. |
Syntax diagram exercise
- Convert the follow EBNF syntax to a syntax diagram:
digit = “1” |” 2” |” 3”
letter = “a” |” b” |”c”
operator = “+” |” –“
identifier = letter {letter | digit}
number = [“-“] digit {digit} [“.”digit { digit } ]
expression =identifier “:=” (identifier | number) {operator (identifier| number)}
|