Week 1 EBNF (Extended Backus

Einführung in die Programmierung (252-0027), ETH Zürich. Lectures 1 & 2 (Manuela Fischer). Slides: “1. EBNF”, sections 1.1–1.6.

Course Organisation (Lecture 1, first half)

Lecturers: Manuela Fischer (theoretical CS, algorithms) and Malte Schwerhoff (formal methods). They alternate roughly week by week.

Lectures: Tue 10–12 and Fri 8–10, live in the lecture hall, with a live stream to an overflow room. The video portal has a projector-only recording. Gestures and live quizzes (EduApp) are not captured, so attending in person is recommended.

Course website: slides, exercises, quizzes with solutions and further material. It is linked from myStudies. Materials are uploaded by the evening before at the latest; last-minute updates are possible.

Questions: raise your hand in the lecture, ask before/after/during the break, post on the Moodle forum (anonymous; everyone sees the answer), or email your TA or the lecturers. “There are no stupid questions — at least a quarter of the room has the same one.”

Exercise sessions (Übungsstunden): Wed 16–18, starting in week 1. Enrol via myStudies. Only enrolled students can submit. Group types: regular (no marker), English (E/ENG), and repeaters only (REP). A myStudies enrolment bug was fixed during lecture 1.

Weekly cycle: exercises are released Tue 18:00, submitted within one week, and get TA feedback.

Ex. 1: install IntelliJ, no submission.

Ex. 2: dummy submission.

Ex. 3–4: first programming tasks.

Bonus exercises from Ex. 5.

Study Center: technical installation support, next Tuesday 16–18. Use it, the troubleshooting guide, or your TA, not AI, for installation problems.

Schedule swap with A&D: EProg takes the Thursday slot in weeks 2–3 and gives a Tuesday slot back in week 6. Same lecture hall.

Exam: 160 min on ETH Windows computers with plain IntelliJ, no plugins.

≈ 1/3 theory on Moodle, ≈ 2/3 programming in IntelliJ.

Programming tasks are graded only by tests. Some tests are provided, but the hidden tests decide. Code style is not graded.

Swiss keyboard by default; a US keyboard is available via a survey at the end of the semester.

German is authoritative; a generated English translation is provided.

Libraries and Java Collections are allowed unless stated otherwise, as long as they don’t trivialise the task (e.g. a library binary search when the task is to implement binary search).

Bonus: up to +0.25 on the exam grade. 80 % of the bonus points give the full 0.25; less scales proportionally (40 % gives 0.125). A 6.0 is reachable without bonus.

Timed bonus: probably in weeks 7 and 12 (3.11. and 8.12., 17–19, online from anywhere). It is optional, but the best predictor of exam performance. A historic plot showed that even students with 100 % (untimed) bonus could score 0 on the programming exam.

Advice:

Programming is learned by doing, not watching.

Copying solutions (web or AI) is a wasted practice opportunity.

Debugging yourself is a core skill, and even more important in the AI era.

Discuss exercises in groups (bonus included), then sleep on it and re-implement alone without notes.

1. Executive Overview & Core Objectives

EBNF is a formalism for describing the syntax (form, structure) of a language, i.e. exactly which strings are allowed. It never describes what they mean. A description consists of rules built from terminals, nonterminals and four control forms (Kontrollformen): sequence, decision (selection/option), repetition, recursion. Membership of a string is proven by a derivation (Ableitung). Recursion is strictly more powerful than repetition in EBNF; the language ${A^{n} B^{n} ∣ n \in N}$ is the standard witness.

Learning objectives. After this week you should be able to:

read and write EBNF rules in the course’s notation, including boxed special characters and the “last rule = start rule” convention;
determine the language of an EBNF description and decide whether a given string is legal;
write derivations as a derivation table (Ableitungstabelle) and as a derivation tree (Ableitungsbaum), with justifications;
design EBNF descriptions that generate exactly a target set of words (not too many, not too few);
recognise equivalent EBNF descriptions and distinguish syntax from semantics;
read syntax graphs (Syntaxgraphen);
use recursion with a termination option, and explain why ${A^{n} B^{n}}$ requires recursion.

2. Core Concepts & Formal Definitions

2.1 Motivation (Slides 1.1)

Computer science constantly needs precise descriptions of allowed values:

Literals: 3,76 vs 4.29 vs 1.23f vs 2.3E20
Input fields: 160 cm vs 1.6 m vs 1600 mm. The lecturer alluded to the Mars Climate Orbiter, lost because of a metric-vs-imperial units mix-up.
Formats in files: XX-XXX-XXX vs XX.XX.XXXX, e.g. a Legi number
Programming languages: what is valid syntax? A parser checks this.

Natural-language descriptions (“two digits, then a hyphen, then three digits…”) quickly become long and ambiguous. A formalism (a set of rules) is precise and allows automatic checking.

Definition (Language and Word)

A language (Sprache) is a set of allowed strings. An allowed string is a word (Wort) of the language.

Language of the integers: every integer is a word.

Language of Java programs: every compiling Java program is one word.

Even a whole integer set like {5, -2, 11} is a single word of the integer-set language.

Remark (Empty language)

The language that contains no words at all is also a language (lecture 2, student question). Do not confuse the empty language $\emptyset$ with the language ${ε}$ containing only the empty word.

Definition (EBNF)

Extended Backus–Naur Form (sometimes “Normal Form”) is a formalism for describing the syntax of a language.

It describes form and structure only. It makes no statement about meaning.

It enables automatic checking, e.g. by a parser.

It is used to describe programming languages and inputs.

Food for thought for the 3rd semester (Theoretical Computer Science): which languages can be described with EBNF?

Why EBNF in EProg?

Foundation for later courses: Theoretical Computer Science, Compiler Design.
Trains formal and precise thinking. The lecturer named this a main goal of the whole degree.
“Programming in the small”: writing an EBNF ↔ writing a Java program, with similar concepts (names, sequence, choice, repetition, recursion).
It gives students time to install Java.
It is new to (almost) everyone, including those with programming experience. A show of hands in lecture 1 showed more people knew EBNF than expected.

2.2 EBNF descriptions and rules (Slides 1.2)

Definition (EBNF description, EBNF rule)

An EBNF description (EBNF-Beschreibung) is a set of EBNF rules (EBNF-Regeln). The order of the rules is irrelevant, except for the start-rule convention (§2.6). Each rule has the form
$LHS ⟵ RHS$

LHS, the left-hand side (linke Seite): the name of the rule in angle brackets, e.g. <digit>. Any name is allowed; descriptive, relevant names are sensible, just like variable names in Java.

$⟵$ is pronounced “is defined as” (ist definiert als).

RHS, the right-hand side (rechte Seite): the definition of the name, i.e. which words it describes.

The RHS can consist of:

Characters (Zeichen), also called literals or terminals, e.g. 0, D, +
Names of EBNF rules, also called nonterminals (Nichtterminale), e.g. <digit>
Combinations of the four control forms (Kontrollformen):
- sequence (Aufreihung)
- decision (Entscheidung): selection (Auswahl) and option (Option)
- repetition (Wiederholung)
- recursion (Rekursion)

<digit_zero>  ⟵ 0               // character as RHS: allows exactly the word "0"
<number_zero> ⟵ <digit_zero>    // name as RHS: allows exactly the words of <digit_zero>

Exam Trap: Brackets mark names

Always write names in angle brackets. <D> is a nonterminal; a bare D is the literal letter D. Some literature uses italics instead; the lecturer uses brackets because her handwritten italics are not distinguishable.

2.3 Control form 1: Sequence (Slides 1.3.1)

Definition (Sequence, Aufreihung)

E1 E2 E3

A sequence of any number of elements, read left to right. Order matters.

Each element must be a valid RHS.

Spaces between elements are only for readability. They are never real space characters in the word.

2.4 Control form 2: Decision (Slides 1.3.2)

Definition (Selection, Auswahl)

E1 | E2 | E3

Alternatives separated by the vertical stroke |. Each alternative is a valid RHS; their order is irrelevant.

Exactly one alternative is chosen: not zero, not several.

Definition (Option)

[ E ]

The element in square brackets may be chosen, or nothing at all. E must be a valid RHS.

Definition (Epsilon)

$ε$ (“epsilon”) denotes the empty string. It never appears in the resulting word. Therefore
$[E_{1} ∣ E_{2}] \equiv E_{1} ∣ E_{2} ∣ ε and in general [X] \equiv X ∣ ε .$

Parentheses for grouping. A | B C is ambiguous:

A | (B C) gives the words “A” or “BC”.
(A | B) C gives the words “AC” or “BC”.

Parentheses only structure the rule; they do not appear in the word. The lecturer’s advice: use as many parentheses as needed so that no brain power is wasted figuring out the grouping. The same holds for programming.

2.5 Control form 3: Repetition (Slides 1.3.3)

Definition (Repetition, Wiederholung)

{ E }

The element in curly braces is repeated 0, 1, 2, … times: any finite number, never infinitely often.

E must be a valid RHS.

Key properties:

Zero repetitions are allowed. For “at least one”, use the idiom E { E }.
Every repetition is an independent choice. Choosing 3 repetitions of {<digit>} yields <digit> <digit> <digit>, and each copy can become a different digit (e.g. 7, 9, 5). There is no coupling between copies; you substitute “blindly”. (Student question, lecture 1, and again in lecture 2.)
You cannot control or count the number of repetitions, unlike a for loop where you write “10 iterations”. This is why some languages cannot be described without recursion (§3.5).
[ { X } ] is the same as { X }, since {X} already includes zero repetitions. (Student question at the end of lecture 1.)

2.6 Language of an EBNF description and the start rule

Definition (Start rule, Startregel)

Every EBNF description has a special start rule (entry rule). Course convention: the last rule is the start rule, unless stated otherwise. Other courses and books may use different conventions.

Definition (Language of an EBNF, informal)

Applying a rule means replacing a name by the RHS of its rule. The language of an EBNF is the set of all strings (without names) that can be produced from the start rule by repeatedly applying rules.

Remarks from student questions (lecture 1):

A rule other than the start rule also generates a language, a “sub-language” (Teilsprache). For example, <digit> alone generates ${0, \dots, 9}$ . But “the” language of the description is the one generated from the start rule.
The order of rules in the set is irrelevant; only the start rule needs to be known, and by convention it is the last one.
Cycles without an exit, e.g. <Z> ⟵ <Y> and <Y> ⟵ <Z>, never terminate. You go around in circles and no word is ever produced, so the language is empty. Sensible cycles are recursion with a termination option (§2.11).

2.7 Special characters (Sonderzeichen)

Definition (Special characters and boxes)

The metasymbols < > ⟵ | [ ] { } ( ) and the space are special in EBNF and do not appear in the resulting words.

If one of them is needed as an actual character of a word, draw a box (frame, Rahmen) around it. In these notes a box is written as ⟦…⟧:

⟦}⟧ means the actual character }.

