Knihovna LibCST umožňující snadnou modifikaci zdrojových kódů Pythonu

Obsah

1. Knihovna LibCST umožňující snadnou modifikaci zdrojových kódů Pythonu

2. AST vs CST

3. Parsing jednoduchého výrazu s konstrukcí CST

4. Zobrazení struktury výsledného CST

5. Zachování formátu výrazu i konstant ve výrazu

6. Rozdíl mezi identifikátorem a řetězcem

7. Strom s reprezentací složitějších výrazů

8. Strom, který reprezentuje výraz „6*7“

9. Bílé znaky zapsané ve výrazu

10. Výraz obalený závorkami

11. Strom pro složitější výraz s několika operátory

12. Parsing celého modulu

13. Ukázky parsingu dalších jednoduchých modulů

14. Modul s definicí funkce

15. Realizace průchodu CST

16. Výpis uzlů stromu tak, aby byla viditelná jeho struktura

17. Získání dalších informací o uzlech známých typů

18. Různé zpracování uzlů podle jejich typů

19. Repositář s demonstračními příklady

20. Odkazy na Internetu

1. Knihovna LibCST umožňující snadnou modifikaci zdrojových kódů Pythonu

Na čtveřici článků, v nichž jsme se zabývali problematikou lexikální a syntaktické analýzy zdrojových kódů programovacího jazyka Python [1] [2] [3] [4] dnes do jisté míry navážeme. Víme již, jak je možné s využitím standardních modulů tokenize a ast provést takzvanou tokenizaci a následně parsing zdrojových kódů, jehož výsledkem je AST neboli abstraktní syntaktický strom (Abstract Syntax Tree). Tyto techniky nám umožní manipulovat s programovým kódem na vhodné úrovni abstrakce, protože abstraktní syntaktický strom je pro tyto účely mnohem vhodnější, než přímo zdrojový kód či pouhá sekvence tokenů. Z tohoto důvodu je tokenizace a parsing součástí většiny linterů i dalších analyzátorů programových kódů.

2. AST vs CST

Standardní abstraktní syntaktický strom má ovšem jednu poměrně zásadní nevýhodu – v případě, že AST upravíme a necháme si z něho zpětně vygenerovat zdrojový kód, ztratíme veškeré původní formátování, tedy například mezery zapsané ve výrazech, přesné umístění komentářů atd. Z tohoto důvodu se pro ty nástroje, které musí modifikovat zdrojový kód (nepřímo – přes strom) používají nepatrně odlišné typy stromů, které se nazývají Concrete Syntax Tree neboli zkráceně CST (popř. derivační stromy nebo parse tree). Tyto stromové datové struktury, jak již ostatně jejich název napovídá, reprezentují syntaktickou strukturu daného bloku programového kódu (což může být konstanta, výraz, příkaz, složený blok, funkce, třída, či celý modul). Díky tomu, že si CST pamatuje původní zápis syntaktických prvků, je umožněna relativně snadná tvorba nástrojů pro refaktoring kódu. Pro manipulaci s CST slouží v Pythonu knihovna LibCST, s jejímiž základními vlastnostmi se seznámíme v dnešním článku.

3. Parsing jednoduchého výrazu s konstrukcí CST

Možnosti knihovny LibCST si otestujeme na množství demonstračních příkladů. První příklady budou velmi jednoduché, protože budeme zpracovávat zdrojový kód obsahující pouze jedinou konstantu. Může se jednat například o konstantu představující celé číslo (což je v Pythonu zcela korektní zdrojový kód):

42

Tato konstanta (tedy její zdrojový kód) se zpracuje tokenizérem a parserem takto:

from libcst import parse_expression
 
constant = "42"
 
parsed = parse_expression(constant)

Výsledek, tedy obsah proměnné parsed, je datová struktura přesně popisující výraz s konstantou. Tuto datovou strukturu si můžeme přímo zobrazit:

print(parsed)

Ovšem užitečnější bývá použití pomocné funkce dump, která vytiskne CST v čitelnější podobě:

from libcst.tool import dump
 
dumped = dump(parsed)
print(dumped)

4. Zobrazení struktury výsledného CST

Celý skript, který provede parsing výrazu do CST a následně zobrazí strukturu CST, vypadá následovně:

#!/usr/bin/python
# vim: set fileencoding=utf-8
 
from libcst import parse_expression
from libcst.tool import dump
 
 
constant = "42"
 
parsed = parse_expression(constant)
print("Parsed:")
print(parsed)
 
print()
 
dumped = dump(parsed)
print("Dumped:")
print(dumped)

Po spuštění tohoto skriptu se nejdříve zobrazí CST se všemi podrobnostmi a posléze „pouze“ výsledek operace dump, který je stručnější a v tomto případě i čitelnější:

Parsed:
Integer(
    value='42',
    lpar=[],
    rpar=[],
)
 
Dumped:
Integer(
  value='42',
)

5. Zachování formátu výrazu i konstant ve výrazu

Knihovna LibCST se nesnaží o „normalizaci“ výrazů ani hodnot, které jsou ve výrazu specifikovány. To je nutné, aby bylo možné zrekonstruovat původní výraz přesně v takové podobě, v jaké byl původně zapsán (samozřejmě za předpokladu, že nedojde k modifikaci stromu).

Vyzkoušejme si, jak bude zparsován výraz s konstantou 1_000, což je běžná celočíselná konstanta 1000, do které byl přidán nepovinný oddělovač řádu:

#!/usr/bin/python
# vim: set fileencoding=utf-8
 
from libcst import parse_expression
from libcst.tool import dump
 
 
constant = "1_000"
 
parsed = parse_expression(constant)
print("Parsed:")
print(parsed)
 
print()
 
dumped = dump(parsed)
print("Dumped:")
print(dumped)

V CST stromu nalezneme původní zápis konstanty, což nám (jak již víme) umožní rekonstrukci originální podoby výrazu:

Parsed:
Integer(
    value='1_000',
    lpar=[],
    rpar=[],
)
 
