top of page

Week 2 Practice

EBNF

Practice Set 3

Write a tabular proof that the <integer> rule to the left accepts +128. In each step reason why your step is correct in a short sentence like "Include option".

<integer> <= [ + | - ] <digit> {<digit>}

<integer> <= [+ | -]  <digit> {<digit>}           (Rule definition)
                     <= [+]  <digit> {<digit>}               (Chose alternative)
                     <= + <digit> {<digit>}                    (Include option)
                     <= + <digit>  <digit>  <digit>     (Repeat twice)
                     <= + 1 <digit>  <digit>                   (Choose alternative 1 in <digit>)
                     <= + 1 2 <digit>                                (Choose alternative 2 in <digit>)
                     <= + 1 2 8                                            (Choose alternative 8 in <digit>)

Hover to reveal answer

EBNF

Practice Set 3

Draw a derivation tree that shows that 007 is a legal symbol according to the <integer> rule to the right.

EPROGTreesExSolution.png

Hover to reveal answer

<integer> <= [ + | - ] <digit> {<digit>}

EBNF

Practice Set 3

Aaron has just learnt about EBNF and found a short rule that accepts all sequences of digits. Is the rule correct? If the rule is incorrect propose an alternative solution.

<digits> <= <digit> <digits>

The rule seems correct at first, it however has a fatal flaw: It never terminates. The recursion goes on forever as we never have the option to select no further recursion. The rule could instead be

<digits> <= <digit>  [<digits>]
<digits> <= (<digit>  <digits>)  |  <digit>
<digits> <= {<digit>}
<digits> <= <digits> | <digit>

Hover to reveal answer

EBNF

Practice Set 3

Aaron has now (encouraged by his earlier findings) found a much better rule for <integer> which skips "unnecessary control forms". What do you think about Aaron's findings? 

<integer> <= <sign> {<digit>}

The rule accepts all words which the <integer> rule in the lecture accepts. This however on its own does not suffice. We must also verify that the new rule does not accept words which the <integer> rule from the lecture rejects. This is the case as for example + and - are accepted by the proposed rule, but <integer> does not accept + or -. This is important to remember and is often forgotten.

Hover to reveal answer

Programming

Practice Set 1

What will the output of the program to the right be?

The output is:
enter c
enter b
exit b
exit c

Hover to reveal answer

ExerciseOutputSolution1.png

That is it.

Well done practising. You can find more programming exercises on exercise sheet 2 on the official website. Solve it!

bottom of page