␣ or an empty box ⟦ ⟧ means a real space. The lecturer recommends a box containing ␣ to be unambiguous.

To have ε as an actual character, box it as well: ⟦ε⟧. Otherwise ε means “empty”.

Exam leniency (lecture 2): whether you draw one box around ab or two separate boxes does not matter, as long as it is clear which EBNF you mean. The course does not split hairs over details such as one vs. three spaces in handwriting.

2.8 Derivations (Slides 1.4)

Definition (Legal word)

A string is legal (legal) for an EBNF description if

informally: all characters match the elements of the rule;

formally: there exists a derivation of the string.

Definition (Derivation, Ableitung)

A derivation is a sequence of derivation steps (Ableitungsschritte) that

starts with the start rule, and

ends with a string containing only terminals. No nonterminals and no EBNF metasymbols may remain; you may not stop halfway.

A derivation step is one of:

Rule: replace a name (LHS) by its definition (RHS).

Selection: choose one alternative.

Option: decide whether the optional element is taken.

Repetition: fix the number of repetitions.

Two representations:

Representation	Structure
Derivation table (Ableitungstabelle)	First row: start rule. Last row: the final string. Each row transition is one derivation step, with a justification (Begründung) next to it.
Derivation tree (Ableitungsbaum)	Root: name of the start rule. Leaves: characters. Each edge is one derivation step. Trees grow top-down, as always in CS. The word is read from the leaves, left to right.

