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

Obsah

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

2. Krátké zopakování z minula – návrhový vzor Visitor

3. Složitější zdrojový kód, jehož AST budeme analyzovat

4. Průchod abstraktním syntaktickým stromem složitějšího programového kódu

5. Filtrace uzlů v AST – výpis definic všech funkcí a metod

6. Informace o modulu, definovaných třídách i definovaných funkcích a metodách

7. Příklad dalších typů uzlů AST: hlavička programové smyčky for

8. Uzly AST využívané ve výrazech

9. Realizace průchodu stromem pro zpracování výrazu

10. Tabulky symbolů

11. Tabulka symbolů pro celý skript

12. Transformace AST do bajtkódu

13. Bajtkód virtuálního stroje Pythonu

14. Zásobníkové vs. registrové virtuální stroje

15. Příklady funkcí přeložených do bajtkódu Pythonu

16. Dekompilace bajtkódu pro jednoduchý výraz s konstantami

17. Dekompilace bajtkódu složitějšího příkazu

18. Příloha: definice gramatiky programovacího jazyka Python

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

20. Odkazy na Internetu

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

V předchozích dvou částech článku o lexikální a syntaktické analýze zdrojových kódů napsaných v Pythonu [1] [2] jsme se seznámili se základními vlastnostmi standardních knihoven nazvaných tokenize a ast. Připomeňme si, že knihovna tokenize nám zpřístupňuje takzvaný lexer (někdy nazývaný právě i tokenizer), zatímco knihovna ast programátorům umožňuje transformovat buď přímo zdrojový kód nebo sekvenci tokenů do formy abstraktního syntaktického stromu (AST). Dnes si ukážeme, jak se AST překládá do bajtkódu (s mezikrokem spočívajícím ve vytvoření tabulky symbolů) i způsob zobrazení bajtkódu v čitelné podobě.

Cesta od zdrojového kódu k bajtkódu se tedy skládá z několika transformací:

1. Zdrojový kód (tedy vlastně 2D struktura) je transformován na sekvenci tokenů
2. Sekvence tokenů (lineární struktura) je transformována do formy stromu (AST)
3. AST je optimalizován (transformace strom-→strom)
4. AST je přeložen do bajtkódu (lineární sekvence instrukcí)

2. Krátké zopakování z minula – návrhový vzor Visitor

V předchozím článku o lexikální a syntaktické analýze zdrojových kódů napsaných v Pythonu jsme si popsali způsob použití návrhového vzoru „visitor“. Ten se používá mj. i pro realizaci průchodu abstraktním syntaktickým stromem za účelem jeho analýzy, provádění různých manipulací (optimalizací) atd. Připomeňme si ve stručnosti, jak lze průchod stromem realizovat. Konkrétně se bude jednat o průchod všemi uzly AST, bez ohledu na typ uzlů:

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 po spuštění tohoto skriptu bude zobrazení informace o devíti uzlech AST:

$ 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>

Výhodnější bude, když vhodným způsobem zvýrazníme úroveň jednotlivých uzlů v rámci AST, od uzlu kořenového po listy stromu:

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>

3. Složitější zdrojový kód, jehož AST budeme analyzovat

