Lecture No. 14

Dated: 25-03-2025

The \(LL(1)\) Property

If \(A \to \alpha\) and \(A \to \beta\) both appear in the grammar.

\[FIRST(\alpha) \cap FIRST(\beta) = \emptyset\]

Predictive parsers¹ accept \(LL(k)\) grammar. The 2 \(LL\) stand for left to right, left most derivation. The \(k\) means number of look ahead tokens²
of input.
If \(A \to \alpha, A \to \beta\) and \(\epsilon \in FIRST(\alpha)\) then we need to ensure that \(FIRST(\beta) \cap FOLLOW(\alpha) = \emptyset\).

Follow

\(FOLLOW(\alpha)\) is the set¹ of all words³ in the grammar that can legally appear after an \(\alpha\).
If \(\epsilon \in FIRST(\alpha)\) then \(FIRST^+(\alpha) = FIRST(\alpha) \cup FOLLOW(\alpha)\). Otherwise, \(FIRST^+(\alpha) = FIRST(\alpha)\).
A grammar is \(LL(1)\) if for every pair of productions \(A \to \alpha\) and \(A \to \beta\), \(FIRST^+(\alpha) \cap FIRST^+(\beta) = \emptyset\)
Consider the following \(LL(1)\)

\[A \to \beta_1 | \beta_2 | \beta_3\]

// find an \(A\)
if (token \(\in\) \(FIRST(\beta_1)\)) find a \(\beta_1\) and return true
else if (token \(\in\) \(FIRST(\beta_2)\)) find a \(\beta_2\) and return true
else if (token \(\in\) \(FIRST(\beta_3)\)) find a \(\beta_3\) and return true
else error and return false

One kind of predictive parser is called recursive descent parser.

Recursive Descent Parsing

1 Goal    ->   expr
2 expr    ->   term expr'
3 expr'   -> + term expr'
4         |  - term expr'
5         |    e
6 term    ->   factor term'
7 term'   -> * factor term'
8         |  / factor term'
9         |    e
10 factor ->   number
11        |    id
12        |    (expr)

This leads to a parser¹ with 6 exclusive routines each of which recognize one non-terminal (NT) or terminal(T).

1. goal
2. expr
3. E'
4. term
5. T'
6. factor

Goal () {
    token = next_token();

    if (Expr() == true && token == EOF)
        next compilation step
    else {
        report syntax error;
        return false;
    }
}

Expr() {
    if (Term() == false)
        return false;
    else
        return Eprime();
}

Eprime() {
    token_type op = next_token();
    if (op == PLUS || op == MINUS) {
        if (Term() == false)
            return false;
        else
            return Eprime();
    }
}

Recursive Descent in C++

class NonTerminal {
public:
    NonTerminal(Scanner* sc) {
        s = sc;
        tree = NULL;
    }
    virtual ~NonTerminal() {}
    virtual bool isPresent() = 0;
    TreeNode* AST() {
        return tree;
    }

protected:
    Scanner* s;
    TreeNode* tree;
};

class Expr : public NonTerminal {
public:
    Expr(Scanner* sc) : NonTerminal(sc) {}
    virtual bool isPresent(); 
};

class Eprime : public NonTerminal {
public:
    Eprime(Scanner* sc, TreeNode* t) : NonTerminal(sc) {
        exprSofar = t;
    }

    virtual bool isPresent();

protected:
    TreeNode* exprSofar;
}

class Term : public NonTerminal {
public:
    Term(Scanner* sc) : NonTerminal(sc) {}
    virtual bool isPresent(); 
};

class Tprime : public NonTerminal {
public:
    Tprime(Scanner* sc, TreeNode* t) : NonTerminal(sc) {
        exprSofar = t;
    }

    virtual bool isPresent(); 

protected:
    TreeNode* exprSofar;
};

class Factor : public NonTerminal {
public:
    Factor(Scanner* sc, TreeNode* t) : NonTerminal(sc) {};
    virtual bool isPresent();
};

References

---

1. Read more about predictive parsers. ↩↩↩

2. Read more about tokens. ↩

3. Read more about words. ↩