Re: FYI: lalr1.cc: Remove the traits

[Hans Aberg]

On 19 Sep 2005, at 12:24, Akim Demaille wrote:

> > > > Also, just use the std::deque for stack. I think that std::stack  
> > > > will
> > > > not be able to look deeper than top, as is required by the parser.
> > >
> > > Of course it can't.
>
> > Why is this of course?
>
> For the reason you gave.

There isn't saying that a stack can't do that in general. The  
std::stack, however doesn't.

> > > That's why we used a dequeue from the start.

This should be deque. "Dequeue" is the opposite of "enqueue".

Also note that the conditions that forces std::deque to allocate new  
chunks are not in the first revision of C++. So that could not have  
been the reason you choose to use std::deque over std::vector.

> > std::stack uses std::deque for implementation.
>
> I doubt the C++ standard mandates this.

std::stack is an adaptor l´class, which uses std::deque as default,  
but otherwise can use std::vector and std::list as well.

One alternative, for the Bison parser, might be to write a similar  
adaptor class, which admits looking down the stack. Then  people  
easily can choose. But in general, I propose to make the C++ parser  
as simple as possible, to get it off the ground.

> > I guess you will have to do some time profiling to figure this
> > out. A typical compilers spends little time in the parsing anyway,
> > so it probably does not matter,
>
> That's a view that a compiler implementer might have, not the one
> Bison maintainers can.

I guess the Bison maintainers cannot cite a good reason to prefer the  
one container over the other, as there is not a best one. The array  
in the C parser is probably used only because it is easiest to  
implement.

BTW, I rewrote he parser so that the pops of the different stacks  
take place in the same place. This way, one can merge them to a  
single stack, if one so wants. This decreases the time spend on  
reallocating the stack.

  Hans Aberg