V rámci navazujících kapitol budeme analyzovat AST tohoto skriptu. Jedná se o skript, v němž je deklarována třída s několika metodami a taktéž jsou zde deklarovány běžné funkce (skript je přitom spustitelný, a to za předpokladu, že máte nainstalovánu knihovnu Pygame:

#!/usr/bin/python
# vim: set fileencoding=utf-8
 
# Demonstrační příklady využívající knihovnu Pygame
 
# Příklad číslo 22: použití spritů, pohyblivý sprite
 
import pygame
import sys
import os
import math
 
# Nutno importovat kvůli konstantám QUIT atd.
from pygame.locals import *
 
# Velikost okna aplikace
WIDTH = 320
HEIGHT = 240
 
 
# Třída představující sprite zobrazený jako jednobarevný čtverec.
class BlockySprite(pygame.sprite.Sprite):
    # Konstruktor
    def __init__(self, color, size, x, y):
        # Nejprve je nutné zavolat konstruktor předka,
        # tj. konstruktor třídy pygame.sprite.Sprite:
        pygame.sprite.Sprite.__init__(self)
 
        # Vytvoření obrázku představujícího vizuální obraz spritu:
        self.image = pygame.Surface([size, size])
        self.image.fill(color)
 
        # Vytvoření obalového obdélníku
        # (velikost se získá z rozměru obrázku)
        self.rect = self.image.get_rect()
        self.rect.x = x
        self.rect.y = y
 
        # Počáteční rychlost spritu
        self.speed_x = 0
        self.speed_y = 0
 
    # Nastavení barvy spritu, který kolidoval s hráčem
    def yellowColor(self):
        self.image.fill(YELLOW)
 
    # Nastavení barvy spritu, který nekolidoval s hráčem
    def grayColor(self):
        self.image.fill(GRAY)
 
 
# Inicializace knihovny Pygame
pygame.init()
 
clock = pygame.time.Clock()
 
# Vytvoření okna pro vykreslování
display = pygame.display.set_mode([WIDTH, HEIGHT])
 
# Nastavení titulku okna
pygame.display.set_caption("Pygame test #22")
 
# Konstanty s n-ticemi představujícími základní barvy
BLACK = (0, 0, 0)
RED = (255, 0, 0)
GRAY = (128, 128, 128)
YELLOW = (255, 255, 0)
 
# Objekt sdružující všechny sprity
all_sprites = pygame.sprite.Group()
# Objekt sdružující všechny sprity kromě hráče
all_sprites_but_player = pygame.sprite.Group()
 
# Vytvoření několika typů spritů
#                    barva  x   y velikost
wall1 = BlockySprite(GRAY, 50, 10, 10)
wall2 = BlockySprite(GRAY, 15, 100, 100)
wall3 = BlockySprite(GRAY, 15, 100, 150)
wall4 = BlockySprite(GRAY, 15, 200, 100)
wall5 = BlockySprite(GRAY, 15, 200, 150)
wall6 = BlockySprite(GRAY, 15, 150, 100)
wall7 = BlockySprite(GRAY, 15, 150, 150)
player = BlockySprite(RED, 40, WIDTH / 2 - 20, HEIGHT / 2 - 20)
 
# Přidání několika dalších spritů do seznamu
# (jen jeden sprite - ten poslední - bude ve skutečnosti pohyblivý)
all_sprites.add(wall1)
all_sprites.add(wall2)
all_sprites.add(wall3)
all_sprites.add(wall4)
all_sprites.add(wall5)
all_sprites.add(wall6)
all_sprites.add(wall7)
all_sprites.add(player)
 
# Seznam všech nepohyblivých spritů
all_sprites_but_player.add(wall1)
all_sprites_but_player.add(wall2)
all_sprites_but_player.add(wall3)
all_sprites_but_player.add(wall4)
all_sprites_but_player.add(wall5)
all_sprites_but_player.add(wall6)
all_sprites_but_player.add(wall7)
 
 
# Posun všech spritů ve skupině na základě jejich rychlosti
def move_sprites(sprite_group, playground_width, playground_height):
    for sprite in sprite_group:
        # Posun spritu
        sprite.rect.x = sprite.rect.x + sprite.speed_x
        sprite.rect.y = sprite.rect.y + sprite.speed_y
        # Kontrola, zda sprite nenarazil do okrajů okna
        if sprite.rect.x < 0:
            sprite.rect.x = 0
            sprite.speed_x = 0
        if sprite.rect.x + sprite.rect.width > playground_width:
            sprite.rect.x = playground_width - sprite.rect.width
            sprite.speed_x = 0
        if sprite.rect.y < 0:
            sprite.rect.y = 0
            sprite.speed_y = 0
        if sprite.rect.y + sprite.rect.height > playground_height:
            sprite.rect.y = playground_height - sprite.rect.height
            sprite.speed_y = 0
 
 
# Vykreslení celé scény na obrazovku
def draw_scene(display, background_color, sprite_group):
    # Vyplnění plochy okna černou barvou
    display.fill(background_color)
    # Vykreslení celé skupiny spritů do bufferu
    sprite_group.draw(display)
    # Obnovení obsahu obrazovky (překlopení zadního a předního bufferu)
    pygame.display.update()
 
 
# Změna barvy spritu na základě kolize s hráčem
def change_colors(sprite_group, hit_list):
    # Projít všemi sprity ze skupiny, kterou detekovala kolizní funkce
    for sprite in sprite_group:
        if sprite in hit_list:
            sprite.yellowColor()
        else:
            sprite.grayColor()
 
 
# Zjistí kolize spritu se "stěnami" (nepohyblivými sprity)
def check_collisions(player, sprite_group):
    # Vytvoření seznamu spritů, které kolidují s hráčem
    hit_list = pygame.sprite.spritecollide(player, sprite_group, False)
    # Změna barev kolidujících spritů
    change_colors(sprite_group, hit_list)
    collisions = len(hit_list)
    # Přenastavení titulku okna
    caption = "Pygame test #22: collisions " + str(collisions)
    pygame.display.set_caption(caption)
 
 
# Hlavní herní smyčka
while True:
    # Načtení a zpracování všech událostí z fronty
    for event in pygame.event.get():
        if event.type == QUIT:
            pygame.quit()
            sys.exit()
        if event.type == KEYDOWN:
            if event.key == K_ESCAPE:
                pygame.quit()
                sys.exit()
            # Stiskem kurzorových kláves je možné měnit směr pohybu spritu
            elif event.key == pygame.K_LEFT:
                player.speed_x = -3
            elif event.key == pygame.K_RIGHT:
                player.speed_x = +3
            elif event.key == pygame.K_UP:
                player.speed_y = -3
            elif event.key == pygame.K_DOWN:
                player.speed_y = +3
        if event.type == KEYUP:
            # Puštění kurzorových kláves vede k zastavení pohybu spritu
            if event.key == pygame.K_LEFT:
                player.speed_x = 0
            elif event.key == pygame.K_RIGHT:
                player.speed_x = 0
            elif event.key == pygame.K_UP:
                player.speed_y = 0
            elif event.key == pygame.K_DOWN:
                player.speed_y = 0
 
    move_sprites(all_sprites, display.get_width(), display.get_height())
    check_collisions(player, all_sprites_but_player)
    draw_scene(display, BLACK, all_sprites)
    clock.tick(20)
 
# finito

4. Průchod abstraktním syntaktickým stromem složitějšího programového kódu

Složitější program, jako například skript uvedený v předchozí kapitole, je transformován do AST stejným způsobem, jako jednoduchý výraz, což znamená, že i takovým AST je možné procházet. Nevýhodou je, že AST je v tomto případě obrovský a má minimálně stovky (spíše tisíce) uzlů:

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
 
 
with open("sprites.py") as fin:
    code = fin.read()
    tree = ast.parse(code)
    visitor = Visitor()
    visitor.visit(tree)

Výsledek je, jak jsme si již ostatně napsali, obrovský, takže v článku uvedu jen malou část AST:

   <_ast.Module object at 0x7fd31f665b80>
     <_ast.Import object at 0x7fd31f665ca0>
       <_ast.alias object at 0x7fd31f5fedf0>
     <_ast.Import object at 0x7fd31f5feeb0>
       <_ast.alias object at 0x7fd31f5fee80>
     <_ast.Import object at 0x7fd31f5fefd0>
       <_ast.alias object at 0x7fd31f5cf880>
     <_ast.Import object at 0x7fd31f5cf700>
       <_ast.alias object at 0x7fd31f5e8070>
       ...
       ...
       ...
     <_ast.ClassDef object at 0x7fd31f5e82b0>
       <_ast.Attribute object at 0x7fd31f5e8280>
         <_ast.Attribute object at 0x7fd31f5e8340>
           <_ast.Name object at 0x7fd31f5e83a0>
             <_ast.Load object at 0x7fd31f5efa60>
           <_ast.Load object at 0x7fd31f5efa60>
         <_ast.Load object at 0x7fd31f5efa60>
       <_ast.FunctionDef object at 0x7fd31f5e83d0>
         <_ast.arguments object at 0x7fd31f5e8430>
           <_ast.arg object at 0x7fd31f5e84c0>
           <_ast.arg object at 0x7fd31f5e84f0>
           <_ast.arg object at 0x7fd31f5e8520>
           <_ast.arg object at 0x7fd31f5e8550>
           <_ast.arg object at 0x7fd31f5e8580>
       ...
       ...
       ...
       <_ast.Expr object at 0x7fd31f5aceb0>
         <_ast.Call object at 0x7fd31f5acee0>
           <_ast.Attribute object at 0x7fd31f5acd60>
             <_ast.Name object at 0x7fd31f5acf10>
               <_ast.Load object at 0x7fd31f5efa60>
             <_ast.Load object at 0x7fd31f5efa60>
           <_ast.Constant object at 0x7fd31f5acf40>

5. Filtrace uzlů v AST – výpis definic všech funkcí a metod

Předností návrhového vzoru „Visitor“ tak, jak je implementován v knihovně ast, je schopnost filtrovat uzly podle jejich typu. Vše je založeno na gramatice Pythonu (viz osmnáctou kapitolu); podle symbolů v gramatice jsou pojmenovány příslušné metody volané při „návštěvě“ uzlů. Podívejme se na jednoduchý příklad – nalezneme a vypíšeme všechny uzly s definicí funkce popř. metody:

import ast
 
 
class Visitor(ast.NodeVisitor):
    def __init__(self):
        self.nest_level = 0
 
    def visit_FunctionDef(self, node):
        indent = " " * self.nest_level * 2
        print("{}def {}:".format(indent, node.name))
        self.nest_level += 1
        self.generic_visit(node)
        self.nest_level -= 1
 
 
with open("sprites.py") as fin:
    code = fin.read()
    tree = ast.parse(code)
    visitor = Visitor()
    visitor.visit(tree)

Výsledkem budou v tomto případě skutečně jen jména deklarovaných funkcí a metod:

def __init__:
def yellowColor:
def grayColor:
def move_sprites:
def draw_scene:
def change_colors:
def check_collisions:

6. Informace o modulu, definovaných třídách i definovaných funkcích a metodách

Můžeme jít ještě dále a zjistit, jaký modul je v AST reprezentován a jaké zde nalezneme definice tříd. Díky tomu, že se v implementaci třídy Visitor korektně pracuje s odsazením uzlů, snadno rozlišíme i definici metody od definice funkce:

import ast
 
 
class Visitor(ast.NodeVisitor):
    def __init__(self):
        self.nest_level = 0
 
    def visit_Module(self, node):
        indent = " " * self.nest_level * 2
        print("{}module begin:".format(indent, node.__dict__))
        self.nest_level += 1
        self.generic_visit(node)
        self.nest_level -= 1
        print("{}module end".format(indent))
 
    def visit_ClassDef(self, node):
        indent = " " * self.nest_level * 2
        print("{}class {}:".format(indent, node.name))
        self.nest_level += 1
        self.generic_visit(node)
        self.nest_level -= 1
 
    def visit_FunctionDef(self, node):
        indent = " " * self.nest_level * 2
        print("{}def {}:".format(indent, node.name))
        self.nest_level += 1
        self.generic_visit(node)
        self.nest_level -= 1
 
 
with open("sprites.py") as fin:
    code = fin.read()
    tree = ast.parse(code)
    visitor = Visitor()
    visitor.visit(tree)

Z výsledku je patrné, že průchod AST nám dává poměrně dobré informace o struktuře programového kódu (a proto IDE většinou pracují právě s AST a nikoli přímo se zdrojovým kódem):

module begin:
  class BlockySprite:
    def __init__:
    def yellowColor:
    def grayColor:
  def move_sprites:
  def draw_scene:
  def change_colors:
  def check_collisions:
module end

7. Příklad dalších typů uzlů AST: hlavička programové smyčky for

Pro zajímavost se podívejme na to, jaké informace můžeme zjistit o bloku se smyčkou for. I tento blok je v AST reprezentován podstromem, jehož kořenovým uzlem je právě informace o smyčce for:

import ast
 
 
class Visitor(ast.NodeVisitor):
    def __init__(self):
        self.nest_level = 0
 
    def visit_Module(self, node):
        indent = " " * self.nest_level * 2
        print("{}module begin:".format(indent, node.__dict__))
        self.nest_level += 1
        self.generic_visit(node)
        self.nest_level -= 1
        print("{}module end".format(indent))
 
    def visit_ClassDef(self, node):
        indent = " " * self.nest_level * 2
        print("{}class {}:".format(indent, node.name))
        self.nest_level += 1
        self.generic_visit(node)
        self.nest_level -= 1
 
    def visit_For(self, node):
        indent = " " * self.nest_level * 2
        iterator = node.iter
        if type(iterator) == ast.Name:
            iterator = iterator.id
        elif type(iterator) == ast.Call:
            iterator = "call()"
 
        print("{}for {} in {}:".format(indent, node.target.id, iterator))
        self.nest_level += 1
        self.generic_visit(node)
        self.nest_level -= 1
 
    def visit_FunctionDef(self, node):
        indent = " " * self.nest_level * 2
        print("{}def {}:".format(indent, node.name))
        self.nest_level += 1
        self.generic_visit(node)
        self.nest_level -= 1
 
 
with open("sprites.py") as fin:
    code = fin.read()
    tree = ast.parse(code)
    visitor = Visitor()
    visitor.visit(tree)

Výsledek po spuštění skriptu bude vypadat následovně:

module begin:
  class BlockySprite:
    def __init__:
    def yellowColor:
    def grayColor:
  def move_sprites:
    for sprite in sprite_group:
  def draw_scene:
  def change_colors:
    for sprite in sprite_group:
  def check_collisions:
  for event in call():
module end

8. Uzly AST využívané ve výrazech

Nejzajímavější částí AST jsou ty poduzly, které reprezentují nějaké výrazy. Zajímavost spočívá v nutnosti řešení priorit operátorů, závorek atd. Podívejme se nyní na implementaci návrhového vzoru „Visitor“, která umožňuje procházet AST pro výrazy ve formě:

a+2*(1-b/4)+c

Upravený skript, který projde AST vygenerovaným pro daný výraz, může vypadat takto. Vše je opět postaveno na gramatice Pythonu, ovšem samotná realizace je poměrně špatně napsaná (sekvence if-elseif-…):

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)

