Re: [Caml-list] Array.make exception and parser

[Yitzhak Mandelbaum <yitzhakm@cs.princeton.edu>]

Good question -- its languages fall into neither of LL(k) or LR(k). It uses a form of priority parsing, with one token lookahead and a few grammar transformations (assuming camlp4 shares the same parsing technology as camlp5, and nothing has changed since I last took a look at the docs and source code).

In more detail:

Its basic operation is to try each branch in a series of branches until one is found which successfully parses beyond one token. So, it uses only 1 token of lookahead, and it decides which branch to take at the beginning of set of branches. These characteristics make it similar to LL(1). However, it does not ensure that branches do not conflict. So, if two branches share the same token (see more on this below), then the second one will never be taken. IIRC, the parsec parser combinator library has similar semantics for its standard branch combinator.

Furthermore, it performs a number of transformations: First, it does a (shallow) left factoring. So, if a set of branches are defined, it will left factor them without looking into any of the nonterminals. Second, it supports a certain amount of left-recursion through dynamic tracking of the current nonterminal.

--Yitzhak

On Jan 4, 2011, at 4:03 PM, Török Edwin wrote:

> On 2011-01-04 22:40, Lukasz Stafiniak wrote:
>> On Tue, Jan 4, 2011 at 9:31 PM, Francois Pottier
>> <Francois.Pottier@inria.fr> wrote:
>>> On Tue, Jan 04, 2011 at 08:30:48PM +0100, Daniel Bünzli wrote:
>>>> So everybody trades developer convenience for end user convenience --
>>>> I mean, the syntax errors produced by LR parsers are just terrible,
>>> 
>>> It is true that ocamlyacc (and Menhir) offer essentially no support for
>>> explaining parse errors.
>> 
>> But Menhir's support for grammar debugging is very nice and already a
>> strong enough argument to switch over from ocamlyacc!
>> 
> 
> How about camlp4, what kind of parser is it? LL/LR?
> I found its error messages more helpful than ocamlc's (for example just
> running my source code through camlp4o), though it could be better
> (it could say ; expected insteam of [semi]).
> 
> Best regards,
> --Edwin
> 
> -- 
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
> 

-----------------------------
Yitzhak Mandelbaum