Automata, Languages and Compilers 2020/21 spring

Pythoni programmi struktuur

Kõikides populaarsetes programmeerimiskeeltes on programmi struktuur hierarhiline -- just nagu failisüsteemi kaustad võivad sisaldada almkaustu, võivad programmi laused sisaldada alamlauseid või avaldisi, mis omakorda võivad sisaldada alamavaldisi jne. Seetõttu teisendatakse neis keeltes programmi tekst enne käivitamist või kompileerimist puukujuliseks andmestruktuuriks, mis toob selle hierarhia kenasti esile.

Taolist programmi struktuuri kujutavat puud nimetatakse süntaksipuuks. Abstraktne süntaksipuu, e AST (ingl abstract syntax tree) on süntaksipuu lakooniline variant, mis sisaldab vaid seda infot, mis on programmi tähenduse edasiandmiseks hädavajalik.

Võtame näiteks järgmise Pythoni programmi:

eesnimi = input("Sisesta oma eesnimi: ")
print("Tere " + eesnimi.capitalize() + "!")

Selle programmi abstraktne süntaksipuu võiks olla midagi sellist:

• Module
  • body=list
    • 0=Assign
      • targets=list
        • 0=Name
          • id='eesnimi'
      • value=Call
        • func=Name
          • id='input'
        • args=list
          • 0=Str
            • s='Sisesta oma eesnimi '
    • 1=Expr
      • value=Call
        • func=Name
          • id='print'
        • args=list
          • 0=BinOp
            • left=BinOp
              • left=Str
                • s='Tere '
              • op=Add
              • right=Call
                • func=Attribute
                  • value=Name
                    • id='eesnimi'
                  • attr='capitalize'
            • op=Add
            • right=Str
              • s='!'

Süntaksipuu tipud on siin näidatud punasega. Mustaga on näidatud tipu attribuudid. Sellist puud nimetatakse mõnikord heterogeenseks, sest erinevad tipud võivad olla erineva ülesehitusega (muuhulgas erineva alluvate arvuga). Konkreetsemalt, Pythoni AST puhul võib igat tippu kujutav objekt olla erinevast klassist -- punane rasvases kirjas teksti antud skeemil ongi klassi nimed.

Vaatame, mida sellest puust annab välja lugeda. Juurtipus olev Module ütleb, et puu juureks on objekt klassist ast.Module, millel on attribuut nimega body, mille väärtuseks on kaheelemendiline list, mille esimeseks elemendiks on objekt klassist ast.Assign -- ühesõnaga, mooduli keha esimeseks lauseks on omistuslause. Selle tipu atribuutideks on targets ja value, millest esimese väärtus ütleb, et võrdusmärgist vasakul on muutuja nimi (ast.Name) "eesnimi" ja paremal on funktsiooni väljakutse (ast.Call)

Pythoni AST tekitamine

Lisaks sellele, et taolised puud tekivad Pythoni kõhus programmide käivitamisel, on võimalik ka tavaprogrammeerijal neid suvalise programmiteksti põhjal koostada. Selle tarvis on Pythoni standardteegis moodul ast:

import ast

# Harilikult loeksime programmi teksti failist sisse, aga lihtuse mõttes
# esitame selle praegu kohe sõnena
programmi_tekst = """
eesnimi = input("Sisesta oma eesnimi: ")
print("Tere " + eesnimi.capitalize() + "!")
"""

# teisendame programmi puu kujule
puu = ast.parse(programmi_tekst)

# väljastame esimese lause (st omistuslause) parema poole 
# (st funktsiooni väljakutse) funktsiooni nime 
print(puu.body[0].value.func.id) # ekraanile peaks ilmuma "input"

# väljastame terve puu 
print(ast.dump(puu))

Nagu näha, siis tegelik puu on tiba keerulisem, kui eespool toodu, aga põhimõte on sama -- puu koosneb Pythoni objektidest, mille atribuutide väärtusteks on omakorda Pythoni objektid (antud näites sõned, listid, ja AST tipud).

Siin võib tulla õigustatud küsimus: kui me seda objekti nimetame puuks, siis miks ei või me puuks nimetada suvalist andmestruktuuri? Teatud nurga alt vaadates isegi võiks suvalist andmestruktuuri puuks nimetada, aga meie struktuuri teeb eriti "puulikuks" see, et tasemete arv ei ole piiratud, nagu ka harilike puukujuliste andmestruktuuride puhul.

Pythoni AST läbimine

Pythoni AST kohta saab täpsemalt infot mooduli ast dokumentatsioonist. Üks oluline asi, mida tähele panna, on see, et puu tippe kujutavatel objektidel on ühine ülemklass ast.AST, mis annab kõikidele tippudele võime loetleda enda alluvaid (ast.AST._fields või ast.iter_child_nodes(node)). See võimaldab meil süntaksipuud käsitleda ka hariliku homogeense puuna (st. puuna, mille kõik tipud on sarnase struktuuriga).

Järgnev programm kuvab ekraanile etteantud programmis sisalduvad muutujanimed, kasutades selleks nii infot konkreetse tipu klassi kohta, kui ka võimalust küsida tipu alluvaid ilma tipu tüüpi teadmata:

import ast

def kuva_muutujanimed(tipp):
    if isinstance(tipp, ast.Name):
        print(tipp.id)
    else:
        for alluv in ast.iter_child_nodes(tipp):
            kuva_muutujanimed(alluv)