Výsledkem činnosti tohoto skriptu je následující textová vizualizace AST:

     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

9. Realizace průchodu stromem pro zpracování výrazu

Existuje však i čistěji implementovaná forma průchodu AST, který reprezentuje aritmetické výrazy. Každý operátor totiž má vlastní typ uzlu, což je opět založeno na již několikrát zmíněné gramatice Pythonu. Pro každý operátor tedy můžeme deklarovat vlastní metodu, která je automaticky „navštívena“ při průchodu AST:

import ast
 
 
class Visitor(ast.NodeVisitor):
    def __init__(self):
        self.nest_level = 1
 
    def visit_Constant(self, node):
        indent = " " * self.nest_level * 2
        print("{}Constant: {}".format(indent, node.value))
        self.nest_level += 1
        self.generic_visit(node)
        self.nest_level -= 1
 
    def visit_Name(self, node):
        indent = " " * self.nest_level * 2
        print("{}Variable: {}".format(indent, node.id))
        self.nest_level += 1
        self.generic_visit(node)
        self.nest_level -= 1
 
    def visit_Expr(self, node):
        indent = " " * self.nest_level * 2
        print("{}Expression:".format(indent))
        self.nest_level += 1
        self.generic_visit(node)
        self.nest_level -= 1
 
    def visit_BinOp(self, node):
        indent = " " * self.nest_level * 2
        print("{}Binary operator:".format(indent))
        self.nest_level += 1
        self.generic_visit(node)
        self.nest_level -= 1
 
    def visit_Add(self, node):
        indent = " " * self.nest_level * 2
        print("{}+".format(indent))
        self.nest_level += 1
        self.generic_visit(node)
        self.nest_level -= 1
 
    def visit_Sub(self, node):
        indent = " " * self.nest_level * 2
        print("{}-".format(indent))
        self.nest_level += 1
        self.generic_visit(node)
        self.nest_level -= 1
 
    def visit_Mult(self, node):
        indent = " " * self.nest_level * 2
        print("{}*".format(indent))
        self.nest_level += 1
        self.generic_visit(node)
        self.nest_level -= 1
 
    def visit_Div(self, node):
        indent = " " * self.nest_level * 2
        print("{}/".format(indent))
        self.nest_level += 1
        self.generic_visit(node)
        self.nest_level -= 1
 
 
