Re: HyperTalk Grammar, Again

[Hans Aberg]

At 20:59 -0500 2002/01/20, Anthony DeRobertis wrote:
>I think it's about time I posted what I have of the grammar. It's 480 lines,
>so I'll just give a URL:
>  <http://freecard.sourceforge.net/InterpreterExpirement/parser.y>
>You'll need to find a nice 132-character display to make it readable ---
>sorry about that. Also, I use 4-character tabs...

I can give you inputs how I fiddle around with this grammar:

Bison says that you have a shift/reduce conflict in
  object_descr:
    part_descr
  | part_descr OF card_descr

One way to test what the problem is to introduce an extra token, and
replace to see if the conflict goes away. For example
  %token FOO
  object_descr:
    FOO
  | FOO OF card_descr
which it does. This means that the problem is that part_descr cannot
distinguish between rules when/not followed by OF.

Roughly speaking, Bison's algorithm would look at the items (where the . is
a pars so far attained)
(1)  object_descr -> part_descr .
(2)  object_descr -> part_descr . OF card_descr
If we want to distinguish between these two rules, we can look at
FOLLOW(part_descr), all token strings of length <= 1 that can immediately
follow this nonterminal.

For simplicity, cut down the grammar (which will keep the shift/reduce
conflict) to:
  factor: INTEGER | object_descr
  object_descr: part_descr | part_descr OF
  part_descr: BUTTON factor

Then:
  FOLLOW(part_descr) contains FOLLOW(factor)
  FOLLOW(factor) contains FOLLOW(object_descr)
  FOLLOW(object_descr) contains {OF}
Thus:
  FOLLOW(part_descr) = {INTEGER, OF, BUTTON}
Since OF is in this set, there is no way to distinguish between items (1)
and (2) above by looking at the following token alone.

If you want to check if LR(n) help you out, I think (but I am not exactly
sure on the theory) you could compute FOLLOW_n(part_descr).

But I tend to think that you have not thought sufficiently about how OF
should appropriately be put into your grammar.

  Hans Aberg