The course’s trees show one specific derivation. Trees found online that try to show all derivable words are something different.

2.9 Equivalence of EBNF descriptions

Definition (Equivalence, Äquivalenz)

The language of an EBNF is the set of its legal strings. Two descriptions $B_{1}, B_{2}$ are equivalent iff their languages are equal:
$w legal for B_{1} ⟺ w legal for B_{2} (hence also illegal ⟺ illegal) .$
The number and names of rules are irrelevant for equivalence, just as variable names are irrelevant to a running Java program.

2.10 Syntax vs. semantics

Definition (Syntax vs. semantics)

Syntax: form and structure. This is what EBNF describes.

Semantics (Semantik): meaning, interpretation. This is a separate topic, not handled by EBNF.

If a string is syntactically illegal, it has no meaning (undefined). A non-compiling Java program is not a program, so asking what it does is pointless.

Two questions about semantics:

Can different strings have the same meaning? Yes.
- 1 and +1
- 0, +0 and -0
- “Herr Wirth”, “Professor Wirth” and “Niklaus Wirth” mean the same person.
- {1, 2, 3}, {3, 2, 1} and {1, 1, 1, 2, 2, 2, 3, 3, 3} are the same mathematical set.
Can one string have several meanings? Yes, depending on context.
- “next lecture” depends on today’s date.
- 0012 vs 12: the same number in mathematics, but not the same PIN code.

Exam Trap: Only syntax counts

For EBNF exercises, only the character strings matter. +6 and 6 are different words, as are 0, 00 and 000. Do not argue that they “mean the same”. Students repeatedly asked this in lectures 1 and 2; the lecturer’s answer was always: we only care about syntax.

2.11 Control form 4: Recursion (Slides 1.6)

Definition (Direct and indirect recursion)

Direct recursion (direkte Rekursion): the rule’s name appears on its own RHS, e.g. <A> ⟵ a | [ <A> ].

Indirect recursion (indirekte Rekursion): there is a chain of rules $R_{1}, \dots, R_{k}$ such that $R_{i + 1}$ appears on the RHS of $R_{i}$ for $1 \leq i \leq k - 1$ , and $R_{1}$ appears on the RHS of $R_{k}$ . Example: <A> ⟵ a |  and  ⟵ [ <A> ].

An EBNF description is recursive if it has at least one recursive rule.

Requirement (Termination option, Abbruchsoption)

Sensible, finite recursion needs a termination option: there must be at least one way to replace the recursive name by an RHS without that name. This can be an option […], an alternative | B, or | ε. EBNF only ever produces finite words: arbitrarily long, but finite. This is the base case known from recursive programs.

2.12 Graphical representation: syntax graphs (Slides 1.5)

Definition (Syntax graph)

An EBNF description can be drawn as a set of syntax graphs (Syntaxgraphen), one graph per rule.

A legal string corresponds to a path through the graph from left to right.

Substitution: a rule’s graph can be inserted in place of its name in another graph. This corresponds to applying the rule, and the internal names disappear.

Control form	Graph shape
Sequence `A B C`	one straight line: `→ A → B → C →`
Selection `A`, `B` or `C`	parallel branches stacked vertically; you must take exactly one (you may not pass through two)
Option `[ A ]`	one branch through `A` and one empty bypass
Repetition `{ A }`	a bypass line plus a backward arrow looping around `A`, so you can pass through `A` 0, 1, 2, … times

Syntax graphs help those who think visually, but they blow up quickly. For example, <integer> with all ten digits drawn twice. Written EBNF stays more compact, especially with many alternatives.

Exam relevance (lecture 2): since the exam is on Moodle without a touchscreen, you will probably not be asked to draw a graph. You might be shown one and asked e.g. whether 125 is legal.

3. Step-by-Step Derivations & Constructions

3.1 Same language, different descriptions

EBNF 1:  <letter_D> ⟵ D
         <digit_2>  ⟵ 2
         <digit_8>  ⟵ 8
         <room1>    ⟵ <letter_D> <digit_2> <digit_8>

EBNF 2:  <room1>    ⟵ D 2 8

EBNF 3:  <letter_D> ⟵ D
         <digit_8>  ⟵ 8
         <room1>    ⟵ <letter_D> 2 <digit_8>

All three have the language ${D28}$ , so they are equivalent. EBNF 3 is legal but “questionable” (lecturer): it is inconsistent to introduce names for some characters and not others. As in programming, you choose how many intermediate names (“variables”) to introduce.

3.2 Selection and option

<digit>    ⟵ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9     // language: {0, …, 9}
<room1>    ⟵ D 2 8
<room2>    ⟵ E 1 2
<room>     ⟵ <room1> | <room2>                        // language: {D28, E12}

<initials> ⟵ M [ H ] S                                // language: {MS, MHS}

<sign>     ⟵ + | -
<number>   ⟵ [ <sign> ] <digit>

The lecturer had no middle name of her own, so she used Malte’s initials (MS or MHS) for the option example.

<number> generates all one-digit numbers with an optional sign, 30 words in total: 0–9, +0–+9, -0–-9.

How the choices combine:

Substitute <sign>, which gives [ + | - ] <digit>.
Decide whether to take the option.
If taken, choose + or -.
Choose one of the ten digits.

Equivalent one-liners: [ + | - ] <digit> and ( + | - | ε ) <digit>.

3.3 Integers of arbitrary length

