Re: [Caml-list] Re: [Menhir-list] There's an elephant in the room: Solution to sharing a symbol table

[skaller <skaller@users.sourceforge.net>]

On Wed, 2007-05-02 at 20:30 +0200, Francois Pottier wrote:
> Hi,
> 
> On Thu, May 03, 2007 at 02:07:26AM +1000, skaller wrote:
> > State must be maintained in function arguments.
> 
> This is a trivial example, but:
> 
>   let x = ref 0
>   let f () : bool = incr x; x / 2 = 0

Yes, but I rule out global mutable state as unacceptable
by requiring reentrancy.

> Here, f exploits an internal state, even though it is not explicitly
> parameterized over a piece of state. Similarly, a parser can have internal
> state, even if the parsing functions are not explicitly parameterized over a
> piece of state. It is sufficient for the entire parser either to refer to a
> global variable or to abstracted over a piece of state (which functors allow).

As above, if that state is global the result isn't re-entrant
and isn't acceptable.

> I don't see why this is so. In fact, nothing in your example seems to require
> any kind of state -- you only need the parser to be able to recursively invoke
> itself. Or am I missing something?

I didn't show the full parser of course. In fact, Felix grammar
is user extensible, so there has to be somewhere to hold
the extensions. Similarly, a C parser requires a symbol table
for typedefs, and Felix allows embedded C.

In fact, Felix can call the FrontC/CIL parser on fragments 
of C code -- and CIL uses global variables so isn't re-entrant.

In fact Joel explained the 'elephant' technique:

   let parser str =
     let tab = .. in
     let lexbuf = Lexing.from_string str in
     let module P = EasyParser.Make (struct let tab = tab end) in
     P.program (token tab) lexbuf

which uses a local module to turn a global variable into
a function local one. That's pretty clever, the function
'parser' here is reentrant (even though P.program is not).

To support recursion you'd need:

     let module P = EasyParser.Make (struct 
       let tab = tab  
       let parser = parser (* pass fun for recursion *)
     end) in

Quite a clever use of a local modules and functors therefore,
allows %parameter to suffice, without further changes to
Menhir .. though it would still be much easier if you
could just do it like Ocamllex, I have to agree this does
work.


-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net