tree = ast.parse("a+2*(1-b/4)+c")
 
visitor = Visitor()
visitor.visit(tree)

Výsledek bude vypadat prakticky stejně (měl by):

  Expression:
    Binary operator:
      Binary operator:
        Variable: a
        +
        Binary operator:
          Constant: 2
          *
          Binary operator:
            Constant: 1
            -
            Binary operator:
              Variable: b
              /
              Constant: 4
      +
      Variable: c

10. Tabulky symbolů

V rámci procesu překladu do bajtkódu je vytvářena i tabulka symbolů (symbol table). I tuto tabulku je možné získat, a to pochopitelně přímo z Pythonu. Podívejme se na velmi jednoduchý příklad – na tabulku symbolů získanou z výrazu „a+b*c“. Pro tento účel se v Pythonu používá knihovna nazvaná přímočaře symtable, jejíž základní použití je snadné:

import symtable
 
 
t = symtable.symtable("a+b*c", "<string>", "eval")
 
print("Symbol table:", t)
print("Type:", t.get_type())
print("Has children:", t.has_children())
print("Identifiers:", t.get_identifiers())
 
symbols = t.get_symbols()
 
print("\nList of symbols:")
 
for symbol in symbols:
    print(symbol.get_name())

Tento skript po svém spuštění vypíše základní metainformace o tabulce symbolů a následně i jednotlivé symboly, které jsou v této tabulce uloženy:

Symbol table: <SymbolTable for module <string>>
Type: module
Has children: False
Identifiers: dict_keys(['a', 'b', 'c'])
 
List of symbols:
a
b
c

11. Tabulka symbolů pro celý skript

Zajímavější pochopitelně bude získat tabulku symbolů pro složitější programový kód, konkrétně pro skript, který byl uveden ve třetí kapitole. Nepatrně tedy upravíme kód, který tabulku symbolů vytvoří a následně vypíše její metainformace i všechny symboly:

import symtable
 
 
with open("sprites.py") as fin:
    code = fin.read()
    t = symtable.symtable(code, "sprites.py", "exec")
 
print("Symbol table:", t)
print("Type:", t.get_type())
print("Has children:", t.has_children())
print("Identifiers:", t.get_identifiers())
 
symbols = t.get_symbols()
 
print("\nList of symbols:")
 
for symbol in symbols:
    print(symbol.get_name())

Nyní výstup vypadá takto:

Symbol table: <SymbolTable for module sprites.py>
Type: module
Has children: True
Identifiers: dict_keys(['pygame', 'sys', 'os', 'math', 'WIDTH', 'HEIGHT', 'BlockySprite', 'clock', 'display', 'BLACK', 'RED', 'GRAY', 'YELLOW', 'all_sprites', 'all_sprites_but_player', 'wall1', 'wall2', 'wall3', 'wall4', 'wall5', 'wall6', 'wall7', 'player', 'move_sprites', 'draw_scene', 'change_colors', 'check_collisions', 'event', 'QUIT', 'KEYDOWN', 'K_ESCAPE', 'KEYUP'])
 
List of symbols:
pygame
sys
os
math
WIDTH
HEIGHT
BlockySprite
clock
display
BLACK
RED
GRAY
YELLOW
all_sprites
all_sprites_but_player
wall1
wall2
wall3
wall4
wall5
wall6
wall7
player
move_sprites
draw_scene
change_colors
check_collisions
event
QUIT
KEYDOWN
K_ESCAPE
KEYUP

12. Transformace AST do bajtkódu

Víme již, že posledními dvěma kroky je optimalizace na úrovni AST a překlad AST do bajtkódu. Tyto kroky jsme si již částečně ukázali minule, takže se pro úplnost podívejme, jak lze zajistit překlad bajtkódu s jeho následným spuštěním:

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="", mode="exec"))
 
print("Done")

Skript nejdříve vypíše neoptimalizovaný AST:

   <_ast.Module object at 0x7f5898b55430>
     <_ast.Expr object at 0x7f5898a98670>
       <_ast.Call object at 0x7f5898a986a0>
         <_ast.Name object at 0x7f5898a987c0>
           <_ast.Load object at 0x7f5898ab2a00>
         <_ast.BinOp object at 0x7f5898a988b0>
           <_ast.BinOp object at 0x7f5898a988e0>
             <_ast.Constant object at 0x7f5898a98910>
             <_ast.Add object at 0x7f5898ab2e80>
             <_ast.BinOp object at 0x7f5898ac0d00>
               <_ast.Constant object at 0x7f5898ac0d30>
               <_ast.Mult object at 0x7f5898ab2f40>
               <_ast.BinOp object at 0x7f5898ac0d90>
                 <_ast.Constant object at 0x7f5898ac0dc0>
                 <_ast.Sub object at 0x7f5898ab2ee0>
                 <_ast.BinOp object at 0x7f5898ac0e20>
                   <_ast.Constant object at 0x7f5898ac0e80>
                   <_ast.Div object at 0x7f5898ac0040>
                   <_ast.Constant object at 0x7f5898ac0eb0>
           <_ast.Add object at 0x7f5898ab2e80>
           <_ast.Constant object at 0x7f5898a989a0>

A následně provede překlad do bajtkódu, který je v posledním kroku spuštěn:

Executing
6.5
Done

13. Bajtkód virtuálního stroje Pythonu

