Make a while parsing function recursive

user_651174 0
Viewed 178

I have a basic function to parse a lisp expression. It's using a while loop, but as an exercise I'd like to convert it into a recursive function. However, it's a bit tricky for me to do. Here is what I have thus far:

def build_ast(self, tokens=None):
    # next two lines example input to make self-contained
    LEFT_PAREN, RIGHT_PAREN = '(', ')'
    tokens = ['(', '+', '2', '(', '*', '3', '4', ')', ')']
    while RIGHT_PAREN in tokens:
        right_idx = tokens.index(RIGHT_PAREN)
        left_idx = right_idx - tokens[:right_idx][::-1].index(LEFT_PAREN)-1
        extraction = [tokens[left_idx+1:right_idx],]
        tokens = tokens[:left_idx] + extraction + tokens[right_idx+1:]
    ast = tokens
    return ast

And so it would parse something like this:

(+ 2 (* 3 4))

Into this:

[['+', '2', ['*', '3', '4']]]

What would be an example of how I could make the above function recursive? So far I've started with something like:

def build_ast(self, ast=None):
    if ast is None: ast=self.lexed_tokens
    if RIGHT_PAREN not in ast:
        return ast
    else:
        right_idx = ast.index(RIGHT_PAREN)
        left_idx = right_idx - ast[:right_idx][::-1].index(LEFT_PAREN)-1
        ast = ast[:left_idx] + [ast[left_idx+1:right_idx],] + ast[right_idx+1:]
        return self.build_ast(ast)

But it just comes across as a bit strange (as if the recursion isn't helpful here). What would be a better way to construct this? Or perhaps a better/more elegant algorithm to build this simple ast?

abstract-syntax-tree algorithm parsing python
3 Answers

You can use a recursive generator function:

def _build_ast(tokens):
   LEFT_PAREN, RIGHT_PAREN = '(', ')'
   #consume the iterator until it is empty or a right paren occurs
   while (n:=next(tokens, None)) is not None and n != RIGHT_PAREN:
      #recursively call _build_ast if we encounter a left paren
      yield n if n != LEFT_PAREN else list(_build_ast(tokens))
   

def build_ast(tokens):
   #pass tokens as an iterator to _build_ast
   return list(_build_ast(iter(tokens)))

tokens = ['(', '+', '2', '(', '*', '3', '4', ')', ')']
print(build_ast(tokens))

Output:

[['+', '2', ['*', '3', '4']]]
user_73267380

Similar to the other answer, I would pass to the recursive function the token that will end the current expression. This usually is the closing parenthesis, but for the very first call, it will be the end-of-input (None).

def build_ast(tokens):
    LEFT_PAREN, RIGHT_PAREN = '(', ')'
    it = iter(tokens)  # Iterator over the input
    
    # Recursive (generator) function that processes tokens until the close 
    #   of the expression, i.e until the given token is encountered
    def recur(until=RIGHT_PAREN):
        # Keep processing tokens until closing token is encountered
        while (token := next(it, None)) != until:
            # If parenthesis opens, recur and convert to list
            #    otherwise just yield the token as-is
            yield list(recur()) if token == LEFT_PAREN else token

    # Main recursive call: process until end of input (i.e. until None)
    return list(recur(None))

Call as:

ast = build_ast(['(', '+', '2', '(', '*', '3', '4', ')', ')'])
user_54598390

The other two approaches are great, here's one more:

# Helper function: pop from left or return default
pops = lambda l, d=None: l.pop(0) if l else d

def read_from_tokens(tokens):
    L = []
    while (token := pops(tokens, ')')) != ')':
        L.append(token if token!='(' else read_from_tokens(tokens))
    return L
user_6511740
Related