Re: [Caml-list] Yacc limitations

Re: [Caml-list] Yacc limitations

[yoann padioleau]

> I am getting very much annoyed with the obtusity of the LALR-yacc parser
> generators. I have unsurmountable difficulties at teaching ocamlyacc how
> to parse SQL decently.
> 
> What is the "way to go" in terms of parser generators for Ocaml? I'd
> like to see if there is some level of agreement in the community on this
> issue.

I personnaly use ocamlyacc and even if there is some difficulties, I like it.
The problems is when there is an ambiguity in the grammar, in which case I look at the output file
generated by ocamlyacc -v, C-s "conflict" in the file,  and hope that my brain will find an easy solution.

All the ocaml project that I know that need some complex parsing use ocamlyacc. 
Some people also use streams but are limited to write LL(1) grammars.
Some people use parser combinators to do the same kind of stuff that stream offers. 

What is the problem with your SQL grammar and with ocamlyacc ? 

Re: [Caml-list] Yacc limitations

[brogoff]

On Thu, 22 Sep 2005, yoann padioleau wrote:
> > I am getting very much annoyed with the obtusity of the LALR-yacc parser
> > generators. I have unsurmountable difficulties at teaching ocamlyacc how
> > to parse SQL decently.
> >
> > What is the "way to go" in terms of parser generators for Ocaml? I'd
> > like to see if there is some level of agreement in the community on this
> > issue.

It would be great to see an all OCaml parser generator, something really fancy,
like an Earley parser. I say "all OCaml", as opposed to, say an OCaml backend
for some existing tool like ANTLR, because code cannibalization is good.
Anyways, if you're looking to do something like this, an ocamllex compatible,
mostly yacc like earley style parser generator would be interesting. Or one
that generates the scanner too. To get people to move beyond yacc you need
to offer something that's both better and (mostly) compatible. All IMO of
course.

> I personnaly use ocamlyacc and even if there is some difficulties, I like it.

I use it because I know yacc, and lots of people I work with know yacc, it
comes with OCaml, and there's a lot of available documentation. I wouldn't say
I like it, but I don't hate it and it's good enough and I'm too lazy to learn
anything else right now.

> All the ocaml project that I know that need some complex parsing use ocamlyacc.
> Some people also use streams but are limited to write LL(1) grammars.

No, they make it easy to write recursive descent parsers "inline", and it's
pretty easy (too easy) to hack recursive descent parsers to handle greater
lookaheads. Neat stuff, but not widely used as far as I can see.

-- Brian

Re: [Caml-list] Yacc limitations

[Pierre Boulet]

Hi,

I like using Camlp4 for that purpose. It has a very convenient way to 
write parsers (the EXTEND notation). Its power is not directly 
comparable to LALR but I find it suiting my needs (at least it is enough 
to parse ocaml). The main pain is writing the lexer that feeds the 
parser. That I remember from the early days of camlp4, it may have changed.

Regards,

Pierre.