V této části článku si ve stručnosti popíšeme bajtkód využívaný programovacím jazykem Python, konkrétně jeho původní verzí CPython (kromě tohoto bajtkódu lze najít i další bajtkódy využívané některými specifickými implementacemi Pythonu). S problematikou bajtkódů jsme se již na stránkách Roota setkali. Víme například, že bajtkód JVM (Java Virtual Machine) je poměrně nízkoúrovňový, zejména v porovnání s bajtkódem používaným v programovacím jazyku Lua (resp. přesněji řečeno virtuálním strojem tohoto jazyka). Totéž platí, a to dokonce ještě ve větší míře, i pro bajtkód programovacího jazyka Python. Ten je opět založen na konceptu zásobníku operandů (jako JVM), ovšem mnohé instrukce pracující s jedním či dvěma operandy (samozřejmě uloženými na zásobníku) ve skutečnosti mohou volat metody objektů a nikoli pouze provádět operace nad primitivními datovými typy. Platí to především pro všechny „aritmetické“ operace, například i pro operátor +, který se překládá do instrukce BINARY_ADD.

To například znamená, že se jednoduchá funkce add() se dvěma operandy:

def add(x, y):
    return x+y

přeloží do následující čtveřice instrukcí bajtkódu:

add:
 28           0 LOAD_FAST                0 (x)
              3 LOAD_FAST                1 (y)
              6 BINARY_ADD
              7 RETURN_VALUE

Tuto funkci lze ovšem volat jak s číselnými parametry, tak i s řetězci, n-ticemi, seznamy či libovolnými objekty s implementovanou metodou __add__, takže instrukce BINARY_ADD není zcela porovnatelná například s JVM instrukcemi iadd, ladd atd. operujícími pouze nad konkrétním primitivním datovým typem.:

    print(add(1, 2))
    print(add(1., 2))
    print(add("Hello ", "world!"))
    print(add([1,2,3], [4,5,6]))
    print(add((1,2,3), (4,5,6)))

Kromě toho může bajtkód Pythonu obsahovat i instrukce pro snazší tvorbu smyček (BREAK_LOOP, CONTINUE_LOOP) i pro práci s kolekcemi (LIST_APPEND, MAP_ADD, BUILD_SLICE apod).

14. Zásobníkové vs. registrové virtuální stroje

Využívání bajtkódů má v současnosti za sebou zhruba čtyřicet let postupného vývoje, takže není divu, že za tuto poměrně dlouhou dobu bylo navrženo a implementováno mnoho různých řešení virtuálního stroje+bajtkódu, která se od sebe v mnoha ohledech odlišovala, a to jak úrovní abstrakce bajtkódu (nízkoúrovňové instrukce dobře transformovatelné na strojový kód vs. vysokoúrovňové instrukce podporující například polymorfismus využívaný například virtuálním strojem Pythonu), tak i způsobem, jakým jednotlivé instrukce pracovaly s argumenty. Naprostou většinu existujících a v současnosti používaných bajtkódů lze rozdělit do dvou skupin. V první skupině se nachází bajtkódy zpracovávané virtuálními stroji založenými na zásobníku operandů (operand stack) a v druhé skupině se nachází bajtkódy využívající sadu registrů (register set) nabízených virtuálním strojem. Oba přístupy mají své přednosti i zápory a taktéž skalní zastánce i odpůrce, jak je tomu ostatně v IT dobrým zvykem :-)

Bajtkódy a virtuální stroje využívající zásobník operandů a instrukce pro práci s argumenty uloženými na tomto zásobníku většinou obsahují mnoho bezparametrických instrukcí, jejichž operační kódy tak mohou být velmi krátké a typicky bývají uloženy v jednom bajtu (z toho také ostatně označení „bajtkód“ vychází). Interpretace takového bajtkódu bývá velmi jednoduchá a lze ji efektivně provádět i na těch mikroprocesorech, které obsahují velmi malé množství pracovních registrů, z čehož ostatně vyplývá i oblíbenost takto navržených bajtkódů v době osmibitových mikroprocesorů a mikrořadičů (poněkud speciálním případem je jazyk Forth). Před přibližně deseti lety, kdy se ve větší míře začaly rozšiřovat JIT překladače, se předpokládalo, že nové JIT překladače budou mít problémy s překladem instrukcí založených na použití zásobníku operandů do strojového kódu moderních mikroprocesorů (ty mají většinou velkou sadu pracovních registrů), ovšem ukázalo se, že JIT dokáží bez větších problémů pracovat jak se zásobníkovými instrukcemi, tak i s instrukcemi využívajícími sadu pracovních registrů VM.

Tím se pomalu dostáváme ke druhému rozšířenému typu bajtkódů. Jedná se o bajtkódy, jejichž instrukce dokážou pracovat s obsahem množiny pracovních registrů zvoleného virtuálního stroje. Délka instrukčního slova i možnosti takto navržených bajtkódů závisí především na počtu těchto pracovních registrů; v moderních VM se setkáme minimálně s použitím šestnácti či 32 registry, což znamená, že mnoho instrukcí má délku minimálně dva bajty, mnohdy i tři či čtyři bajty. Liší se taktéž počet operandů instrukcí – některé bajtkódy využívají takzvaný dvouadresový kód (používají dva registry – jeden registr zdrojový a druhý registr současně zdrojový i cílový), jiné se zaměřují na tříadresový kód (dva zdrojové registry a jeden registr cílový). Způsob interpretace takto navržených bajtkódů může být problematičtější v případě, že mikroprocesor, na němž interpret běží, obsahuje menší množství fyzických pracovních registrů, ovšem (jak již bylo řečeno v předchozím odstavci), při použití JIT se rozdíly mezi oběma způsoby práce s operandy do značné míry rozostřují.

Podívejme se nyní na dvě ukázky, jak se může lišit bajtkód založený na zásobníkovém virtuálním stroji od bajtkódu, který je určen pro registrový virtuální stroj. V obou příkladech se má vyhodnotit jednoduchý výraz result = a+b*c-d; pro jednoduchost předpokládejme, že všech pět proměnných je lokálních a současně mají typ celé číslo (integer). Způsob překladu do bajtkódu využívajícího zásobník operandů (konkrétně je použit bajtkód JVM) může vypadat následovně:

              ; 0 je index proměnné a
              ; 1 je index proměnné b
              ; 2 je index proměnné c
              ; 3 je index proměnné d
              ; 4 je index proměnné result
