The process of deciding whether a string of input symbols is a sentence of a given language and if so determining the syntactic structure of the string as defined by a grammar (usually context-free) for the language. This is achieved by means of a program known as a parser or syntax analyser. For example, a syntax analyser of arithmetic expressions should report an error in the string
since the juxtaposition of the minus and plus operators is invalid. On the other hand the string
is a valid arithmetic expression with structure specified by the statement that its subexpressions are
(Note that 2–3 is not a subexpression.)
The input to a parser is a string of tokens supplied by a lexical analyser. Its output may be in the form of a parse tree or a derivation sequence. See also bottom-up parsing, precedence parsing, top-down parsing.