Re: HyperTalk Grammar, Again

[Hans Aberg]

At 02:07 -0500 2002/01/26, Anthony DeRobertis wrote:
>>   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.

Please note that what I wrote is not a mathematically strict analysis, but
only hints on how to mow onto the problem empirically: In the full LR(1)
algorithm, the parsing items (rules with dots, as in the Bison output
grammar description file) are carried along with tokens by which one can
reduce.

>Soon after writing my previous message, I realized that the problem is:
>
> BUTTON BUTTON INTEGER OF
>
>It isn't clear which the of goes with ---
>
> BUTTON (BUTTON INTEGER OF)
>vs.
> BUTTON (BUTTON INTGER) OF
>
>Which is pretty much the classic dangling-else problem, except this is a
>dangling of.

Good. The dangling "else" problems is treated in the Bison manual, section
5.2, where it is suggested to use the %expect. However:

> Fortunately, HyperCard (the reference implementation) likes
>shift.

I am able to resolve the example indicated there (in the manual), by

%token IF THEN ELSE variable

%nonassoc ELSE
%nonassoc THEN

%%

stmt:
    expr
  | if_stmt

if_stmt:
    IF expr THEN stmt
  | IF expr THEN stmt ELSE stmt

expr: variable

Thus indicating the priorities between the THEN and ELSE tokens (changing
the order should give the two possibilities of resolving the dangling
"else"). Thus, rather than relying on being "lucky", one can write out a
correct grammar that does not rely on any Bison specifics, such as %expect.

>I _think_ this means that there wasn't really a problem in the first place
>(other than ambiguous grammar, of course); am I wrong?

I think that you need to analyze these things to the point that you
understand why the grammar should look it should look. Then you will be
able to design a better grammar, in case you want to write a new hyperlink
card grammar. Using a compiler-compiler like Bison gives one a great deal
of flexibility in designing a new grammar; it is easy to change.

Also note that using a back-tracking may not resolve your problem, because
then you may end up with multiple parses, which you must indicate which one
to use, as in the classical example:
    Fruit flies like a banana.
Which parse is correct here, or should one used both?


  Hans Aberg