Difference between revisions of "Context-free grammar"
Jump to navigation
Jump to search
m (moved Context-Free Grammar to Context-free grammar) |
(add cross-reference to Backus-Naur Form) |
||
| Line 1: | Line 1: | ||
| + | ''An equivalent grammar [[Backus-Naur Form]] is often used for describing the syntax/grammar of programming languages.'' | ||
| + | |||
A '''Context-Free''' Grammar is a tuple (T, V, S, P); | A '''Context-Free''' Grammar is a tuple (T, V, S, P); | ||
T is a set of atomic symbols. | T is a set of atomic symbols. | ||
| Line 23: | Line 25: | ||
::real-number → part . part | ::real-number → part . part | ||
:} | :} | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
[[category:linguistics]] | [[category:linguistics]] | ||
[[Category:Computer Science]] | [[Category:Computer Science]] | ||
Revision as of 19:38, May 14, 2012
An equivalent grammar Backus-Naur Form is often used for describing the syntax/grammar of programming languages.
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
- }