Be able to check language syntax by referring to BNF or syntax diagrams and formulate simple production rules.
Regular expressions can be used to represent the syntax of languages which use a simple syntax; however they are not suitable for languages with complex syntax.
Context free languages are used to represent syntax rules of languages with complex syntax.
Backus-Naur Form (BNF) is an example of a context-free language.
| Notation | Meaning |
|---|---|
| < > | Encloses each element |
| ::= | Defines the rule for a previous element |
| | | Or |
| { } | Encloses optional elements |
Example
The production rule below shows that the student-details must include the following elements:
- name
- address
- gender
<student-details> ::= <name> <address> <gender>
Each element should be broken down further until a terminal is reached; this is an element that can't be broken down any further.
In the first example below, gender is the only terminal element as each of the other elements can be broken down further.
Example
<name> ::= <first-name> <middle-name> <last-name>
<address> ::= <street> <town> <county> <post-code>
<gender> ::= "M" | "F"
Example 2
<digit> ::= 0|1|2|3|4|5|6|7|8|9
<upper> ::= A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z
<lower> ::= a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z
<space> ::= ' '
<letter> ::= <upper>|<lower>
<string> ::= <letter>|<letter><string>
A syntax diagram is another method of representing a context-free language.
| Symbol | Use |
|---|---|
 |
Used to represent a non-terminal element |
 |
Used to represent a terminal element |
 |
Used to represent a non-terminal element that can be reused |
Be able to explain why BNF can represent some languages that cannot be represented using regular expressions.
BNF really shines once you have a solid syntax definition as you can then use the tools to rigorously parse the syntax it describes.