0. VocabularyPermalink

In this post we use the following abbreviation, symbols, and operators:

• $A\uplus B$ means $A:=A\cup B$ for two sets $A,B$
• Grammar $G=(V,\mathrm{\Sigma },S,P)$
• $\mathrm{\Phi }$ is a map of $\alpha \mapsto \mathrm{FIRST}(\alpha )$ where $\alpha$ could be:
  • a single terminal $a\in \mathrm{\Sigma }$
  • a single variable $X\in V$
  • an RHS sequence as in any production $(X\to \alpha )\in P$
• $\mathrm{\Lambda }$ is a map of $X\mapsto \mathrm{FOLLOW}(X)$ where $X\in V$
• PPT stands for Predictive Parsing Table

1. If you know your grammar is $LL(1)$Permalink

Our logic should follow this state diagram on writing an $LL(1)$ parser:

Let’s start with the easy case: suppose you already know your grammar is $LL(1)$.

If your grammar is simple or straightforward, you can write the parser directly by looking at the productions. E.g.:

S : 'a' X ;
  | 'b' Y ;

The parser is like:

def S():
    if lookahead() == 'a':
        match('a')
        X()
    elif lookahead() == 'b':
        match('b')
        Y()
    else:
        raise error()

If your grammar is not so straightforward, like:

S : AX ;
  | BY ;
A : CD ;
B : EF ;
...

then you need PPT since you cannot infer when to match A or when to match B simply from the lookahead and productions.

def S():
    if lookahead() == ???:
        A()
        X()
    elif lookahead() == ???:
        B()
        Y()
    else:
        raise error()

2. If you don’t know if your grammar is $LL(1)$Permalink

But what if you’re not sure whether your grammar is $LL(1)$? Before writing a parser, you’ll need to verify that your grammar satisfies the $LL(1)$ condition.

The verification can also be done with a PPT.

3. How to compute PPTPermalink

In 2 out of the 3 cases we listed above, we need to compute PPT. It needs do some groundwork, specifically, the $\mathrm{FIRST}$ and $\mathrm{FOLLOW}$ sets.

• $\mathrm{FIRST}(\alpha \in (V\cup \mathrm{\Sigma }{)}^{\ast })=\{x\in \mathrm{\Sigma }\mid x\text{ is the first terminal derivable from }\alpha \text{. I.e. }\alpha \stackrel{\ast }{\Rightarrow }x\dots \}$
• $\mathrm{FOLLOW}(A\in V)=\{x\in \mathrm{\Sigma }\mid x\text{ is the first terminal that follows }A\text{ in a sentential form}\text{. I.e. }S\stackrel{\ast }{\Rightarrow }\dots Ax\dots \}$

3.1 $\mathrm{FIRST}$ SetPermalink

3.1.1 DefinitionsPermalink

Definition: Given CFG $G=(V,\mathrm{\Sigma },P,S)$ and a sequence of symbols $\alpha \in (V\cup \mathrm{\Sigma }{)}^{\ast }$, the $\mathrm{FIRST}$ set of $\alpha$ is the set of terminals that begin the sentential forms derivable from $\alpha$. Plus, if $\alpha$ can derive $\epsilon$, then $\epsilon \in \mathrm{FIRST}(\alpha )$. $◼$

Definition: If we only consider single symbols $X\in V\cup \mathrm{\Sigma }$, we can define:

$\mathrm{FIRST}$ sets on $\alpha \in (V\cup \mathrm{\Sigma }{)}^{\ast }$ is similar to the cases of $X\in V$.

$◼$

3.1.2 Pilot Algorithm: computing $\mathrm{FIRST}$ set for a single symbol, when other $\mathrm{FIRST}$ sets are knownPermalink

We can use the following algorithm:

where:

• for-else works like in Python
• If $\mathrm{\exists }{Y}_i\in \mathrm{\Sigma }$, then the inner for loop breaks, and $\epsilon \notin \mathrm{\Phi }[X]$
• You can also initialize $\mathrm{\Phi }$ to contain all $\mathrm{\Phi }[a]=\{a\},\mathrm{\forall }a\in \mathrm{\Sigma }$ so Line (1) and (2) can be removed

Explanation on the block starting from Line (3):

• if $b\in \mathrm{\Phi }[Y_1]$, then $Y_1\stackrel{\ast }{\Rightarrow }b\dots$, and then $X\stackrel{\ast }{\Rightarrow }b\dots Y_2\dots Y_k$. Therefore $b\in \mathrm{\Phi }[X]$, and consequently $\mathrm{\Phi }[Y_1]\subseteq \mathrm{\Phi }[X]$
• if $Y_1$ is nullable, then $X\stackrel{\ast }{\Rightarrow }{Y}_2\dots Y_k$. Logic falls back to above.
• if $Y_1$ is not nullable, then we don’t have to consider $\mathrm{\Phi }[Y_2]$ since $Y_2$ can never be the leftmost symbol for $X$, w.r.t. this particular production.

If you have a grammar without any $\epsilon$-production, this algorithm becomes way simpler:

However in real world, $\epsilon$-production are not always elimimated.

3.1.3 Algorithm: computing $\mathrm{FIRST}$ sets for all symbolsPermalink

Now we want to compute all $\mathrm{FIRST}$ sets at the grammar level with a single function.

3.1.3.1 A Flawed IntuitionPermalink

An intuition is to call compute_first_set_for_symbol$(S,\mathrm{\Phi }=\{\})$ with modification: if $\mathrm{\Phi }[Y_i]$ is unknow, recursively call compute_first_set_for_symbol$(Y_i,\mathrm{\Phi })$.

This intuition has a big flaw: it cannot handle circular dependencies. Note that:

