Start | prefix2ast
 

Abstrakt syntax träd



Ett abstrakt syntaxträd beskriver ett uttryck eller kod i form av ett träd.

Om AST

Programspråk inkl. python parsar koden du skrivit och konverterar det till ett abstrakt syntax -träd. Detta AST konverteras sedan till objektkod, vilket senare skickas in i en interpretator och koden får liv!

prefix till AST


Hur kan prefix notation användas? Låt oss titta på hur python själv "löser problemet" när python får ett uttryck att parsa. Python kan parsa, kompilera och exekvera sin egen kod så alla verktyg finns där. Vi kör vårt exempeluttryck genom pythons egen parser.
import ast uttryck = "17 - 120.9 * ( 12 + 12 * 312 ) - 8 / ( 3 + 1 )" print(ast.dump(ast.parse(uttryck, "", "eval")))

Klicka kör. Om vi snyggar till utskriften ser det ut som nedan. Vad vi ser kallas abstrakt syntax träd (AST). När vi kör pythonkod, så parsar python först koden och bygger ett abstrakt syntax träd (AST). (Därefter skapas objektkod och därefter interpreteras objektkoden, men det är en senare historia.)

Expression(

body=	BinOp(

 left=BinOp(
  left=Constant(value=17), 
  op=Sub(), 
  right=BinOp(
   left=Constant(value=120.9), 
   op=Mult(), 
   right=BinOp(
    left=Constant(value=12), 
    op=Add(), 
    right=BinOp(
     left=Constant(value=12), 
     op=Mult(), 
     right=Constant(value=312))    
   )
  )
 ), 

 op=Sub(),     
 right=BinOp(
  left=Constant(value=8), 
  op=Div(), 
  right=BinOp(
   left=Constant(value=3), 
   op=Add(), 
   right=Constant(value=1))
   )
 )
)

Vi kan vidare göra en graf av detta, närmare bestämt nedan abstrakta syntax träd (AST)



Ovan träd är AST -trädet för uttrycket
17 - 120.9 * ( 12 + 12 * 312 ) - 8 / ( 3 + 1 )

Prefix notation
- - 17 * 120.9 + 12 * 12 312 / 8 + 3 1

Jämför nu detta AST med prefix -uttrycket.

Okej, vi vänder nu på allt. Låt säga vi hade prefix -utrycket. Det är enkelt konvertera prefix -uttryck till just ett abstrakt syntax träd.

Vi går igenom prefix -uttrycket token för token.

prefix2ast algoritm


1. Om det är en siffra lägg på stacken.
2. Om är en operator, skapa en ny nod som får värdet av operatorn (value = operatorn). Pop:a samtidigt vänstervärdet, pop:a högervärdet. Lägg den nya nya noden på stacken.

class Node: def __init__(self, value): self.value = value self.left = None self.right = None def is_number(n): try: float(n) except: return False return True def construct_tree(prefix_expr): stack = [] tokens = prefix_expr.split()[::-1] for token in tokens: if is_number(token): stack.append(Node(token)) else: node = Node(token) node.left = stack.pop() node.right = stack.pop() stack.append(node) return stack.pop() def print_tree(node, level=0): if node is not None: print_tree(node.right, level + 1) print(' ' * 4 * level + '->', node.value) print_tree(node.left, level + 1) prefix = '- - 17 * 120.9 + 12 * 12 312 / 8 + 3 1' ast_tree = construct_tree(prefix) print_tree(ast_tree)
Evaluera ett ast träd
14.091968536377 ms