Parsing newbie -- recursion question (probably simple)

sonicsmooth@gmail.com
12 Nov 2005 16:08:02 -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: sonicsmooth@gmail.com
Newsgroups: comp.compilers
Date: 12 Nov 2005 16:08:02 -0500
Organization: http://groups.google.com
Keywords: parse, question

Hi, I'm trying to write a parser for SPICE files. In short, a SPICE
file "deck" describes a circuit, with each line "card" adding a
circuit element or describing something to the simulator. I wrote a
grammar for it because I didn't find any online. I'm implementing
this is Python and am not using any lex/yacc/gnu tool. I'd like to be
able to call a function for each rule and have it return a match or
not. BTW, I'm an EE not a CS person, so this is pretty much the first
time I'm writing something like this. I'm splitting up my tokens with
a regex.


I'm having trouble getting my head wrapped around recursion. If I have
the following rule to generate a list of nodes:


nodelist := nodelist node | node


where node is a terminal (in this case a user defined
string/token/whatever), then I'd like to write two functions like this:


def node(tokens):
        if valid_token_checker(tokens.pop(0)):
                return good
        else:
                return bad


def nodelist(tokens):
        # some logic maybe...
        # copy the tokens list in case I need to back up
        nodelist(tokens)
        # some logic for ANDing this with
        node(tokens)
        # some more logic for ORing this with
        node(tokens)


I don't understand how to keep from getting caught in an infinite
recursive loop. The only way out is to find a terminal node, but I'm
not sure how to do that if the first thing in the rule is to check
another nodelist. Should I check for the terminal first? Should I
carry around a flag someplace that says where I am in the rule? I'd
like to avoid explicit stacks and just use the function return stack as
my stack. I also want to avoid an official parser generator because a)
I'm doing this in python, b) SPICE syntax is simple enough that this
shouldn't be toooo hard, and c) I want to learn it this way.


Thanks for any/all help


Michael


Post a followup to this message

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