lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


David Given wrote:

> Depends on the state machine.
>
> For example (this is a classic example by David Tribble, not my own):
>
> int parse()
> {
>     Token   tok;
>
> reading:
>     tok = gettoken();
>     if (tok == END)
>         return ACCEPT;
> shifting:
>     if (shift(tok))
>         goto reading;
> reducing:
>     if (reduce(tok))
>         goto shifting;
>     return ERROR;
> }

The state machine in a shift-reduce parser is not really revealed
by that code; the states themselves are hidden in the parser's stack.
In any event, the code is incorrect; the END token needs to be handled
(causing pending productions to be reduced) before returning ACCEPT.

So it could just as well be written:

int parse() {
  Token tok;
  do {
    tok = gettoken();
    while (!shift(tok)) {
      if (!reduce(tok)) return ERROR;
    }
  } while (tok != END);
  return ACCEPT;
}

However, a more interesting implementation might use tail-calls to
the actual state resulting from the shift or reduce.