Tengo una función básica para analizar una expresión ceceo. Utiliza un bucle while, pero como ejercicio me gustaría convertirlo en una función recursiva. Sin embargo, es un poco complicado para mí hacerlo. Esto es lo que tengo hasta ahora:
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
Y entonces analizaría algo como esto:
(+ 2 (* 3 4))
En esto:
[['+', '2', ['*', '3', '4']]]
¿Cuál sería un ejemplo de cómo podría hacer que la función anterior sea recursiva? Hasta ahora he empezado con algo como:
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)
Pero parece un poco extraño (como si la recursividad no fuera útil aquí). ¿Cuál sería una mejor manera de construir esto? ¿O tal vez un algoritmo mejor/más elegante para construir este ast simple?
1
Vea mi respuesta de desbordamiento de pila sobre cómo crear analizadores de descenso recursivos: stackoverflow.com/a/2336769/120163
- Ira Baxter
31 de marzo de 2021 a las 3:38
------------------------------------
Puedes utilizar una función generadora recursiva:
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))
Salida:
[['+', '2', ['*', '3', '4']]]
4
Vaya, eso es tan conciso y genial. ¿Podría proporcionarme un enlace para que pueda aprender un poco sobre eso? ¿Es n:= algo nuevo en Python, nunca lo había visto antes? Además, ¿quieres agregar algunos comentarios al código para mostrar lo que está haciendo y todo?
-David542
28 de marzo de 2021 a las 4:59
2
@David542 Consulte mi edición reciente, ya que agregué varios comentarios para aclarar el proceso. n:= es una expresión de asignación, introducida recientemente en PVersiones de ython >= 3.8. Vea más aquí: stackoverflow.com/questions/50297704/…
-Ajax1234
28/03/2021 a las 15:29
¡Gracias por la actualización! Una pregunta: publiqué mi propia respuesta en la parte inferior, ¿cuál es la diferencia entre (1) usar el siguiente en lugar de pop; y luego (2) ¿usar rendimiento en lugar de simplemente devolver en este caso?
-David542
31 de marzo de 2021 a las 1:24
@David542 El paradigma recursivo es el mismo y ambos métodos se basan en referencias para consumir adecuadamente los tokens. Sin embargo, en mi opinión, el rendimiento es una forma más limpia de manejar casos en los que el objetivo es recopilar resultados individuales, producidos en un proceso iterativo, en un contenedor.
-Ajax1234
31 de marzo de 2021 a las 1:49
------------------------------------
De manera similar a la otra respuesta, pasaría a la función recursiva el token que finalizará la expresión actual. Este suele ser el paréntesis de cierre, pero para la primera llamada,será el final de la entrada (Ninguno).
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))
Llamar como:
ast = build_ast(['(', '+', '2', '(', '*', '3', '4', ')', ')'])
2
¿Es next(it, None)) una forma de hacer tokens.pop() sin IndexError cuando llega al final?
-David542
31 de marzo de 2021 a las 1:08
2
En realidad no. pop (sin argumento) elimina el último elemento del final of la lista, mientras que next(it) lee el siguiente valor de un iterador (en este caso creado con iter(tokens)), de izquierda a derecha. Es más como i += 1; fichas[yo]. De hecho, el argumento Ninguno evitará un error cuando no haya más valor siguiente.
-trincot
31 de marzo de 2021 a las 5:49
------------------------------------
Los otros dos enfoques son geniales, aquí hay uno más:
# 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
1
2
Tenga en cuenta que esta función tiene un efecto secundario: los tokens se vaciarán.
-trincot
31 de marzo de 2021 a las 5:52