puu = ast.parse("""
x = 2 + 3
y = x * x
print("y")
print("z")
""")

kuva_muutujanimed(puu)

Selle programmi kirjutamiseks pidin ma teadma, et muutujate esitamiseks on klass ast.Name ja et sellel on isendiväli id, mis sisaldab muutuja nime. See info on saadaval mooduli ast dokumentatsioonis, jaotuses Abstract Grammar. Annan siin mõned selgitused sealse skeemi lugemiseks:

• Assign(expr* targets, expr value) tähendab, et omistuslausele vastava klassi nimi on Assign ja et selle klassi objektidel on järgmised väljad:
  • targets, mille väärtus on avaldiste (ingl expression) list (listile viitab tärn expr järel) ja mis esitab omistuslause vasakut poolt (enamasti on seal üksainus muutujanimi);
  • value, mille väärtus on mingi avaldis ja mis esitab omistuslause paremat poolt.
• BinOp(expr left, operator op, expr right) tähendab, et binaarsetele operatsioonidele (nt. 2+3) vastava tipu attribuutideks on left, op ja right, kusjuures left ja right väärtuseks on avaldis ja op väärtuseks on mingi operaator (nt. ast.Add() või ast.Mult()).

Kuigi dokumentatsioonis on vajalik info olemas, on AST-i koostamise juures mõnikord lihtsam toetuda näidetele: parsid (ast.parse) mingi Pythoni programmi, mis teeb sulle huvipakkuva toimingu ning uurid, milline vastav AST välja näeb (print(ast.dump(...))).

Pythoni AST uurimine Thonnyga

Thonny (http://thonny.cs.ut.ee/) on peamiselt algajatele mõeldud Pythoni IDE, aga ta oskab ka Pythoni ASTi graafiliselt näidata:

Thonny käivitamine ja kasutamine

Peale Thonny käivitamist tuleks avada soovitud Pythoni fail ja valida menüüst View => AST. Seepeale avaneb AST aken, kus näidatakse aktiivses redaktoris oleva koodi ASTi (editori sisu ei pea olema salvestatud). Klõpsates puul ridadele, millel on näidatud ära koodipositsioonid, tõstetakse redaktoris sellele tipule vastav lähtetekst esile.

Peale koodis muudatuste tegemist ja faili salvestamist värskendab Thonny ASTi automaatselt.

Ülesanded

Erinevad muutujanimed

Muuda eelpool toodud muutujanimede esitamise programmi nii, et iga nimi kuvatakse vaid üks kord

Omistatud muutujad

Kirjuta programm, mis kuvab muutujanimed, mis esinevad etteantud programmitekstis omistamise vasakus pooles.

Maksimaalne tsükli aste

Kirjuta programm, mis väljastab etteantud programmi while-lausete maksimaalse astme. Selgitus: kui programmis pole ühtegi while-lauset, siis tuleb tagastada 0. Kui leidub mõni while lause, aga ükski neist ei sisalda while-lauset (ei vahetult, ega mõne teise konstruktsiooni all), siis tuleb tagastada 1. Kui leidub while-lause, mille sees on veel üks while-lause, tuleb tagastada 2 jne.

If koos else-ga

Kirjuta programm, mis väljastab etteantud programmis olevate if-lausete arvu, millel on olemas ka else-haru.

Maksimaalne täisarvu literaal

Kirjuta programm, mis väljastab etteantud programmis oleva maksimaalse täisarvu literaali väärtuse, või ütleb, et ühtegi täisarvuliteraali ei leidu.

Pythoni AST-i kasutamise näited

AST muutmise näide

Järgnev koodilõik demonstreerib, kui lihtne on Pythoniga Pythoni programme töödelda:

import ast

programm = """
x = 3
y = "tere".upper()
print(x * y)
"""

# parsime programmi abstraktseks süntaksipuuks:
puu = ast.parse(programm)
print("Programmi AST:", ast.dump(puu))

# AST-i saab kompileerida ja seejärel käivitada
exec(compile(puu, "<katsetus>", "exec"))


# Ma võin teha puus mingi muudatuse,
# nt. muudan ära esimese omistuslause parema poole
laused = puu.body
laused[0].value = ast.Num(10)

# Python tahab, et kõikide tippude juures on viide lähtekoodile
# aga kuna meie Num(10) ei pärine lähtekoodist, siis laseme Pythonil
# leiutada talle mingi pseudo-asukoha
ast.fix_missing_locations(puu) 

# Muudetud puud võin jälle kompileerida ja käivitada
exec(compile(puu, "<katsetus>", "exec"))

AST koostamise näide

Abstraktse süntaksipuu võib ka nullist kokku panna:

from ast import *

omistuslause = Assign (
    targets = [Name(id="x", ctx=Store())],
    value = Num(10)
)

liitmistehe = BinOp (
    left=Name(id="x", ctx=Load()),
    right=Num(2),
    op=Add()
)

print_avaldis = Call (
    func=Name(id="print", ctx=Load()),
    args=[
        Str("Vastus on:"),
        liitmistehe
    ],
    keywords=[]
)

print_lause = Expr(print_avaldis)


moodul = Module([omistuslause, print_lause])
fix_missing_locations(moodul)

exec(compile(moodul, "<katsetus>", "exec"))

Seda võtet võiks kasutada näiteks omaenda programmeerimiskeele tõlkimiseks Pythonisse.