# Computing - Backus-Naur Form

> Source: https://ollybritton.com/notes/a-level/computing/topics/backus-naur-form/ · Updated: 2024-08-25 · Tags: computing, regular-languages

##### What is Backus-Naur Form??
A formal notation used to describe the syntax rules of a language.

##### What type of languages can't be expressed by a regular expression??
Context-free languages.

##### What does `::=` mean in BNF??
Is defined as.

##### What does `|` mean in BNF??
Or.

##### What does `<>` mean in BNF??
Specifys a category.

##### What do two symbols side by side mean in BNF??
That one symbol must follow the other.

##### What is a terminal symbol in BNF??
A symbol that can't be broken further down.

##### What is a non-terminal symbol in BNF??
A symbol that can be further broken down.

##### What does it look like to define a "digit" category in BNF??
```
<digit> ::= 0|1|2|3|4|5|6|7|8|9
```
##### How would you define a `postcode` category as two `upper`case letters followed by two `digits`??
```
<postcode> ::= <upper><upper><digit><digit>
```

##### In `ab|cd`, is it `ab OR cd` or `a (b OR c) d`??
```
ab OR cd
```

##### Why is BNF used for programming languages??
Because the instructions for a computer must not be ambiguous in any way.

##### What is a single BNF statement called??
A production rule.

### 2021-01-21
##### How could you write a `<number>` category that's made of a `<digit>`??
```
<number> ::= <digit>|<digit><number>
```

##### ![PHOTO PRODUCTION RULES EXAMPLE](paste-3c2b3000bc22a461a5eeaf8bc4e9ed105f7b8a57.jpg) What does $1234$ match??
- `value`
- `term`

##### ![PHOTO PRODUCTION RULES EXAMPLE](paste-3c2b3000bc22a461a5eeaf8bc4e9ed105f7b8a57.jpg) What does $0 + A$ match??
- `sum`

##### ![PHOTO PRODUCTION RULES EXAMPLE](paste-3c2b3000bc22a461a5eeaf8bc4e9ed105f7b8a57.jpg) What does $XY$ match??
Nothing, not defined.

##### ![PHOTO PRODUCTION RULES EXAMPLE](paste-3c2b3000bc22a461a5eeaf8bc4e9ed105f7b8a57.jpg) What does $X + Y + 3 + 1$ match??
- `sum`

---
Olly Britton — https://ollybritton.com. Machine-readable index: https://ollybritton.com/llms.txt