help-bison
[Top][All Lists]
Advanced

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

Re: Re[2]: LALR : How it work during parsing time with empty rule ? what


From: Hans Aberg
Subject: Re: Re[2]: LALR : How it work during parsing time with empty rule ? what to do to the stack?
Date: Tue, 13 Sep 2005 11:43:18 +0200

On 13 Sep 2005, at 11:12, Baldurien (club internet) wrote:

When I have to reduce, saying by rule X : Y '+' X I know I have to pop 3 times, but what happens when the rule is simply X : /* empty */ ? I
can't pop at all, so what should I do?

HA> Just don't pop. If  s  is the state on top of the state stack, the
HA> total effect is that the state goto(s, X) is pushed onto it. If you
HA> have a stack for non-terminals and terminals, which the Bison
HA> generated parser doesn't, then X will be pushed onto that. The rule
HA> action is executed.

$reduce: the rule we use to reduce.
$ss : the stack of state
$sl : the level of this stack. The top state is $ss[$sl-1].
$ls  :  the  location stack, it's a stack that contains only the start
and  the  end  line of a rule. I use it in order to have comprehensive
error  message (like : syntax error between line x and y for a string,
etc).

$rule = $__xtf_parser_rule_lhs[$reduce];

/**
 * We have to pop a certain amount of time
 */
$pop = $__xtf_parser_rule_count[$reduce];
$sl -= $pop;

$goto = &$__xtf_parser_goto[$__xtf_parser_sgoto[$ss[$sl-1]]];

/* call reduce handler, etc : action set by the user */

$ls[$sl-1] = array(
  $ls[$sl-1][0],
  $ls[$sl-2+$pop][1]
);

$ss[$sl++] = $goto[$rule];

Here I do $sl++, meaning I increment the stack level (but after). When
pop is null, should it be only $ss[$sl-1] ?

The LALR algorithm is described in books like the one by Aho, Sethi & Ullman, "Compilers...". Just follow it. As I said above, just pop (= nothing, if the rule is of length 0), look at the top state s of the stack, and add goto (s, X) on top. Your RHS does not have the stack top state, so it looks wrong to me.

  Hans Aberg






reply via email to

[Prev in Thread] Current Thread [Next in Thread]