1. Circular dependencies means endless recurisive calls
2. We usually elimiates Left Recursion beforehand but it is only a special form of circular dependencies

Some circular dependencies are direct and obvious, like:

A -> B a
B -> A b | c

Some are involved with “skip-ahead” and less obvious, like:

A -> B C a
B -> ε | d
C -> A e | f

where $\mathrm{\Phi }[A]$ depends on $\mathrm{\Phi }[B]$ and $\mathrm{\Phi }[C]$ (because $B$ is nullable), and $\mathrm{\Phi }[C]$ depends on $\mathrm{\Phi }[A]$. Therefore compute_first_set_for_symbol$(A,\cdot )$ will end up calling itself.

3.1.3.2 Fixed-Point ApproachPermalink

How it works:

1. Go through every production, compute every $\mathrm{\Phi }(X)$ where $X$ is the LHS of the production
2. Repeat until $\mathrm{\Phi }$ is not changed anymore

This approach cannot eliminate circular dependencies, but terimiates in time when the fixed-point is reached.

3.1.4 Algorithm: computing $\mathrm{FIRST}$ set for any RHS sequencePermalink

To construct PPT, we need $\mathrm{\Phi }[\alpha ]$ for each RHS $\alpha$ appearing in a production. This algorithm is similar to Section 3.1.2:

3.2 $\mathrm{FOLLOW}$ SetPermalink

Definition: Given CFG $G=(V,\mathrm{\Sigma },P,S)$ and a single variable $A\in V$, the $\mathrm{FOLLOW}$ set of $A$ is the set of terminals that can appear immediately to the right of $A$ in some sentential form. Plus, if $A$ is the rightmost symbol in some sentential form, then the EOF symbol $Ⅎ\in \mathrm{FOLLOW}(A)$.

I.e. $\mathrm{\forall }A\in V$

$◼$

We can follow the fixed-point strategy of Section 3.1.3.2 and implement a single function to compute all $\mathrm{FOLLOW}$ sets at once at the grammar level.

We need pre-computed collection $\mathrm{\Phi }$ of $\mathrm{FIRST}$ sets in the computation, and we initialize the collection $\mathrm{\Lambda }$ of $\mathrm{FOLLOW}$ sets as: $\mathrm{\Lambda }[S]=\{Ⅎ\}$ since we always have $S\stackrel{\ast }{\Rightarrow }SℲ$.

Note that always $\epsilon \notin \mathrm{FOLLOW}(\cdot )$

The algorithm is shown below:

Explanation:

• Line (1): if $b\in \mathrm{\Lambda }[Y]$, then string $Yy$ appears in some sentential form. Apply the production $Y\to \alpha X$, and string $\alpha Xb$ appears in the corresponding sentential form. Therefore $b\in \mathrm{\Lambda }[X]$
• Line (2)(3)(4):
  • If $\epsilon \in \mathrm{\Phi }[\beta ]$, logic falls back to Line (1)
  • If $b\in \mathrm{\Phi }[\beta ]$, then $\beta \stackrel{\ast }{\Rightarrow }b\dots$, which means $Y\stackrel{\ast }{\Rightarrow }\alpha Xb\dots$. Plus $Y$ should be reachable from $S$, therefore there should be a sentential form $S\stackrel{\ast }{\Rightarrow }\dots Y\cdots \stackrel{\ast }{\Rightarrow }\dots \alpha Xb\dots$, and in the end $b\in \mathrm{\Lambda }[X]$

3.3 Construct PPT from $\mathrm{FIRST}$ and $\mathrm{FOLLOW}$ SetsPermalink

PPT $T$ is a table whose row-index is $V$, column-index is $\mathrm{\Sigma }$, and each cell is a production $\in P$.

If you have a grammar without any $\epsilon$-production, the whole thing becomes way simpler:

1. All the three algorithms on $\mathrm{FIRST}$ sets are way simpler
   • See Section 3.1.2 as an example
2. No need to compute $\mathrm{FOLLOW}$ sets at all!
3. Line (1)(2)(3) in above algorithm can be removed

Howeve as we mentioned in Section 3.1.2, in real world, $\epsilon$-production are not always elimimated.

3.4 Prove your grammar is $LL(1)$Permalink

Corollary: $G$ is a $LL(1)$ grammar $⟺$ $T$ is conflict-free $⟺$ There is at most 1 production in any cell of $T$. $◼$

To write parsers for ambiguous grammars, sometimes we impose prioritization of certain derivation. This is like prioritizing certain production involved in a PPT conflict.

3.5 ExamplePermalink

See LL(1) Parser Visualization, by Zak Kincaid and Shaowei Zhu.

S -> E
E -> T E'          // Expression
E' -> + T E' | ε
T -> F T'          // Term
T' -> * F T' | ε
F -> ( E ) | id    // Factor

def S():
    E()

def E():
    T()
    E_prime()

def T():
    F()
    T_prime()

def T_prime():
    if lookahead() in "$+)":  # T' -> ε
        return
    elif lookahead() == "*":
        consume('*')
        F()
        T_prime()
    else:
        raise ValueError()

def F():
    if lookahead() == "id":
        consume("id")
        return
    elif lookahead() == "(":
        consume("(")
        E()
        consume(")")
    else:
        raise ValueError()

def E_prime():
    if lookahead() in "$)":  # E' -> ε
        return
    elif lookahead() == "+":
        consume('+')
        T()
        E_prime()
    else:
        raise ValueError()
    

4. Write your $LL(1)$ parserPermalink

Just follow the script skeleton in Section 1.

Other top-down parser implementation techniques can be found in Top-Down Parsers: Recursive Descent, Predictive, and More.