Ad Block Detected!

Our website is made possible by displaying ads to our visitors. Please support us by whitelisting our website or allowing necessary trackers.

What is Backus-Naur Form?

Backus-Naur form (BNF) is a notation used to formally describe the syntax of programming languages. It ensures that the language's rules are clearly defined so that a computer can easily parse the source code.

Additionally, regular expressions are not always sufficient for defining certain languages. Therefore, Backus-Naur form serves as a robust metalanguage.

Diagram illustrating Backus-Naur form

Example 1

<DIGIT> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6

This definition specifies that a digit can be any value from 0 to 6.

Example 2

<LETTER> ::= A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

This definition specifies that a letter can be any character from A to Z.

<WORD> ::= <LETTER><LETTER>

This rule defines a word as two letters. For instance, "W" and "WE" are valid words, while "GOING" is not, as it consists of more than two letters.

Recursion in Backus-Naur Form

Instead of defining new rules for each letter, recursion allows us to generalize rules. Here’s how recursion is used:

<LETTER> ::= A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

A "LETTER" can be any character from A to Z.

<WORD> ::= <LETTER> | <LETTER><WORD>

This recursive definition means that a word can be a single letter or a letter followed by another word.

This process of analyzing a statement using these rules is known as parsing.

Syntax Diagram

Backus-Naur syntax diagram

For more information on regular expressions, click here. To explore other topics, click here.