Obsah
1. Lexikální a syntaktická analýza zdrojových kódů programovacího jazyka Python
2. Od volně zapsaného zdrojového kódu k AST
3. Lexémy a tokeny (tokenizace)
4. Malá odbočka: tokenizace a programovací jazyk BASIC
5. Příklad tokenizace jednoduchého kódu napsaného v Pythonu
6. Tokenizace standardním modulem tokenize
7. Tokenizace jednoduchého výrazu
8. Tokenizace kódu s funkcí, vnořenými smyčkami a podmínkou
9. Tokenizace kódu s klíčovými slovy async a await
10. Rozlišení operátorů v sekvenci tokenů
11. Zobrazení AST pro část zdrojového kódu Pythonu
12. Zobrazení AST pro soubor se zdrojovým kódem
14. Repositář s demonstračními příklady
1. Lexikální a syntaktická analýza zdrojových kódů programovacího jazyka Python
Na trojici článků, v nichž jsme se zabývali problematikou lexikální a syntaktické analýzy zdrojových kódů jazyka Go [1] [2] [3] dnes do jisté míry navážeme, ovšem přesuneme se z jazyka Go k pravděpodobně nejpopulárnějšímu jazyku současnosti – k Pythonu. Ukážeme si, jak lze provést takzvanou tokenizaci a následně parsing zdrojových kódů, jehož výsledkem je AST neboli abstraktní syntaktický strom (Abstract Syntax Tree). A samozřejmě se zmíníme i o tom, jakým způsobem lze abstraktním syntaktickým stromem procházet či jinak manipulovat.
K čemu je však získání AST pro zadaný zdrojový kód vhodné? Uveďme si několik příkladů:
- Statická analýza kódu s vyhledáváním potenciálně problematických částí
- Formátování zdrojového kódu
- Vyhledávání strukturálních změn ve dvou verzích kódu
- AST používají i mnohé generátor kódu (code generators)
- Nástroje typu Hypothesis taktéž pracují s AST
- Většina transpilerů manipuluje právě s AST (Transcrypt)
- Optimalizace typu constant folding
- Některé šablonovací nástroje taktéž pracují s AST
- A samozřejmě AST slouží v samotném Pythonu pro konstrukci CFG (Control Flow Graph) a následně k produkci bajtkódu
V případě samotného Pythonu je cesta od zdrojového kódu k bajtkódu (dosti zjednodušeně řečeno) následující:
zdrojový kód → parse tree → AST → CFG → bajtkód
2. Od volně zapsaného zdrojového kódu k AST
Při zpracování zdrojových kódů se postupně provádí jednotlivé dílčí kroky, a to jak v klasických překladačích (Go), tak i v jazycích, které provádí překlad „jen“ do bajtkódu s jeho pozdější interpretací (Python). Díky rozdělení celého zpracování do několika konfigurovatelných kroků je zajištěna velká flexibilita a možnost případného relativně snadného rozšiřování o další syntaktické prvky, existuje možnost použití jediné sady nástrojů více jazyky, lze přidat podporu pro různé výstupní formáty (překlad do nativního kódu nebo do WebAssembly atd.), podporu pro speciální filtry apod. (nehledě na to, že každá činnost je založena na odlišné teorii). Celý průběh zpracování vypadá při určitém zjednodušení následovně:
- Na začátku zpracování se nachází takzvaný lexer, který postupně načítá jednotlivé znaky ze vstupního řetězce (resp. ze vstupního souboru) a vytváří z nich lexikální tokeny. Teoreticky se pro každý programovací jazyk používá odlišný lexer a samozřejmě je možné v případě potřeby si napsat lexer vlastní. V případě Pythonu můžeme použít standardní modul tokenizer, nebo lze alternativně použít například projekt Pygments, jenž obsahuje lexery pro mnoho dalších programovacích jazyků.
- Výstup z lexeru může procházet libovolným počtem filtrů sloužících pro odstranění nebo (častěji) modifikaci jednotlivých tokenů; ať již jejich typů či přímo textu, který tvoří hodnotu tokenu. Díky existenci filtrů je například možné nechat si zvýraznit vybrané bílé znaky, slova se speciálním významem v komentářích (TODO:, FIX:) apod. Některé lexery obsahují filtr přímo ve svém modulu.
- Sekvence tokenů tvoří základ pro syntaktickou analýzu. Nástroj, který syntaktickou analýzu provádí, se většinou nazývá parser a proto se taktéž někdy setkáme s pojmem parsing (tento termín je ovšem chybně používán i v těch případech, kdy se provádí „pouze“ lexikální analýza). Výsledkem činnosti parseru je vhodně zvolená datová struktura, typicky abstraktní syntaktický strom (AST); někdy též strom derivační. V případě Pythonu vypadá postupné zpracování vstupního zdrojového textu takto: lexer → derivační strom (parse tree) → AST.
3. Lexémy a tokeny (tokenizace)
První část zpracování zdrojových textů je nejzajímavější, a to jak z hlediska použití, tak i z hlediska implementace (zde ovšem záleží na tom, jaké techniky jsou použity pro implementaci lexeru). Lexer totiž musí v sekvenci znaků tvořících zdrojový text najít takzvané lexémy, tj. skupiny (sousedních) znaků odpovídajících nějakému vzorku (použít lze gramatiku, regulární výraz či ad-hoc testy). Z lexémů se posléze tvoří již zmíněné lexikální tokeny, což je – poněkud zjednodušeně řečeno – typicky dvojice obsahující typ tokenu (někdy se namísto „typ“ používá označení „jméno“) a řetězec ze vstupního zdrojového souboru (jak uvidíme dále, obsahují tokeny generované standardním Pythonovským lexerem mnohem více informací, například i celý řádek zdrojového kódu atd.). Převodu zdrojového textu na sekvenci tokenů se někdy říká tokenizace. Účelem tokenizace může být:
- Transformace zdrojového textu do podoby, která může být dále zpracovávána dalším modulem překladače (syntaktická analýza popř. nějaké prvotní optimalizace). V takovém případě se však některé tokeny mohou zahazovat; příkladem mohou být komentáře, tokeny představující bílé znaky apod. Spojením lexeru a modulu pro syntaktickou analýzu vznikne parser (jeho typickým výsledkem je AST, mezivýsledkem pak již zmíněný derivační strom).
- Transformace zdrojového kódu pro účely zvýraznění syntaxe v programátorských textových editorech či prohlížečích. V tomto případě se žádné tokeny nezahazují, což je mimochodem i případ knihovny Pygments, kde obecně vyžadujeme, aby výstup obsahoval všechny informace získané ze vstupu (zdrojového kódu).
4. Malá odbočka: tokenizace a programovací jazyk BASIC
Výše zmíněná tokenizace se používala například již v interpretrech programovacího jazyka BASIC na mnoha osmibitových domácích počítačích (ovšem i na některých minipočítačích, kde však BASIC nebyl primárním programovacím jazykem). Ovšem v tomto případě měly tokeny poněkud odlišnou strukturu, protože všechny příkazy a funkce byly většinou reprezentovány jednoznačným osmibitovým celým číslem, které tak současně představovalo jak typ tokenu, tak i jeho hodnotu. Důvod byl jednoduchý – v operační paměti (a ostatně i na disketě nebo magnetické pásce) mohl být uložen tokenizovaný kód a nikoli kód zapsaný uživatelem. Tento kód byl již mnohem jednodušeji zpracovatelný interpretrem, než původní zdrojový kód (odpadlo neustálé volání lexeru – lexikální analýza totiž nebyla na procesorech s frekvencemi okolo 1MHz tak rychlá operace, jako dnes). Navíc se každý programový řádek ihned po svém zápisu automaticky normalizoval (odstranily se bílé znaky, zkratky příkazů se expandovaly atd.). Ostatně množina příkazů a funkcí byla předem známá a nebyla rozšiřitelná (až na uživatelské funkce dostupné jen v některých BASICech). Tokenizovaná podoba programu mohla být i kratší.
Příkladem tokenizace tohoto typu mohou být tokeny použité v interpretru programovacího jazyka Atari BASIC, které skutečně přímo odpovídají příkazům, funkcím a operátorům tohoto jazyka. Pro zajímavost:
Příkaz | Kód tokenu | Příkaz | Kód tokenu | Příkaz | Kód tokenu | Příkaz | Kód tokenu |
---|---|---|---|---|---|---|---|
REM | 00 | NEXT | 09 | CLR | 18 | NOTE | 27 |
DATA | 01 | GOTO | 10 | DEG | 19 | POINT | 28 |
INPUT | 02 | GO TO | 11 | DIM | 20 | XIO | 29 |
COLOR | 03 | GOSUB | 12 | END | 21 | ON | 30 |
LIST | 04 | TRAP | 13 | NEW | 22 | POKE | 31 |
ENTER | 05 | BYE | 14 | OPEN | 23 | 32 | |
LET | 06 | CONT | 15 | LOAD | 24 | RAD | 33 |
IF | 07 | COM | 16 | SAVE | 25 | READ | 34 |
FOR | 08 | CLOSE | 17 | STATUS | 26 | RESTORE | 35 |
…atd…
Podívejme se nyní na způsob uložení programového kódu v operační paměti. Ihned po zápisu každého řádku se provádí již několikrát zmíněná tokenizace, která nahradí jednotlivé konstrukce jazyka osmibitovými kódy. Příkladem může být tokenizace tohoto programového řádku:
10 LET X=1 : PRINT X
V operační paměti tento kód není uložen (pouze v bufferu textového editoru, odtud je však ihned poté přemazán, jakmile je tokenizace dokončena). Namísto toho se do paměti uloží sekvence bajtů s následujícím významem:
číslo programového řádku (10)Sekvence bajtů | Stručný popis |
---|---|
A0 00 | |
13 | délka celého tokenizovaného řádku (19 bajtů) |
0F | offset konce prvního příkazu |
06 | token příkazu LET |
80 | index proměnné X |
2D | token operátoru = |
0E | následuje numerická konstanta |
40 01 00 00 00 00 | takto vypadá zakódovaná hodnota 1 (na začátku je exponent) |
14 | konec (prvního) příkazu |
13 | offset konce druhého příkazu |
20 | token příkazu PRINT |
80 | index proměnné X |
16 | značka EOL pro konec řádku |
5. Příklad tokenizace jednoduchého kódu napsaného v Pythonu
Podívejme se nyní na příklad tokenizace velmi jednoduchého a krátkého zdrojového kódu, který je naprogramován v Pythonu:
for i in range(1, 11): print("Hello world!")
Pro tokenizaci v tomto případě použijeme knihovnu Pygments, která skutečně obsahuje zcela klasickou podobu lexeru. Výsledkem tokenizace je následující sekvence tokenů, tj. dvojic typ+hodnota (řetězec):
Typ tokenu | Řetězec |
---|---|
Token.Keyword | ‚for‘ |
Token.Text | ' ' |
Token.Name | ‚i‘ |
Token.Text | ' ' |
Token.Operator.Word | ‚in‘ |
Token.Text | ' ' |
Token.Name.Builtin | ‚range‘ |
Token.Punctuation | ‚(‘ |
Token.Literal.Number.Integer | ‚1‘ |
Token.Punctuation | ‚,‘ |
Token.Text | ' ' |
Token.Literal.Number.Integer | ‚11‘ |
Token.Punctuation | ‚)‘ |
Token.Punctuation | ‚:‘ |
Token.Text | ‚\n‘ |
Token.Text | ' ' |
Token.Keyword | ‚print‘ |
Token.Punctuation | ‚(‘ |
Token.Literal.String.Double | ‚"‘ |
Token.Literal.String.Double | ‚Hello world!‘ |
Token.Literal.String.Double | ‚"‘ |
Token.Punctuation | ‚)‘ |
Token.Text | ‚\n‘ |
range(1, "FDA") for while with i except for for i else print("Hello world!")
Výsledek tokenizace v tomto případě vypadá následovně:
Typ tokenu | Řetězec |
---|---|
Token.Name.Builtin | ‚range‘ |
Token.Punctuation | ‚(‘ |
Token.Literal.Number.Integer | ‚1‘ |
Token.Punctuation | ‚,‘ |
Token.Text | ' ' |
Token.Literal.String.Double | ‚"‘ |
Token.Literal.String.Double | ‚FDA‘ |
Token.Literal.String.Double | ‚"‘ |
Token.Punctuation | ‚)‘ |
Token.Text | ' ' |
Token.Keyword | ‚for‘ |
Token.Text | ' ' |
Token.Keyword | ‚while‘ |
Token.Text | ' ' |
Token.Keyword | ‚with‘ |
Token.Text | ' ' |
Token.Name | ‚i‘ |
Token.Text | ‚\n‘ |
Token.Keyword | ‚except‘ |
Token.Text | ' ' |
Token.Keyword | ‚for‘ |
Token.Text | ' ' |
Token.Keyword | ‚for‘ |
Token.Text | ' ' |
Token.Name | ‚i‘ |
Token.Text | ' ' |
Token.Keyword | ‚else‘ |
Token.Text | ‚\n‘ |
Token.Text | ' ' |
Token.Keyword | ‚print‘ |
Token.Punctuation | ‚(‘ |
Token.Literal.String.Double | ‚"‘ |
Token.Literal.String.Double | ‚Hello world!‘ |
Token.Literal.String.Double | ‚"‘ |
Token.Punctuation | ‚)‘ |
Token.Text | ‚\n‘ |
6. Tokenizace standardním modulem tokenize
V navazujících kapitolách se budeme zabývat standardním Pythonovským modulem nazvaným příznačně tokenize. Tento modul je určen pro prvotní zpracování vstupních zdrojových kódů s tím, že výsledkem je sekvence tokenů. Tokeny (tedy jejich typ a příslušný numerický kód) jsou deklarovány v modulu nazvaném token. Vzhledem k tomu, že jsou postupně přidávány další typy tokenů (ASYNC apod.), může být zajímavé si nechat vypsat všechny tokeny pro konkrétní (právě nainstalovanou) verzi Pythonu. Pro tento účel může sloužit následující skript:
import token for name, value in vars(token).items(): if not name.startswith('_'): if isinstance(value, int): print("{:20s} {}".format(name, value))
Výsledkem činnosti tohoto skriptu budou symbolická jména i numerické hodnoty všech rozeznávaných tokenů.
Konkrétně pro dnes již poněkud obstarožní Python 3.8:
ENDMARKER 0 NAME 1 NUMBER 2 STRING 3 NEWLINE 4 INDENT 5 DEDENT 6 LPAR 7 RPAR 8 LSQB 9 RSQB 10 COLON 11 COMMA 12 SEMI 13 PLUS 14 MINUS 15 STAR 16 SLASH 17 VBAR 18 AMPER 19 LESS 20 GREATER 21 EQUAL 22 DOT 23 PERCENT 24 LBRACE 25 RBRACE 26 EQEQUAL 27 NOTEQUAL 28 LESSEQUAL 29 GREATEREQUAL 30 TILDE 31 CIRCUMFLEX 32 LEFTSHIFT 33 RIGHTSHIFT 34 DOUBLESTAR 35 PLUSEQUAL 36 MINEQUAL 37 STAREQUAL 38 SLASHEQUAL 39 PERCENTEQUAL 40 AMPEREQUAL 41 VBAREQUAL 42 CIRCUMFLEXEQUAL 43 LEFTSHIFTEQUAL 44 RIGHTSHIFTEQUAL 45 DOUBLESTAREQUAL 46 DOUBLESLASH 47 DOUBLESLASHEQUAL 48 AT 49 ATEQUAL 50 RARROW 51 ELLIPSIS 52 COLONEQUAL 53 OP 54 AWAIT 55 ASYNC 56 TYPE_IGNORE 57 TYPE_COMMENT 58 ERRORTOKEN 59 COMMENT 60 NL 61 ENCODING 62 N_TOKENS 63 NT_OFFSET 256
AMPER 19 AMPER 19 AMPEREQUAL 42 | AMPEREQUAL 41 AT 50 | ASYNC 56 BACKQUOTE 25 | AT 49 CIRCUMFLEX 33 | ATEQUAL 50 CIRCUMFLEXEQUAL 44 | AWAIT 55 > CIRCUMFLEX 32 > CIRCUMFLEXEQUAL 43 COLON 11 COLON 11 > COLONEQUAL 53 COMMA 12 COMMA 12 > COMMENT 60 DEDENT 6 DEDENT 6 DOT 23 DOT 23 DOUBLESLASH 48 | DOUBLESLASH 47 DOUBLESLASHEQUAL 49 | DOUBLESLASHEQUAL 48 DOUBLESTAR 36 | DOUBLESTAR 35 DOUBLESTAREQUAL 47 | DOUBLESTAREQUAL 46 > ELLIPSIS 52 > ENCODING 62 ENDMARKER 0 ENDMARKER 0 EQEQUAL 28 | EQEQUAL 27 EQUAL 22 EQUAL 22 ERRORTOKEN 52 | ERRORTOKEN 59 GREATER 21 GREATER 21 GREATEREQUAL 31 | GREATEREQUAL 30 INDENT 5 INDENT 5 LBRACE 26 | LBRACE 25 LEFTSHIFT 34 | LEFTSHIFT 33 LEFTSHIFTEQUAL 45 | LEFTSHIFTEQUAL 44 LESS 20 LESS 20 LESSEQUAL 30 | LESSEQUAL 29 LPAR 7 LPAR 7 LSQB 9 LSQB 9 MINEQUAL 38 | MINEQUAL 37 MINUS 15 MINUS 15 NAME 1 NAME 1 NEWLINE 4 NEWLINE 4 NOTEQUAL 29 | NL 61 > NOTEQUAL 28 NT_OFFSET 256 NT_OFFSET 256 N_TOKENS 53 | N_TOKENS 63 NUMBER 2 NUMBER 2 OP 51 | OP 54 PERCENT 24 PERCENT 24 PERCENTEQUAL 41 | PERCENTEQUAL 40 PLUS 14 PLUS 14 PLUSEQUAL 37 | PLUSEQUAL 36 RBRACE 27 | RARROW 51 RIGHTSHIFT 35 | RBRACE 26 RIGHTSHIFTEQUAL 46 | RIGHTSHIFT 34 > RIGHTSHIFTEQUAL 45 RPAR 8 RPAR 8 RSQB 10 RSQB 10 SEMI 13 SEMI 13 SLASH 17 SLASH 17 SLASHEQUAL 40 | SLASHEQUAL 39 STAR 16 STAR 16 STAREQUAL 39 | STAREQUAL 38 STRING 3 STRING 3 TILDE 32 | TILDE 31 > TYPE_COMMENT 58 > TYPE_IGNORE 57 VBAR 18 VBAR 18 VBAREQUAL 43 | VBAREQUAL 42
7. Tokenizace jednoduchého výrazu
Vyzkoušejme si nyní, jakým způsobem lze získat sekvenci tokenů pro nějaký jednoduchý výraz zapsaný v syntaxi Pythonu:
1+2*3
Tento výraz uložíme do souboru nazvaného expression.py. Následně využijeme výše zmíněný modul tokenize, a to jeho přímým zavoláním z příkazové řádky:
$ python3 -m tokenize expression.py
Výsledek by měl vypadat takto:
0,0-0,0: ENCODING 'utf-8' 1,0-1,1: NUMBER '1' 1,1-1,2: OP '+' 1,2-1,3: NUMBER '2' 1,3-1,4: OP '*' 1,4-1,5: NUMBER '3' 1,5-1,6: NEWLINE '\n' 2,0-2,0: ENDMARKER ''
Tokenizer ovšem ve skutečnosti neprovádí žádnou kontrolu syntaxe, takže dokáže získat sekvenci tokenů i pro následující kód, který je v Pythonu syntakticky nesprávný:
1*+2*3@4
S výsledkem:
$ python3 -m tokenize err_expression.py 0,0-0,0: ENCODING 'utf-8' 1,0-1,1: NUMBER '1' 1,1-1,2: OP '*' 1,2-1,3: OP '+' 1,3-1,4: NUMBER '2' 1,4-1,5: OP '*' 1,5-1,6: NUMBER '3' 1,6-1,7: OP '@' 1,7-1,8: NUMBER '4' 1,8-1,9: NEWLINE '\n' 2,0-2,0: ENDMARKER ''
Tokenizaci lze ovšem vyvolat přímo z Pythonu, a to přímým zavoláním funkce tokenize z modulu se stejným jménem. Výsledkem je sekvence tokenů, kterou lze procházet:
import tokenize with open("expression.py", "rb") as fin: token_generator = tokenize.tokenize(fin.readline) for token in token_generator: print(token)
S výsledkem:
$ python3 tokenize_expression_1.py TokenInfo(type=62 (ENCODING), string='utf-8', start=(0, 0), end=(0, 0), line='') TokenInfo(type=2 (NUMBER), string='1', start=(1, 0), end=(1, 1), line='1+2*3\n') TokenInfo(type=54 (OP), string='+', start=(1, 1), end=(1, 2), line='1+2*3\n') TokenInfo(type=2 (NUMBER), string='2', start=(1, 2), end=(1, 3), line='1+2*3\n') TokenInfo(type=54 (OP), string='*', start=(1, 3), end=(1, 4), line='1+2*3\n') TokenInfo(type=2 (NUMBER), string='3', start=(1, 4), end=(1, 5), line='1+2*3\n') TokenInfo(type=4 (NEWLINE), string='\n', start=(1, 5), end=(1, 6), line='1+2*3\n') TokenInfo(type=0 (ENDMARKER), string='', start=(2, 0), end=(2, 0), line='')
Alternativní způsob zápisu s využitím funkce tokenize.open:
import tokenize with tokenize.open("expression.py") as fin: token_generator = tokenize.generate_tokens(fin.readline) for token in token_generator: print(token)
Výsledek bude prakticky totožný s předchozím příkladem, až na chybějící token s informací o kódování:
TokenInfo(type=2 (NUMBER), string='1', start=(1, 0), end=(1, 1), line='1+2*3\n') TokenInfo(type=54 (OP), string='+', start=(1, 1), end=(1, 2), line='1+2*3\n') TokenInfo(type=2 (NUMBER), string='2', start=(1, 2), end=(1, 3), line='1+2*3\n') TokenInfo(type=54 (OP), string='*', start=(1, 3), end=(1, 4), line='1+2*3\n') TokenInfo(type=2 (NUMBER), string='3', start=(1, 4), end=(1, 5), line='1+2*3\n') TokenInfo(type=4 (NEWLINE), string='\n', start=(1, 5), end=(1, 6), line='1+2*3\n') TokenInfo(type=0 (ENDMARKER), string='', start=(2, 0), end=(2, 0), line='')
8. Tokenizace kódu s funkcí, vnořenými smyčkami a podmínkou
Nyní se podívejme na poněkud složitější programový kód, konkrétně na funkci určenou pro výpočet prvočísel až do nastaveného limitu. Povšimněte si, že tato funkce obsahuje vnořené programové smyčky, podmínku, generátorovou notaci seznamu atd., takže její tokenizovaná podoba bude zajímavější, než tomu bylo u jednoduchého výrazu:
# 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))
Tokenizaci provedeme tímto skriptem:
import tokenize with tokenize.open("primes.py") as fin: token_generator = tokenize.generate_tokens(fin.readline) for token in token_generator: print(token)
Zkrácený výsledek bude vypadat následovně:
TokenInfo(type=60 (COMMENT), string='# originální kód lze nalézt na adrese:', start=(1, 0), end=(1, 38), line='# originální kód lze nalézt na adrese:\n') TokenInfo(type=61 (NL), string='\n', start=(1, 38), end=(1, 39), line='# originální kód lze nalézt na adrese:\n') TokenInfo(type=60 (COMMENT), string='# http://www.rosettacode.org/wiki/Sieve_of_Eratosthenes#Using_array_lookup', start=(2, 0), end=(2, 74), line='# http://www.rosettacode.org/wiki/Sieve_of_Eratosthenes#Using_array_lookup\n') TokenInfo(type=61 (NL), string='\n', start=(2, 74), end=(2, 75), line='# http://www.rosettacode.org/wiki/Sieve_of_Eratosthenes#Using_array_lookup\n') ... ... ...
Zajímavá je tokenizace této programové smyčky:
for n in range(int(limit**0.5 + 1.5)): # stop at ``sqrt(limit)``
Do podoby (pro větší přehlednost jsou sloupce zarovnány):
TokenInfo(type=5 (INDENT), string=' ', start=(8, 0), end=(8, 12), line=' for i in range(n*n, limit+1, n):\n') TokenInfo(type=1 (NAME), string='for', start=(8, 12), end=(8, 15), line=' for i in range(n*n, limit+1, n):\n') TokenInfo(type=1 (NAME), string='i', start=(8, 16), end=(8, 17), line=' for i in range(n*n, limit+1, n):\n') TokenInfo(type=1 (NAME), string='in', start=(8, 18), end=(8, 20), line=' for i in range(n*n, limit+1, n):\n') TokenInfo(type=1 (NAME), string='range', start=(8, 21), end=(8, 26), line=' for i in range(n*n, limit+1, n):\n') TokenInfo(type=54 (OP), string='(', start=(8, 26), end=(8, 27), line=' for i in range(n*n, limit+1, n):\n') TokenInfo(type=1 (NAME), string='n', start=(8, 27), end=(8, 28), line=' for i in range(n*n, limit+1, n):\n') TokenInfo(type=54 (OP), string='*', start=(8, 28), end=(8, 29), line=' for i in range(n*n, limit+1, n):\n') TokenInfo(type=1 (NAME), string='n', start=(8, 29), end=(8, 30), line=' for i in range(n*n, limit+1, n):\n') TokenInfo(type=54 (OP), string=',', start=(8, 30), end=(8, 31), line=' for i in range(n*n, limit+1, n):\n') TokenInfo(type=1 (NAME), string='limit', start=(8, 32), end=(8, 37), line=' for i in range(n*n, limit+1, n):\n') TokenInfo(type=54 (OP), string='+', start=(8, 37), end=(8, 38), line=' for i in range(n*n, limit+1, n):\n') TokenInfo(type=2 (NUMBER), string='1', start=(8, 38), end=(8, 39), line=' for i in range(n*n, limit+1, n):\n') TokenInfo(type=54 (OP), string=',', start=(8, 39), end=(8, 40), line=' for i in range(n*n, limit+1, n):\n') TokenInfo(type=1 (NAME), string='n', start=(8, 41), end=(8, 42), line=' for i in range(n*n, limit+1, n):\n') TokenInfo(type=54 (OP), string=')', start=(8, 42), end=(8, 43), line=' for i in range(n*n, limit+1, n):\n') TokenInfo(type=54 (OP), string=':', start=(8, 43), end=(8, 44), line=' for i in range(n*n, limit+1, n):\n') TokenInfo(type=4 (NEWLINE), string='\n', start=(8, 44), end=(8, 45), line=' for i in range(n*n, limit+1, n):\n')
Zajímavé je, že v této chvíli vlastně ještě nemáme k dispozici informaci o tom, že například for je klíčové slovo zatímco limit je jméno proměnné. Toto rozlišení je provedeno až na úrovni AST. Totéž platí pro závorky, které jsou uloženy v tokenu OP a nikoli LBRACE a RBRACE.
9. Tokenizace kódu s klíčovými slovy async a await
Ve výpisu tokenů nalezneme kromě jiného i tyto tokeny:
AWAIT 55 ASYNC 56
Vyzkoušejme si tedy, jestli jsou tyto tokeny skutečně použity, a to při tokenizaci tohoto zdrojového kódu:
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)
Pro tokenizaci použijeme tento jednoduchý skript:
import tokenize with tokenize.open("async.py") as fin: token_generator = tokenize.generate_tokens(fin.readline) for token in token_generator: print(token)
Výsledek je poměrně dlouhý, takže je zobrazen pouze výběr tokenů z celé sekvence:
$ python3 tokenize_async.py | grep -E 'string=.async|string=.await' TokenInfo(type=1 (NAME), string='async', start=(4, 0), end=(4, 5), line='async def producer(send_channel):\n') TokenInfo(type=1 (NAME), string='await', start=(8, 8), end=(8, 13), line=' await send_channel.send(message)\n') TokenInfo(type=1 (NAME), string='async', start=(11, 0), end=(11, 5), line='async def consumer(receive_channel):\n') TokenInfo(type=1 (NAME), string='async', start=(12, 4), end=(12, 9), line=' async for value in receive_channel:\n') TokenInfo(type=1 (NAME), string='await', start=(14, 8), end=(14, 13), line=' await trio.sleep(1)\n') TokenInfo(type=1 (NAME), string='async', start=(17, 0), end=(17, 5), line='async def main():\n') TokenInfo(type=1 (NAME), string='async', start=(18, 4), end=(18, 9), line=' async with trio.open_nursery() as nursery:\n')
Vidíme, že klíčová slova prozatím nejsou při tokenizaci rozeznávána a jsou vrácena ve formě tokenu typu NAME, tedy obecné jméno či identifikátor. Rozeznání je opět provedeno až na úrovni AST.
10. Rozlišení operátorů v sekvenci tokenů
Ještě jednou se vraťme k tokenizaci jednoduchého výrazu:
(1+2)*3
V případě, že si necháme vypsat pouze sekvenci tokenů skriptem:
import tokenize with tokenize.open("expression2.py") as fin: token_generator = tokenize.generate_tokens(fin.readline) for token in token_generator: print(token)
Získáme výsledek, v němž mají všechny „operátorové“ tokeny, a to včetně závorek, typ 54 (OP):
TokenInfo(type=54 (OP), string='(', start=(1, 0), end=(1, 1), line='(1+2)*3\n') TokenInfo(type=2 (NUMBER), string='1', start=(1, 1), end=(1, 2), line='(1+2)*3\n') TokenInfo(type=54 (OP), string='+', start=(1, 2), end=(1, 3), line='(1+2)*3\n') TokenInfo(type=2 (NUMBER), string='2', start=(1, 3), end=(1, 4), line='(1+2)*3\n') TokenInfo(type=54 (OP), string=')', start=(1, 4), end=(1, 5), line='(1+2)*3\n') TokenInfo(type=54 (OP), string='*', start=(1, 5), end=(1, 6), line='(1+2)*3\n') TokenInfo(type=2 (NUMBER), string='3', start=(1, 6), end=(1, 7), line='(1+2)*3\n') TokenInfo(type=4 (NEWLINE), string='\n', start=(1, 7), end=(1, 8), line='(1+2)*3\n') TokenInfo(type=0 (ENDMARKER), string='', start=(2, 0), end=(2, 0), line='')
Pro rozlišení konkrétních operátorů a závorek je nutné přečíst atribut exact_type, což vede k následující úpravě skriptu:
import tokenize with tokenize.open("expression2.py") as fin: token_generator = tokenize.generate_tokens(fin.readline) for token in token_generator: print("{:2} {:2} {}".format(token.type, token.exact_type, token))
Tento skript vypíše obecný typ tokenu, „přesný“ typ tokenu a vlastní n-tici s obsahem tokenu. Povšimněte si rozdílů v hodnotách v prvním a druhém sloupci, ovšem pouze u obecného typu OP:
54 7 TokenInfo(type=54 (OP), string='(', start=(1, 0), end=(1, 1), line='(1+2)*3\n') 2 2 TokenInfo(type=2 (NUMBER), string='1', start=(1, 1), end=(1, 2), line='(1+2)*3\n') 54 14 TokenInfo(type=54 (OP), string='+', start=(1, 2), end=(1, 3), line='(1+2)*3\n') 2 2 TokenInfo(type=2 (NUMBER), string='2', start=(1, 3), end=(1, 4), line='(1+2)*3\n') 54 8 TokenInfo(type=54 (OP), string=')', start=(1, 4), end=(1, 5), line='(1+2)*3\n') 54 16 TokenInfo(type=54 (OP), string='*', start=(1, 5), end=(1, 6), line='(1+2)*3\n') 2 2 TokenInfo(type=2 (NUMBER), string='3', start=(1, 6), end=(1, 7), line='(1+2)*3\n') 4 4 TokenInfo(type=4 (NEWLINE), string='\n', start=(1, 7), end=(1, 8), line='(1+2)*3\n') 0 0 TokenInfo(type=0 (ENDMARKER), string='', start=(2, 0), end=(2, 0), line='')
11. Zobrazení AST pro část zdrojového kódu Pythonu
Víme již, že dalším krokem ve zpracování zdrojového kódu je převod sekvence tokenů na abstraktní syntaktický strom (AST). Interně se jedná o relativně komplikovaný proces, protože gramatika Pythonu je již poměrně složitá. Nicméně z pohledu programátora postačuje znalost modulu ast, který dokáže převést část zdrojového kódu reprezentovaného řetězcem nebo dokonce i celý soubor se zdrojovým kódem na AST. AST lze následně zobrazit funkcí ast.dump. Podívejme se na převod jednoduchého výrazu do AST:
import ast tree = ast.parse("1+2*3") print(ast.dump(tree))
Získaný výsledek je ovšem poměrně nečitelný:
Module(body=[Expr(value=BinOp(left=Num(n=1), op=Add(), right=BinOp(left=Num(n=2), op=Mult(), right=Num(n=3))))])
Do Pythonu 3.10 byla přidána možnost zobrazení stromu v čitelnější podobě – poduzly jsou v tomto případě jednoduše odsazeny o počet mezer specifikovaných v nepovinném parametru indent:
import ast tree = ast.parse("1+2*3") print(ast.dump(tree, indent=4))
Výsledek je již mnohem čitelnější:
Module( body=[ Expr( value=BinOp( left=Constant(value=1), op=Add(), right=BinOp( left=Constant(value=2), op=Mult(), right=Constant(value=3))))], type_ignores=[])
12. Zobrazení AST pro soubor se zdrojovým kódem
Do AST lze převést i celý soubor se zdrojovým kódem, a to následujícím způsobem:
import ast with open("async.py") as fin: code = fin.read() tree = ast.parse(code) print(ast.dump(tree))
Výsledek je ovšem opět poměrně nečitelný, protože není zdůrazněna samotná struktura AST, ale pouze hodnoty jeho uzlů:
Module(body=[Import(names=[alias(name='trio', asname=None)]), AsyncFunctionDef(name='producer', args=arguments(posonlyargs=[], args=[arg(arg='send_channel', annotation=None, type_comment=None)], vararg=None, kwonlyargs=[], kw_defaults=[], kwarg=None, defaults=[]), body=[For(target=Name(id='i', ctx=Store()), iter=Call(func=Name(id='range', ctx=Load()), args=[Constant(value=1, kind=None), Constant(value=10, kind=None)], keywords=[]), body=[Assign(targets=[Name(id='message', ctx=Store())], value=JoinedStr(values=[Constant(value='message ', kind=None), FormattedValue(value=Name(id='i', ctx=Load()), conversion=-1, format_spec=None)]), type_comment=None), Expr(value=Call(func=Name(id='print', ctx=Load()), args=[JoinedStr(values=[Constant(value='Producer: ', kind=None), FormattedValue(value=Name(id='message', ctx=Load()), conversion=-1, format_spec=None)])], keywords=[])), Expr(value=Await(value=Call(func=Attribute(value=Name(id='send_channel', ctx=Load()), attr='send', ctx=Load()), args=[Name(id='message', ctx=Load())], keywords=[])))], orelse=[], type_comment=None)], decorator_list=[], returns=None, type_comment=None), AsyncFunctionDef(name='consumer', args=arguments(posonlyargs=[], args=[arg(arg='receive_channel', annotation=None, type_comment=None)], vararg=None, kwonlyargs=[], kw_defaults=[], kwarg=None, defaults=[]), body=[AsyncFor(target=Name(id='value', ctx=Store()), iter=Name(id='receive_channel', ctx=Load()), body=[Expr(value=Call(func=Name(id='print', ctx=Load()), args=[JoinedStr(values=[Constant(value='Consumer: received', kind=None), FormattedValue(value=Name(id='value', ctx=Load()), conversion=114, format_spec=None)])], keywords=[])), Expr(value=Await(value=Call(func=Attribute(value=Name(id='trio', ctx=Load()), attr='sleep', ctx=Load()), args=[Constant(value=1, kind=None)], keywords=[])))], orelse=[], type_comment=None)], decorator_list=[], returns=None, type_comment=None), AsyncFunctionDef(name='main', args=arguments(posonlyargs=[], args=[], vararg=None, kwonlyargs=[], kw_defaults=[], kwarg=None, defaults=[]), body=[AsyncWith(items=[withitem(context_expr=Call(func=Attribute(value=Name(id='trio', ctx=Load()), attr='open_nursery', ctx=Load()), args=[], keywords=[]), optional_vars=Name(id='nursery', ctx=Store()))], body=[Assign(targets=[Tuple(elts=[Name(id='send_channel', ctx=Store()), Name(id='receive_channel', ctx=Store())], ctx=Store())], value=Call(func=Attribute(value=Name(id='trio', ctx=Load()), attr='open_memory_channel', ctx=Load()), args=[Constant(value=0, kind=None)], keywords=[]), type_comment=None), Expr(value=Call(func=Attribute(value=Name(id='nursery', ctx=Load()), attr='start_soon', ctx=Load()), args=[Name(id='producer', ctx=Load()), Name(id='send_channel', ctx=Load())], keywords=[])), Expr(value=Call(func=Attribute(value=Name(id='nursery', ctx=Load()), attr='start_soon', ctx=Load()), args=[Name(id='consumer', ctx=Load()), Name(id='receive_channel', ctx=Load())], keywords=[]))], type_comment=None)], decorator_list=[], returns=None, type_comment=None), Expr(value=Call(func=Attribute(value=Name(id='trio', ctx=Load()), attr='run', ctx=Load()), args=[Name(id='main', ctx=Load())], keywords=[]))], type_ignores=[])
Úprava pro Python 3.10 vypadá následovně:
import ast with open("async.py") as fin: code = fin.read() tree = ast.parse(code) print(ast.dump(tree, indent=4))
S mnohem čitelnějším výsledkem:
Module( body=[ Import( names=[ alias(name='trio')]), AsyncFunctionDef( name='producer', args=arguments( posonlyargs=[], args=[ arg(arg='send_channel')], kwonlyargs=[], kw_defaults=[], defaults=[]), body=[ For( target=Name(id='i', ctx=Store()), iter=Call( func=Name(id='range', ctx=Load()), args=[ Constant(value=1), Constant(value=10)], keywords=[]), body=[ Assign( targets=[ Name(id='message', ctx=Store())], value=JoinedStr( values=[ Constant(value='message '), FormattedValue( value=Name(id='i', ctx=Load()), conversion=-1)])), Expr( value=Call( func=Name(id='print', ctx=Load()), args=[ JoinedStr( values=[ Constant(value='Producer: '), FormattedValue( value=Name(id='message', ctx=Load()), conversion=-1)])], keywords=[])), Expr( value=Await( value=Call( func=Attribute( value=Name(id='send_channel', ctx=Load()), attr='send', ctx=Load()), args=[ Name(id='message', ctx=Load())], keywords=[])))], orelse=[])], decorator_list=[]), AsyncFunctionDef( name='consumer', args=arguments( posonlyargs=[], args=[ arg(arg='receive_channel')], kwonlyargs=[], kw_defaults=[], defaults=[]), body=[ AsyncFor( target=Name(id='value', ctx=Store()), iter=Name(id='receive_channel', ctx=Load()), body=[ Expr( value=Call( func=Name(id='print', ctx=Load()), args=[ JoinedStr( values=[ Constant(value='Consumer: received'), FormattedValue( value=Name(id='value', ctx=Load()), conversion=114)])], keywords=[])), Expr( value=Await( value=Call( func=Attribute( value=Name(id='trio', ctx=Load()), attr='sleep', ctx=Load()), args=[ Constant(value=1)], keywords=[])))], orelse=[])], decorator_list=[]), AsyncFunctionDef( name='main', args=arguments( posonlyargs=[], args=[], kwonlyargs=[], kw_defaults=[], defaults=[]), body=[ AsyncWith( items=[ withitem( context_expr=Call( func=Attribute( value=Name(id='trio', ctx=Load()), attr='open_nursery', ctx=Load()), args=[], keywords=[]), optional_vars=Name(id='nursery', ctx=Store()))], body=[ Assign( targets=[ Tuple( elts=[ Name(id='send_channel', ctx=Store()), Name(id='receive_channel', ctx=Store())], ctx=Store())], value=Call( func=Attribute( value=Name(id='trio', ctx=Load()), attr='open_memory_channel', ctx=Load()), args=[ Constant(value=0)], keywords=[])), Expr( value=Call( func=Attribute( value=Name(id='nursery', ctx=Load()), attr='start_soon', ctx=Load()), args=[ Name(id='producer', ctx=Load()), Name(id='send_channel', ctx=Load())], keywords=[])), Expr( value=Call( func=Attribute( value=Name(id='nursery', ctx=Load()), attr='start_soon', ctx=Load()), args=[ Name(id='consumer', ctx=Load()), Name(id='receive_channel', ctx=Load())], keywords=[]))])], decorator_list=[]), Expr( value=Call( func=Attribute( value=Name(id='trio', ctx=Load()), attr='run', ctx=Load()), args=[ Name(id='main', ctx=Load())], keywords=[]))], type_ignores=[])
13. Obsah navazujícího článku
Dnes jsme se věnovali pouze naprostému základu manipulace s abstraktními syntaktickými stromy. Příště si ukážeme některé zajímavější a v některých případech i praktičtější operace. Zejména se budeme věnovat tomu, jak lze zajistit průchod všemi uzly AST, a to takovým způsobem, aby bylo například možné zpracovat jednotlivé výrazy, filtrovat uzly podle různých kritérií atd. (některé ze skriptů již můžete najít v repositáři. Ovšem vzhledem k tomu, že AST mohou být (a jsou) velmi rozsáhlé, je vhodné mít nástroj pro jejich vizualizaci nejenom na terminálu, ale i v grafické podobě. I tímto nástrojem, resp. přesněji řečeno nástroji, se budeme zabývat příště.
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 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