Re: [Caml-list] Ocamlyacc vs stream parser

[Diego Olivier Fernandez Pons <Diego.FERNANDEZ_PONS@etu.upmc.fr>]

    Bonjour,

Michal Moskal a écrit :

> Sorry, I thought camlp4 recognizes LL(1) languages, and my dragon
> book copy states that LR(1) > LL(1) (I'm not sure about LARL(1)
> though.

Well... I must admit remembering that LL(1) < LALR(1) was almost true.
Which means that I knew from the beginning you weren't so far :-)

I found in comp.compilers an example by Terence Parr of a LL(1)
grammar which is not LALR(1) - I have not checked it ! -

http://compilers.iecc.com/comparch/article/93-09-025

He says 'there is at least one LL(1) grammar which is not LALR(1)'

Same comment in the Errata page of Andrew Appel's book, edition of
1997 (the figure of that edition was incorrect)

http://www.cs.princeton.edu/~appel/modern/basic/ml/errata.html

'Figure 3.26 incorrectly shows LL(1) as a subset of SLR. In fact,
LL(1) is not even a subset of LALR(1): there is an LL(1) grammar that
is not LALR(1)'

And a lot of people state that LL(1) < LALR(1) is 'essentially' true.

Wim Pijls writes in his paper 'unifying LL and LR' that LL(1) is a
subclass of LALR(1) but he seems to have removed the problematic
cases. (Once more, I have not checked the proofs since it wasn't the
point I was interested in when reading that paper).

        Diego Olivier

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners