Context-Free Grammar

From Conservapedia

A Context-Free Grammar is a tuple (T, V, S, P); T is a set of atomic symbols. V is a set of variables. S is a special start symbol. P is a set of productions, each production describes how to produce a variable using a sequence of tokens and variables.

For example, a Context-Free Grammar for the real numbers would be:

T = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, .}

V = {real-number, part, digit}

S = real-number

P = { digit → 0

digit → 1

digit → 2

digit → 3

digit → 4

digit → 5

digit → 6

digit → 7

digit → 8

digit → 9

part → digit

part → digit part

real-number → part . part

}

Or in Backus-Naur notation:

<real-numbers> → <part> . <part>

<part> → <digit> | <digit> <part>

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

The Backus-Naur form was discovered independently in the late 1950s by John Backus and Noam Chomsky.