Dumped:
Integer(
  value='1_000',
)

Nakonec si ještě pro úplnost ukažme výsledek parsingu komplexního čísla:

#!/usr/bin/python
# vim: set fileencoding=utf-8
 
from libcst import parse_expression
from libcst.tool import dump
 
 
constant = "1+2j"
 
parsed = parse_expression(constant)
print("Parsed:")
print(parsed)
 
print()
 
dumped = dump(parsed)
print("Dumped:")
print(dumped)

Zkonstruovaný strom vypadá takto:

Parsed:
BinaryOperation(
    left=Integer(
        value='1',
        lpar=[],
        rpar=[],
    ),
    operator=Add(
        whitespace_before=SimpleWhitespace(
            value='',
        ),
        whitespace_after=SimpleWhitespace(
            value='',
        ),
    ),
    right=Imaginary(
        value='2j',
        lpar=[],
        rpar=[],
    ),
    lpar=[],
    rpar=[],
)
 
Dumped:
BinaryOperation(
  left=Integer(
    value='1',
  ),
  operator=Add(),
  right=Imaginary(
    value='2j',
  ),
)

6. Rozdíl mezi identifikátorem a řetězcem

Zkusme si nyní nechat převést na CST výraz obsahující jedinou konstantu True. Samotný výraz, který má být zparsován, je uložen v řetězci, což může být v tomto případě poněkud matoucí, ovšem knihovna LibCST parsuje zdrojový kód uložený v řetězci, takže zápis „True“ skutečně znamená logickou konstantu True:

#!/usr/bin/python
# vim: set fileencoding=utf-8
 
from libcst import parse_expression
from libcst.tool import dump
 
 
constant = "True"
 
parsed = parse_expression(constant)
print("Parsed:")
print(parsed)
 
print()
 
dumped = dump(parsed)
print("Dumped:")
print(dumped)

Povšimněte si, že se ve výsledném CST stromu objevil uzel typu Name. LibCST tedy nerozlišuje mezi běžným pojmenovaným identifikátorem a „speciálními“ identifikátory typu True, False či None (což může později způsobovat nepatrné problémy při analýze programu):

Parsed:
Name(
    value='True',
    lpar=[],
    rpar=[],
)
 
Dumped:
Name(
  value='True',
)

Naproti tomu zápis „‚True‘“ (dvojice uvozovek) značí řetězcový literál, který jen náhodou obsahuje známé slovo:

#!/usr/bin/python
# vim: set fileencoding=utf-8
 
from libcst import parse_expression
from libcst.tool import dump
 
 
constant = "'True'"
 
parsed = parse_expression(constant)
print("Parsed:")
print(parsed)
 
print()
 
dumped = dump(parsed)
print("Dumped:")
print(dumped)

Rozdíl je ihned patrný při pohledu na typ uzlu stromu – nyní se jedná o uzel SimpleString a nikoli o uzel Name:

Parsed:
SimpleString(
    value="'True'",
    lpar=[],
    rpar=[],
)
 
Dumped:
SimpleString(
  value="'True'",
)

7. Strom s reprezentací složitějších výrazů

Prozatím jsme si ukázali parsing těch nejjednodušších možných výrazů, které obsahovaly jen jedinou hodnotu – buď konstantu (celočíselnou, řetězec atd.) nebo jméno identifikátoru. Speciálním případem bylo komplexní číslo, které je vlastně výrazem s reálnou a imaginární složkou. Ovšem v praxi se pochopitelně setkáme s mnohem složitějšími výrazy. V rámci navazujících kapitol si ukážeme, jak knihovna LibCST ze složitějších výrazů tvoří strom. A odtud je již jen malý krok k parsingu programových bloků, funkcí, či celých modulů.

8. Strom, který reprezentuje výraz „6*7“

Podívejme se na způsob parsingu výrazu 6*7, tedy výrazu obsahujícího aritmetickou operaci součinu. Samotný skript zůstane zachován, pouze se změní výraz, se kterým se bude pracovat:

#!/usr/bin/python
# vim: set fileencoding=utf-8
 
from libcst import parse_expression
from libcst.tool import dump
 
 
expression = "6*7"
 
parsed = parse_expression(expression)
print("Parsed:")
print(parsed)
 
print()
 
dumped = dump(parsed)
print("Dumped:")
print(dumped)

Výsledkem nyní bude strom obsahující kořenový uzel typu BinaryOperation. Tento uzel obsahuje trojici poduzlů reprezentujících postupně celé číslo, operátor součinu a další celé číslo. To znamená, že samotný uzel BinaryOperation nenese informaci o prováděné operaci; je nutné se podívat do poduzlů. Taktéž si povšimněte atributů lpar a rpar, v nichž mohou být uloženy informace o závorkách (zde žádné závorky nepoužíváme) a atributů whitespace_before a whitespace_after, k nimž se ještě vrátíme:

BinaryOperation(
    left=Integer(
        value='6',
        lpar=[],
        rpar=[],
    ),
    operator=Multiply(
        whitespace_before=SimpleWhitespace(
            value='',
        ),
        whitespace_after=SimpleWhitespace(
            value='',
        ),
    ),
    right=Integer(
        value='7',
        lpar=[],
        rpar=[],
    ),
    lpar=[],
    rpar=[],
)
 
Dumped:
BinaryOperation(
  left=Integer(
    value='6',
  ),
  operator=Multiply(),
  right=Integer(
    value='7',
  ),
)

9. Bílé znaky zapsané ve výrazu

V samotném výrazu povoluje programovací jazyk Python používat bílé znaky, ostatně podobně jako mnohé další programovací jazyky. Ovšem tyto bílé znaky musí být v CST zachovány, aby bylo možné zrekonstruovat původní zdrojový kód. Podívejme se tedy na výsledek parsingu výrazu 6 * 7 (tedy s mezerami mezi celočíselnými konstantami a operátorem):

#!/usr/bin/python
# vim: set fileencoding=utf-8
 
from libcst import parse_expression
from libcst.tool import dump
 
 
expression = "6 * 7"
 
