This is an old revision of the document!
How Can We Define Languages in Computer Science?
Several scientific methods have been developed to precisely define the syntactic rules of languages.
Backus-Naur Form (BNF):
A meta-language used to describe the syntax of languages.
<name> | meta-symbol |
::= | definition |
| | alternative |
{expression} | repetition (minimum and maximum repetitions can be specified using subscripts) |
GOTO | terminal symbol (in quotes for clarity, can also use apostrophes instead) |
1. Example: Syntax of License Plates
Let’s start with a few typical examples and try to generalize:
ABC-1234, GHT-234, HSD-333, AI-BB-654
Syntax definition: $$ <license\_plate>::=<newType> | <oldType> \\ <oldType>::=\{<letter>\}_3^3 − \{<number>\}_3^3 \\ <newType>::=\{<letter>\}_2^2 − \{<letter>\}_2^2 − \{<number>\}_3^3 \\ <letter>::=A|B|C...|Z \\ <number>::=0|1|2|3|4|5|6|7|8|9 \\ $$
2. Example: Syntax of Phone Calls in Hungary
Let’s list a few examples and try to generalize:
062012345, +36301234567, 0680460046
Syntax definition: $$ <phone call>::= \{<prefix>\}_0^1 <city> <customer> \\ <prefix>::=\{+\}_0^1 36|06 \\ <city>::=\{<number>\}_1^2\\ <customer>::=\{<number>\}_6^7\\ <number>::=0|1|2|3|4|5|6|7|8|9 \\ $$