:: Re: [DNG] Studying C as told. (For …
Etusivu
Poista viesti
Vastaa
Lähettäjä: Hendrik Boom
Päiväys:  
Vastaanottaja: dng
Aihe: Re: [DNG] Studying C as told. (For help)
On Fri, Jul 08, 2016 at 05:05:29PM +0100, KatolaZ wrote:
> On Fri, Jul 08, 2016 at 11:48:25AM -0400, Hendrik Boom wrote:
>
> [cut]
>
> > >
> > > I am not asking because I want to be pedantic, but rather because this
> > > is usually where parsing context-free languages becomes an enormous
> > > error-prone mess, and is the reason why we have tools like lex/flex
> > > and yacc/bison which take care of constructing the parser associated
> > > to a set of productions on your behalf.
> >
> > It is precisely where recursive descent becomes a really easy wy of
> > writing a parser. This isn't a difficult language to hand-write a
> > parser for. Look up "recursive descent parsing" in the Wikipedia, and
> > you'll see how easy it is:
> >
>
> You should first put your language in LL(k) form, which is normally
> done at the price of multiplying the number of productions, and the
> number of functions to be implemented, unless the language is
> extremely simple. And maybe Edward's language is simple enough.


I'm pretty sure it is.
>
> I have done that for several languages in the past, and I didn't find
> it particularly fun or instructive. Once you have your grammar in
> LL(k) form (and the procedure to transform a language in LL(k) form is
> basically automatic), it's just about writing mostly repetitive code
> which can be efficiently generated by flex and bison in a few seconds.


I've found recursive descent techniques easier for parsing C++ than LR
techniques. Of course that was about two decades ago. THe language may
have changed.

The reason is that recursive descent integrates well with backtracking.
This is invoked in the original language definition, where it says
soething like 'if it can be parsed as a declaration, it is one;
otherwise parse it as a statement'. That is an invitation to backtrack.
Getting LR to handle it is a case of unbounded lookahead. Not
impossible, but not an easy fit into the formalism.

As for repetitive code, that's a lot of tedium. For large grammars, you
do want to machine-generate your parser. And it does help to have
automatic sanity checks on the grammar.

I used to be an LR advocate, because it was much more powerful than
other tehniques in terms of the number of context-free grammars it can
handle. But I also have found it difficult to adapt to unusual
pragmatics. This is usually dead easy with recursive descent -- you
core the special casess into the parser, using the same programming
language you write the parser in.

>
> But again, I agree that we can disagree on what is fun/instructive and
> what is not :)


Edward is trying to hand-code a parser, and he'll learn parsing and some
more C. Using yacc, or bison, or, for that matter, antlr, isn't going
to help him with this.

If he were trying to learn all about parsing, I'd blast him with LL, LR,
NSLR, etc.

What's fun/instructive depends on what you're trying to learn.

-- hendrik


>
> HND
>
> KatolaZ
>
> -- 
> [ ~.,_  Enzo Nicosia aka KatolaZ - GLUGCT -- Freaknet Medialab  ]  
> [     "+.  katolaz [at] freaknet.org --- katolaz [at] yahoo.it  ]
> [       @)   http://kalos.mine.nu ---  Devuan GNU + Linux User  ]
> [     @@)  http://maths.qmul.ac.uk/~vnicosia --  GPG: 0B5F062F  ] 
> [ (@@@)  Twitter: @KatolaZ - skype: katolaz -- github: KatolaZ  ]
> _______________________________________________
> Dng mailing list
> Dng@???
> https://mailinglists.dyne.org/cgi-bin/mailman/listinfo/dng