parsed = parse_expression(expression)
print("Parsed:")
print(parsed)
 
print()
 
dumped = dump(parsed)
print("Dumped:")
print(dumped)

Bílé znaky jsou v CST uloženy v atributech whitespace_before a whitespace_after v uzlu typu Multiply, což sice může vypadat zvláštně, ovšem umožní snadnou rekonstrukci zdrojového kódu:

BinaryOperation(
    left=Integer(
        value='6',
        lpar=[],
        rpar=[],
    ),
    operator=Multiply(
        whitespace_before=SimpleWhitespace(
            value=' ',
        ),
        whitespace_after=SimpleWhitespace(
            value=' ',
        ),
    ),
    right=Integer(
        value='7',
        lpar=[],
        rpar=[],
    ),
    lpar=[],
    rpar=[],
)
 
Dumped:
BinaryOperation(
  left=Integer(
    value='6',
  ),
  operator=Multiply(),
  right=Integer(
    value='7',
  ),
)

Co se ovšem stane ve chvíli, kdy mezeru umístíme před první celočíselnou konstantu? Otestujme si i tento případ:

#!/usr/bin/python
# vim: set fileencoding=utf-8
 
from libcst import parse_expression
from libcst.tool import dump
 
 
expression = " 6 * 7 "
 
parsed = parse_expression(expression)
print("Parsed:")
print(parsed)
 
print()
 
dumped = dump(parsed)
print("Dumped:")
print(dumped)

Nyní dojde při pokusu o konstrukci CST k výjimce, jak je to ostatně patrné i z následujícího opisu obsahu terminálu:

