In computer science and linguistics, parsing (more formally: syntactic analysis) is the process of analyzing a sequence of tokens to determine grammatical structure with respect to a given (more or less) formal grammar. A parser is thus one of the components in an interpreter or compiler, where it captures the implied hierarchy of the input text and transforms it into a form suitable for further processing (often some kind of parse tree, abstract syntax tree or other hierarchical structure) and normally checks for syntax errors at the same time. The parser often uses a separate lexical analyser to create tokens from the sequence of input characters. Parsers may be programmed by hand or may be semi-automatically generated (in some programming language) by a tool (such as Yacc) from a grammar written in Backus-Naur form.Parsing is also an earlier term for the diagramming of sentences of natural languages, and is still used for the diagramming of inflected languages, such as the Romance languages or Latin.Parsers can also be constructed as executable specifications of grammars in functional programming languages. Frost, Hafiz and Callaghan [1] have built on the work of others to construct a set of higher-order functions (called parser combinators) which allow polynomial time and space complexity top-down parser to be constructed as executable specifications of ambiguous grammars containing left-recursive productions.
This information is from Wikipedia, distributed under the GNU Free Documentation license
