Computing - Backus-Naur Form

What Backus-Naur Form is

What is Backus-Naur Form?

bnf-definition

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-not-regular

Context-free languages.

BNF notation symbols

What does ::= mean in BNF?

bnf-defined-as-symbol

Is defined as.

What does | mean in BNF?

bnf-or-symbol

Or.

What does <> mean in BNF?

bnf-angle-brackets-category

Specifies a category.

What do two symbols side by side mean in BNF?

bnf-concatenation-meaning

That one symbol must follow the other.

Terminal and non-terminal symbols

What is a terminal symbol in BNF?

bnf-terminal-symbol

A symbol that can’t be broken further down.

What is a non-terminal symbol in BNF?

bnf-non-terminal-symbol

A symbol that can be further broken down.

Writing production rules

What does it look like to define a “digit” category in BNF?

bnf-digit-category-rule

<digit> ::= 0|1|2|3|4|5|6|7|8|9

How would you define a postcode category as two uppercase letters followed by two digits?

bnf-postcode-category-rule

<postcode> ::= <upper><upper><digit><digit>

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

bnf-concatenation-precedence

ab OR cd

Why BNF is used

Why is BNF used for programming languages?

bnf-unambiguous-rationale

Because the instructions for a computer must not be ambiguous in any way.

What is a single BNF statement called?

bnf-production-rule-name

A production rule.

How could you write a <number> category that’s made of a <digit>?

bnf-recursive-number-rule

<number> ::= <digit>|<digit><number>

Matching strings against production rules

What does $1234$ match?

bnf-match-1234

value
term

What does $0 + A$ match?

bnf-match-zero-plus-a

sum

What does $XY$ match?

bnf-match-xy-undefined

Nothing, not defined.

What does $X + Y + 3 + 1$ match?

bnf-match-x-plus-y-plus-3-plus-1

sum