Motivation
Why programming is important and why you should care.
First and foremost the importance of programming cannot be denied. Programs, applications and electronic devices are part of our everyday life more than ever. This course is not a Java course, it serves the purpose to teach you the basics and underlying fundamentals of all programming languages. Java is simply a tool used to illustrate the topics discussed and to practice programming.
The lecture "Einführung in die Programmierung" is often underestimated by students. No matter your previous knowledge it is recommended to follow the lecture, to practice with the given exercises and to participate in the exercise class. The lecture tends to start of easier than other lectures, but it will get more difficult over time and it might be to late to catch up at that point. If you feel that the material is not challenging you enough reach out to us and we can give you additional material.
EBNF
Extended Backus-Naur Form
Humans are extremely good at recognising but quickly reach their limit when it comes to processing. A computer is the exact opposite. A computer is extremely good at processing, it however is also to recognise most inputs given to it. A computer requires input that follows a strict set of rules. A human quickly recognises a sentence like "Bred go get stor and aple now." even though it is grammatically and incorrect and contains spelling mistakes. A computer is not able to do this, at least not without further assistance.
We hence require a program which tells the computer to do something to follow a set of rules. This set of rules is what we call the syntax. The lecture introduces EBNF which is a tool to describe the syntax of a language. Having a quick look at the Java documentation one can see that EBNF-like syntax description language is used to define the Java language itself. Understanding EBNF is valuable for lectures in the coming semester, for example Formal Methods and Functional Programming where it is assumed that one understands how to read syntax rules.
EBNF
Definition
LHS <= RHS
<digit_9> <= 9
digit_9 <= 9
The definition symbol <= is used to define rules in the syntax declaration of EBNF. The left hand side (LHS) describes the name of the rule and the right hand side (RHS) gives a description of the rule.
We write rules in cursive or use the brackets < and > to allow to differentiate between EBNF rules and potential strings of characters which themselves are not rules.
EBNF
Sequence I
We assume that the known alphabet, numbers and other characters are defined and use these to further define the rules of the language we define using EBNF. The first of four control forms is given by the sequence. A sequence allows us to put multiple characters after each other (in a sequence). The order of the sequence is important and we read the sequence from left to right. Whitespaces are ignored.
We can also use sequence with previously defined rules, which will put the result of each rule evaluation in sequence.
<eleven> <= 1 1
<number_98> <= 9 8
<concat_11_98> <= <eleven> <number_98>
EBNF
Sequence II
<number_2> <= 2
<number_8> <= 8
<room> <= <number_2> <number_8>
There are multiple ways to define a certain result and no singular rule can be determined which is the best. The correctness of a rule is more important than it being short and concise. It may be easier to determine whether a rule is correct or not if the rule is split into multiple subrules.
<room> <= 2 8
EBNF
Option I
<room> <= D 2 8 | E 1 2
<room> <= (D 2 8) | (E 12)
One may have noticed that writing a new rule for every single number is cumbersome. We would like to avoid this. This is why we introduce the choice operator | as the second control form. It allows to choose between given options separated by | and select exactly one of them. This allows us to write more general rules.
One can use brackets to avoid confusion. However the sequence takes precedence over the option control form. Hence it is clear even without brackets, but it helps when one uses brackets, as it is more readable that way.
<digit> <= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
EBNF
Selection
<room> <= D 2 8 | E 1 2
<room> <= (D 2 8) | (E 12)
One may have noticed that writing a new rule for every single number is cumbersome. We would like to avoid this. This is why we introduce the selection operator | as the second control form. It allows to select exactly one of the given symbols separated by |. This allows us to write more general rules.
One can use brackets to avoid confusion. However the sequence takes precedence over the selection control form. Hence it is clear even without brackets, but it helps when one uses brackets, as it is more readable that way.
<digit> <= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<my_number> <= (+ 4 1 | 0) (7 9 6 0 8 5 8 5 6)
EBNF
Option I
<sign> <= [+ | -]
We have seen before that the selection requires exactly one symbol to be chosen. This means that we must choose one. Sometimes we would like to choose none of symbols, or leave out a subrule completely. For this purpose we introduce the option control form. Anything we put between brackets [ and ] we have a choice over using or not.
<initials> <= A [D] Z
EBNF
Option II
<sign> <= [+ | -]
We can replace the usage of the option control form by allowing for an empty symbol. It is preferred to use the option control form. The empty symbol is represented by the Greek letter epsilon ε. We can the replace the brackets [ and ] of the option control form by allowing to select the empty symbol ε.
<sign> <= + | - | ε
EBNF
Repetition I
<numbers> <= {<digit>}
Using the control forms we have seen until now a rule can only allow a finite number of words in our language. The repetition control form enables us to allow an infinite number of words, such as all odd, all even numbers, all strings ending in 'a', and many more. We put the anything to be repeated zero, one, or many times between the brackets { and }.
<integer> <= <sign> <numbers>
EBNF
Repetition II
Repetition allows for much more general rules, it however also introduces complexity in the form of making it more difficult to decide whether a rule is correct or not.
In the example above the rule <integer> allows the empty symbol, as we have the option to choose no sign and we can repeat the <digit> rule zero times. The empty symbol is not an integer however. We must thus fix the given rule by forcing at least one digit to be chosen in any case.
<integer> <= <sign> <digit> <numbers>
EBNF
Repetition III
One can see that the above EBNF rule does not allow the empty symbol anymore. It however allows words like 01 and 007. One understands that 01 represents 1 and 007 represents 7, we however want our rules to leave as little up to interpretation as possible. We hence introduce a special <digit_no_zero> rule to avoid this.
<digit_no_zero> <= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<digit> <= 0 | <digit_no_zero>
<numbers> <= {<digit>}
<integer> <= 0 | (<sign> <digit_no_zero> <numbers>)
EBNF
Legal Words
A word is legal according to some rule if it can be derived from it without leaving any rules unused. We compare symbols in the given words from left to right with the given elements of the EBNF rule. If at the end all symbols have been produced by the EBNF rule and there are no more (non-optional) elements left a symbol is legal. We will look at techniques to informally prove this legality of a word next week.