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 wiki/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.


Compiler - LL parser


Compiler - LR parser

Example of parsing algorithm

Error recovery

See Compiler - Error Recovery

Documentation / Reference

Discover More
Card Puncher Data Processing
Antlr (ANother Tool for Language Recognition)

ANTLR is lexer generator. It translates: a grammar to a lexer and parser. ANTLR is implemented in Java and generates lexer and parser in the following languages: Java, Ruby, Python, C,...
Card Puncher Data Processing
Antlr - Parser

in Antlr. The parser is a generated class that is build from the grammar (specifically from the parser rule of the grammar). The job of the parser is to create a parse tree from: a parser start rule...
Card Puncher Data Processing
Code - (Programming|Computer) Language

how the language is structured (grammar), how to name things you want to talk (vocabulary), and the customary and effective ways to say everyday things (usage). ...Grammarvocabularycommunity...B00B8V09HYEffective...
Compiler (Parser/Lexer) - Exception handling

exception handling in a parser. By default, parser will stop matching on any failure. But they may have a sort of recovery mode that allows to define an alternate rule or match . For idea, it's...
Compiler - Code generation

Code generation is one of the last compiler step. The process takes a parse tree (generally an AST) created by the parser and turns it into a sequence of instructions. In general it is the most involved...
Compiler - LL parser

An LL(k) parser is a type of parser that build the tree in a top-down way. LR approach It is a top-down parser that parses from left to right, constructs a leftmost derivation of the input ...
Compiler - LR parser

LR is a type of parser that build the tree from the leaves (bottom-up). LL parser LR(k) means:Left to right,Rightmost derivation parser. LR(k), is: a bottom-up parser that parses from left to...
Compiler - Parser Rule

A parser rule is a rule that defines the structure of the parse tree. The parser uses them to build the parse tree. lexer rulestokenstree Parser rule names always start with a lowercase letter (...
Compiler - Semantics Analysis

Semantic analysis is the phase in which the compiler: adds semantic information to the parse tree builds the symbol table. This phase performs semantic checks such as: type checking (checking...
Computer Language - (Compiler|Interpreter) - Language translator

Computer Language are written in plain text. However, computers interpret only particular sequence of instructions. This transformation from a plain text language to instructions is called compilation...

Share this page:
Follow us:
Task Runner