Parser

A parser reads the token stream (mostly generated by the lexer) and matches (phrases) it against parser rules. The output is usually an Abstract Syntax Tree (AST). Each matched phrase could also result in some custom action being taken.

The AST does not contain all the information from the source, such as parentheses, etc. This information may be present in the concrete syntax tree. A parser may produce either an AST or a concrete syntax tree, based on ruled defined (?)?

ANTLR's AST processing is pretty powerful. We can write tree grammar, which will generate a tree parser which can contain custom actions, or String template output statements.

In some implementations the parsing stage may not produce an AST at all. We may build custom actions, which could be performed in the parsing stage.