User Tools

Site Tools


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.

first_set.txt · Last modified: 2020/10/08 12:45 by revusky