Parsers

Parser turns a sequence of tokens (usually produced by the Lexer|lexer) into a tree representation called a syntax tree (not be to be confused with AST).

A parser relies on a grammar. Regular expressions can't express operator precedence, so Context-Free Grammar is needed. CFG grammars have a single nonterminal symbol on the left side of a production rule. They are often specified in a Backus-Naur Form.

Parsing can happen top-down (recursive descent, LL) or bottom-up (LR). LL parsers generate leftmost derivation and LR rightmost in reverse.

LL(1) means: Left-to-right, leftmost derivation, single lookahead token. LL and recursive descent can't handle left recursion in production rules, e.g. Sum ::= Sum '+' Int | Int. In practice it can be solved by using a loop in a recursive descent parser.

Many industrial compilers use recursive descent parsers.

Representing expressions in BNF is not straight forward. Recursive descent parser is often paired with a bottom-up Pratt parser to efficiently parse operator precedence.

Bison, Yacc, and ANTLR are examples of parser generators. They usually generate bottom-up parsers, like LR.

Recursive descent code example 

std::unique_ptr<BlockNode> parseBlock() {
  expect(Token::Kind::LeftCurly);
  getNextToken();

  std::vector<std::unique_ptr<Node>> statements;
  while (true) {
    if (auto statement = parseStatement()) {
      statements.push_back(std::move(statement));
    } else {
      break;
    }
  }

  expect(Token::Kind::RightCurly);
  getNextToken();

  return std::make_unique<BlockNode>(std::move(statements));
}

Links

AST (Abstract Syntax Trees)