Differences
This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
|
notes_on_context-free_grammars [2007/03/17 20:24] vkuncak created |
notes_on_context-free_grammars [2007/03/18 17:11] vkuncak |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | Here is general information on [[wk>Context-free Grammar|Wikipedia]]s. | + | Here is general information on [[wk>Context-free Grammar]]s. |
| Typically, in a context-free grammar one can have multiple productions of the form | Typically, in a context-free grammar one can have multiple productions of the form | ||
| Line 15: | Line 15: | ||
| N ::= w1 | w2 | N ::= w1 | w2 | ||
| M ::= w3 | w4 | w5 | M ::= w3 | w4 | w5 | ||
| + | |||
| + | Note that, when we write, for example, | ||
| + | |||
| + | N ::= a | N + N | ||
| + | |||
| + | the two occurrences of N in "N + N" need not denote the same expression, they merely denote two subexpressions both of which conform to the syntax defined by N. Sometimes, to make this clear and to make it possible to refer to individual occurrences, we can write subscripts, as in | ||
| + | |||
| + | N ::= a | N_1 + N_2 | ||
| + | |||
| + | using the convention that N_i denotes the same set of strings as N. | ||