
Title:
0425 Computing The Closure Solution

Description:

Let's take a look at the answers together,

It's going to turn out that we'll be able to compute this, fairly systematically,

just by remembering the rule for how to compute the closure.

We have a dot in front of the nonterminal E,

so I go over to our grammar

and find all of the rules that start with nonterminal E.

And there are 3 of them, and I'm going to add all of them to chart[2]

with a red dot right at the beginning and a from2

because that's where we currently are1, 2

as they are little provenance information off here, to the right.

So one of our rules is:

(E > int)

so we will definitely add (E > dot int from2).

Again, the from2 is because we brought in

or we computed the closure, starting in state[2].

Another possible rule is:

E > (F).

So (E > dot (F), coming from position 2)

is a valid prediction we might make.

We might see parentheses right after seeing a minus sign; that's valid for this language.

Now our third rule is: (E > E  E)

so this option may look very tempting.

It's got the (E  E).

It's got the dot in the front, but it has the wrong (from) state information.

It's included from0 instead of from2.

We need to remember these 2 tokens we've seen previouslythe (E) and the ().

We need to know which state we were in

when we decided to take the closure.

This one is not correct.

Over here we see one that's very similar:

(E > E  E, with a dot in front).

That's very good; it's a rule that starts with (E),

and we need to start with (E) because the dot is before the (E).

And this one correctly has from2.

We computed the closure in chart[2].

And finally, this one's a bit of a ringer

it has (F > dot string from2).

Well, the from2 looks pretty good; the dot at the beginning looks very good.

But our rule is: since this dot was before an (E),

we take all the grammar rules that start with (E)

on the lefthand side, and that's it.

So (F > string)that's out of place.

I'm not going to predict seeing a string

until I've seen an open parenthesis.

If you think about this grammar,

the only way to get to string is after an open parenthesis.

I haven't seen one of those, so this is a bad prediction.