Recursive parsing for lisp like syntax

Question

im trying to parse lines in the form:

(OP something something (OP something something ) ) ( OP something something )

Where OP is a symbol for a logical gate (AND, OR, NOT) and something is the thing i want to evaluate.

The output im looking for is something like:

{ 'OPERATOR': [condition1, condition2, .. , conditionN] }

Where a condition itself can be a dict/list pair itself (nested conditions). So far i tried something like:

        tree = dict()
        cond = list()
        tree[OP] = cond


    for string in conditions:
        self.counter += 1
        if string.startswith('('):
            try:
                OP = string[1]
            except IndexError:
                OP = 'AND'
            finally:
                if OP == '?':
                    OP = 'OR'
                elif OP == '!':
                    OP = 'N'

            # Recurse
            cond.append(self.parse_conditions(conditions[self.counter:], OP))
            break

        elif not string.endswith(")"):
            cond.append(string)

        else:
            return tree

    return tree

I tried other ways aswell but i just can't wrap my head around this whole recursion thing so im wondering if i could get some pointers here, i looked around the web and i found some stuff about recursive descent parsing but the tutorials were all trying to do something more complicated than i needed.

PS: i realize i could do this with existing python libraries but what would i learn by doing that eh?

Is it the actual recursion you have problem with understanding, or how a recursive descent parser works? — Some programmer dude
– Some programmer dude, Commented Mar 28, 2013 at 10:46
And what if there's a space after '('? Don't try to reinvent the bicycle, learn from a nice and clean library like code.google.com/p/funcparserlib or pyparsing.wikispaces.com — SK-logic
– SK-logic, Commented Mar 28, 2013 at 10:55
@JoachimPileborg I guess its the whole recursion thing, i just can't get it right. — axujen
– axujen, Commented Mar 28, 2013 at 11:06
@SK-logic I have that taken care of, and im not trying to reinvent the wheel im trying to learn. — axujen
– axujen, Commented Mar 28, 2013 at 11:08
You're learning the wrong way. Ad hoc solutions like yours won't teach you anything useful. You'd better learn the right approach straight away, and the right approach is using combinators. It's also easier to understand, cleaner and much more flexible. So if you want to learn, start writing your own combinators library. — SK-logic
– SK-logic, Commented Mar 28, 2013 at 11:10

georg · Accepted Answer · 2013-03-28 11:40:47Z

6

I'm posting this without further comments, for learning purposes (in the real life please do use a library). Note that there's no error checking (a homework for you!)

Feel free to ask if there's something you don't understand.

# PART 1. The Lexer

symbols = None

def read(input):
    global symbols
    import re
    symbols = re.findall(r'\w+|[()]', input)

def getsym():
    global symbols
    return symbols[0] if symbols else None

def popsym():
    global symbols
    return symbols.pop(0)

# PART 2. The Parser
# Built upon the following grammar:
#  
#     program = expr*
#     expr    = '(' func args ')'
#     func    = AND|OR|NOT
#     args    = arg*
#     arg     = string|expr
#     string  = [a..z]

def program():
    r = []
    while getsym():
        r.append(expr())
    return r

def expr():
    popsym() # (
    f = func()
    a = args()
    popsym() # )
    return {f: a}

def func():
    return popsym()

def args():
    r = []
    while getsym() != ')':
        r.append(arg())
    return r

def arg():
    if getsym() == '(':
        return expr()
    return string()

def string():
    return popsym()

# TEST = Lexer + Parser

def parse(input):
    read(input)
    return program()

print parse('(AND a b (OR c d)) (NOT foo) (AND (OR x y))')
# [{'AND': ['a', 'b', {'OR': ['c', 'd']}]}, {'NOT': ['foo']}, {'AND': [{'OR': ['x', 'y']}]}]

edited Mar 28, 2013 at 11:40

answered Mar 28, 2013 at 11:32

georg

216k57 gold badges324 silver badges401 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

axujen Over a year ago

Thank you. This does exactly what i needed. I still have to figure how exactly it does it but your code will help greatly so thank you.

Collectives™ on Stack Overflow

Recursive parsing for lisp like syntax

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related