Backus-Naur Form and syntax diagrams

Overview

Recall questions on production rules, terminals against non-terminals, recursion in a rule, and why BNF describes languages regular expressions cannot.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What is Backus-Naur Form used for?

   Model answer

   Backus-Naur Form is a notation for defining the syntax of a language precisely — the rules saying which sequences of symbols are valid. It is used to specify the grammar of programming languages, so that a compiler can be written to check and translate programs, and to specify data formats.

2. 2

   Describe how a BNF production rule is written.

   Model answer

   A rule has a name on the left, written in angle brackets to show it is a non-terminal — something that still has to be defined — then the symbol ::= meaning 'is defined as', then the definition on the right. The right-hand side is a sequence of terminals, which are literal symbols that appear in the language itself, and non-terminals, which refer to other rules. Alternatives are separated by |. For example: <digit> ::= 0|1|2|3|4|5|6|7|8|9

3. 3

   What is the difference between a terminal and a non-terminal in BNF?

   Model answer

   A terminal is a symbol that actually appears in the language being defined and is not defined any further — the characters 0 to 9, the word WHILE, a bracket. A non-terminal is a name for a construct that is defined by another rule, written in angle brackets. Every non-terminal must eventually be reduced to terminals by applying rules, otherwise the definition is incomplete.

4. 4

   Write BNF production rules for an unsigned integer of one or more digits.

   Model answer

   <digit> ::= 0|1|2|3|4|5|6|7|8|9 <unsigned integer> ::= <digit> | <digit><unsigned integer> The first alternative allows a single digit; the second allows a digit followed by another unsigned integer, and applying that repeatedly gives numbers of any length.

5. 5

   Using those rules, check whether 407 is a valid unsigned integer, showing each step.

   Model answer

   Apply <unsigned integer> ::= <digit><unsigned integer>: 4 is a <digit>, leaving 07 to be an <unsigned integer>. Apply the same rule again: 0 is a <digit>, leaving 7. Apply the first alternative <unsigned integer> ::= <digit>: 7 is a <digit> and nothing is left over. Every symbol has been accounted for by the rules, so 407 is valid.

6. 6

   Write BNF rules for an identifier that must begin with a letter and may then contain any number of letters or digits, and check whether 2ab and a2b are valid.

   Model answer

   <letter> ::= a|b|c|…|z <digit> ::= 0|1|2|3|4|5|6|7|8|9 <identifier> ::= <letter> | <identifier><letter> | <identifier><digit> 2ab is invalid: every route through the rules eventually requires the leftmost symbol to come from <letter>, and 2 is a digit, so no derivation exists. a2b is valid: a is an <identifier> by the first alternative; a2 is an <identifier> by <identifier><digit>; a2b is an <identifier> by <identifier><letter>.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.