Hlavní navigace

Lexikální a syntaktická analýza zdrojových kódů programovacího jazyka Python (2.část)

4. 8. 2022
Doba čtení: 24 minut

Sdílet

 Autor: Depositphotos
Dnes si nejdříve řekneme, jak jsou tokenizovány pythonovské bloky. Následně se budeme zabývat konstrukcí a zobrazením abstraktního syntaktického stromu (AST). Nakonec si ukážeme, jak lze AST přeložit a spustit.

Obsah

1. Tokenizace bloků v Pythonu

2. Ukázka použití tokenů INDENT a DEDENT

3. Tokenizace kódu s vnořenými úplnými konstrukcemi if-else

4. Realizace průchodu AST

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ě

7. Grafická vizualizace AST

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

15. Odkazy na Internetu

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>
Poznámka: ze zobrazeného výsledku je patrné, že jednotlivé typy uzlů jsou reprezentovány speciálními objekty. K jejich významu se ještě vrátíme.

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>
Poznámka: sami si vyzkoušejte, co se stane ve chvíli, kdy se prohodí volání funkce print a metody generic_visit.

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.

Poznámka: z AST je patrné, že podvýraz 2*3 bude vyhodnocen dříve, protože se jedná o binární operaci s vyšší prioritou. Tudíž je celý tento podvýraz reprezentován podstromem (zvýrazněno po konstrukci AST v grafickém editoru).

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.

Poznámka: nyní bude naopak nejdříve vyhodnocen podvýraz 1+2 (zvýrazněno). Povšimněte si, že v AST již není informace o závorkách.

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:

  1. Souběžné a paralelně běžící úlohy naprogramované v Pythonu
    https://www.root.cz/clanky/soubezne-a-paralelne-bezici-ulohy-naprogramovane-v-pythonu/
  2. 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/
  3. 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/
  4. 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/
  5. 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/
  6. 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)
Poznámka: v novějším Pythonu bude lepší použít pattern matching, což je ovšem téma na samostatný článek.

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:

skolení ELK

   <_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:

# Demonstrační příklad Stručný popis příkladu Cesta
1 expression.py zdrojový kód, který se bude tokenizovat a parsovat, obsahující jednoduchý výraz https://github.com/tisnik/most-popular-python-libs/blob/master/ast/expression.py
2 err_expression.py zdrojový kód, který se bude tokenizovat a parsovat, obsahující chybný výraz https://github.com/tisnik/most-popular-python-libs/blob/master/ast/err_expression.py
3 async.py zdrojový kód, který se bude tokenizovat a parsovat, obsahující async a await https://github.com/tisnik/most-popular-python-libs/blob/master/ast/async.py
4 primes.py zdrojový kód, který se bude tokenizovat a parsovat, obsahující výpočet celočísel https://github.com/tisnik/most-popular-python-libs/blob/master/ast/primes.py
       
5 print_tokens.py výpis všech typů a hodnot tokenů pro aktuální verzi Pythonu https://github.com/tisnik/most-popular-python-libs/blob/master/ast/print_tokens.py
6 tokenize_expression1.py tokenizace výrazu https://github.com/tisnik/most-popular-python-libs/blob/master/ast/toke­nize_expression1.py
7 tokenize_expression2.py tokenizace výrazu, alternativní způsob otevření zdrojového souboru https://github.com/tisnik/most-popular-python-libs/blob/master/ast/toke­nize_expression2.py
8 tokenize_expression3.py tokenizace výrazu s více operátory https://github.com/tisnik/most-popular-python-libs/blob/master/ast/toke­nize_expression3.py
9 tokenize_expression4.py tokenizace výrazu s více operátory, výpis přesného typu tokenu https://github.com/tisnik/most-popular-python-libs/blob/master/ast/toke­nize_expression4.py
10 tokenize_async.py tokenizace zdrojového kódu async.py https://github.com/tisnik/most-popular-python-libs/blob/master/ast/tokenize_async.py
11 tokenize_primes.py tokenizace zdrojového kódu primes.py https://github.com/tisnik/most-popular-python-libs/blob/master/ast/toke­nize_primes.py
12 tokenize_primes2.py tokenizace zdrojového kódu primes.py, výpis přesného typu tokenu https://github.com/tisnik/most-popular-python-libs/blob/master/ast/toke­nize_primes2.py
       
13 parse_expression.py parsing zdrojového kódu s výrazem https://github.com/tisnik/most-popular-python-libs/blob/master/ast/parse_ex­pression.py
14 parse_expression3_10.py parsing zdrojového kódu s výrazem, vylepšený výpis v Pythonu 3.10 https://github.com/tisnik/most-popular-python-libs/blob/master/ast/parse_ex­pression3_10.py
15 parse_async.py parsing zdrojového kodu async.py https://github.com/tisnik/most-popular-python-libs/blob/master/ast/parse_async.py
16 parse_async3_10.py parsing zdrojového kodu async.py, vylepšený výpis v Pythonu 3.10 https://github.com/tisnik/most-popular-python-libs/blob/master/ast/parse_a­sync3_10.py
17 parse_primes.py parsing zdrojového kodu primes.py https://github.com/tisnik/most-popular-python-libs/blob/master/ast/parse_primes.py
18 parse_primes3_10.py parsing zdrojového kodu primes.py, vylepšený výpis v Pythonu 3.10 https://github.com/tisnik/most-popular-python-libs/blob/master/ast/parse_pri­mes3_10.py
       
