Syntax Analysis and Parsing in Compiler Design

The Role of the Parser

• Syntax analysis or parsing is the second phase of a compiler
• Parsing is the process of finding a parse tree for a string of tokens
• A parser verifies whether a string of tokens belongs to the language generated by a given grammar
• A parser creates a parse tree if the input sentence is syntactically correct
• If the input sentence is not syntactically correct, the parser produces a syntax error

Types of Parsers

• Top-down parser (LL parser)
  • Builds parse trees from top (root) to bottom (leaves)
  • Scans the input string from left to right
  • Performs left-most derivation
• Bottom-up parser (LR parser)
  • Builds parse trees from leaves to root
  • Scans the input string from left to right
  • Performs right-most derivation

Context Free Grammar

• A context-free grammar (CFG) is recognized by push-down automata
• A CFG has four components: G={V,P,Σ,S}
  • V: set of non-terminals (syntactic variables)
  • P: set of productions (specify how terminals and non-terminals combine to form strings)
  • Σ: set of tokens (terminal symbols)
  • S: start symbol (where production begins)

Productions

• Each production consists of a non-terminal (left side) and a sequence of tokens and/or non-terminals (right side)
• Production rule: Non-terminal → Non-terminals. (Or) Non-terminal → terminals
• Example: A → β A1 and A1 → α A1 | ε

Eliminating Left-Recursion

• Example: Eliminating left-recursion for the grammar E → E+T|T, T → T*F|F, F → (E)|id
• Apply the formula A → β A' and A' → αA' | ε to eliminate left-recursion