Naive attempt: <integer> ⟵ [ + | - ] { <digit> }. With zero repetitions this also allows ε, + and -. That is wrong for integers. (Discussed at the start of lecture 2.)

Correct, using the at-least-one idiom:

<digit>    ⟵ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<sequence> ⟵ <digit> { <digit> }
<sign>     ⟵ + | -
<integer>  ⟵ [ <sign> ] <sequence>

Compact version: <integer> ⟵ [ + | - ] <digit> { <digit> }

Why write <digit> { <digit> } instead of { <digit> }? (Question to the audience in lecture 1.) The repetition alone could be chosen 0 times. Writing one <digit> outside guarantees at least one digit. If exactly one digit is wanted, choose 0 repetitions afterwards.

Colloquial reading (slide):

<digit> is defined as one of the characters 0, …, 9.
<integer> is defined as a sequence of 3 elements:
1. an optional sign (one of the alternatives + and -);
2. one <digit>;
3. a repetition of 0 or arbitrarily many <digit>s (in particular, also none).

Leading zeros (007, 0000) are still legal here. Syntactically, 0, 00 and 000 are distinct words.

3.4 Canonical integers (kanonische Zahlen): no leading zeros

Goal: 7 is legal, 007 is illegal. (In the lecture this was said as “0,07”; 007 is meant.)

Idea (from a student, refined by the lecturer): the first digit must be non-zero; after that, any digits including 0.

<zero>        ⟵ 0
<nonzero>     ⟵ 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<digit>       ⟵ <zero> | <nonzero>
<canonic_int> ⟵ ( [ + | - ] <nonzero> { <digit> } ) | <zero>

Step-by-step reasoning:

[ + | - ] <nonzero> { <digit> } covers every integer except 0: the first digit is forced to be 1–9.
Are we satisfied? No. The audience spotted that the number 0 itself is not derivable, because every word must start with a non-zero digit.
Fix: add the lone zero as a separate alternative, | <zero>. The slide shows this as an annotation ( … ) | <zero> wrapped around the rule. The lecturer described such an added alternative as a common “hack” for a forgotten case.
Consequence: with this version +0 and -0 are excluded. Signed zero isn’t canonical.

Later slides use plain <digit>/<integer> again to keep the rules short; the canonical version can always be “planted in”.

3.5 Numbers with thousands separators (lecture 2 clicker question)

Target words (leading zeros allowed for simplicity; D stands for <digit>): 234, 1'234, 1'123'123, 12'123'123, -123'123.

Requirements:

The first group has 1–3 digits.
Every following group is ' followed by exactly 3 digits.
The word never starts or ends with '.
There is no apostrophe-free run of more than 3 digits.

