Grammar Generation
To generate a string in the language, one begins with a string consisting of only a single start symbol, and then successively applies the rules (any number of times, in any order) to rewrite this string. This stops when we obtain a string containing only terminals. The language consists of all the strings that can be generated in this manner. Any particular sequence of legal choices taken during this rewriting process yields one particular string in the language. If there are multiple different ways of generating this single string, then the grammar is said to be ambiguous.
For example, assume the alphabet consists of and, with the start symbol, and we have the following rules:
- 1.
- 2.
then we start with, and can choose a rule to apply to it. If we choose rule 1, we replace with and obtain the string . If we choose rule 1 again, we replace with and obtain the string . This process is repeated until we only have symbols from the alphabet (i.e., and ). If we now choose rule 2, we replace with and obtain the string, and are done. We can write this series of choices more briefly, using symbols: . The language of the grammar is the set of all the strings that can be generated using this process: .
Read more about this topic: Production (computer Science)
Famous quotes containing the words grammar and/or generation:
“Syntax is the study of the principles and processes by which sentences are constructed in particular languages. Syntactic investigation of a given language has as its goal the construction of a grammar that can be viewed as a device of some sort for producing the sentences of the language under analysis.”
—Noam Chomsky (b. 1928)
“Society in America means all the honest, kindly-mannered, pleasant- voiced women, and all the good, brave, unassuming men, between the Atlantic and the Pacific. Each of these has a free pass in every city and village, good for this generation only, and it depends on each to make use of this pass or not as it may happen to suit his or her fancy.”
—Henry Brooks Adams (18381918)