Table of Contents

FIRST ยท Definition & Derivation

๐ŸŽ“ This is the Advanced track ยท Theory. It's good to grab the concept first from the Basics-track FIRST/FOLLOW and then come here. On this page we'll look at exactly what FIRST is (the definition) and the process of deriving it by hand, straight from that definition.

Don't let it weigh on you โ€” we'll go slowly.

๐Ÿ“ Where it lives ยท engine FirstFollowAnalyzer ยท module Janglim.FrontEnd โ€” Layer 2 (the lower layer, below the parse table)

The example grammar we keep using.

Expr   : Expr '+' Term | Term ;
Term   : Term '*' Factor | Factor ;
Factor : '(' Expr ')' | id ;

The answer we worked out by hand in the basics was FIRST(Expr) = FIRST(Term) = FIRST(Factor) = { '(', id }.
But before that โ€” let's pin down clearly what FIRST exactly is first.
(Skip this, and the computation rules that follow become a spell you just memorize.)

Definition โ€” What FIRST is

Let me nail it down in one line first.

FIRST(X) = the set of terminals that can appear first when you derive the symbol X.

There are two key words โ€” derive and the terminal that appears first (the terminal that comes at the very front).
Let's look at them one at a time.

"derivation" โ€” expanding via the rules

We call one step of substituting a nonterminal with the right-hand side of its production a derivation, and write it with the arrow โ‡’.

Let me expand Expr one step at a time.

   Expr  โ‡’  Term  โ‡’  Factor  โ‡’  id
        (Expr:Term)  (Term:Factor)  (Factor:id)

By applying rules three times, we finally reached a string made of terminals only, id.
Expanding like this in several steps is written โ‡’* โ†’ Expr โ‡’* id ("Expr derives id").

So FIRST is

Expanding X every which way all the way down, and gathering up all the terminals that can appear first (= the terminal that comes at the very front).

Seeing it directly with Expr:

   Expr โ‡’* id โ€ฆ             โ†’  front is id   โ‡’   id โˆˆ FIRST(Expr)
   Expr โ‡’* ( Expr ) โ€ฆ       โ†’  front is (    โ‡’   ( โˆˆ FIRST(Expr)

Expr can make countless strings (id, id + id, ( id ) * id, โ€ฆ), but the terminals that can come at the front end up being just two, id or (. So:

   FIRST(Expr) = { '(', id }

Written more firmly in symbols, it's this (T = the set of terminals):

   FIRST(X) = { a โˆˆ T | X โ‡’* a โ€ฆ (derives a string starting with a) }

๐Ÿ“Ž Just one more thing about ฮต (the empty string). If X can derive even nothing at all (X โ‡’* ฮต), we put ฮต into FIRST(X) too. It's the mark for "X can disappear entirely."

But our expr grammar has no nonterminal that can become nothing at all, so we can't show this with expr. To see ฮต with our own eyes, let's bring in a small grammar. Here's the grammar we'll use for examples in this chapter:

S โ†’ A B
A โ†’ a | ฮต
B โ†’ b | ฮต

Here A has two productions, and one of them is A โ†’ ฮต, so A โ‡’ ฮต โ€” it derives nothing at all. Straight from the definition, ฮต is in A's FIRST too, and so is B's for the same reason.

   FIRST(A) = { a, ฮต }
   FIRST(B) = { b, ฮต }

We'll keep using this small ฮต grammar for ฮต examples in the later Computation rules chapter too โ€” whenever it shows up instead of expr, just read it as "ah, the grammar that shows ฮต."

To sum up โ€” whether it's a terminal, a nonterminal, or a sequence of several symbols, FIRST is "the set of terminals (plus ฮต if needed) that can appear first when you derive it."
That's the whole definition.

Straight from the definition โ€” deriving it by hand

Now let's work out "deriving and gathering the front terminals" by applying that definition directly, by hand.
Starting with the easy one, Factor.

Factor โ€” expands all the way without a hitch

Let's derive Factor's two productions (one per line, split by | โ€” of the form A โ†’ ฮฑ, where ฮฑ is the sequence of symbols on the right-hand side. Details in Single) all the way down.

   Factor โ‡’ id              โ†’  front terminal :  id
   Factor โ‡’ ( Expr )        โ†’  front terminal :  (

The front of the strings Factor produces is either id or ( โ€” just those two.
Gathering them up straight from the definition:

   FIRST(Factor) = { id, '(' }

Easy, right?
Inside Factor, it doesn't show up by itself, so the derivation ends cleanly.

Term โ€” as you expand, itself shows up again

Term : Term '*' Factor | Factor.
Let me derive the two productions.

   โ‘  Term โ‡’ Factor โ‡’ โ€ฆ โ‡’ id or (          โ†’  front :  id, (
   โ‘ก Term โ‡’ Term '*' Factor                  โ†’  front is again Term ?!

โ‘ก is the odd one.
The front is itself, Term, so to know the front terminal you have to expand that Term again.

   Term โ‡’ Term '*' Factor
        โ‡’ Term '*' Factor '*' Factor
        โ‡’ โ€ฆ                              โ†  expand and expand, the front is still Term, no end in sight

But eventually the front Term too settles down into the Factor production, and then the front terminal becomes id or ( again. So:

   FIRST(Term) = { id, '(' }

Expr (Expr : Expr '+' Term | Term) has the same shape, so FIRST(Expr) = { id, '(' }.

Here's the snag โ€” we can't derive "all the way"

As we saw with Term, when it bites its own tail (recursion), the derivation can grow infinitely long.
The definition is clear ("the terminal that appears first when you derive"), but actually expanding that derivation all the way to the end, one by one is awkward both by hand and by computer.

Next โ€” on to the computation rules

So on the next page we'll move to a computation rule that pulls out the same FIRST without expanding the derivation directly.
(And recursion gets handled gracefully too.)

๐Ÿ‘‰ FIRST ยท Computation Rules

๐Ÿ‘ˆ Back to the basic concept: FIRST / FOLLOW

Edit this page