0: iload  0   ; uložení obsahu proměnné a na zásobník
1: iload  1   ; uložení obsahu proměnné b na zásobník
2: iload  2   ; uložení obsahu proměnné c na zásobník
3: imul       ; provedení operace b*c, výsledek je ponechán na zásobníku
4: iadd       ; provedení operace a+(b*c)
5: iload  3   ; uložení obsahu proměnné d na zásobník
6: isub       ; dokončit příkaz a+(b*c)+d
7: istore 4   ; uložení výsledku z TOS (obsah zásobníku operandů) do proměnné result

Příklad kompilace téhož příkazu result = a+b*c-d do bajtkódu využívajícího pracovní registry, konkrétně do bajtkódu využívaného programovacím jazykem Lua:

                               ; 0 je index proměnné a
                               ; 1 je index proměnné b
                               ; 2 je index proměnné c
                               ; 3 je index proměnné d
                               ; 4 je index proměnné result
1       [101]   MUL    4 1 2   ; přímé vynásobení obsahu proměnných b a c
2       [101]   ADD    4 0 4   ; přičíst k obsahu proměnné a mezivýsledek, výsledek uložit do proměnné result
3       [101]   SUB    4 4 3   ; odečíst od mezivýsledku obsah proměnné b, výsledek uložit do proměnné result

Ve druhém případě se nemusely vůbec použít instrukce pro uložení proměnných na zásobník ani pro načtení hodnoty zpět ze zásobníku operandů do proměnné, ovšem na druhou stranu musely mít všechny aritmetické instrukce v instrukčním slovu uloženy i indexy operandů.

15. Příklady funkcí přeložených do bajtkódu Pythonu

Podívejme se nejdříve na zdrojový kód příkladu, který ve své závěrečné části obsahuje funkci pro disassembling bajtkódu:

#
# Modul s nekolika jednoduchymi funkcemi
# pro otestovani zakladnich vlastnosti bajtkodu jazyka Python
#
 
#
# Prazdna funkce bez parametru.
#
def nop1():
    pass
 
#
# Taktez prazdna funkce bez parametru.
#
def nop2():
    return
 
#
# Funkce bez parametru vracejici konstantu.
#
def answer():
    return 42
 
#
# Soucet dvou cisel.
#
def add(x, y):
    return x+y
 
#
# Funkce s podminkou.
#
def isNegative(x):
    if x < 0:
        return True
    return False
 
#
# Funkce s podminkou a se smyckou.
#
def fibonacciIter(n):
    if n <= 1:
        return n
 
    result = 0
    n1 = 0
    n2 = 1
 
    for i in xrange(n-1, 0, -1):
        result = n1 + n2
        n1 = n2
        n2 = result
 
    return result
 
#
# Funkce s rekurzi.
#
def fibonacciRecursive(n):
    if n <= 1:
        return n
    else:
        return fibonacciRecursive(n-1) + fibonacciRecursive(n-2)
 
#
# Vse je nutne otestovat.
#
def main():
    nop1()
    nop2()
    print(answer())
    print(add(1, 2))
    print(add("Hello ", "world!"))
    print(isNegative(-10))
 
    for n in xrange(0,11):
        print(str(n) + "\t" + str(fibonacciIter(n)) + "\t" + str(fibonacciRecursive(n)))
 
#main()
 
def disassemble():
    from dis import dis
 
    print("\nnop1:")
    dis(nop1)
 
    print("\nnop2:")
    dis(nop2)
 
    print("\nanswer:")
    dis(answer)
 
    print("\nadd:")
    dis(add)
 
    print("\nisNegative:")
    dis(isNegative)
 
    print("\nfibonacciIter:")
    dis(fibonacciIter)
 
    print("\nfibonacciRecursive:")
    dis(fibonacciRecursive)
 
disassemble()

Opět se podívejme, jak bude vypadat bajtkód vygenerovaný překladačem Pythonu, resp. přesněji řečeno CPythonu:

Na překladu funkce nop1() pravděpodobně nenajdeme nic překvapivého:

nop1:
 10           0 LOAD_CONST               0 (None)
              3 RETURN_VALUE

Stejným způsobem je přeložena i funkce nop2(), což je pochopitelné:

nop2:
 16           0 LOAD_CONST               0 (None)
              3 RETURN_VALUE

V bajtkódu funkce answer() se na zásobník nejdříve uloží číselná konstanta 42, která je následně instrukcí RETURN_VALUE vrácena volající funkci:

answer:
 22           0 LOAD_CONST               1 (42)
              3 RETURN_VALUE

Ve funkci add() se používá instrukce BINARY_ADD, která však ve skutečnosti může pracovat nejenom s čísly, ale i s řetězci, n-ticemi apod., což je velký rozdíl oproti bajtkódu JVM, což jsme ostatně mohli vidět v předchozích kapitolách:

add:
 28           0 LOAD_FAST                0 (x)
              3 LOAD_FAST                1 (y)
              6 BINARY_ADD
              7 RETURN_VALUE

V bajtkódu funkce isNegative() je zajímavá především kombinace instrukcí COMPARE_OP (s operandem <) a JUMP_IF_FALSE. Instrukce bajtkódu Pythonu evidentně nejsou pojmenovány s ohledem na jejich ruční zápis :-):

isNegative:
 34           0 LOAD_FAST                0 (x)
              3 LOAD_CONST               1 (0)
              6 COMPARE_OP               0 (<)
              9 JUMP_IF_FALSE            5 (to 17)
             12 POP_TOP
 
 35          13 LOAD_GLOBAL              0 (True)
             16 RETURN_VALUE
        >>   17 POP_TOP

 36          18 LOAD_GLOBAL              1 (False)
             21 RETURN_VALUE

I v bajtkódu funkce fibonacciIter() nalezneme dvojici instrukcí COMPARE_OP s JUMP_IF_FALSE. Kromě toho si povšimněte instrukce FOR_ITER, která pro zadaný iterátor uložený na zásobníku vytvoří základ pro programovou smyčku for:

