Lexical Analysis - Parser (Syntax analysis|Linter)


A parser create a parse tree data structure from a series of token created by the lexer.

The creation of the tree is based on the rules declared in the grammar (which defines the syntactic structure of the source).

A parser is generally generated from the grammar. See Language - Compiler compilers or (lexer|parser) generators

A parser is the component of a compiler that deals with the recursively nested features such as expressions arithmetic, conditional, and so on). Example of recursive grammatical rule a = a + a

Parsing is done generally at the token level but can be done at the character level when the lexer and parser are done in one step: See Scannerless parsing

Syntax analysis is also known as Sentence recognition

Additional step can be added to the parse phase in order to construct an Abstract Syntax Tree (AST) from the parse tree.

The term parsing comes from Latin pars (orationis), meaning part (of speech)


A syntax analyzer would check:



To construct the tree, we have many choices for selecting nodes, which can lead to the leaves to correspond to the input sequence seen so far.

method of construction:

  • LR parsing: a bottom up approach. The tree is build from the leaves.
  • LL parsing: a top down approach. The tree is build from the root.



Example of parsing algorithm

Error recovery

Documentation / Reference

Powered by ComboStrap