CPSC 411 - Lab Notes - 03-03 (Good/almost good/improvable rules)

All of the below assume you have a partial order on your rules. You may pick the partial order as you see fit. (See Dr. Cockett's examples at his LL(1) notes)

Good rules

In a grammar a rule x->a b c ... t is good if:

1. There are no a b c ... t, that is, it is a null rule. (Immediately nullable).
2. The first thing, a is actually a terminal T.
3. The first thing, a, is not nullable AND it is a non-terminal AND x<a.
4. The first thing, a, is nullable AND the derived rule, x->b c ... t is good.

Naturally, we choose the ordering so that as many rules are good as is possible.

x is good if all of it's productions are good.

Improvable rules, almost good non-terminals

In a grammar a rule x->a b c ... t is improvable if:

1. The first thing, a, is good AND a<y.(Note this is the opposite direction for the ordering rule in the good case above)
2. The first thing, a, is nullable AND is not x AND the derived rule, x->b c ... t is improvable.
3. The first thing, a, is nullable AND is not x AND x = b.

x is almost good if all of it's productions are of the form:

```x -> x a's
x -> x b's
x -> x c's
...
x -> p's
x -> q's
x -> r's
```

and each production, once we remove the initial x on the right hand side of the first few rules, is good.