19 traverse_expression1.py průchod AST, nejjednodušší varianta https://github.com/tisnik/most-popular-python-libs/blob/master/ast/traver­se_expression1.py
20 traverse_expression2.py průchod AST, vzor Visitor https://github.com/tisnik/most-popular-python-libs/blob/master/ast/traver­se_expression2.py
21 traverse_expression3.py průchod AST, vzor Visitor, odsazení kódu https://github.com/tisnik/most-popular-python-libs/blob/master/ast/traver­se_expression3.py
22 traverse_expression4.py průchod AST, vzor Visitor, odsazení kódu, rozpoznání uzlů https://github.com/tisnik/most-popular-python-libs/blob/master/ast/traver­se_expression4.py
23 traverse_expression5.py průchod AST, vzor Visitor, odsazení kódu, rozpoznání uzlů https://github.com/tisnik/most-popular-python-libs/blob/master/ast/traver­se_expression5.py
       
24 ifs1.py zdrojový kód s několika zanořenými podmínkami https://github.com/tisnik/most-popular-python-libs/blob/master/ast/ifs1.py
25 ifs2.py zdrojový kód s několika zanořenými úplnými podmínkami https://github.com/tisnik/most-popular-python-libs/blob/master/ast/ifs2.py
26 tokenize_ifs1.py tokenizace zdrojového kódu „ifs1.py“ https://github.com/tisnik/most-popular-python-libs/blob/master/ast/tokenize_ifs1.py
27 tokenize_ifs2.py tokenizace zdrojového kódu „ifs2.py“ https://github.com/tisnik/most-popular-python-libs/blob/master/ast/tokenize_ifs2.py
       
28 compile_tree.py překlad a spuštění AST https://github.com/tisnik/most-popular-python-libs/blob/master/ast/compile_tree.py

15. Odkazy na Internetu

  1. Abstract syntax tree
    https://en.wikipedia.org/wi­ki/Abstract_syntax_tree
  2. Lexical analysis
    https://en.wikipedia.org/wi­ki/Lexical_analysis
  3. Parser
    https://en.wikipedia.org/wi­ki/Parsing#Parser
  4. Parse tree
    https://en.wikipedia.org/wi­ki/Parse_tree
  5. Derivační strom
    https://cs.wikipedia.org/wi­ki/Deriva%C4%8Dn%C3%AD_strom
  6. Python doc: ast — Abstract Syntax Trees
    https://docs.python.org/3/li­brary/ast.html
  7. Python doc: tokenize — Tokenizer for Python source
    https://docs.python.org/3/li­brary/tokenize.html
  8. 5 Amazing Python AST Module Examples
    https://www.pythonpool.com/python-ast/
  9. Intro to Python ast Module
    https://medium.com/@wshanshan/intro-to-python-ast-module-bbd22cd505f7
  10. Golang AST Package
    https://golangdocs.com/golang-ast-package
  11. AP8, IN8 Regulární jazyky
    http://statnice.dqd.cz/home:inf:ap8
  12. AP9, IN9 Konečné automaty
    http://statnice.dqd.cz/home:inf:ap9
  13. AP10, IN10 Bezkontextové jazyky
    http://statnice.dqd.cz/home:inf:ap10
  14. AP11, IN11 Zásobníkové automaty, Syntaktická analýza
    http://statnice.dqd.cz/home:inf:ap11
  15. Introduction to YACC
    https://www.geeksforgeeks­.org/introduction-to-yacc/
  16. Introduction of Lexical Analysis
    https://www.geeksforgeeks­.org/introduction-of-lexical-analysis/?ref=lbp
  17. Využití knihovny Pygments (nejenom) pro obarvení zdrojových kódů
    https://www.root.cz/clanky/vyuziti-knihovny-pygments-nejenom-pro-obarveni-zdrojovych-kodu/
  18. Pygments – Python syntax highlighter
    http://pygments.org/
  19. Pygments (dokumentace)
    http://pygments.org/docs/
  20. Write your own filter
    http://pygments.org/docs/fil­terdevelopment/
  21. Write your own lexer
    http://pygments.org/docs/le­xerdevelopment/
  22. Write your own formatter
    http://pygments.org/docs/for­matterdevelopment/
  23. Jazyky podporované knihovnou Pygments
    http://pygments.org/languages/
  24. Pygments FAQ
    http://pygments.org/faq/
  25. Compiler Construction/Lexical analysis
    https://en.wikibooks.org/wi­ki/Compiler_Construction/Le­xical_analysis
  26. Compiler Design – Lexical Analysis
    https://www.tutorialspoin­t.com/compiler_design/com­piler_design_lexical_analy­sis.htm
  27. Lexical Analysis – An Intro
    https://www.scribd.com/do­cument/383765692/Lexical-Analysis
  28. Python AST Visualizer
    https://github.com/pombredanne/python-ast-visualizer
  29. What is an Abstract Syntax Tree
    https://blog.bitsrc.io/what-is-an-abstract-syntax-tree-7502b71bde27
  30. Why is AST so important
    https://medium.com/@obernar­dovieira/why-is-ast-so-important-b1e7d6c29260
  31. Emily Morehouse-Valcarcel – The AST and Me – PyCon 2018
    https://www.youtube.com/wat­ch?v=XhWvz4dK4ng
  32. Python AST Parsing and Custom Linting
    https://www.youtube.com/wat­ch?v=OjPT15y2EpE
  33. Chase Stevens – Exploring the Python AST Ecosystem
    https://www.youtube.com/wat­ch?v=Yq3wTWkoaYY
  34. Full Grammar specification
    https://docs.python.org/3/re­ference/grammar.html

Autor článku

Pavel Tišnovský vystudoval VUT FIT a v současné době pracuje ve společnosti Red Hat, kde vyvíjí nástroje pro OpenShift.io.