Obsah
2. Ukázka použití tokenů INDENT a DEDENT
3. Tokenizace kódu s vnořenými úplnými konstrukcemi if-else
5. Rekurzivní průchod AST s pevně daným pořadím procházení uzly
6. Rekurzivní průchod AST se zvýrazněním úrovně
8. Vizualizace AST jednoduchého výrazu
9. Vizualizace AST programu pro výpočet prvočísel
10. Vizualizace AST programu pro provádění asynchronních operací
11. Rozpoznání uzlů tvořících algebraický výraz
12. Algebraický výraz s proměnnými
13. Překlad AST s jeho spuštěním
14. Repositář s demonstračními příklady
1. Tokenizace bloků v Pythonu
V diskuzi pod úvodním článkem zazněl mj. i zajímavý dotaz, jak se v tokenizovaném kódu vlastně rozeznávají začátky a konce bloků. V „klasických“ lexerech (tedy nástrojích provádějících tokenizaci) určených například pro zpracování zdrojových kódu v jazyku C či Pythonu, se běžně pracuje s tokeny reprezentujícími znaky „{“ a „}“ popř. slova begin a end – samotný lexer ovšem tyto tokeny dále nerozlišuje (tj. například neví, zda znak „{“ reprezentuje začátek programového bloku nebo deklaraci struktury). Naproti tomu v lexeru Pythonu je tomu poněkud jinak, protože bloky jsou značeny odsazením. Z tohoto důvodu lexer (s využitím k tomu určené speciální logiky) rozlišuje tokeny INDENT a DEDENT.
2. Ukázka použití tokenů INDENT a DEDENT
Pro otestování, jakým způsobem se v tokenizovaném kódu rozeznávají začátky a konce bloků s využitím tokenů INDENT a DEDENT, se pokusíme o tokenizaci tohoto zdrojového kódu s trojicí vnořených bloků if (to, jaká podmínka se testuje, je v dané chvíli nepodstatné):
if True:
if False:
if False and True:
print("impossible")
Tokenizaci provedeme tímto skriptem:
import tokenize
with tokenize.open("ifs1.py") as fin:
token_generator = tokenize.generate_tokens(fin.readline)
for token in token_generator:
print(token)
Výsledkem tokenizace s využitím výše uvedeného skriptu je sekvence tokenů, v nichž jsou zvýrazněny právě tokeny INDENT a DEDENT. Povšimněte si toho, že token INDENT je vždy prvním tokenem na prvním odsazeném řádku bloku. Naproti tomu token DEDENT je „hlášen“ na prázdném řádku:
TokenInfo(type=1 (NAME), string='if', start=(1, 0), end=(1, 2), line='if True:\n')
TokenInfo(type=1 (NAME), string='True', start=(1, 3), end=(1, 7), line='if True:\n')
TokenInfo(type=54 (OP), string=':', start=(1, 7), end=(1, 8), line='if True:\n')
TokenInfo(type=4 (NEWLINE), string='\n', start=(1, 8), end=(1, 9), line='if True:\n')
TokenInfo(type=5 (INDENT), string=' ', start=(2, 0), end=(2, 4), line=' if False:\n')
TokenInfo(type=1 (NAME), string='if', start=(2, 4), end=(2, 6), line=' if False:\n')
TokenInfo(type=1 (NAME), string='False', start=(2, 7), end=(2, 12), line=' if False:\n')
TokenInfo(type=54 (OP), string=':', start=(2, 12), end=(2, 13), line=' if False:\n')
TokenInfo(type=4 (NEWLINE), string='\n', start=(2, 13), end=(2, 14), line=' if False:\n')
TokenInfo(type=5 (INDENT), string=' ', start=(3, 0), end=(3, 8), line=' if False and True:\n')
TokenInfo(type=1 (NAME), string='if', start=(3, 8), end=(3, 10), line=' if False and True:\n')
TokenInfo(type=1 (NAME), string='False', start=(3, 11), end=(3, 16), line=' if False and True:\n')
TokenInfo(type=1 (NAME), string='and', start=(3, 17), end=(3, 20), line=' if False and True:\n')
TokenInfo(type=1 (NAME), string='True', start=(3, 21), end=(3, 25), line=' if False and True:\n')
TokenInfo(type=54 (OP), string=':', start=(3, 25), end=(3, 26), line=' if False and True:\n')
TokenInfo(type=4 (NEWLINE), string='\n', start=(3, 26), end=(3, 27), line=' if False and True:\n')
TokenInfo(type=5 (INDENT), string=' ', start=(4, 0), end=(4, 12), line=' print("impossible")\n')
TokenInfo(type=1 (NAME), string='print', start=(4, 12), end=(4, 17), line=' print("impossible")\n')
TokenInfo(type=54 (OP), string='(', start=(4, 17), end=(4, 18), line=' print("impossible")\n')
TokenInfo(type=3 (STRING), string='"impossible"', start=(4, 18), end=(4, 30), line=' print("impossible")\n')
TokenInfo(type=54 (OP), string=')', start=(4, 30), end=(4, 31), line=' print("impossible")\n')
TokenInfo(type=4 (NEWLINE), string='\n', start=(4, 31), end=(4, 32), line=' print("impossible")\n')
TokenInfo(type=6 (DEDENT), string='', start=(5, 0), end=(5, 0), line='')
TokenInfo(type=6 (DEDENT), string='', start=(5, 0), end=(5, 0), line='')
TokenInfo(type=6 (DEDENT), string='', start=(5, 0), end=(5, 0), line='')
TokenInfo(type=0 (ENDMARKER), string='', start=(5, 0), end=(5, 0), line='')
3. Tokenizace kódu s vnořenými úplnými konstrukcemi if-else
Nyní si vyzkoušejme, jakým způsobem bude tokenizován následující programový kód, který obsahuje trojici vnořených úplných programových smyček if-else:
if True:
if False:
if False and True:
print("impossible")
else:
print("possible")
else:
pass
else:
pass
Pro tokenizaci výše uvedeného příkladu je použit tento jednoduchý skript:
import tokenize
with tokenize.open("ifs2.py") as fin:
token_generator = tokenize.generate_tokens(fin.readline)
for token in token_generator:
print(token)
Výsledná sekvence tokenů vypadá následovně. Opět jsou zvýrazněny tokeny INDENT a DEDENT:
TokenInfo(type=1 (NAME), string='if', start=(1, 0), end=(1, 2), line='if True:\n')
TokenInfo(type=1 (NAME), string='True', start=(1, 3), end=(1, 7), line='if True:\n')
TokenInfo(type=54 (OP), string=':', start=(1, 7), end=(1, 8), line='if True:\n')
TokenInfo(type=4 (NEWLINE), string='\n', start=(1, 8), end=(1, 9), line='if True:\n')
TokenInfo(type=5 (INDENT), string=' ', start=(2, 0), end=(2, 4), line=' if False:\n')
TokenInfo(type=1 (NAME), string='if', start=(2, 4), end=(2, 6), line=' if False:\n')
TokenInfo(type=1 (NAME), string='False', start=(2, 7), end=(2, 12), line=' if False:\n')
TokenInfo(type=54 (OP), string=':', start=(2, 12), end=(2, 13), line=' if False:\n')
TokenInfo(type=4 (NEWLINE), string='\n', start=(2, 13), end=(2, 14), line=' if False:\n')
TokenInfo(type=5 (INDENT), string=' ', start=(3, 0), end=(3, 8), line=' if False and True:\n')
TokenInfo(type=1 (NAME), string='if', start=(3, 8), end=(3, 10), line=' if False and True:\n')
TokenInfo(type=1 (NAME), string='False', start=(3, 11), end=(3, 16), line=' if False and True:\n')
TokenInfo(type=1 (NAME), string='and', start=(3, 17), end=(3, 20), line=' if False and True:\n')
TokenInfo(type=1 (NAME), string='True', start=(3, 21), end=(3, 25), line=' if False and True:\n')
TokenInfo(type=54 (OP), string=':', start=(3, 25), end=(3, 26), line=' if False and True:\n')
TokenInfo(type=4 (NEWLINE), string='\n', start=(3, 26), end=(3, 27), line=' if False and True:\n')
TokenInfo(type=5 (INDENT), string=' ', start=(4, 0), end=(4, 12), line=' print("impossible")\n')
TokenInfo(type=1 (NAME), string='print', start=(4, 12), end=(4, 17), line=' print("impossible")\n')
TokenInfo(type=54 (OP), string='(', start=(4, 17), end=(4, 18), line=' print("impossible")\n')
TokenInfo(type=3 (STRING), string='"impossible"', start=(4, 18), end=(4, 30), line=' print("impossible")\n')
TokenInfo(type=54 (OP), string=')', start=(4, 30), end=(4, 31), line=' print("impossible")\n')
TokenInfo(type=4 (NEWLINE), string='\n', start=(4, 31), end=(4, 32), line=' print("impossible")\n')
TokenInfo(type=6 (DEDENT), string='', start=(5, 8), end=(5, 8), line=' else:\n')
TokenInfo(type=1 (NAME), string='else', start=(5, 8), end=(5, 12), line=' else:\n')
TokenInfo(type=54 (OP), string=':', start=(5, 12), end=(5, 13), line=' else:\n')
TokenInfo(type=4 (NEWLINE), string='\n', start=(5, 13), end=(5, 14), line=' else:\n')
TokenInfo(type=5 (INDENT), string=' ', start=(6, 0), end=(6, 12), line=' print("possible")\n')
TokenInfo(type=1 (NAME), string='print', start=(6, 12), end=(6, 17), line=' print("possible")\n')
TokenInfo(type=54 (OP), string='(', start=(6, 17), end=(6, 18), line=' print("possible")\n')
TokenInfo(type=3 (STRING), string='"possible"', start=(6, 18), end=(6, 28), line=' print("possible")\n')
TokenInfo(type=54 (OP), string=')', start=(6, 28), end=(6, 29), line=' print("possible")\n')
TokenInfo(type=4 (NEWLINE), string='\n', start=(6, 29), end=(6, 30), line=' print("possible")\n')
TokenInfo(type=6 (DEDENT), string='', start=(7, 4), end=(7, 4), line=' else:\n')
TokenInfo(type=6 (DEDENT), string='', start=(7, 4), end=(7, 4), line=' else:\n')
TokenInfo(type=1 (NAME), string='else', start=(7, 4), end=(7, 8), line=' else:\n')
TokenInfo(type=54 (OP), string=':', start=(7, 8), end=(7, 9), line=' else:\n')
TokenInfo(type=4 (NEWLINE), string='\n', start=(7, 9), end=(7, 10), line=' else:\n')
TokenInfo(type=5 (INDENT), string=' ', start=(8, 0), end=(8, 8), line=' pass\n')
TokenInfo(type=1 (NAME), string='pass', start=(8, 8), end=(8, 12), line=' pass\n')
TokenInfo(type=4 (NEWLINE), string='\n', start=(8, 12), end=(8, 13), line=' pass\n')
TokenInfo(type=6 (DEDENT), string='', start=(9, 0), end=(9, 0), line='else:\n')
TokenInfo(type=6 (DEDENT), string='', start=(9, 0), end=(9, 0), line='else:\n')
TokenInfo(type=1 (NAME), string='else', start=(9, 0), end=(9, 4), line='else:\n')
TokenInfo(type=54 (OP), string=':', start=(9, 4), end=(9, 5), line='else:\n')
TokenInfo(type=4 (NEWLINE), string='\n', start=(9, 5), end=(9, 6), line='else:\n')
TokenInfo(type=5 (INDENT), string=' ', start=(10, 0), end=(10, 4), line=' pass\n')
TokenInfo(type=1 (NAME), string='pass', start=(10, 4), end=(10, 8), line=' pass\n')
TokenInfo(type=4 (NEWLINE), string='\n', start=(10, 8), end=(10, 9), line=' pass\n')
TokenInfo(type=6 (DEDENT), string='', start=(11, 0), end=(11, 0), line='')
TokenInfo(type=0 (ENDMARKER), string='', start=(11, 0), end=(11, 0), line='')
4. Realizace průchodu AST
Podívejme se nyní na způsob realizace průchodu abstraktním datovým stromem. Zcela nejjednodušší způsob spočívá v parsingu zdrojového kódu do AST (pochopitelně přes lexer), čímž získáme objekt obsahující všechny uzly AST. S využitím funkce walk lze projít všemi uzly tohoto stromu, což lze v Pythonu realizovat jednoduše:
import ast
tree = ast.parse("1+2*3")
for node in ast.walk(tree):
print(node)
Výsledkem bude výpis devíti uzlů AST, ovšem bez podrobnějších informací:
$ python3 traverse_expression_1.py <_ast.Module object at 0x7fbbc9c230d0> <_ast.Expr object at 0x7fbbc9c234f0> <_ast.BinOp object at 0x7fbbc9c23250> <_ast.Constant object at 0x7fbbc9b5f550> <_ast.Add object at 0x7fbbc9b80dc0> <_ast.BinOp object at 0x7fbbc9b5f6a0> <_ast.Constant object at 0x7fbbc9b5f730> <_ast.Mult object at 0x7fbbc9b80e80> <_ast.Constant object at 0x7fbbc9b5f7f0>
5. Rekurzivní průchod AST s pevně daným pořadím procházení uzly
Průchod uzly AST ukázaný v předchozí kapitole není příliš vhodný ve chvíli, kdy potřebujeme stromem procházet v určitém pořadí uzlů – inorder, preorder či postorder, filtrovat nezajímavé uzly, nebo dokonce když potřebujeme AST nějakým způsobem modifikovat. V takových případech je vhodnější využít návrhového vzoru Visitor, který je založen na volání callback metody visit pro každý navštívený uzel. V případě, že tento uzel obsahuje poduzly, lze je navštívit zavoláním metody generic_visit (tedy rekurzivně):
Realizace algoritmu pro průchod AST je díky podpoře návrhového vzoru Visitor triviální. Povšimněte si, jak rekurzivně voláme metodu generic_visit při návštěvě uzlu:
import ast
class Visitor(ast.NodeVisitor):
def visit(self, node):
print(node)
self.generic_visit(node)
tree = ast.parse("1+2*3")
visitor = Visitor()
visitor.visit(tree)
Výsledkem bude opět devět uzlů:
$ python3 traverse_expression_2.py <_ast.Module object at 0x7f59ac3320d0> <_ast.Expr object at 0x7f59ac3324f0> <_ast.BinOp object at 0x7f59ac26d610> <_ast.Constant object at 0x7f59ac26d640> <_ast.Add object at 0x7f59ac28fe50> <_ast.BinOp object at 0x7f59ac26d820> <_ast.Constant object at 0x7f59ac26d880> <_ast.Mult object at 0x7f59ac28ff10> <_ast.Constant object at 0x7f59ac26d8e0>
6. Rekurzivní průchod AST se zvýrazněním úrovně
Vzhledem k tomu, že i pro jednoduchý výraz obsahuje AST uzly v několika úrovních, bude vhodné si tyto úrovně nějakým způsobem zvýraznit. Pomoci si můžeme malým trikem – zapamatováním úrovně, ve které se při zpracování uzlů právě nacházíme. To je z implementačního pohledu snadné; postačuje pouze do naší třídy Visitor přidat (nestatický) atribut, do něhož bude uložena úroveň právě zpracovávaného uzlu. Při průchodu podstromem se tato úroveň o jedničku zvýší, po dokončení průchodu opět sníží. A číselnou hodnotu úrovně lze následně použít například pro odsazení uzlů v podstromech. Upravený kód může vypadat následovně:
import ast
class Visitor(ast.NodeVisitor):
def __init__(self):
self.nest_level = 1
def visit(self, node):
indent = " " * self.nest_level * 2
print(indent, node)
self.nest_level += 1
self.generic_visit(node)
self.nest_level -= 1
tree = ast.parse("1+2*3+1")
visitor = Visitor()
visitor.visit(tree)
Nyní bude již výsledek čitelnější (i když ne příliš):
$ python3 traverse_expression_3.py
<_ast.Module object at 0x7f21f20fc0d0>
<_ast.Expr object at 0x7f21f20fc4f0>
<_ast.BinOp object at 0x7f21f20376d0>
<_ast.BinOp object at 0x7f21f2037700>
<_ast.Constant object at 0x7f21f20377f0>
<_ast.Add object at 0x7f21f2059ee0>
<_ast.BinOp object at 0x7f21f2037910>
<_ast.Constant object at 0x7f21f2037940>
<_ast.Mult object at 0x7f21f2059fa0>
<_ast.Constant object at 0x7f21f2037a00>
<_ast.Add object at 0x7f21f2059ee0>
<_ast.Constant object at 0x7f21f2037880>
7. Grafická vizualizace AST
AST je formou stromové datové struktury, která se na klasickém terminálu zobrazuje poměrně špatně – informace totiž na ploše terminálu obsazují hodně místa a přesto nejsou patrné vazby mezi jednotlivými uzly stromu. Z tohoto důvodu je vhodnější si AST zobrazit graficky. V konkrétním případě programovacího jazyka Python a jeho standardního balíčku ast slouží pro vizualizaci AST nástroj nazvaný přímočaře python-ast-visualizer. Ten transformuje AST do podoby kompatibilní s nástrojem Graphviz (viz též tento článek). Následně je zavolán Graphviz, který AST vykreslí do vektorového obrázku uloženého do formátu PDF.
Nástroj python-ast-visualizer lze nainstalovat přes PyPi nebo přímo naklonováním repositáře s jeho zdrojovými kódy:
$ git clone git@github.com:pombredanne/python-ast-visualizer.git Cloning into 'python-ast-visualizer'... remote: Enumerating objects: 14, done. remote: Counting objects: 100% (6/6), done. remote: Compressing objects: 100% (2/2), done. Receiving objects: 100% (14/14), done. Resolving deltas: 100% (5/5), done. remote: Total 14 (delta 4), reused 4 (delta 4), pack-reused 8
Tento nástroj je realizován skriptem a lze ho spustit následovně:
$ python3 astvisualizer.py --help
Usage: astvisualizer.py [options] [string]
Options:
-h, --help show this help message and exit
-f FILE, --file=FILE Read a code snippet from the specified file
-l LABEL, --label=LABEL
The label for the visualization
8. Vizualizace AST jednoduchého výrazu
Vyzkoušejme si nyní, jak vlastně bude vypadat vizualizace AST pro velmi jednoduchý výraz, konkrétně pro tento výraz:
1+2*3
Vizualizace se provede příkazem:
$ python3 astvisualizer.py -f expression2.py
S výsledkem:
Obrázek 1: AST s vizualizací výrazu 1+2*3.
Nyní výraz pozměníme přidáním závorek, které změní prioritu operací:
(1+2)*3
Výsledek bude v tomto případě vypadat následovně:
Obrázek 2: AST s vizualizací výrazu (1+2)*3.
9. Vizualizace AST programu pro výpočet prvočísel
AST jednoduchého výrazu obsahuje malé množství uzlů, takže je možné obraz celého AST jednoduše vložit i do dnešního článku, což jsme ostatně mohli vidět i v předchozí kapitole. Jak však bude vypadat AST složitějšího kódu, například funkce pro výpočet prvočísel, s níž jsme se již seznámili minule?
# originální kód lze nalézt na adrese:
# http://www.rosettacode.org/wiki/Sieve_of_Eratosthenes#Using_array_lookup
def primes2(limit):
"""Výpočet seznamu prvočísel až do zadaného limitu."""
is_prime = [False] * 2 + [True] * (limit - 1)
for n in range(int(limit**0.5 + 1.5)): # stop at ``sqrt(limit)``
if is_prime[n]:
for i in range(n*n, limit+1, n):
is_prime[i] = False
return [i for i, prime in enumerate(is_prime) if prime]
print(primes2(100))
Celý AST již v takovém případě obsahuje desítky až nižší stovky uzlů:
Obrázek 3: AST popisující algoritmus pro výpočet prvočísel.
Bližší pohled na AST odhaluje, s jakými typy uzlů se zde můžeme setkat:
Obrázek 4: Podrobnější pohled na AST popisující algoritmus pro výpočet prvočísel.
10. Vizualizace AST programu pro provádění asynchronních operací
Do Pythonu 3.5 byla přidána nová klíčová slova async a await určená pro tvorbu a koordinaci souběžně běžících úloh, což je téma, s nímž jsme se na Rootu seznámili v následujících článcích:
- Souběžné a paralelně běžící úlohy naprogramované v Pythonu
https://www.root.cz/clanky/soubezne-a-paralelne-bezici-ulohy-naprogramovane-v-pythonu/ - Souběžné a paralelně běžící úlohy naprogramované v Pythonu (2)
https://www.root.cz/clanky/soubezne-a-paralelne-bezici-ulohy-naprogramovane-v-pythonu-2/ - Souběžné a paralelně běžící úlohy naprogramované v Pythonu – Curio a Trio
https://www.root.cz/clanky/soubezne-a-paralelne-bezici-ulohy-naprogramovane-v-pythonu-curio-a-trio/ - Souběžné a paralelně běžící úlohy naprogramované v Pythonu – knihovna Trio
https://www.root.cz/clanky/soubezne-a-paralelne-bezici-ulohy-naprogramovane-v-pythonu-knihovna-trio/ - Souběžné a paralelně běžící úlohy naprogramované v Pythonu – knihovna Trio (2)
https://www.root.cz/clanky/soubezne-a-paralelne-bezici-ulohy-naprogramovane-v-pythonu-knihovna-trio-2/ - Souběžné a paralelně běžící úlohy naprogramované v Pythonu – závěrečné zhodnocení
https://www.root.cz/clanky/soubezne-a-paralelne-bezici-ulohy-naprogramovane-v-pythonu-zaverecne-zhodnoceni/
Víme již, že při tokenizaci se tato klíčová slova nerozeznávají, ovšem ve výsledném AST již budou mít speciální uzly. Ostatně můžeme se o tom přesvědčit velmi snadno, a to převodem následujícího kódu do AST:
import trio
async def producer(send_channel):
for i in range(1, 10):
message = f"message {i}"
print(f"Producer: {message}")
await send_channel.send(message)
async def consumer(receive_channel):
async for value in receive_channel:
print(f"Consumer: received{value!r}")
await trio.sleep(1)
async def main():
async with trio.open_nursery() as nursery:
send_channel, receive_channel = trio.open_memory_channel(0)
nursery.start_soon(producer, send_channel)
nursery.start_soon(consumer, receive_channel)
trio.run(main)
AST zkonstruovaný z tohoto zdrojového kódu vypadá následovně (opět se jedná o desítky až menší stovky uzlů):
Obrázek 5: Celý AST s funkcemi používajícími klíčová slova async a await.
Zajímavější bude se podívat na konkrétní uzly, které souvisí s klíčovým slovem async. Konkrétně se jedná o uzly s definicí asynchronní funkce, asynchronní smyčky for a asynchronní smyčky with (tedy se třemi uzly různého typu):
Obrázek 6: Podrobnější pohled na AST s funkcemi používajícími klíčová slova async a await se zvýrazněním příslušných uzlů.
11. Rozpoznání uzlů tvořících algebraický výraz
Jednotlivé uzly AST jsou tvořeny instancemi tříd z balíčku AST. Tyto instance lze rozlišit podle jejich typu a tím pádem můžeme v AST nalézt a vlastně i zpětně zrekonstruovat algebraické výrazy. Tento postup je naznačen v dalším demonstračním příkladu, který z důvodu větší čitelnosti rozpoznává jen základní typy uzlů – binární operátory a číselné konstanty (pouze u typu uzlu „konstanta“ vypisujeme i hodnotu této konstanty):
import ast
class Visitor(ast.NodeVisitor):
def __init__(self):
self.nest_level = 1
def visit(self, node):
indent = " " * self.nest_level * 2
print(indent, node2string(node))
self.nest_level += 1
self.generic_visit(node)
self.nest_level -= 1
def node2string(node):
t = type(node)
if t == ast.Constant:
return "Constant: {}".format(node.value)
elif t == ast.Expr:
return "Expression:"
elif t == ast.BinOp:
return "Binary operation"
elif t == ast.Add:
return "Operator: +"
elif t == ast.Sub:
return "Operator: -"
elif t == ast.Mult:
return "Operator: *"
elif t == ast.Div:
return "Operator: /"
return ""
tree = ast.parse("1+2*(1-3/4)+5")
visitor = Visitor()
visitor.visit(tree)
Zrekonstruovaný výraz se zobrazí tímto způsobem:
Expression:
Binary operation
Binary operation
Constant: 1
Operator: +
Binary operation
Constant: 2
Operator: *
Binary operation
Constant: 1
Operator: -
Binary operation
Constant: 3
Operator: /
Constant: 4
Operator: +
Constant: 5
12. Algebraický výraz s proměnnými
Algebraické výrazy mohou pochopitelně obsahovat i proměnné (nebo symbolické konstanty). Proměnnou v AST poznáme tak, že se jedná o uzel ast.Name následovaný poduzly ast.Id a ast.Load, což znamená načtení hodnoty proměnné:
Obrázek 7: Výraz s proměnnou: 1+2*3+x.
Při analýze AST a pro zobrazení výrazu na terminálu nám postačuje zpracovat pouze uzel ast.Name a jeho poduzel ast.Id, takže skript z předchozí kapitoly je možné nepatrně rozšířit takto:
Opět se podívejme na upravený kód skriptu:
import ast
class Visitor(ast.NodeVisitor):
def __init__(self):
self.nest_level = 1
def visit(self, node):
indent = " " * self.nest_level * 2
print(indent, node2string(node))
self.nest_level += 1
self.generic_visit(node)
self.nest_level -= 1
def node2string(node):
t = type(node)
if t == ast.Constant:
return "Constant: {}".format(node.value)
elif t == ast.Name:
return "Variable: {}".format(node.id)
elif t == ast.Expr:
return "Expression:"
elif t == ast.BinOp:
return "Binary operation"
elif t == ast.Add:
return "Operator: +"
elif t == ast.Sub:
return "Operator: -"
elif t == ast.Mult:
return "Operator: *"
elif t == ast.Div:
return "Operator: /"
return ""
tree = ast.parse("a+2*(1-b/4)+c")
visitor = Visitor()
visitor.visit(tree)
Nyní skript dokáže zobrazit i názvy proměnných použitých ve výrazu:
Expression:
Binary operation
Binary operation
Variable: a
Operator: +
Binary operation
Constant: 2
Operator: *
Binary operation
Constant: 1
Operator: -
Binary operation
Variable: b
Operator: /
Constant: 4
Operator: +
Variable: c
13. Překlad AST s jeho spuštěním
S AST je pochopitelně možné manipulovat a tím například provádět různé optimalizace. Ovšem současně je AST ústředním prvkem pythonovského překladače:
zdrojový kód → parse tree → AST → CFG → bajtkód
Co to v praxi znamená? Pokud již máme vytvořený AST (ať již vznikl jakýmkoli způsobem), můžeme ho přeložit do bajtkódu a následně tento bajtkód spustit. K tomu slouží základní (built-in) funkce nazvané compile a exec. Tyto funkce pochopitelně není nutné importovat, takže pro překlad a spuštění AST můžeme psát:
import ast
class Visitor(ast.NodeVisitor):
def __init__(self):
self.nest_level = 1
def visit(self, node):
indent = " " * self.nest_level * 2
print(indent, node)
self.nest_level += 1
self.generic_visit(node)
self.nest_level -= 1
tree = ast.parse("print(1+2*(1-3/4)+5)", mode="exec")
visitor = Visitor()
visitor.visit(tree)
print("Executing")
exec(compile(tree, filename="<ast>", mode="exec"))
print("Done")
Po spuštění tohoto skriptu se nejdříve zobrazí všechny uzly AST:
<_ast.Module object at 0x7f4db2abf430>
<_ast.Expr object at 0x7f4db2a02670>
<_ast.Call object at 0x7f4db2a026a0>
<_ast.Name object at 0x7f4db2a027c0>
<_ast.Load object at 0x7f4db2a1ca00>
<_ast.BinOp object at 0x7f4db2a028b0>
<_ast.BinOp object at 0x7f4db2a028e0>
<_ast.Constant object at 0x7f4db2a02910>
<_ast.Add object at 0x7f4db2a1ce80>
<_ast.BinOp object at 0x7f4db2a2ad00>
<_ast.Constant object at 0x7f4db2a2ad30>
<_ast.Mult object at 0x7f4db2a1cf40>
<_ast.BinOp object at 0x7f4db2a2ad90>
<_ast.Constant object at 0x7f4db2a2adc0>
<_ast.Sub object at 0x7f4db2a1cee0>
<_ast.BinOp object at 0x7f4db2a2ae20>
<_ast.Constant object at 0x7f4db2a2ae80>
<_ast.Div object at 0x7f4db2a2a040>
<_ast.Constant object at 0x7f4db2a2aeb0>
<_ast.Add object at 0x7f4db2a1ce80>
<_ast.Constant object at 0x7f4db2a029a0>
Následně je AST přeložen do bajtkódu a tento bajtkód je spuštěn. Výsledkem je řetězec 6.5:
Executing 6.5 Done
14. Repositář s demonstračními příklady
Zdrojové kódy všech prozatím popsaných demonstračních příkladů určených pro programovací jazyk Python 3 (některé přímo pro Python 3.10) byly uloženy do Git repositáře dostupného na adrese https://github.com/tisnik/most-popular-python-libs. V případě, že nebudete chtít klonovat celý repositář (ten je ovšem stále velmi malý, dnes má velikost zhruba několik desítek kilobajtů), můžete namísto toho použít odkazy na jednotlivé příklady, které naleznete v následující tabulce:
15. Odkazy na Internetu
- Abstract syntax tree
https://en.wikipedia.org/wiki/Abstract_syntax_tree - Lexical analysis
https://en.wikipedia.org/wiki/Lexical_analysis - Parser
https://en.wikipedia.org/wiki/Parsing#Parser - Parse tree
https://en.wikipedia.org/wiki/Parse_tree - Derivační strom
https://cs.wikipedia.org/wiki/Deriva%C4%8Dn%C3%AD_strom - Python doc: ast — Abstract Syntax Trees
https://docs.python.org/3/library/ast.html - Python doc: tokenize — Tokenizer for Python source
https://docs.python.org/3/library/tokenize.html - 5 Amazing Python AST Module Examples
https://www.pythonpool.com/python-ast/ - Intro to Python ast Module
https://medium.com/@wshanshan/intro-to-python-ast-module-bbd22cd505f7 - Golang AST Package
https://golangdocs.com/golang-ast-package - AP8, IN8 Regulární jazyky
http://statnice.dqd.cz/home:inf:ap8 - AP9, IN9 Konečné automaty
http://statnice.dqd.cz/home:inf:ap9 - AP10, IN10 Bezkontextové jazyky
http://statnice.dqd.cz/home:inf:ap10 - AP11, IN11 Zásobníkové automaty, Syntaktická analýza
http://statnice.dqd.cz/home:inf:ap11 - Introduction to YACC
https://www.geeksforgeeks.org/introduction-to-yacc/ - Introduction of Lexical Analysis
https://www.geeksforgeeks.org/introduction-of-lexical-analysis/?ref=lbp - Využití knihovny Pygments (nejenom) pro obarvení zdrojových kódů
https://www.root.cz/clanky/vyuziti-knihovny-pygments-nejenom-pro-obarveni-zdrojovych-kodu/ - Pygments – Python syntax highlighter
http://pygments.org/ - Pygments (dokumentace)
http://pygments.org/docs/ - Write your own filter
http://pygments.org/docs/filterdevelopment/ - Write your own lexer
http://pygments.org/docs/lexerdevelopment/ - Write your own formatter
http://pygments.org/docs/formatterdevelopment/ - Jazyky podporované knihovnou Pygments
http://pygments.org/languages/ - Pygments FAQ
http://pygments.org/faq/ - Compiler Construction/Lexical analysis
https://en.wikibooks.org/wiki/Compiler_Construction/Lexical_analysis - Compiler Design – Lexical Analysis
https://www.tutorialspoint.com/compiler_design/compiler_design_lexical_analysis.htm - Lexical Analysis – An Intro
https://www.scribd.com/document/383765692/Lexical-Analysis - Python AST Visualizer
https://github.com/pombredanne/python-ast-visualizer - What is an Abstract Syntax Tree
https://blog.bitsrc.io/what-is-an-abstract-syntax-tree-7502b71bde27 - Why is AST so important
https://medium.com/@obernardovieira/why-is-ast-so-important-b1e7d6c29260 - Emily Morehouse-Valcarcel – The AST and Me – PyCon 2018
https://www.youtube.com/watch?v=XhWvz4dK4ng - Python AST Parsing and Custom Linting
https://www.youtube.com/watch?v=OjPT15y2EpE - Chase Stevens – Exploring the Python AST Ecosystem
https://www.youtube.com/watch?v=Yq3wTWkoaYY - Full Grammar specification
https://docs.python.org/3/reference/grammar.html
