Re: Parsing newbie -- recursion question (probably simple)

Chris F Clark <cfc@shell01.TheWorld.com>
15 Nov 2005 23:28:34 -0500

          From comp.compilers

Related articles
Parsing newbie -- recursion question (probably simple) sonicsmooth@gmail.com (2005-11-12)
Re: Parsing newbie -- recursion question (probably simple) wyrmwif@tsoft.org (SM Ryan) (2005-11-13)
Re: Parsing newbie -- recursion question (probably simple) DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2005-11-13)
Re: Parsing newbie -- recursion question (probably simple) desw@sussex.ac.uk (Des Watson) (2005-11-13)
Re: Parsing newbie -- recursion question (probably simple) 63q2o4i02@sneakemail.com (2005-11-15)
Re: Parsing newbie -- recursion question (probably simple) cfc@shell01.TheWorld.com (Chris F Clark) (2005-11-15)
Re: Parsing newbie -- recursion question (probably simple) nicola.musatti@gmail.com (Nicola Musatti) (2005-11-15)
| List of all articles for this month |

From: Chris F Clark <cfc@shell01.TheWorld.com>
Newsgroups: comp.compilers
Date: 15 Nov 2005 23:28:34 -0500
Organization: The World Public Access UNIX, Brookline, MA
References: 05-11-059
Keywords: parse
Posted-Date: 15 Nov 2005 23:28:34 EST

Michael wrote:
> Hi, I'm trying to write a parser for SPICE files.
...
> I'm implementing this is Python and am not using any lex/yacc/gnu
> tool.
...
> I'm having trouble getting my head wrapped around recursion.


Parsing while not difficult, is a lot subtler than most people
realize. You are fortunate that you figured out that recursion was
potentially problematic. It is unfortunately not the only
thing. There are lots of little gotchas (common prefixes that need to
be left-factored, for example) that one needs to attend to. Some of
the problems will cause obvious flaws in the resulting parser, others
may go undetected at first--what if the infinite loop was in an
obscure part of the grammar you didn't happen to test? Many simple
languages are actually not simple to parse.


This is why one *SHOULD* use a parser generator. A good parser
generator will give you error messages when you make mistakes that it
is programmed to catch. You can still make other mistakes, but at
least you won't make the errors the parser generator knows about.


This is particularly true if one is a "newbie". You don't have the
experience to know what can go wrong. That said, I've been writing
compilers for some 20+ years and still use a parser generator if the
grammar has more than about half-a-dozen productions, expecially if
the result is something I care that I get right and not a one-off.


Next, you might find that taking a class (or reading a textbook) can
help. That would acquaint you with FIRST and FOLLOW sets and the LL
conditions. A good book would might even teach you how to factor
grammars and how to handle if-then-else trees. Even a modest book
will teach you about left versus right recursion.


Finally, I do believe there are parser generators that output Python.
In particular, I believe I read about Python output for PCCTS/ANTLR.


So, you've shown some promise by writing a grammar before starting
your implementation. Take the next step and use a tool. You will
actually learn *more* that way. Otherwise, as some one wise once
said, "those who refuse to learn from history are forced to repeat
it."


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.