Difference between revisions of "Context-free grammar"
Jump to navigation
Jump to search
| Line 23: | Line 23: | ||
::real-number → part . part | ::real-number → part . part | ||
:} | :} | ||
| − | |||
Or in '''Backus-Naur notation''': | Or in '''Backus-Naur notation''': | ||
| Line 29: | Line 28: | ||
:<part> → <digit> | <digit> <part> | :<part> → <digit> | <digit> <part> | ||
:<digit> → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | :<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]]. | ||
[[category:linguistics]] | [[category:linguistics]] | ||
[[category:computer science]] | [[category:computer science]] | ||
Revision as of 19:01, May 31, 2007
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.