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:
“A sure proportion of rogue and dunce finds its way into every school and requires a cruel share of time, and the gentle teacher, who wished to be a Providence to youth, is grown a martinet, sore with suspicions; knows as much vice as the judge of a police court, and his love of learning is lost in the routine of grammars and books of elements.”
—Ralph Waldo Emerson (1803–1882)