Lexical Analysis - Parser (Syntax analysis|Linter)


A parser takes a token stream (emitted by a lexical analyzer) as input and based on the rules declared in the grammar (which define the syntactic structure of the source) produces a parse tree data structure.

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 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:

  • the syntax
  • the type correctness


  • Language - Linter (Code Analysis, Validation)


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 on the subject:

  • Josef Grosch. Efficient and comfortable error recovery in recursive descent parsers. Structured Programming, 11(3):129–140, 1990.
  • Rodney W. Topor. A note on error recovery in recursive descent parsers. SIGPLAN Not., 17(2):37–40, 1982.
  • Niklaus Wirth. Algorithms + Data Structures = Programs. Prentice Hall PTR, Upper Saddle River, NJ, USA, 1978.

Documentation / Reference

Powered by ComboStrap