Context-free Grammars and Parsers
A parser is an important component of a compiler. It parses the source code of a computer programming language to create some form of internal representation. Programming languages tend to be specified in terms of a context-free grammar because fast and efficient parsers can be written for them. Parsers can be written by hand or generated by a parser generator. A context-free grammar provides a simple and precise mechanism for describing the block structure of a program – that is, how programming language constructs are built from smaller blocks. The formalism of context-free grammars was developed in the mid-1950s by Noam Chomsky.
Block structure was introduced into computer programming languages by the ALGOL project (1957–1960), which, as a consequence, also featured a context-free grammar to describe the resulting ALGOL syntax.
Context-free grammars are simple enough to allow the construction of efficient parsing algorithms which, for a given string, determine whether and how it can be generated from the grammar. If a programming language designer is willing to work within some limited subsets of context-free grammars, more efficient parsers are possible.
Read more about this topic: History Of Compiler Construction
Famous quotes containing the word grammars:
“The violent illiteracies of the graffiti, the clenched silence of the adolescent, the nonsense cries from the stage-happening, are resolutely strategic. The insurgent and the freak-out have broken off discourse with a cultural system which they despise as a cruel, antiquated fraud. They will not bandy words with it. Accept, even momentarily, the conventions of literate linguistic exchange, and you are caught in the net of the old values, of the grammars that can condescend or enslave.”
—George Steiner (b. 1929)