Define a context-free language.
A set of strings and symbols which follow the rules of context-free grammar.
Define context-free grammar.
Context free grammars describe which strings are and not possible by laying out production rules.
Define production rules.
The replacement of one character with another.
E.g. a → aba → aab → a
What is BNF used for?
Notation of context-free languages.
Describe the basic structure of BNF expressions.
E.g. <FullName> ::= <Title><Forename><Surname>
- Left hand side if defined by the right hand side.
- Each component is a non-terminal or a terminal value.
Define BNF non-terminal.
Text which is placed inside of angle brackets which can be broken down further into either more non-terminals, terminals or a combination of the two.
E.g. <FullName> ::= <Title><Forename><Surname>
Define BNF terminal.
Text without any brackets, which cannot be broken down any further and must be taken to be the written value.
E.g. <Number> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
- Number is a non-terminal which is defined by nine terminals from 1 to 9.
- The pipe symbol, which looks like a straight vertical line, represents the OR operator.
Explain why you would use BNF over regular expressions
BNF can represent some languages which cannot be represented by expressions, because only BNF supports recursion, which allows for more complex definitions.
Describe in plain English this BNF definition:
<Integer> ::= <Digit>|<Digit><Integer> <Digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
An integer is defined as a digit or as a digit followed by an integer” and “A digit is defined as one the the numbers from 0 to 9”.
Define syntax diagrams
A syntax diagram is a visual representation of a regular language. Where rectangles represent non-terminals and ellipses represent terminals.
Draw a syntax diagram for this BNF definition:
<Integer> ::= <Digit>|<Digit><Integer> <Digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
