meta data for this page
  •  

An expansion's first set is simply the set of all tokens that can begin the expansion.

The most trivial example imaginable is any expansion that begins with a single token. Thus, the first set of:

    "foo" "bar" "baz"

is simply a set with one element, “foo”.

The first set of

    ("foo" | "bar") "baz"

has two elements, “foo” and “bar”. The above expansion must necessarily begin with one of those two tokens.

For example, if the production Foobar is defined as:

    Foobar : "foo" | "bar";

then the first set of the expansion:

     [ Foobar ] "baz"

contains the three tokens, “foo”, “bar” , and “baz. To say that a grammar is LL(1) is equivalent to saying that, at any choice point the expansion's first set is enough to decide whether or not to enter the expansion.