Re: HyperTalk Grammar, Again

[Hans Aberg]

At 10:58 -0500 2002/01/20, Anthony DeRobertis wrote:
>I'm beginning to agree with Scott that LALR(1) isn't enough.

First note that languages are often not themselves LL(1) or LALR(1) even
though  such parsers may be used: One can tweak the lexer by say a lookup
table deciding which token to return. Or one can decide that some data is
semantic, and let it be handled via the actions. This data can the be fed
back to alter the lexer.

So if you say that the original parser used a recursive decent parser
(probably LL(1) then), that is good indication that Bison would suffice
(keeping in mind Akim's claim that perhaps not LL(1) => LALR(1)). -- You
just haven't considered all possible tweaks yet.

>The first question is if a shift or reduce is to be performed

Also note that it can be quite difficult to tell when to shift or reduce,
because the LR(1) algorithm consists of considering the whole grammar at
once, and all possible parser positions, called items. The states of the
deterministic parser is then roughly the closures of such items together
with the lookahead. LALR(1) roughly a compactification of a subset of LR(1).

Thus, it may look as though a larger lookahead is needed in a simplistic
analysis.

>Also, what do you think of btyacc for situations like this?

Non deterministic parsing is often slow, so consider all tweaks of
deterministic parsing before resorting to that. -- But perhaps somebody
else has a different opinion.

>These come from the lexical analyzer (flex) as:
>
>LINE FIELD INTEGER OF CARD FIELD INTEGER
>LINE FIELD INTEGER OF CARD INTEGER
>LINE FIELD 1 OF FIRST CARD
>LINE FIELD 1 OF FIRST CARD FIELD

The grammar:

%token LINE, FIELD, INTEGER, OF, FIRST, CARD
%%
foo:
    LINE FIELD INTEGER OF CARD FIELD INTEGER
  | LINE FIELD INTEGER OF CARD INTEGER
  | LINE FIELD INTEGER OF FIRST CARD
  | LINE FIELD INTEGER OF FIRST CARD FIELD
%%
passes Bison. So your example is parsable with one token lookahead LALR.

  Hans Aberg