Re: [Caml-list] menhir

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

On Wed, 2007-05-02 at 14:30 +0200, Francois Pottier wrote:
> Hello,
> 
> On Wed, May 02, 2007 at 06:41:44PM +1000, skaller wrote:
> > Exactly. In Ocamlyacc it is named 'eof', and you can use that
> > token in your productions.
> 
> As far as I know, this is incorrect. ocamlyacc does not have a predefined
> eof token. Perhaps you are thinking of ocamllex, which has an eof pattern.

I believe you're right, I apologise for confusion.

> > compilation_unit:
> >   | statement_aster ENDMARKER { $1 }
> > 
> > where no non-terminal on which statements_aster depends 
> > has a production containing ENDMARKER or # (eof).
> > 
> > Therefore, there is no conflict. When compilation_unit
> > is reduced the parser returns, the next token, whether
> > it is # or any other, is irrelevant.
> 
> Good. I seem to agree with you. Menhir should not report an end-of-stream
> conflict here. So, what does it report?

Built an LR(0) automaton with 1416 states.
Built an LR(1) automaton with 2009 states.
Warning: 145 states have an end-of-stream conflict.

Can I send you the file?

[signature of parser]

> I believe this is a separate issue. 

Yes, I agree.

> You are right in saying that the historic
> signature, which involves lexbuf, is dubious. Following your suggestion, we
> could just as well use
> 
>   parser: (state -> token * state) -> state -> ast * state
> 
> if we wish to promote a purely functional style (where values of type
> state are immutable), or just
> 
>   parser: (unit -> token) -> ast
> 
> if we are willing to accept mutable state. (I am sweeping the issue of
> locations under the rug; we should use token * location instead of just
> token.)

Or forget it, which is the approach taken by Felix: every token
contains its location: the user can organise this. This has the
advantage of not specifying a particular location format.

> That said, the historic signature 
> 
>   parser: (lexbuf -> token) -> lexbuf -> ast
> 
> is really equivalent to the previous one, in the sense that I can write
> functions that convert between the two styles (see attached file).

Yes, but you cannot write functions that take a state argument
because lexbuf is a fixed data type and there's no where to
add in any user state data.

> > The point again is that the token input to the parser is infinite: it can't
> > ever be an error to read a next token.
> 
> I beg to disagree. First, the input stream does not have to be infinite: if
> I am reading from a file, clearly it is finite.

EOF is returned an infinite number of times in C.

>  Second, regardless of whether
> the stream is finite or infinite, it *is* an error to read more tokens than
> you were supposed to. If the grammar's start symbol is S, then the parser
> should read a sequence of tokens that derives from S, and nothing more; it
> should not overshoot and consume the first token that follows.

This requires the definition: parse the *shortest* head of the
input stream.

> The only way of avoiding these conflicts is to change your grammar somehow.
> But I still haven't understood what causes these conflicts in your grammar.
> Perhaps it would be time to show it?

> ocamlyacc never complains. It just trusts you to know what you are doing.

I generate an .output file, grep for the word 'conflict',
and terminate my build if there is one found. I do not permit
any conflicts in my grammar: it's strictly unambiguous LALR(1).

It's also pure in the sense that it doesn't use crud 
like %left, %prec etc to resolve conflicts.
[The way dypgen does this is vastly superior!]


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