Correct solution (slides; clicker option 5)
<digit> ⟵ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<prefix> ⟵ <digit> | <digit> <digit> | <digit> <digit> <digit>
<integer> ⟵ [ + | - ] <prefix> { ' <digit> <digit> <digit> }
Clicker result: option 5 was correct and got about 130 votes. Option 3 also received a noticeable number of votes.

Equivalent student proposals:

D D D alternatives for the prefix, followed by { ' D D D }.

D [D] [D] { ' D D D }, since D [D] [D] is exactly “1, 2 or 3 digits”.

The lecturer found these more intuitive than the slide’s options, which were deliberately chosen to be unintuitive.

Wrong options discussed in class, each with a counterexample:

Flaw in the candidate	Illegal word it produces, or legal word it misses
A free repetition of digits `{ D }` that contains no `'`	`12345678`; it could also produce `'123`
The group repetition can end with `'`	`9'234'`
The prefix can be deselected entirely	`'123`
The prefix is forced to exactly 3 digits	over-restrictive: `12'345` is not derivable
The apostrophe is optional inside the repetition	`3334`: deselect `'` every time
The repeated group is `{ D ' }` or similar	`1'2'3`: groups must be exactly 3 digits

Student objection to option 5: “you can’t represent numbers below 1000”. Rebuttal: choose zero repetitions, then 123 comes from the prefix alone.

Exam Trap: Exactly the target language

“Describe language X” means exactly X. Every word of X must be derivable, and no other word. Over-generating is as wrong as under-generating. Otherwise <any> ⟵ { anything } would trivially “solve” every task. (A student asked whether a description that generates all numbers with separators plus more counts; it doesn’t.)

3.6 Integer sets (Zahlenmengen)

Target words: { }, {1}, {3, 2}, {3, 2, 3}. The curly braces are real characters here, so they must be boxed.

Solution (slides)
<digit> ⟵ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<integer> ⟵ [ + | - ] <digit> { <digit> }
<integer_list> ⟵ <integer> { , <integer> }
<integer_set> ⟵ ⟦{⟧ [ <integer_list> ] ⟦}⟧
<integer_list> is a non-empty list: one integer, then any number of “comma + integer”. The option [ … ] adds the empty set.

How the solution develops (from class):

⟦{⟧ { <integer> } ⟦}⟧: there are no commas between the numbers.
⟦{⟧ { <integer> , } ⟦}⟧: there is always a trailing comma, e.g. {1,2,}.
⟦{⟧ { <integer> , } <integer> ⟦}⟧: no trailing comma, but the student noticed the empty set { } is no longer derivable. You could add | ⟦{⟧⟦}⟧, but that is a hack.
Clean pattern: a non-empty separated list X { sep X }, wrapped in an option for the empty case.

Student question: “What exactly are the words here?” A word is the entire set string, e.g. {5, -2, 11}, not the individual numbers. Everything derivable from the start rule is one word.

Exam Trap: What EBNF can't enforce

Duplicates ({3, 2, 3}) and the order of numbers cannot be prevented. Forbidding duplicates would require remembering which numbers already appeared. So {3, 2, 3} is accepted as a valid word. Its meaning as a mathematical set is a separate, semantic question.

3.7 Derivation of `-4` as a table (slides)

(R1) <digit>  ⟵ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
(R2) <sign>   ⟵ + | -
(R3) <number> ⟵ [ <sign> ] <digit>

Step	Current string	Justification
0	`[ <sign> ] <digit>`	start rule (R3)
1	`<sign> <digit>`	option: take it
2	`( + \| - ) <digit>`	apply (R2)
3	`- <digit>`	selection: choose `-`
4	`- ( 0 \| 1 \| … \| 9 )`	apply (R1)
5	`- 4`	selection: choose `4`; only terminals remain, so the derivation is finished

Step 4 still contains metasymbols (an open selection), so the derivation is not finished there.

3.8 Derivation of `-4` as a tree (slides)

                 <number>                       (R3)
              /             \
       [ <sign> ]           <digit>
           |  Option           |  (R1)
        <sign>          0|1|2|3|4|5|6|7|8|9
           |  (R2)             |  Selection
         + | -                 4
           |  Selection
           -
Leaves left to right:  -  4   gives  "-4"

The sequence [ <sign> ] <digit> becomes two branches: one per component.
The left and right subtrees develop independently.
Edge labels state which rule or choice was applied.

3.9 Derivation of `6`: deselecting the option

Step	Current string	Justification
0	`[ <sign> ] <digit>`	start rule (R3)
1	`<digit>`	option: not taken
2	`0 \| 1 \| … \| 9`	apply (R1)
3	`6`	selection: choose `6`

Tree: <number> has the children [ <sign> ], which becomes ε (option deselected), and <digit>, which becomes 6. The leaves give ε6 = 6.

Student question: how should a deselected option be shown in a tree? The lecture and exercises are not perfectly consistent. The lecturer’s recommendation is to label the edge “option deselected” (Option abwählen) and write ε as the leaf, so it is clear that nothing is produced.

3.10 Derivation of `284` (repetition) as a tree

Rule: <integer> ⟵ [ + | - ] <digit> { <digit> }

                          <integer>
          /                   |                      \
     [ + | - ]             <digit>               { <digit> }        // choose 2 repetitions
         |                    |                   /         \
         ε                    2               <digit>     <digit>
                                                 |           |
                                                 8           4
Leaves:  ε 2 8 4   gives  "284"

Choosing $k$ repetitions gives the repetition node $k$ children, each resolved independently. (Student question, lecture 2: “what would 2 or 3 repetitions look like?“)

3.11 A failed derivation attempt: `A15` (slides)

With the same rule, the first <digit> must become one of 0–9. Matching A is impossible, so the derivation gets stuck (????? on the slide).

Remark (Proving non-derivability)

Proving that a word is not derivable is generally much harder than proving that it is. You must rule out all possible derivations, not just exhibit one. In exams it is only asked for very small examples.

3.12 Derivation of `{5, -2, 11}` (slides)

<integer_set>
├── ⟦{⟧  ->  {
├── [ <integer_list> ]  ->  option taken
│     └── <integer_list>
│          ├── <integer>  ->  5
│          └── { , <integer> }  ->  2 repetitions
│                ├── ,
│                ├── <integer>  ->  -2
│                ├── ,
│                └── <integer>  ->  11
└── ⟦}⟧  ->  }
Leaves:  { 5 , -2 , 11 }

The slide abbreviates the <integer> subtrees. In general you may abbreviate on paper, e.g. not drawing four branches just to produce a +. If the exam asks for a full derivation, it will not be unreasonably long.

3.13 Recursion: the endless story

“Es war einmal ein Mann. Der hatte einen hohlen Zahn. In diesem hohlen Zahn befand sich eine Schachtel. In der Schachtel war ein Brief. In diesem Brief stand: Es war einmal ein Mann. …”

The lecturer’s favourite recursion story. It is apparently less well known today, maybe regional.

Write the repeated text as <paragraph>:

<endless_story> ⟵ <paragraph> <endless_story>

Expanding:

<paragraph> <endless_story>
<paragraph> <paragraph> <endless_story>
… and so on forever.

A nonterminal always remains, so no word is derivable and the language is empty. This is not a useful EBNF description.

Fixes proposed by students:

make the recursive call optional: <endless_story> ⟵ <paragraph> [ <endless_story> ]
an alternative ending, e.g. with a full stop: <paragraph> ( <endless_story> | . )
with ε: <paragraph> ( <endless_story> | ε ), which is the same as the optional form, since $[X] \equiv X ∣ ε$
with repetition: <paragraph> { <endless_story> }. This is correct, but it needlessly mixes two mechanisms. The lecturer’s advice: usually pick either recursion or repetition, though some problems need both.

Example: Arbitrarily long stories

With <endless_story> ⟵ <paragraph> [ <endless_story> ]:

Deselect the option immediately: 1 paragraph.

Take it once, then deselect: 2 paragraphs.

Take it twice, then deselect: 3 paragraphs.

And so on.

Deselecting the option is the base case: the recursion stops there.

Without recursion, the same language is <paragraph> { <paragraph> }.

3.14 Recursion: natural numbers

<positive_integer> ⟵ <digit> [ <positive_integer> ]

This has exactly the structure of the endless story. Each recursive step adds one digit, and deselecting the option ends the recursion. It is equivalent to <digit> { <digit> }.

3.15 Derivation of `AAB` with recursion (slides)

Rule: <r> ⟵ B | ( A <r> )

Step	Current string	Justification
0	`B \| ( A <r> )`	rule
1	`A <r>`	selection `A <r>`
2	`A ( B \| ( A <r> ) )`	rule
3	`A A <r>`	selection `A <r>`
4	`A A ( B \| ( A <r> ) )`	rule
5	`A A B`	selection `B`: the base case, the recursion stops

Notes:

Here the termination option is an alternative (B), not an [ … ] option. “It doesn’t always have to be the direct option.”
The language is ${A^{k} B ∣ k \geq 0}$ .
On the slide’s tree version, selection and sequence are drawn combined, as an abbreviation.

3.16 Recursion vs. repetition: ${A^{n} B^{n} ∣ n \in N}$

Target language: ${ε, A B, AA B B, AAA B B B, \dots}$ . Notation: $A^{n}$ means $n$ concatenated copies of A (“A squared is A times A, where times is concatenation”), and $A^{0} = ε$ . This is the notation of 3rd-semester Theoretical Computer Science. A student first misread it as “independent numbers of A’s and B’s”; the same $n$ is meant.

With recursion
<equalAB> ⟵ [ A <equalAB> B ]
Every recursive step adds one A in front and one B at the back, simultaneously. That keeps the counts equal. Deselecting the option gives ε, which is both the base case and the $n = 0$ word. A student proposed the equivalent <equalAB> ⟵ A <equalAB> B | ε.

Derivation of AABB:

<equalAB>  ->  A <equalAB> B           (option taken)
           ->  A A <equalAB> B B       (option taken)
           ->  A A B B                 (option deselected, gives ε)

Derivation of AB (student question): take the option once, then deselect it.

“Do it without recursion.” Every attempt from class fails:

Attempt	Counterexample	Problem
`{ A } { B }`	`ABBB` (or `AAABB`)	the two repetition counts are chosen independently
`{ A B }`	`ABAB`	A’s and B’s interleave
`A { A B } B`	`AABABABB`	interleaving inside
`{ A { A B } B }`	`AABBAABB`	blocks repeat

Why every attempt must fail (intuition): repetition cannot count; there is no way to force two separate repetitions to use the same number. Recursion can “remember”, by placing matching symbols on both sides of the recursive call.

Theorem (Expressive power, stated; proof in 3rd semester)

In EBNF, recursion is strictly more powerful than repetition. Every language describable with repetition can also be described with recursion, but some languages, such as ${A^{n} B^{n}}$ , can only be described with recursion.

In programming languages the two are equally powerful. Every recursion can be expressed with loops and vice versa, because a for loop can count (“repeat 10 times, then the same number again”). Sometimes one formulation is just simpler or more elegant.

3.17 History: from BNF to EBNF (Slides)

The original BNF (Backus–Naur, Algol 60 report) has only sequence, selection and recursion.
Niklaus Wirth (ETH Zürich and Xerox PARC) added option and repetition in “What Can We Do about the Unnecessary Diversity of Notation for Syntactic Definitions?”, Communications of the ACM 20(11), November 1977.
These additions are not essential; they only improve readability.

<integer> in BNF, without [ ] and { }:

<sign>    ⟵ + | -
<digit>   ⟵ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<digits>  ⟵ <digit> | <digit> <digits>
<integer> ⟵ ( ε | <sign> ) <digits>

Even the selection | is not needed. The slide asks: what instead? Answer: several rules with the same LHS, each one an alternative.

<sign>    ⟵ +
<sign>    ⟵ -
<digit>   ⟵ 0
   ⋮
<digit>   ⟵ 9
<digits>  ⟵ <digit>
<digits>  ⟵ <digit> <digits>
<integer> ⟵ <digits>
<integer> ⟵ <sign> <digits>

4. Worked Examples & Applications

Example: Classify strings (slide 36)

Rule: <number> ⟵ [ + | - ] { <digit> }

String Legal? Reason
4 yes option deselected, 1 repetition
+9 yes
-09 yes leading zero, but syntax doesn’t care
-0 yes
+ yes zero repetitions
- yes zero repetitions
ε yes option deselected and zero repetitions
+-6 no the option is chosen once; the sign is not repeatable
7- no order matters: the sign must come first
+- no

String	Legal?	Reason
`4`	yes	option deselected, 1 repetition
`+9`	yes
`-09`	yes	leading zero, but syntax doesn’t care
`-0`	yes
`+`	yes	zero repetitions
`-`	yes	zero repetitions
ε	yes	option deselected and zero repetitions
`+-6`	no	the option is chosen once; the sign is not repeatable
`7-`	no	order matters: the sign must come first
`+-`	no

Example: The two recursion examples (slide 59)

<A> ⟵ a | [ <A> ], direct recursion.

Choose a: the word a.

Choose [<A>] and deselect: ε.

Taking the option only leads back to the same choice.

Language: ${a, ε}$ .

<A> ⟵ a |  and  ⟵ [ <A> ], indirect recursion with start rule . The language is again ${a, ε}$ .

Example: Syntax graph for <integer> (slides 52–53)

Graph: an option box (+ or - or bypass), then one digit with ten parallel branches, then a repetition loop around a second ten-branch digit box with a backward arrow.

Substituting the <digit> graph into the <integer> graph gives the single-rule form
<integer> ⟵ [ + | - ] ( 0 | 1 | … | 9 ) { 0 | 1 | … | 9 }.

Path for 125: bypass the sign box, take the 1 branch, loop twice through the repetition box (2, then 5), exit.

Exam Trap: Zero repetitions

{ X } allows zero repetitions. Always check whether ε, a lone sign, or a lone separator slips into your language.

Exam Trap: Independent choices

Repetitions, and selections inside repetitions, are independent per copy. { <digit> } with 3 repetitions does not force three equal digits, and { ( ' | ε ) D } lets you skip the separator every single time.

Exam Trap: Start rule

Forgetting the course convention: the language is defined by the last rule.

Exam Trap: Unboxed metasymbols

Literal {, }, (, ), [, ], |, <, >, and spaces must be boxed. Unboxed { } means repetition, not braces in the word.

Exam Trap: Recursion without an exit

A recursive rule without a termination option produces the empty language.

Exam Trap: Unfinished derivations

A derivation may only end when no nonterminal and no metasymbol (open selection, option, repetition) remains.

Exam format notes from lecture 2:

Derivation tasks will be on Moodle. The Moodle exercises in week 2–3 practise exactly that format, including boxes for justifications.
Write justifications explicitly in exercises, even though the slides sometimes omit them for space.
EBNF can and very likely will be exam-relevant (student question, lecture 1).

5. Intuition & Conceptual Bridges

Intuition: EBNF as a tiny programming language

EBNF Java
rule names variable and method names (choose descriptive ones)
sequence sequence of statements
selection / option if / else
repetition loops, but without a counter
recursion recursive methods: always need a base case; can be direct or indirect

Just as different programs can compute the same thing, different EBNFs can describe the same language. Writing everything in one rule or splitting it into named parts is a style choice, like introducing variables.

EBNF	Java
rule names	variable and method names (choose descriptive ones)
sequence	sequence of statements
selection / option	`if` / `else`
repetition	loops, but without a counter
recursion	recursive methods: always need a base case; can be direct or indirect

Intuition: Why repetition can't count

A repetition is like a loop while (coinFlip()) { … } with no memory: it cannot know how many times it ran, so it cannot force a second repetition to run equally often. Recursion builds structures from the outside in, placing a matching A and B around the recursive call. That is exactly what nested structures in programming languages need, such as matched brackets and nested blocks.

Intuition: Derivation trees and parsers

A parser reconstructs a derivation tree for your program to decide whether it is syntactically valid. Only then does the compiler consider meaning. In Compiler Design you will build such parsers.

Connections:

Outlook, 3rd semester (Theoretical Computer Science): EBNF without recursion describes the regular languages; with recursion, the context-free languages. ${A^{n} B^{n}}$ is the textbook example of a context-free language that is not regular. This is not exam material now, but it is where “which languages are describable?” leads.
Next week (week 2): first Java programs. The Java Language Specification itself is defined with EBNF plus extra textual rules, e.g. “identifiers must not be keywords”, which EBNF cannot express.
The EBNF exercises (Moodle, same format as the exam theory part) come in the following weeks.

6. Summary & Self-Assessment Questions

Cheat sheet

Notation	Meaning	Number of choices
`<name> ⟵ RHS`	”is defined as”
`E1 E2 E3`	sequence, left to right; order matters
`E1 \| E2 \| E3`	selection	exactly one
`[ E ]`	option, $\equiv E ∣ ε$	0 or 1
`{ E }`	repetition	0, 1, 2, … (finite, can’t be counted)
`( … )`	grouping only, not part of the word
⟦x⟧ (box)	literal metasymbol `x`
␣ or ⟦ ⟧	literal space
ε	empty string
`E { E }`	at least one E
`X { sep X }`	non-empty separated list
`[ X { sep X } ]`	possibly empty separated list
`X [ <self> ]`	recursion with a termination option
`[ A <self> B ]`	matched pairs $A^{n} B^{n}$ ; needs recursion

Key facts:

The last rule is the start rule. Rule order and names are otherwise irrelevant.
A derivation ends only when no nonterminals or metasymbols remain.
Derivation steps: apply a rule, choose an alternative, decide an option, fix a repetition count.
Equivalent descriptions have identical languages.
EBNF describes syntax only; +6 ≠ 6 as words.
Proving derivability: exhibit one derivation. Proving non-derivability: rule out all of them (hard).
In EBNF, recursion is strictly more powerful than repetition. In programming languages they are equally powerful.
BNF has sequence, selection and recursion. Wirth’s EBNF (1977) adds option and repetition.

Self-assessment questions

Question 1. Give the language of <x> ⟵ [ 0 | 1 ] [ 0 | 1 ] explicitly. How many words does it contain?

Solution to Question 1

Each option independently becomes one of ε, 0, 1, so there are $3 \times 3 = 9$ derivations:

εε = ε

ε0 = 0 and ε1 = 1

0ε = 0 and 1ε = 1

00, 01, 10, 11

Duplicates collapse, because a language is a set:
$L = {ε, 0, 1, 00, 01, 10, 11}$
The language has 7 words. Lesson: different derivations can yield the same word.

Question 2. Is <s> ⟵ ( a | b ) { , ( a | b ) } equivalent to <s> ⟵ { ( a | b ) , } ( a | b )? Justify.

Solution to Question 2

Yes.

First description: one element, then $k \geq 0$ copies of “, element”. Its words are exactly the non-empty comma-separated lists $e_{0}, e_{1}, \dots, e_{k}$ with $e_{i} \in {a, b}$ .

Second description: $k \geq 0$ copies of “element ,”, then one element. These are the same strings $e_{0}, e_{1}, \dots, e_{k}$ ; each comma is just attached to its left neighbour instead of its right one.

Choosing the same $k$ and the same elements shows that every word of one description is a word of the other, in both directions. Neither allows ε, a leading comma, or a trailing comma. The grouping of the rule is irrelevant for equivalence.

Question 3. Write an EBNF for canonical natural numbers with thousands separators. Examples: 0, 7, 1'000 and 12'345 are legal; 012, 0'123 and 1'23 are not.

Solution to Question 3
<zero> ⟵ 0
<nonzero> ⟵ 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<digit> ⟵ <zero> | <nonzero>
<group> ⟵ ' <digit> <digit> <digit>
<num> ⟵ ( <nonzero> [ <digit> ] [ <digit> ] { <group> } ) | <zero>
Checking each requirement:

The first group has 1–3 digits and starts with a non-zero digit. So there are no leading zeros, which excludes 012 and 0'123.

Every following group is exactly ' plus 3 digits, which may include zeros (1'000 is legal). This excludes 1'23.

Zero is only derivable through the separate alternative <zero>. Without it, 0 would not be derivable; this is the same trap as in §3.4.

No word starts or ends with ', because ' only ever appears directly before 3 digits.

Question 4. Write the derivation table for {1,2} using the <integer_set> description of §3.6.

Solution to Question 4

Step Current string Justification
0 ⟦{⟧ [ <integer_list> ] ⟦}⟧ start rule <integer_set> (last rule)
1 ⟦{⟧ <integer_list> ⟦}⟧ option taken
2 ⟦{⟧ <integer> { , <integer> } ⟦}⟧ rule <integer_list>
3 ⟦{⟧ <integer> , <integer> ⟦}⟧ repetition: 1 time
4 ⟦{⟧ [ + | - ] <digit> { <digit> } , <integer> ⟦}⟧ rule <integer>, first occurrence
5 ⟦{⟧ <digit> { <digit> } , <integer> ⟦}⟧ option not taken
6 ⟦{⟧ <digit> , <integer> ⟦}⟧ repetition: 0 times
7 ⟦{⟧ ( 0 | 1 | … | 9 ) , <integer> ⟦}⟧ rule <digit>
8 ⟦{⟧ 1 , <integer> ⟦}⟧ selection 1
9 ⟦{⟧ 1 , [ + | - ] <digit> { <digit> } ⟦}⟧ rule <integer>, second occurrence
10 ⟦{⟧ 1 , <digit> { <digit> } ⟦}⟧ option not taken
11 ⟦{⟧ 1 , <digit> ⟦}⟧ repetition: 0 times
12 ⟦{⟧ 1 , ( 0 | 1 | … | 9 ) ⟦}⟧ rule <digit>
13 { 1 , 2 } selection 2; the boxed braces are now ordinary characters

Each step does exactly one thing (rule, selection, option or repetition), as the exam expects.

Step	Current string	Justification
0	`⟦{⟧ [ <integer_list> ] ⟦}⟧`	start rule `<integer_set>` (last rule)
1	`⟦{⟧ <integer_list> ⟦}⟧`	option taken
2	`⟦{⟧ <integer> { , <integer> } ⟦}⟧`	rule `<integer_list>`
3	`⟦{⟧ <integer> , <integer> ⟦}⟧`	repetition: 1 time
4	`⟦{⟧ [ + \| - ] <digit> { <digit> } , <integer> ⟦}⟧`	rule `<integer>`, first occurrence
5	`⟦{⟧ <digit> { <digit> } , <integer> ⟦}⟧`	option not taken
6	`⟦{⟧ <digit> , <integer> ⟦}⟧`	repetition: 0 times
7	`⟦{⟧ ( 0 \| 1 \| … \| 9 ) , <integer> ⟦}⟧`	rule `<digit>`
8	`⟦{⟧ 1 , <integer> ⟦}⟧`	selection `1`
9	`⟦{⟧ 1 , [ + \| - ] <digit> { <digit> } ⟦}⟧`	rule `<integer>`, second occurrence
10	`⟦{⟧ 1 , <digit> { <digit> } ⟦}⟧`	option not taken
11	`⟦{⟧ 1 , <digit> ⟦}⟧`	repetition: 0 times
12	`⟦{⟧ 1 , ( 0 \| 1 \| … \| 9 ) ⟦}⟧`	rule `<digit>`
13	`{ 1 , 2 }`	selection `2`; the boxed braces are now ordinary characters

Question 5. Give an EBNF for $L = {A^{n} B^{2 n} ∣ n \geq 0}$ . Then explain why { A } { B B } is not a correct answer.

Solution to Question 5
Recursive solution:
<x> ⟵ [ A <x> B B ]
Each recursive step adds exactly one A in front and exactly two Bs at the back, so the ratio $1 : 2$ always holds. Deselecting the option ends the recursion and produces ε, the word for $n = 0$ .

Derivation for $n = 2$ :

A <x> B B

A A <x> B B B B

AABBBB (option deselected)

Why { A } { B B } is wrong: the two repetition counts are chosen independently. For example, 1 and 2 repetitions give ABBBB, which is not in $L$ . The description over-generates: it describes
${A^{i} B^{2 j} ∣ i, j \geq 0} ⊋ L .$
No recursion-free EBNF can describe $L$ , because repetition cannot couple counts. The argument is the same as for $A^{n} B^{n}$ .

Vedant's ETH Notes

Explorer

Week 1 EBNF (Extended Backus–Naur Form)

1. Executive Overview & Core Objectives

2. Core Concepts & Formal Definitions

2.1 Motivation (Slides 1.1)

2.2 EBNF descriptions and rules (Slides 1.2)

2.3 Control form 1: Sequence (Slides 1.3.1)

2.4 Control form 2: Decision (Slides 1.3.2)

2.5 Control form 3: Repetition (Slides 1.3.3)

2.6 Language of an EBNF description and the start rule

2.7 Special characters (Sonderzeichen)

2.8 Derivations (Slides 1.4)

2.9 Equivalence of EBNF descriptions

2.10 Syntax vs. semantics

2.11 Control form 4: Recursion (Slides 1.6)

2.12 Graphical representation: syntax graphs (Slides 1.5)

3. Step-by-Step Derivations & Constructions

3.1 Same language, different descriptions

3.2 Selection and option

3.3 Integers of arbitrary length

3.4 Canonical integers (kanonische Zahlen): no leading zeros

3.5 Numbers with thousands separators (lecture 2 clicker question)

3.6 Integer sets (Zahlenmengen)

3.7 Derivation of -4 as a table (slides)

3.8 Derivation of -4 as a tree (slides)

3.9 Derivation of 6: deselecting the option

3.10 Derivation of 284 (repetition) as a tree

3.11 A failed derivation attempt: A15 (slides)

3.12 Derivation of {5, -2, 11} (slides)

3.13 Recursion: the endless story

3.14 Recursion: natural numbers

3.15 Derivation of AAB with recursion (slides)

3.16 Recursion vs. repetition: {AnBn∣n∈N}

3.17 History: from BNF to EBNF (Slides)

4. Worked Examples & Applications

5. Intuition & Conceptual Bridges

6. Summary & Self-Assessment Questions

Cheat sheet

Self-assessment questions

Graph View

Table of Contents

3.7 Derivation of `-4` as a table (slides)

3.8 Derivation of `-4` as a tree (slides)

3.9 Derivation of `6`: deselecting the option

3.10 Derivation of `284` (repetition) as a tree

3.11 A failed derivation attempt: `A15` (slides)

3.12 Derivation of `{5, -2, 11}` (slides)

3.15 Derivation of `AAB` with recursion (slides)

3.16 Recursion vs. repetition: ${A^{n} B^{n} ∣ n \in N}$