Traceback (most recent call last):
  File "parse_expression_3.py", line 10, in <module>
    parsed = parse_expression(expression)
  File "/home/ptisnovs/.local/lib/python3.12/site-packages/libcst/_parser/entrypoints.py", line 160, in parse_expression
    result = _parse(
  File "/home/ptisnovs/.local/lib/python3.12/site-packages/libcst/_parser/entrypoints.py", line 55, in _parse
    return parse(source_str)
libcst._exceptions.ParserSyntaxError: Syntax Error @ 1:1.
parser error: error at 1:1: expected one of *, +, -, ..., AWAIT, False, NAME, NUMBER, None, True, lambda, not, ~
 
 6 * 7
^

10. Výraz obalený závorkami

Celý výraz může být v Pythonu obalený závorkami. V takovém případě závorky nemají syntaktický význam, ovšem opět platí, že musí být zachovány, aby bylo možné provést rekonstrukci původního zdrojového kódu. Vyzkoušejme si tedy, jakým způsobem jsou tyto závorky reprezentovány v CST:

#!/usr/bin/python
# vim: set fileencoding=utf-8
 
from libcst import parse_expression
from libcst.tool import dump
 
 
expression = "(6*7)"
 
parsed = parse_expression(expression)
print("Parsed:")
print(parsed)
 
print()
 
dumped = dump(parsed)
print("Dumped:")
print(dumped)

Z výpisu stromu je patrné, že informace o závorkách jsou uloženy v atributech nazvaných lpar a rpar. Tyto atributy v našem případě obsahují informace o typu závorek a případně i informace o mezerách mezi závorkami a výrazem (zde již jsou mezery povoleny):

Parsed:
BinaryOperation(
    left=Integer(
        value='6',
        lpar=[],
        rpar=[],
    ),
    operator=Multiply(
        whitespace_before=SimpleWhitespace(
            value='',
        ),
        whitespace_after=SimpleWhitespace(
            value='',
        ),
    ),
    right=Integer(
        value='7',
        lpar=[],
        rpar=[],
    ),
    lpar=[
        LeftParen(
            whitespace_after=SimpleWhitespace(
                value='',
            ),
        ),
    ],
    rpar=[
        RightParen(
            whitespace_before=SimpleWhitespace(
                value='',
            ),
        ),
    ],
)
 
Dumped:
BinaryOperation(
  left=Integer(
    value='6',
  ),
  operator=Multiply(),
  right=Integer(
    value='7',
  ),
  lpar=[
    LeftParen(),
  ],
  rpar=[
    RightParen(),
  ],
)

11. Strom pro složitější výraz s několika operátory

Knihovna LibCST pochopitelně dokáže zparsovat prakticky libovolně složitý výraz a vytvořit z něj strom, který původní výraz plnohodnotně reprezentuje. Ukažme si to na příkladu výrazu (1+2)*3/2**4, v němž jsou použity operátory s různou prioritou i asociativitou a navíc i kulaté závorky, které mění prioritu operací:

#!/usr/bin/python
# vim: set fileencoding=utf-8
 
from libcst import parse_expression
from libcst.tool import dump
 
 
expression = "(1+2)*3/2**4"
 
parsed = parse_expression(expression)
print("Parsed:")
print(parsed)
 
print()
 
dumped = dump(parsed)
print("Dumped:")
print(dumped)

Výsledný strom již obsahuje větší množství poduzlů, což je ostatně jen pochopitelné:

Parsed:
BinaryOperation(
    left=BinaryOperation(
        left=BinaryOperation(
            left=Integer(
                value='1',
                lpar=[],
                rpar=[],
            ),
            operator=Add(
                whitespace_before=SimpleWhitespace(
                    value='',
                ),
                whitespace_after=SimpleWhitespace(
                    value='',
                ),
            ),
            right=Integer(
                value='2',
                lpar=[],
                rpar=[],
            ),
            lpar=[
                LeftParen(
                    whitespace_after=SimpleWhitespace(
                        value='',
                    ),
                ),
            ],
            rpar=[
                RightParen(
                    whitespace_before=SimpleWhitespace(
                        value='',
                    ),
                ),
            ],
        ),
        operator=Multiply(
            whitespace_before=SimpleWhitespace(
                value='',
            ),
            whitespace_after=SimpleWhitespace(
                value='',
            ),
        ),
        right=Integer(
            value='3',
            lpar=[],
            rpar=[],
        ),
        lpar=[],
        rpar=[],
    ),
    operator=Divide(
        whitespace_before=SimpleWhitespace(
            value='',
        ),
        whitespace_after=SimpleWhitespace(
            value='',
        ),
    ),
    right=BinaryOperation(
        left=Integer(
            value='2',
            lpar=[],
            rpar=[],
        ),
        operator=Power(
            whitespace_before=SimpleWhitespace(
                value='',
            ),
            whitespace_after=SimpleWhitespace(
                value='',
            ),
        ),
        right=Integer(
            value='4',
            lpar=[],
            rpar=[],
        ),
        lpar=[],
        rpar=[],
    ),
    lpar=[],
    rpar=[],
)
 
Dumped:
BinaryOperation(
  left=BinaryOperation(
    left=BinaryOperation(
      left=Integer(
        value='1',
      ),
      operator=Add(),
      right=Integer(
        value='2',
      ),
      lpar=[
        LeftParen(),
      ],
      rpar=[
        RightParen(),
      ],
    ),
    operator=Multiply(),
    right=Integer(
      value='3',
    ),
  ),
  operator=Divide(),
  right=BinaryOperation(
    left=Integer(
      value='2',
    ),
    operator=Power(),
    right=Integer(
      value='4',
    ),
  ),
)

12. Parsing celého modulu

Prozatím jsme pro parsing konstant a výrazů používali funkci libcst.parse_expression. Ovšem v případě, že se parsují větší celky kódu, které mohou obsahovat další metainformace atd., se namísto této funkce může použít funkce nazvaná libcst.parse_module. Výsledný strom přitom bude odlišný, i když se bude ve skutečnosti parsovat naprosto stejný výraz. Ostatně si to můžeme velmi snadno ověřit:

#!/usr/bin/python
# vim: set fileencoding=utf-8
 
from libcst import parse_module
from libcst.tool import dump
 
 
expression = "1 + 2"
 
parsed = parse_module(expression)
print("Parsed:")
print(parsed)
 
print()
 
dumped = dump(parsed)
print("Dumped:")
print(dumped)
 
print()

Výsledkem bude strom reprezentující celý modul, tedy jeho tělo, které obsahuje řádky kódu atd. Podívejme se na výsledek, z něhož je patrné, že je celý modul reprezentován uzlem typu Module. Navíc jsou formou atributů přidány metainformace o modulu:

Parsed:
Module(
    body=[
        SimpleStatementLine(
            body=[
                Expr(
                    value=BinaryOperation(
                        left=Integer(
                            value='1',
                            lpar=[],
                            rpar=[],
                        ),
                        operator=Add(
                            whitespace_before=SimpleWhitespace(
                                value=' ',
                            ),
                            whitespace_after=SimpleWhitespace(
                                value=' ',
                            ),
                        ),
                        right=Integer(
                            value='2',
                            lpar=[],
                            rpar=[],
                        ),
                        lpar=[],
                        rpar=[],
                    ),
                    semicolon=MaybeSentinel.DEFAULT,
                ),
            ],
            leading_lines=[],
            trailing_whitespace=TrailingWhitespace(
                whitespace=SimpleWhitespace(
                    value='',
                ),
                comment=None,
                newline=Newline(
                    value=None,
                ),
            ),
        ),
    ],
    header=[],
    footer=[],
    encoding='utf-8',
    default_indent='    ',
    default_newline='\n',
    has_trailing_newline=False,
)
 
Dumped:
Module(
  body=[
    SimpleStatementLine(
      body=[
        Expr(
          value=BinaryOperation(
            left=Integer(
              value='1',
            ),
            operator=Add(),
            right=Integer(
              value='2',
            ),
          ),
        ),
      ],
    ),
  ],
)

13. Ukázky parsingu dalších jednoduchých modulů

Podívejme se na příklad parsingu dalších jednoduchých modulů. Začneme modulem, který obsahuje pouze výraz, ovšem s různým počtem mezer mezi operandem a operátorem. I tyto mezery pochopitelně musí zůstat zachovány v CST, aby se z něho dal zpětně vytvořit původní zdrojový kód:

#!/usr/bin/python
# vim: set fileencoding=utf-8
 
from libcst import parse_module
from libcst.tool import dump
 
 
expression = "1  + 2"
 
parsed = parse_module(expression)
print("Parsed:")
print(parsed)
 
print()
 
dumped = dump(parsed)
print("Dumped:")
print(dumped)
 
print()
 
code = parsed.code
print("Code:")
print(code)

Ve výsledném CST se zaměřte především na atributy whitespace_before a whitespace_after v uzlu typu Add. A opět si povšimněte, že se na konci vypsal i původní zdrojový kód (včetně všech mezer atd.):

Parsed:
Module(
    body=[
        SimpleStatementLine(
            body=[
                Expr(
                    value=BinaryOperation(
                        left=Integer(
                            value='1',
                            lpar=[],
                            rpar=[],
                        ),
                        operator=Add(
                            whitespace_before=SimpleWhitespace(
                                value='  ',
                            ),
                            whitespace_after=SimpleWhitespace(
                                value=' ',
                            ),
                        ),
                        right=Integer(
                            value='2',
                            lpar=[],
                            rpar=[],
                        ),
                        lpar=[],
                        rpar=[],
                    ),
                    semicolon=MaybeSentinel.DEFAULT,
                ),
            ],
            leading_lines=[],
            trailing_whitespace=TrailingWhitespace(
                whitespace=SimpleWhitespace(
                    value='',
                ),
                comment=None,
                newline=Newline(
                    value=None,
                ),
            ),
        ),
    ],
    header=[],
    footer=[],
    encoding='utf-8',
    default_indent='    ',
    default_newline='\n',
    has_trailing_newline=False,
)
 
Dumped:
Module(
  body=[
    SimpleStatementLine(
      body=[
        Expr(
          value=BinaryOperation(
            left=Integer(
              value='1',
            ),
            operator=Add(),
            right=Integer(
              value='2',
            ),
          ),
        ),
      ],
    ),
  ],
)
 
Code:
1  + 2

Dále se podívejme na modul s logickým výrazem:

#!/usr/bin/python
# vim: set fileencoding=utf-8
 
from libcst import parse_module
from libcst.tool import dump
 
 
expression = "True or False"
 
parsed = parse_module(expression)
print("Parsed:")
print(parsed)
 
print()
 
dumped = dump(parsed)
print("Dumped:")
print(dumped)
 
print()
 
code = parsed.code
print("Code:")
print(code)

Ve výsledném stromu nalezneme uzel typu BooleanOperation s poduzlem Or a pochopitelně i poduzly obsahujícími oba operandy:

Parsed:
Module(
    body=[
        SimpleStatementLine(
            body=[
                Expr(
                    value=BooleanOperation(
                        left=Name(
                            value='True',
                            lpar=[],
                            rpar=[],
                        ),
                        operator=Or(
                            whitespace_before=SimpleWhitespace(
                                value=' ',
                            ),
                            whitespace_after=SimpleWhitespace(
                                value=' ',
                            ),
                        ),
                        right=Name(
                            value='False',
                            lpar=[],
                            rpar=[],
                        ),
                        lpar=[],
                        rpar=[],
                    ),
                    semicolon=MaybeSentinel.DEFAULT,
                ),
            ],
            leading_lines=[],
            trailing_whitespace=TrailingWhitespace(
                whitespace=SimpleWhitespace(
                    value='',
                ),
                comment=None,
                newline=Newline(
                    value=None,
                ),
            ),
        ),
    ],
    header=[],
    footer=[],
    encoding='utf-8',
    default_indent='    ',
    default_newline='\n',
    has_trailing_newline=False,
)
 
Dumped:
Module(
  body=[
    SimpleStatementLine(
      body=[
        Expr(
          value=BooleanOperation(
            left=Name(
              value='True',
            ),
            operator=Or(),
            right=Name(
              value='False',
            ),
          ),
        ),
      ],
    ),
  ],
)
 
Code:
True or False

14. Modul s definicí funkce

Pouze pro úplnost (k tomuto tématu se totiž ještě vrátíme) si ukažme, jakým způsobem lze naparsovat modul obsahující definici jedné funkce (s dvojicí parametrů). Pro jednoduchost tato funkce neobsahuje typové informace, protože i ty se pochopitelně v CST musí zachovat:

#!/usr/bin/python
# vim: set fileencoding=utf-8
 
from libcst import parse_module
from libcst.tool import dump
 
 
module = """
def add(x, y):
    return x + y
"""
 
parsed = parse_module(module)
print("Parsed:")
print(parsed)
 
print()
 
dumped = dump(parsed)
print("Dumped:")
print(dumped)
 
print()
 
code = parsed.code
print("Code:")
print(code)

Výsledkem je již poměrně rozsáhlý strom, jehož stručná verze je však stále dobře čitelná. Povšimněte si toho, že u funkce je uloženo jak její tělo, tak i podrobné informace o parametrech atd. A až do zdrojového kódu přidáme typové informace, nalezneme v CST stromu i tyto atributy:

Parsed:
Module(
    body=[
        FunctionDef(
            name=Name(
                value='add',
                lpar=[],
                rpar=[],
            ),
            params=Parameters(
                params=[
                    Param(
                        name=Name(
                            value='x',
                            lpar=[],
                            rpar=[],
                        ),
                        annotation=None,
                        equal=MaybeSentinel.DEFAULT,
                        default=None,
                        comma=Comma(
                            whitespace_before=SimpleWhitespace(
                                value='',
                            ),
                            whitespace_after=SimpleWhitespace(
                                value=' ',
                            ),
                        ),
                        star='',
                        whitespace_after_star=SimpleWhitespace(
                            value='',
                        ),
                        whitespace_after_param=SimpleWhitespace(
                            value='',
                        ),
                    ),
                    Param(
                        name=Name(
                            value='y',
                            lpar=[],
                            rpar=[],
                        ),
                        annotation=None,
                        equal=MaybeSentinel.DEFAULT,
                        default=None,
                        comma=MaybeSentinel.DEFAULT,
                        star='',
                        whitespace_after_star=SimpleWhitespace(
                            value='',
                        ),
                        whitespace_after_param=SimpleWhitespace(
                            value='',
                        ),
                    ),
                ],
                star_arg=MaybeSentinel.DEFAULT,
                kwonly_params=[],
                star_kwarg=None,
                posonly_params=[],
                posonly_ind=MaybeSentinel.DEFAULT,
            ),
            body=IndentedBlock(
                body=[
                    SimpleStatementLine(
                        body=[
                            Return(
                                value=BinaryOperation(
                                    left=Name(
                                        value='x',
                                        lpar=[],
                                        rpar=[],
                                    ),
                                    operator=Add(
                                        whitespace_before=SimpleWhitespace(
                                            value=' ',
                                        ),
                                        whitespace_after=SimpleWhitespace(
                                            value=' ',
                                        ),
                                    ),
                                    right=Name(
                                        value='y',
                                        lpar=[],
                                        rpar=[],
                                    ),
                                    lpar=[],
                                    rpar=[],
                                ),
                                whitespace_after_return=SimpleWhitespace(
                                    value=' ',
                                ),
                                semicolon=MaybeSentinel.DEFAULT,
                            ),
                        ],
                        leading_lines=[],
                        trailing_whitespace=TrailingWhitespace(
                            whitespace=SimpleWhitespace(
                                value='',
                            ),
                            comment=None,
                            newline=Newline(
                                value=None,
                            ),
                        ),
                    ),
                ],
                header=TrailingWhitespace(
                    whitespace=SimpleWhitespace(
                        value='',
                    ),
                    comment=None,
                    newline=Newline(
                        value=None,
                    ),
                ),
                indent=None,
                footer=[],
            ),
            decorators=[],
            returns=None,
            asynchronous=None,
            leading_lines=[],
            lines_after_decorators=[],
            whitespace_after_def=SimpleWhitespace(
                value=' ',
            ),
            whitespace_after_name=SimpleWhitespace(
                value='',
            ),
            whitespace_before_params=SimpleWhitespace(
                value='',
            ),
            whitespace_before_colon=SimpleWhitespace(
                value='',
            ),
            type_parameters=None,
            whitespace_after_type_parameters=SimpleWhitespace(
                value='',
            ),
        ),
    ],
    header=[
        EmptyLine(
            indent=True,
            whitespace=SimpleWhitespace(
                value='',
            ),
            comment=None,
            newline=Newline(
                value=None,
            ),
        ),
    ],
    footer=[],
    encoding='utf-8',
    default_indent='    ',
    default_newline='\n',
    has_trailing_newline=True,
)
 
Dumped:
Module(
  body=[
    FunctionDef(
      name=Name(
        value='add',
      ),
      params=Parameters(
        params=[
          Param(
            name=Name(
              value='x',
            ),
            star='',
          ),
          Param(
            name=Name(
              value='y',
            ),
            star='',
          ),
        ],
      ),
      body=IndentedBlock(
        body=[
          SimpleStatementLine(
            body=[
              Return(
                value=BinaryOperation(
                  left=Name(
                    value='x',
                  ),
                  operator=Add(),
                  right=Name(
                    value='y',
                  ),
                ),
              ),
            ],
          ),
        ],
      ),
    ),
  ],
)
 
Code:
 
def add(x, y):
    return x + y

15. Realizace průchodu CST

Podívejme se nyní na způsob realizace průchodu CST. Pro tento účel je nutné vytvořit třídu odvozenou od třídy CSTVisitor. Při průchodu CST se budou volat metody nazvané on_visit a on_leave; první metoda při vstupu do uzlu, druhá naopak při jeho opouštění. Důležité přitom je, že metoda on_visit vrací pravdivostní hodnotu, která určuje, zda se má vstoupit do poduzlů daného uzlu či nikoli. V našem velmi jednoduchém příkladu vstup do poduzlů vždy povolíme a tím umožníme průchod celým stromem, až do listů stromu (naproti tomu metoda on_leave nic nevrací):

class Visitor(CSTVisitor):
    def __init__(self):
        ...
        ...
        ...
 
    def on_visit(self, node):
        ...
        ...
        ...
        return True
 
    def on_leave(self, node):
        ...
        ...
        ...

Nejprve zahájíme parsing, a to vždy celého modulu (nestačí parsing výrazu):

constant = "1 + 2 * 3"
 
parsed = parse_module(constant)

Dále zkonstruujeme instanci třídy Visitor a předáme ji do metody parsed.visit. Tím se zahájí průchod jednotlivými uzly CST:

visitor = Visitor()
parsed.visit(visitor)

Výsledek (tedy jednotlivé navštívené uzly) bude vypadat takto:

Visitor init
Visited node:  Module
Visited node:  SimpleStatementLine
Visited node:  Expr
Visited node:  BinaryOperation
Visited node:  Integer
Visited node:  Add
Visited node:  SimpleWhitespace
Visited node:  SimpleWhitespace
Visited node:  BinaryOperation
Visited node:  Integer
Visited node:  Multiply
Visited node:  SimpleWhitespace
Visited node:  SimpleWhitespace
Visited node:  Integer
Visited node:  TrailingWhitespace
Visited node:  SimpleWhitespace
Visited node:  Newline

Úplný zdrojový kód tohoto demonstračního příkladu vypadá následovně:

#!/usr/bin/python
# vim: set fileencoding=utf-8
 
from libcst import parse_module, CSTVisitor
from libcst.tool import dump
 
 
class Visitor(CSTVisitor):
    def __init__(self):
        print("Visitor init")
 
    def on_visit(self, node):
        print("Visited node: ", node.__class__.__name__)
        return True
 
    def on_leave(self, node):
        pass
 
 
constant = "1 + 2 * 3"
 
parsed = parse_module(constant)
visitor = Visitor()
parsed.visit(visitor)

16. Výpis uzlů stromu tak, aby byla viditelná jeho struktura

V demonstračním příkladu popsaném v předchozí kapitole byly jednotlivé uzly navštívené při průchodu stromem vypsány pod sebou bez vizuálního zvýraznění struktury stromu (tedy na jaké úrovni stromu se uzel nachází). Ovšem poměrně snadno si můžeme výpis upravit tak, aby se zvýraznila struktura stromu. Postačuje si pamatovat aktuální úroveň (začínáme v kořenu, tedy na nulté úrovni) a při každém volání metody on_visit se úroveň zvýší a naopak při volání metody on_leave se úroveň sníží. Před jméno každého uzlu potom vložíme tolik mezer, aby to odpovídalo úrovni uložení uzlu ve stromu:

#!/usr/bin/python
# vim: set fileencoding=utf-8
 
from libcst import parse_module, CSTVisitor
from libcst.tool import dump
 
 
class Visitor(CSTVisitor):
    def __init__(self):
        self.nest_level = 0
 
    def on_visit(self, node):
        indent = " " * self.nest_level * 2
        print(indent, node.__class__.__name__)
        self.nest_level += 1
        return True
 
    def on_leave(self, node):
        self.nest_level -= 1
 
 
constant = "1 + 2 * 3"
 
parsed = parse_module(constant)
visitor = Visitor()
parsed.visit(visitor)

Výsledek, který se vypíše na terminál, již vypadá poměrně čitelně:

 Module
   SimpleStatementLine
     Expr
       BinaryOperation
         Integer
         Add
           SimpleWhitespace
           SimpleWhitespace
         BinaryOperation
           Integer
           Multiply
             SimpleWhitespace
             SimpleWhitespace
           Integer
     TrailingWhitespace
       SimpleWhitespace
       Newline

17. Získání dalších informací o uzlech známých typů

Každý uzel, kterým třída typu Visitor prochází, je reprezentován objektem nějakého typu (tedy například operátor je reprezentován jiným typem než řetězec apod.). A tento objekt většinou – podle typu uzlu – obsahuje i další atributy, s nimiž je možné dále pracovat a získávat tak například podrobnější informace o tom, jakou část programového kódu tento uzel reprezentuje.

V dalším demonstračním příkladu je ukázáno zpracování uzlů typu BinaryOperation (libovolný binární operátor, resp. výraz s tímto operátorem), Integer (celočíselná konstanta), Add (operace součtu) a Multiply (operace součinu). U binárního operátoru je ukázáno zjištění konkrétní třídy (klasický Pythonní přístup), u celočíselné konstanty je přečtena a vypsána hodnota této konstanty a u součtu a součinu se vypíšou pouze znaky „+“ resp. „*“:

#!/usr/bin/python
# vim: set fileencoding=utf-8
 
from libcst import parse_module, CSTVisitor
from libcst import BinaryOperation, Integer, Add, Multiply
from libcst.tool import dump
 
 
class Visitor(CSTVisitor):
    def __init__(self):
        self.nest_level = 0
 
    def on_visit(self, node):
        indent = " " * self.nest_level * 2
        info = node.__class__.__name__
 
        if isinstance(node, BinaryOperation):
            info = "Binary operation: " + node.operator.__class__.__name__
 
        if isinstance(node, Integer):
            info = node.value
 
        if isinstance(node, Add):
            info = "+"
 
        if isinstance(node, Multiply):
            info = "*"
 
        print(indent, info)
 
        self.nest_level += 1
        return True
 
    def on_leave(self, node):
        self.nest_level -= 1
 
 
constant = "1 + 2 * 3"
 
parsed = parse_module(constant)
visitor = Visitor()
parsed.visit(visitor)

Výsledkem je již poměrně čitelná reprezentace kódu s využitím stromové struktury:

 Module
   SimpleStatementLine
     Expr
       Binary operation: Add
         1
         +
           SimpleWhitespace
           SimpleWhitespace
         Binary operation: Multiply
           2
           *
             SimpleWhitespace
             SimpleWhitespace
           3
     TrailingWhitespace
       SimpleWhitespace
       Newline

18. Různé zpracování uzlů podle jejich typů

Samozřejmě nám ovšem nic nebrání v tom, abychom nějaké uzly sice při průchodu stromem zpracovali, ale vůbec je nevypsali. Příkladem může být „ignorování“ uzlů typu SimpleWhitespace. Informace o těchto uzlech se ve výsledku neobjeví, protože pokud na tento uzel narazíme, je metoda on_visit ihned ukončena:

#!/usr/bin/python
# vim: set fileencoding=utf-8
 
from libcst import parse_module, CSTVisitor
from libcst import BinaryOperation, Integer, Add, Multiply
from libcst import SimpleWhitespace
from libcst.tool import dump
 
 
class Visitor(CSTVisitor):
    def __init__(self):
        self.nest_level = 0
 
    def on_visit(self, node):
        indent = " " * self.nest_level * 2
        info = node.__class__.__name__
        self.nest_level += 1
 
        if isinstance(node, SimpleWhitespace):
            return True
 
        if isinstance(node, BinaryOperation):
            info = "Binary operation: " + node.operator.__class__.__name__
 
        if isinstance(node, Integer):
            info = node.value
 
        if isinstance(node, Add):
            info = "+"
 
        if isinstance(node, Multiply):
            info = "*"
 
        print(indent, info)
 
        return True
 
    def on_leave(self, node):
        self.nest_level -= 1
 
 
constant = "1 + 2 * 3"
 
parsed = parse_module(constant)
visitor = Visitor()
parsed.visit(visitor)

Výsledek bude vypadat takto:

 Module
   SimpleStatementLine
     Expr
       Binary operation: Add
         1
         +
         Binary operation: Multiply
           2
           *
           3
     TrailingWhitespace
       Newline

Popř. můžeme zcela odstranit všechny uzly, které se týkají nových řádků či mezer v programovém kódu:

#!/usr/bin/python
# vim: set fileencoding=utf-8
 
from libcst import parse_module, CSTVisitor
from libcst import BinaryOperation, Integer, Add, Multiply
from libcst import SimpleWhitespace, TrailingWhitespace, SimpleStatementLine, Newline
from libcst.tool import dump
 
 
class Visitor(CSTVisitor):
    def __init__(self):
        self.nest_level = 0
 
    def on_visit(self, node):
        indent = " " * self.nest_level * 2
        info = node.__class__.__name__
        self.nest_level += 1
 
        if isinstance(node, SimpleWhitespace) or \
           isinstance(node, TrailingWhitespace) or \
           isinstance(node, SimpleStatementLine) or \
           isinstance(node, Newline):
            return True
 
        if isinstance(node, BinaryOperation):
            info = "Binary operation: " + node.operator.__class__.__name__
 
        if isinstance(node, Integer):
            info = node.value
 
        if isinstance(node, Add):
            info = "+"
 
        if isinstance(node, Multiply):
            info = "*"
 
        print(indent, info)
 
        return True
 
    def on_leave(self, node):
        self.nest_level -= 1
 
 
constant = "1 + 2 * 3 + 4 * 5"
 
parsed = parse_module(constant)
visitor = Visitor()
parsed.visit(visitor)

Čitelný výsledek:

 Module
     Expr
       Binary operation: Add
         Binary operation: Add
           1
           +
           Binary operation: Multiply
             2
             *
             3
         +
         Binary operation: Multiply
           4
           *
           5

19. 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 a knihovnu libcst byly uloženy do Git repositáře dostupného na adrese https://github.com/tisnik/most-popular-python-libs:

20. Odkazy na Internetu

1. Lexikální a syntaktická analýza zdrojových kódů programovacího jazyka Python
   https://www.root.cz/clanky/lexikalni-a-syntakticka-analyza-zdrojovych-kodu-programovaciho-jazyka-python/
2. Lexikální a syntaktická analýza zdrojových kódů programovacího jazyka Python (2.část)
   https://www.root.cz/clanky/lexikalni-a-syntakticka-analyza-zdrojovych-kodu-programovaciho-jazyka-python-2-cast/
3. Lexikální a syntaktická analýza zdrojových kódů programovacího jazyka Python (3.část)
   https://www.root.cz/clanky/lexikalni-a-syntakticka-analyza-zdrojovych-kodu-programovaciho-jazyka-python-3-cast/
4. Lexikální a syntaktická analýza zdrojových kódů jazyka Python (4.část)
   https://www.root.cz/clanky/lexikalni-a-syntakticka-analyza-zdrojovych-kodu-jazyka-python-4-cast/
5. LibCST – dokumentace
   https://libcst.readthedoc­s.io/en/latest/index.html
6. libCST na PyPi
   https://pypi.org/project/libcst/
7. libCST na GitHubu
   https://github.com/Instagram/LibCST
8. Inside The Python Virtual Machine
   https://leanpub.com/insidet­hepythonvirtualmachine
9. module-py_compile
   https://docs.python.org/3­.8/library/py_compile.html
10. Given a python .pyc file, is there a tool that let me view the bytecode?
    https://stackoverflow.com/qu­estions/11141387/given-a-python-pyc-file-is-there-a-tool-that-let-me-view-the-bytecode
11. The structure of .pyc files
    https://nedbatchelder.com/blog/200804/the_str­ucture_of_pyc_files.html
12. Python Bytecode: Fun With Dis
    http://akaptur.github.io/blog/2013/08/14/pyt­hon-bytecode-fun-with-dis/
13. Python's Innards: Hello, ceval.c!
    http://tech.blog.aknin.na­me/category/my-projects/pythons-innards/
14. Byterun
    https://github.com/nedbat/byterun
15. Python Byte Code Instructions
    http://document.ihg.uni-duisburg.de/Documentation/Pyt­hon/lib/node56.html
16. Python Byte Code Instructions
    https://docs.python.org/3­.2/library/dis.html#python-bytecode-instructions
17. dis – Python module
    https://docs.python.org/2/li­brary/dis.html
18. Comparison of Python virtual machines
    http://polishlinux.org/ap­ps/cli/comparison-of-python-virtual-machines/
19. O-code
    http://en.wikipedia.org/wiki/O-code_machine
20. Abstract syntax tree
    https://en.wikipedia.org/wi­ki/Abstract_syntax_tree
21. Lexical analysis
    https://en.wikipedia.org/wi­ki/Lexical_analysis
22. Parser
    https://en.wikipedia.org/wi­ki/Parsing#Parser
23. Parse tree
    https://en.wikipedia.org/wi­ki/Parse_tree
24. Derivační strom
    https://cs.wikipedia.org/wi­ki/Deriva%C4%8Dn%C3%AD_strom
25. Python doc: ast — Abstract Syntax Trees
    https://docs.python.org/3/li­brary/ast.html
26. Python doc: tokenize — Tokenizer for Python source
    https://docs.python.org/3/li­brary/tokenize.html
27. SymbolTable
    https://docs.python.org/3­.8/library/symtable.html
28. 5 Amazing Python AST Module Examples
    https://www.pythonpool.com/python-ast/
29. Intro to Python ast Module
    https://medium.com/@wshanshan/intro-to-python-ast-module-bbd22cd505f7
30. Golang AST Package
    https://golangdocs.com/golang-ast-package
31. AP8, IN8 Regulární jazyky
    http://statnice.dqd.cz/home:inf:ap8
32. AP9, IN9 Konečné automaty
    http://statnice.dqd.cz/home:inf:ap9
33. AP10, IN10 Bezkontextové jazyky
    http://statnice.dqd.cz/home:inf:ap10
34. AP11, IN11 Zásobníkové automaty, Syntaktická analýza
    http://statnice.dqd.cz/home:inf:ap11
35. Introduction to YACC
    https://www.geeksforgeeks­.org/introduction-to-yacc/
36. Introduction of Lexical Analysis
    https://www.geeksforgeeks­.org/introduction-of-lexical-analysis/?ref=lbp
37. Využití knihovny Pygments (nejenom) pro obarvení zdrojových kódů
    https://www.root.cz/clanky/vyuziti-knihovny-pygments-nejenom-pro-obarveni-zdrojovych-kodu/
38. Pygments – Python syntax highlighter
    http://pygments.org/
39. Pygments (dokumentace)
    http://pygments.org/docs/
40. Write your own filter
    http://pygments.org/docs/fil­terdevelopment/
41. Write your own lexer
    http://pygments.org/docs/le­xerdevelopment/
42. Write your own formatter
    http://pygments.org/docs/for­matterdevelopment/
43. Jazyky podporované knihovnou Pygments
    http://pygments.org/languages/
44. Pygments FAQ
    http://pygments.org/faq/
45. Compiler Construction/Lexical analysis
    https://en.wikibooks.org/wi­ki/Compiler_Construction/Le­xical_analysis
46. Compiler Design – Lexical Analysis
    https://www.tutorialspoin­t.com/compiler_design/com­piler_design_lexical_analy­sis.htm
47. Lexical Analysis – An Intro
    https://www.scribd.com/do­cument/383765692/Lexical-Analysis
48. Python AST Visualizer
    https://github.com/pombredanne/python-ast-visualizer
49. What is an Abstract Syntax Tree
    https://blog.bitsrc.io/what-is-an-abstract-syntax-tree-7502b71bde27
50. Why is AST so important
    https://medium.com/@obernar­dovieira/why-is-ast-so-important-b1e7d6c29260
51. Emily Morehouse-Valcarcel – The AST and Me – PyCon 2018
    https://www.youtube.com/wat­ch?v=XhWvz4dK4ng
52. Python AST Parsing and Custom Linting
    https://www.youtube.com/wat­ch?v=OjPT15y2EpE
53. Chase Stevens – Exploring the Python AST Ecosystem
    https://www.youtube.com/wat­ch?v=Yq3wTWkoaYY
54. Full Grammar specification
    https://docs.python.org/3/re­ference/grammar.html