fibonacciIter:
 42           0 LOAD_FAST                0 (n)
              3 LOAD_CONST               1 (1)
              6 COMPARE_OP               1 (<=)
              9 JUMP_IF_FALSE            5 (to 17)
             12 POP_TOP
 
 43          13 LOAD_FAST                0 (n)
             16 RETURN_VALUE
        >>   17 POP_TOP
 
 45          18 LOAD_CONST               2 (0)
             21 STORE_FAST               1 (result)
 
 46          24 LOAD_CONST               2 (0)
             27 STORE_FAST               2 (n1)
 
 47          30 LOAD_CONST               1 (1)
             33 STORE_FAST               3 (n2)
 
 49          36 SETUP_LOOP              52 (to 91)
             39 LOAD_GLOBAL              0 (xrange)
             42 LOAD_FAST                0 (n)
             45 LOAD_CONST               1 (1)
             48 BINARY_SUBTRACT
             49 LOAD_CONST               2 (0)
             52 LOAD_CONST               3 (-1)
             55 CALL_FUNCTION            3
             58 GET_ITER
        >>   59 FOR_ITER                28 (to 90)
             62 STORE_FAST               4 (i)
 
 50          65 LOAD_FAST                2 (n1)
             68 LOAD_FAST                3 (n2)
             71 BINARY_ADD
             72 STORE_FAST               1 (result)
 
 51          75 LOAD_FAST                3 (n2)
             78 STORE_FAST               2 (n1)
 
 52          81 LOAD_FAST                1 (result)
             84 STORE_FAST               3 (n2)
             87 JUMP_ABSOLUTE           59
        >>   90 POP_BLOCK
 
 54     >>   91 LOAD_FAST                1 (result)
             94 RETURN_VALUE

V bajtkódu funkce fibonacciRecursive() si povšimněte zejména instrukce pojmenované LOAD_GLOBAL, kterou je možné využít pro uložení hodnoty globálního symbolu na zásobník:

fibonacciRecursive:
 60           0 LOAD_FAST                0 (n)
              3 LOAD_CONST               1 (1)
              6 COMPARE_OP               1 (<=)
              9 JUMP_IF_FALSE            5 (to 17)
             12 POP_TOP
 
 61          13 LOAD_FAST                0 (n)
             16 RETURN_VALUE
        >>   17 POP_TOP

 63          18 LOAD_GLOBAL              0 (fibonacciRecursive)
             21 LOAD_FAST                0 (n)
             24 LOAD_CONST               1 (1)
             27 BINARY_SUBTRACT
             28 CALL_FUNCTION            1
             31 LOAD_GLOBAL              0 (fibonacciRecursive)
             34 LOAD_FAST                0 (n)
             37 LOAD_CONST               2 (2)
             40 BINARY_SUBTRACT
             41 CALL_FUNCTION            1
             44 BINARY_ADD
             45 RETURN_VALUE
             46 LOAD_CONST               0 (None)
             49 RETURN_VALUE

16. Dekompilace bajtkódu pro jednoduchý výraz s konstantami

Díky součinnosti standardních modulů ast a dis můžeme jít ještě dále a provést postupně tyto operace:

1. Tokenizaci příkazu (statement)
2. Transformaci sekvence tokenů na AST (parsing)
3. Překlad AST do bajtkódu
4. Zpětný překlad bajtkódu do čitelnější podoby

Všechny tyto operace jsou ukázány v následujícím příkladu:

import ast
import dis
 
 
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("Compiling")
 
compiled = compile(tree, filename="<ast>", mode="exec")
 
print("Decompiling")
 
dis.dis(compiled)
 
print("Done")

Tento demonstrační příklad po svém spuštění nejdříve vypíše obsah AST (nepříliš formátovaný):

   <_ast.Module object at 0x7fd10db86430>
     <_ast.Expr object at 0x7fd10daf1cd0>
       <_ast.Call object at 0x7fd10da84d90>
         <_ast.Name object at 0x7fd10da84dc0>
           <_ast.Load object at 0x7fd10dae39d0>
         <_ast.BinOp object at 0x7fd10da84f40>
           <_ast.BinOp object at 0x7fd10da84eb0>
             <_ast.Constant object at 0x7fd10da84f70>
             <_ast.Add object at 0x7fd10dae3e50>
             <_ast.BinOp object at 0x7fd10da84e80>
               <_ast.Constant object at 0x7fd10daaf130>
               <_ast.Mult object at 0x7fd10dae3f10>
               <_ast.BinOp object at 0x7fd10daaf310>
                 <_ast.Constant object at 0x7fd10daaf2b0>
                 <_ast.Sub object at 0x7fd10dae3eb0>
                 <_ast.BinOp object at 0x7fd10daaf340>
                   <_ast.Constant object at 0x7fd10daaf460>
                   <_ast.Div object at 0x7fd10dae3fd0>
                   <_ast.Constant object at 0x7fd10daaf400>
           <_ast.Add object at 0x7fd10dae3e50>
           <_ast.Constant object at 0x7fd10da84520>

Následně se provede překlad AST do bajtkódu a zpětný překlad do čitelné podoby:

Compiling
Decompiling
  1           0 LOAD_NAME                0 (print)
              2 LOAD_CONST               0 (6.5)
              4 CALL_FUNCTION            1
              6 POP_TOP
              8 LOAD_CONST               1 (None)
             10 RETURN_VALUE
Done

17. Dekompilace bajtkódu složitějšího příkazu

Zkusme nyní provést všechny operace vyjmenované v předchozí kapitole, ovšem nyní pro příkaz, který nemůže překladač zjednodušit. Konkrétně se jedná o tento příkaz:

print(a+b*(c-d/e)+f)

Tokenizace, parsing, překlad i zpětný překlad zajišťuje tento jednoduchý skript:

import ast
import dis
 
 
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(a+b*(c-d/e)+f)", mode="exec")
 
visitor = Visitor()
visitor.visit(tree)
 
print("Compiling")
 
compiled = compile(tree, filename="<ast>", mode="exec")
 
print("Decompiling")
 
dis.dis(compiled)
 
print("Done")

Tento skript po svém spuštění opět nejdříve vypíše strukturu celého AST:

   <_ast.Module object at 0x7f21685c2430>
     <_ast.Expr object at 0x7f216852dcd0>
       <_ast.Call object at 0x7f21684c0d90>
         <_ast.Name object at 0x7f21684c0dc0>
           <_ast.Load object at 0x7f216851f9d0>
         <_ast.BinOp object at 0x7f21684c0f40>
           <_ast.BinOp object at 0x7f21684c0eb0>
             <_ast.Name object at 0x7f21684c0f70>
               <_ast.Load object at 0x7f216851f9d0>
             <_ast.Add object at 0x7f216851fe50>
             <_ast.BinOp object at 0x7f21684c0e80>
               <_ast.Name object at 0x7f21684eb130>
                 <_ast.Load object at 0x7f216851f9d0>
               <_ast.Mult object at 0x7f216851ff10>
               <_ast.BinOp object at 0x7f21684eb310>
                 <_ast.Name object at 0x7f21684eb2b0>
                   <_ast.Load object at 0x7f216851f9d0>
                 <_ast.Sub object at 0x7f216851feb0>
                 <_ast.BinOp object at 0x7f21684eb340>
                   <_ast.Name object at 0x7f21684eb460>
                     <_ast.Load object at 0x7f216851f9d0>
                   <_ast.Div object at 0x7f216851ffd0>
                   <_ast.Name object at 0x7f21684eb400>
                     <_ast.Load object at 0x7f216851f9d0>
           <_ast.Add object at 0x7f216851fe50>
           <_ast.Name object at 0x7f21684c0520>
             <_ast.Load object at 0x7f216851f9d0>

