S-exression parsing

[George Sakkis]

The S-expression parser below works, but I wonder if it can be simplified; it's not as short and
straightforward as I would expect given the simplicity of S-expressions. Can you see a simpler
non-recursive solution ?

George

# usage

parseSexpression("(a (b c) (d))") ['a', ['b', 'c'], ['d']]
parseSexpression("(a (b c)) (d))") ValueError: Unbalanced right parenthesis: (a (b c)) (d))
parseSexpression("(a ((b c) (d))") ValueError: Unbalanced left parenthesis: (a ((b c) (d))
parseSexpression("(a (b c)) (d)") ValueError: Single s-expression expected (2 given)
parseSexpression("(a (b c)) e")

ValueError: Unenclosed subexpression (near e)


def parseSexpression(expression):
subexpressions,stack = [],[]
for token in re.split(r'([()])|\s+', expression):
if token == '(':
new = []
if stack:
stack[-1].append(new)
else:
subexpressions.append(new)
stack.append(new)
elif token == ')':
try: stack.pop()
except IndexError:
raise ValueError("Unbalanced right parenthesis: %s" % expression)
elif token:
try: stack[-1].append(token)
except IndexError:
raise ValueError("Unenclosed subexpression (near %s)" % token)
if stack:
raise ValueError("Unbalanced left parenthesis: %s" % expression)
if len(subexpressions) > 1:
raise ValueError("Single s-expression expected (%d given)" % len(subexpressions))
return subexpressions[0]


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Haiku of the day:

"The Web site you seek / Can not be located but / Countless more exist. "
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 

[Michael Spencer]

The S-expression parser below works, but I wonder if it can be simplified; it's not as short and
straightforward as I would expect given the simplicity of S-expressions. Can you see a simpler
non-recursive solution ?

How about this (minus your error checking)?

def parseS(expression):
stack = []
stacks = []
for token in re.split(r'([()])|\s+', expression):
print stack
if token == '(':
stacks.append(stack)
stack = []
elif token == ')':
stacks[-1].append(stack)
stack = stacks.pop()
elif token:
stack.append(token)
return stack[0]

Michael