Procedures

Classically, parsing involves three stages:

1. Tokenisation: A practical question in parsing is known as `lexical pre-processing', `lexical analysis' or `tokenisation'; it deals with the identification of the symbols themselves. Symbols generally consist of characters, which have to be identified before the actual parsing can take place. Tokenisation is a kind of lexical lookup.
2. Syntactic analysis: The tokenised input string is matched with the grammar by the interpreter, based on a particular parsing algorithm.
3. Parse (tree) construction: Based on the parse results, a parse tree (or related structure) is constructed.

In a practical implementation, the three stages may be performed serially or linked incrementally.