Následuje překlad a posléze i zpětný překlad:

Compiling
Decompiling
  1           0 LOAD_NAME                0 (print)
              2 LOAD_NAME                1 (a)
              4 LOAD_NAME                2 (b)
              6 LOAD_NAME                3 (c)
              8 LOAD_NAME                4 (d)
             10 LOAD_NAME                5 (e)
             12 BINARY_TRUE_DIVIDE
             14 BINARY_SUBTRACT
             16 BINARY_MULTIPLY
             18 BINARY_ADD
             20 LOAD_NAME                6 (f)
             22 BINARY_ADD
             24 CALL_FUNCTION            1
             26 POP_TOP
             28 LOAD_CONST               0 (None)
             30 RETURN_VALUE
Done

Zde můžeme vidět, že k žádné optimalizaci nedošlo (a ani nemohlo) a současně je patrné, že se překladač příliš nesnaží zmenšovat obsazení zásobníku operandů při vyhodnocování („spuštění“) tohoto bajtkódu. Nejprve jsou na zásobník uloženy reference na funkci print i proměnné a až e. Posléze je provedena sekvence binárních aritmetických operací (binárních proto, že každá operace má dva operandy, které čte ze zásobníku). Teprve poté je na zásobník uložena reference proměnné f, je provedena poslední binární aritmetická operace a nakonec se zavolá funkce print s jedním parametrem. Funkce nevrací žádnou hodnotu, což v Pythonu ovšem znamená, že ve skutečnosti vrací None, což zajišťuje poslední dvojice instrukcí.

18. Příloha: definice gramatiky programovacího jazyka Python

Jména filtrů použitých v návrhovém vzoru Visitor přímo vychází z gramatiky programovacího jazyka Python. Ta (už) není v žádném případě jednoduchá, což je ostatně patrné i při pohledu na tuto přílohu:

module Python version "$Revision$"
{
        mod = Module(stmt* body)
            | Interactive(stmt* body)
            | Expression(expr body)
 
            -- not really an actual node but useful in Jython's typesystem.
            | Suite(stmt* body)
 
        stmt = FunctionDef(identifier name, arguments args,
                            stmt* body, expr* decorator_list)
              | ClassDef(identifier name, expr* bases, stmt* body, expr* decorator_list)
              | Return(expr? value)
 
              | Delete(expr* targets)
              | Assign(expr* targets, expr value)
              | AugAssign(expr target, operator op, expr value)
 
              -- not sure if bool is allowed, can always use int
              | Print(expr? dest, expr* values, bool nl)
 
              -- use 'orelse' because else is a keyword in target languages
              | For(expr target, expr iter, stmt* body, stmt* orelse)
              | While(expr test, stmt* body, stmt* orelse)
              | If(expr test, stmt* body, stmt* orelse)
              | With(expr context_expr, expr? optional_vars, stmt* body)
 
              -- 'type' is a bad name
              | Raise(expr? type, expr? inst, expr? tback)
              | TryExcept(stmt* body, excepthandler* handlers, stmt* orelse)
              | TryFinally(stmt* body, stmt* finalbody)
              | Assert(expr test, expr? msg)
 
              | Import(alias* names)
              | ImportFrom(identifier? module, alias* names, int? level)
 
              -- Doesn't capture requirement that locals must be
              -- defined if globals is
              -- still supports use as a function!
              | Exec(expr body, expr? globals, expr? locals)
 
              | Global(identifier* names)
              | Expr(expr value)
              | Pass | Break | Continue
 
              -- XXX Jython will be different
              -- col_offset is the byte offset in the utf8 string the parser uses
              attributes (int lineno, int col_offset)
 
              -- BoolOp() can use left & right?
        expr = BoolOp(boolop op, expr* values)
             | BinOp(expr left, operator op, expr right)
             | UnaryOp(unaryop op, expr operand)
             | Lambda(arguments args, expr body)
             | IfExp(expr test, expr body, expr orelse)
             | Dict(expr* keys, expr* values)
             | Set(expr* elts)
             | ListComp(expr elt, comprehension* generators)
             | SetComp(expr elt, comprehension* generators)
             | DictComp(expr key, expr value, comprehension* generators)
             | GeneratorExp(expr elt, comprehension* generators)
             -- the grammar constrains where yield expressions can occur
             | Yield(expr? value)
             -- need sequences for compare to distinguish between
             -- x < 4 < 3 and (x < 4) < 3
             | Compare(expr left, cmpop* ops, expr* comparators)
             | Call(expr func, expr* args, keyword* keywords,
                         expr? starargs, expr? kwargs)
             | Repr(expr value)
             | Num(object n) -- a number as a PyObject.
             | Str(string s) -- need to specify raw, unicode, etc?
             -- other literals? bools?
 
             -- the following expression can appear in assignment context
             | Attribute(expr value, identifier attr, expr_context ctx)
             | Subscript(expr value, slice slice, expr_context ctx)
             | Name(identifier id, expr_context ctx)
             | List(expr* elts, expr_context ctx)
             | Tuple(expr* elts, expr_context ctx)
 
              -- col_offset is the byte offset in the utf8 string the parser uses
              attributes (int lineno, int col_offset)
 
        expr_context = Load | Store | Del | AugLoad | AugStore | Param
 
        slice = Ellipsis | Slice(expr? lower, expr? upper, expr? step)
              | ExtSlice(slice* dims)
              | Index(expr value)
 
        boolop = And | Or
 
        operator = Add | Sub | Mult | Div | Mod | Pow | LShift
                 | RShift | BitOr | BitXor | BitAnd | FloorDiv
 
        unaryop = Invert | Not | UAdd | USub
 
        cmpop = Eq | NotEq | Lt | LtE | Gt | GtE | Is | IsNot | In | NotIn
 
        comprehension = (expr target, expr iter, expr* ifs)
 
        -- not sure what to call the first argument for raise and except
        excepthandler = ExceptHandler(expr? type, expr? name, stmt* body)
                        attributes (int lineno, int col_offset)
 
        arguments = (expr* args, identifier? vararg,
                     identifier? kwarg, expr* defaults)
 
        -- keyword arguments supplied to call
        keyword = (identifier arg, expr value)
 
        -- import name with optional 'as' alias.
        alias = (identifier name, identifier? asname)
}

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

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