Christophe Raffalli a écrit :
> Alex Baretta a écrit :
> 
>> I am getting very much annoyed with the obtusity of the LALR-yacc parser
>> generators. I have unsurmountable difficulties at teaching ocamlyacc how
>> to parse SQL decently.
>>
>> What is the "way to go" in terms of parser generators for Ocaml? I'd
>> like to see if there is some level of agreement in the community on this
>> issue.
>>
> 
> may be give a try to elkhound
> (http://www.cs.berkeley.edu/~smcpeak/elkhound/) ? It generated both
> OCaml and C++. I haven't used it, But it seems nice and will remove the
> LALR(1) constraint .
> 
> 
>> Alex
>>
>>
> 
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: [Caml-list] Yacc limitations

[Alan Falloon]

Alex Baretta wrote:

>I am getting very much annoyed with the obtusity of the LALR-yacc parser
>generators. I have unsurmountable difficulties at teaching ocamlyacc how
>to parse SQL decently.
>
>What is the "way to go" in terms of parser generators for Ocaml? I'd
>like to see if there is some level of agreement in the community on this
>issue.
>  
>
I am not very familiar with SQL, so I may be missing something 
important, but a quick google search for 'sql grammar' turned up what 
appears to be an LALR grammer already in *yacc syntax at 
http://docs.openlinksw.com/virtuoso/GRAMMAR.html

I have also been frustrated in the past with yacc, bison, and ocamlyacc, 
but its usually not the LALR restriction as much as the lack of decent 
short-hand for common operations like a list of elements (with or 
without a separator token) which make the grammar a lot more verbose 
than it should really need to be. Also, with the C parser generators, it 
was always a huge pain to represent the parse tree in any reasonable 
way, but with ocaml and ocamlyacc that is a non-issue.

I do agree that debugging conflicts seems to be harder than it should 
be. It would be wonderful if that could be addressed.

As far as the LALR restriction goes, bison has an optional GLR parser 
(see http://www.delorie.com/gnu/docs/bison/bison_90.html) that seems 
like it could be added to ocamlyacc with a pretty straightforward 
translation if anyone had the time and motivation to do it.

--
Alan Falloon

Re: [Caml-list] Yacc limitations

[Alex Baretta]

yoann padioleau wrote:
>>>What is the problem with your SQL grammar and with ocamlyacc ? 
>>
>>The problem is that context-free is bad. Did you ever see or hear of any
>>real language where the context of a token is not meaningful? 
> 
> 
> Even with a context free grammar I can capture the context of a token.
> in 
> S -> A B token C 

Sometimes you can capture enough. Sometimes not enough. The point is
that some of the alternative expansions of S are meaningful in some
contexts and not in others.

> Because grammar is about syntax, not semantics. The same is true for natural langage. 

Not quite. Remember "semantic actions"? A parser generator like yacc
maps semantics onto a set of strings by recognizing structures generated
by a grammar. We are hardly ever interested in recognizing but almost
always in "semantizing" a string of a language.

> Now let's say that you can write context free grammar for your SQL langage, what would you write ? 
> You now have the ability to put multiple non-terminal at the left of the rule, such as in 
> 
> A B C -> D 
> 
> What would you write for your SQL grammar ? 

I'm not sure what I would write in a generalized grammar framework. What
I definitely sometimes feel the need for is the possibility of selecting
within a semantic action the set of "active" productions which are the
parser is "allowed" to use until further notice. This would allow me to
provide an explicit distinction in cases where contextual
information--implicitly available within the scope of a semantic
action--allows to discriminate any ambiguity in the production rules.

Alex


-- 
*********************************************************************
http://www.barettadeit.com/
Baretta DE&IT
A division of Baretta SRL

tel. +39 02 370 111 55
fax. +39 02 370 111 54

Our technology:

The Application System/Xcaml (AS/Xcaml)
<http://www.asxcaml.org/>

The FreerP Project
<http://www.freerp.org/>

Re: [Caml-list] Yacc limitations

[yoann padioleau]

> > What is the problem with your SQL grammar and with ocamlyacc ? 
> 
> The problem is that context-free is bad. Did you ever see or hear of any
> real language where the context of a token is not meaningful? 

Even with a context free grammar I can capture the context of a token.
in 
S -> A B token C 

I control that token  is in the context  of having A B before and C after.


> It is
> often possible and sometimes easy to describe the set of strings
> belonging to a language in terms of a context-free grammar, but it is
> very difficult in general to describe *the semantics* of that set of
> strings without reference to the context.

Because grammar is about syntax, not semantics. The same is true for natural langage. 

Now let's say that you can write context free grammar for your SQL langage, what would you write ? 
You now have the ability to put multiple non-terminal at the left of the rule, such as in 

A B C -> D 

What would you write for your SQL grammar ? 


> 
> Now, I don't necessarily ask for undecidable generalized
> grammars--although IIRC the camlp4 parsing engine actually provides them
> as LL1+backtracking. I would be more than happy to have a smarter
> context-free yacc-like tool providing human readable explanations of
> syntactic conflicts.

Yes a better explanation of conflicts is something I would like too. 

Re: [Caml-list] Yacc limitations

[Jake A. Kirilenko]

Hello Alex,

Thursday, September 22, 2005, 1:57:03 PM, you wrote:

I'm  developing  a  RD  parser  generator  (YARD)  in  pure Ocaml that
combines  modern  ideas  about functional parsers. I have not analyzed
the  class  of  grammars  being parsed but it is wider then CFG. Smth
about left attributed but I am not ready to discuss this topic.
Short example of rule `iter' that applies argument `a' `n' times:

iter[a n] : => n > 0 =>   <hd> = a  <tl> = iter[ a  (n - 1)] {hd::tl}
           | => n = 0 => {[]}
(  `=> ... =>' is a predicate/guardian, `<..>' is a binding)
           
Do you believe that this kind of parsers are able to parse SQL?

YARD  is open source project, but I have not published sources yet but
if somebody is interested I will. Generator (YARD) is ready to be used
and is being used in our projects, but it rapidly changes =). YARD

AB> I am getting very much annoyed with the obtusity of the LALR-yacc parser
AB> generators. I have unsurmountable difficulties at teaching ocamlyacc how
AB> to parse SQL decently.

AB> What is the "way to go" in terms of parser generators for Ocaml? I'd
AB> like to see if there is some level of agreement in the community on this
AB> issue.

AB> Alex





Best regards,
 Jake                            mailto:jake@freemail.ru

Re: [Caml-list] Yacc limitations

[Christophe TROESTLER]

On Thu, 22 Sep 2005, Alex Baretta <alex@barettadeit.com> wrote:
> 
> What is the "way to go" in terms of parser generators for Ocaml? I'd
> like to see if there is some level of agreement in the community on this
> issue.

Maybe you could write an OCaml backend for ANTLR
(http://www.antlr.org/) for which a SQL2 grammar is already available?

My 2¢,
ChriS

Re: [Caml-list] Yacc limitations

[Alex Baretta]

Christophe Raffalli wrote:
> Alex Baretta a écrit :
> 
>> I am getting very much annoyed with the obtusity of the LALR-yacc parser
>> generators. I have unsurmountable difficulties at teaching ocamlyacc how
>> to parse SQL decently.
>>
>> What is the "way to go" in terms of parser generators for Ocaml? I'd
>> like to see if there is some level of agreement in the community on this
>> issue.
>>
> 
> may be give a try to elkhound
> (http://www.cs.berkeley.edu/~smcpeak/elkhound/) ? It generated both
> OCaml and C++. I haven't used it, But it seems nice and will remove the
> LALR(1) constraint .

Elkhound is C++ stuff. I really would prefer to avoid having to
introduce C++ in my toolchain. Is it possible to install Elkhound as a
Debian package and forget about it?

Alex


-- 
*********************************************************************
http://www.barettadeit.com/
Baretta DE&IT
A division of Baretta SRL

tel. +39 02 370 111 55
fax. +39 02 370 111 54

Our technology:

The Application System/Xcaml (AS/Xcaml)
<http://www.asxcaml.org/>

The FreerP Project
<http://www.freerp.org/>

Re: [Caml-list] Yacc limitations

[Christophe Raffalli]

Alex Baretta a écrit :
> I am getting very much annoyed with the obtusity of the LALR-yacc parser
> generators. I have unsurmountable difficulties at teaching ocamlyacc how
> to parse SQL decently.
> 
> What is the "way to go" in terms of parser generators for Ocaml? I'd
> like to see if there is some level of agreement in the community on this
> issue.
> 

may be give a try to elkhound
(http://www.cs.berkeley.edu/~smcpeak/elkhound/) ? It generated both
OCaml and C++. I haven't used it, But it seems nice and will remove the
LALR(1) constraint .


> Alex
> 
>