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.

Last modified by Brett Giles

Last modified: Mon Mar 3 11:36:35 MST 2003 Valid XHTML 1.0!