A parser is a program that converts a linear string of input words into a structured representation that shows how the phrases (substructures) are related and shows how the input could have been derived according to the grammar of the language.
Finding the correct parsing of a sentence is an essential step towards extracting its meaning.
Natural languages are harder to parse than programming languages; the parser will often make a mistake and have to fail and back up: parsing is search. There may be hundreds of ambiguous parses, most of which are wrong.
Parsers are generally classified as top-down or bottom-up, though real parsers have characteristics of both.
There are several well-known context-free parsers: