Syntax Analysis

The parser takes tokens and checks that they form a valid sentence of the grammar, producing a parse tree (or syntax tree).

Text

Parsers
├── Top-down:  Recursive descent (with backtracking), Predictive / LL(1)
└── Bottom-up: Shift-reduce → Operator precedence, LR(0), SLR(1), LALR(1), CLR(1)

Eliminating Left Recursion

Top-down parsers loop forever on left-recursive rules A → Aα | β. Rewrite them as:

Text

A  → βA'
A' → αA' | ε

Example:
E → E + T | T        ⇒   E  → T E'
                          E' → + T E' | ε
T → T * F | F        ⇒   T  → F T'
                          T' → * F T' | ε

Left Factoring

When two alternatives share a prefix, the parser can't choose between them with one token of lookahead. Factor out the prefix:

Text

S → iEtS | iEtSeS | a     ⇒     S  → iEtS S' | a
                                 S' → eS | ε

Recursive Descent Parser

// Grammar: E → T E',  E' → + T E' | ε,  T → id
#include <stdio.h>
const char *in = "i+i+i";   // 'i' stands for id
int pos = 0;

int T()  { if (in[pos] == 'i') { pos++; return 1; } return 0; }
int Ep() { if (in[pos] == '+') { pos++; return T() && Ep(); } return 1; }   // ε
int E()  { return T() && Ep(); }

int main() {
    printf(E() && in[pos] == '\0' ? "Accepted\n" : "Rejected\n");
}

Accepted

Track your progress through the Compiler Design course

← Prev Next →