Hlavní navigace

Lexikální a syntaktická analýza zdrojových kódů jazyka Go

21. 12. 2021
Doba čtení: 35 minut

Sdílet

 Autor: Go lang
Ukážeme si, jak je možné s využitím standardní knihovny jazyka Go provádět lexikální i syntaktickou analýzu zdrojových kódů napsaných v Go, včetně konstrukce a zobrazení AST (abstraktního syntaktického stromu).

Obsah

1. Lexikální a syntaktická analýza zdrojových kódů jazyka Go

2. Lexémy a tokeny (tokenizace)

3. Použití balíčku go/scanner

4. Syntaktická analýza (parsing) a abstraktní syntaktický strom

5. Syntaktická analýza v Go – balíčky go/token a go/parser

6. Čitelný výpis obsahu abstraktního syntaktického stromu

7. Průchod abstraktním syntaktickým stromem

8. Návrhový vzor Visitor

9. Zobrazení hloubky uzlu v AST

10. Koncové uzly v AST

11. AST zkonstruovaný pro sekvenci příkazů

12. Výrazy se závorkami a s různými prioritami operátorů

13. Konstrukce AST pro jediný výraz

14. Typy uzlů v AST

15. Podrobnější výpis informací o uzlech v AST

16. Složitější aritmetické výrazy, zjednodušení zobrazení AST

17. Logické výrazy

18. Výrazy obsahující operace s poli či řezy

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

20. Odkazy na Internetu

1. Lexikální a syntaktická analýza zdrojových kódů jazyka Go

V předchozím článkuprogramovacím jazyku Go jsme se věnovali popisu nástrojů nazvaných gosec a go-critic. Oba zmíněné nástroje přitom pracují nad AST (abstraktním syntaktickým stromem), nikoli přímo nad zdrojovými kódy Go. Pro tyto účely se přitom využívá standardní knihovna programovacího jazyka Go, která obsahuje všechny potřebné nástroje, konkrétně nástroj pro lexikální analýzu i nástroj pro syntaktickou analýzu (v jejímž rámci se AST tvoří). Dnes se budeme zabývat právě touto velmi zajímavou a užitečnou součástí standardní knihovny jazyka Go. Ukážeme si, jak lze provést takzvanou tokenizaci a následně parsing, jehož výsledkem je AST. A samozřejmě se zmíníme i o tom, jakým způsobem lze abstraktním syntaktickým stromem procházet. V navazujícím článku si pak ukážeme způsob modifikace AST, což sice výše zmíněné nástroje neprovádí, ovšem může se jednat o dobrý základ pro (například) projekty pro vysokoúrovňové optimalizace, přidání dalších datových typů do jazyka, rozšíření sémantiky pro existující datové typy apod.

Poznámka: všechny balíčky určené pro lexikální i syntaktickou analýzu, které jsou součástí standardní knihovny jazyka Go, jsou primárně určeny pro parsing zdrojových kódů naprogramovaných přímo v tomto jazyce. Nejedná se tedy v žádném případě o obecné lexikální analyzátory a parsery. Pokud tedy například v projektu potřebujete zpracovávat zdrojové kódy vytvořené v jiných programovacích jazycích, je vhodnější použít externí balíčky navržené k tomuto účelu (pro Go existuje například i goyacc, což je nástroj odvozený od známého Yaccu – yet another compiler compiler).

Při zpracování zdrojových kódů se postupně provádí jednotlivé dílčí kroky. Díky rozdělení celého zpracování do několika konfigurovatelných kroků je zajištěna velká flexibilita a možnost případného relativně snadného rozšiřování o další podporované jazyky, výstupní formáty, speciální filtry atd. (nehledě na to, že každá činnost je založena na odlišné teorii). Celý průběh zpracování vypadá následovně:

  1. Na začátku zpracování se nachází takzvaný lexer, který postupně načítá jednotlivé znaky ze vstupního řetězce (resp. souboru) a vytváří z nich lexikální tokeny. Teoreticky se pro každý programovací jazyk používá odlišný lexer a samozřejmě je možné v případě potřeby si napsat lexer vlastní.
  2. Výstup z lexeru může procházet libovolným počtem filtrů sloužících pro odstranění nebo (častěji) modifikaci jednotlivých tokenů; ať již jejich typů či přímo textu, který tvoří hodnotu tokenu. Díky existenci filtrů je například možné nechat si zvýraznit vybrané bílé znaky, slova se speciálním významem v komentářích (TODO:, FIX:) apod.
  3. Sekvence tokenů tvoří základ pro syntaktickou analýzu. Nástroj, který syntaktickou analýzu provádí, se většinou nazývá parser a proto se taktéž někdy setkáme s pojmem parsing (ten je ovšem chybně používán i v těch případech, kdy se provádí „pouze“ lexikální analýza). Výsledkem parseru je vhodně zvolená datová struktura, typicky abstraktní syntaktický strom (AST); někdy též strom derivační.
Poznámka: díky tomu, že se prakticky veškeré zpracování zdrojových textů odehrává na úrovni tokenů, není nutné, aby byl celý zpracovávaný zdrojový kód (nebo jeho tokenizovaná podoba) uložen v operační paměti. Je tedy možné zpracovávat i velmi rozsáhlé dokumenty, a to bez větších nároků na operační paměť – i to je ostatně použito v balíčku go/scanner.

2. Lexémy a tokeny (tokenizace)

První část zpracování zdrojových textů je nejzajímavější a to jak z hlediska teorie, tak i implementace (vygenerované konečné automaty atd.). Lexer totiž musí v sekvenci znaků tvořících zdrojový text najít takzvané lexémy, tj. skupiny (sousedních) znaků odpovídajících nějakému vzorku (použít lze gramatiku, regulární výraz či ad-hoc testy). Z lexémů se posléze tvoří již zmíněné lexikální tokeny, což je – poněkud zjednodušeně řečeno – dvojice obsahující typ tokenu (někdy se namísto „typ“ používá označení „jméno“) a řetězec ze vstupního zdrojového souboru (v případě standardních knihoven jazyka Go je situace ještě nepatrně složitější, což ostatně uvidíme v dalším textu). Převodu zdrojového textu na sekvenci tokenů se z tohoto důvodu někdy říká tokenizace. Účelem tokenizace může být:

  • Transformace zdrojového textu do podoby, která může být dále zpracovávána dalším modulem překladače (syntaktická analýza). V takovém případě se však některé tokeny mohou zahazovat; příkladem mohou být komentáře, tokeny představující bílé znaky apod. (opět uvidíme v navazující kapitole). Spojením lexeru a modulu pro syntaktickou analýzu vznikne parser (jeho typickým výsledkem je AST).
  • Transformace zdrojového kódu pro účely zvýraznění syntaxe v editorech či prohlížečích. V tomto případě se žádné tokeny nezahazují, což je i případ knihovny Pygments určené pro ekosystém programovacího jazyka Python.
Poznámka: výše zmíněná tokenizace se používala například již v interpretrech programovacího jazyka BASIC na mnoha osmibitových domácích počítačích. Ovšem v tomto případě měly tokeny poněkud odlišnou strukturu, protože všechny příkazy a funkce byly většinou reprezentovány jednoznačným osmibitovým celým číslem, které tak současně představovalo jak typ tokenu, tak i jeho hodnotu. Důvod byl jednoduchý – v operační paměti byl uložen tokenizovaný kód a nikoli kód zapsaný uživatelem. Tento kód byl již mnohem jednodušeji zpracovatelný interpretrem, než původní zdrojový kód (odpadlo neustálé volání lexeru). Navíc se každý programový řádek ihned po svém zápisu automaticky normalizoval (odstranily se bílé znaky, zkratky příkazů se expandovaly atd.). Ostatně množina příkazů a funkcí byla předem známá a nebyla rozšiřitelná (až na uživatelské funkce dostupné jen v některých BASICech – a i tehdy byl počet funkcí omezen). Příkladem tokenizace tohoto typu mohou být tokeny použité v interpretru programovacího jazyka Atari BASIC, které skutečně přímo odpovídají příkazům, funkcím a operátorům tohoto jazyka. Jen pro zajímavost:
Příkaz Kód tokenu Příkaz Kód tokenu Příkaz Kód tokenu Příkaz Kód tokenu
REM 00 NEXT 09 CLR 18 NOTE 27
DATA 01 GOTO 10 DEG 19 POINT 28
INPUT 02 GO TO 11 DIM 20 XIO 29
COLOR 03 GOSUB 12 END 21 ON 30
LIST 04 TRAP 13 NEW 22 POKE 31
ENTER 05 BYE 14 OPEN 23 PRINT 32
LET 06 CONT 15 LOAD 24 RAD 33
IF 07 COM 16 SAVE 25 READ 34
FOR 08 CLOSE 17 STATUS 26 RESTORE 35

…atd…

3. Použití balíčku go/scanner

Tokenizaci zdrojového kódu, který by měl obsahovat pouze tokeny rozpoznatelné překladačem jazyka Go, lze provést relativně snadno, a to konkrétně s využitím balíčku pojmenovaného přímočaře go/scanner. Tento balíček obsahuje nástroj zajišťující postupný průchod zdrojovým kódem (který je pro obecnost reprezentován typem []byte – nikoli řetězcem) s tím, že se postupně vytváří sekvence tokenů, což je datový typ definovaný ve standardním balíčku go/token. Celá tokenizace může vypadat následovně (tento kód je do značné míry inspirován příkladem ze standardní dokumentace jazyka Go):

package main
 
import (
        "fmt"
        "go/scanner"
        "go/token"
)
 
// zdrojový kód, který má být tokenizován
const source = `
var x int = 1    + 2 * 3 // nejlepší kód
`
 
func main() {
        // objekt představující scanner
        var s scanner.Scanner
 
        // struktura reprezentující množinu zdrojových kódů
        fset := token.NewFileSet()
 
        // přidání informace o zdrojovém kódu
        file := fset.AddFile("", fset.Base(), len(source))
 
        // inicializace scanneru
        s.Init(file, []byte(source), nil, scanner.ScanComments)
 
        // postupné provádění tokenizace a výpis jednotlivých tokenů
        for {
                pos, tok, lit := s.Scan()
                // byl nalezen speciální token reprezentující konec tokenizace
                if tok == token.EOF {
                        fmt.Println("<EOF>")
                        break
                }
                // výpis obsahu tokenu
                fmt.Printf("%s\t%s\t%q\n", fset.Position(pos), tok, lit)
        }

}

Výsledek, tj. sekvence tokenů získána tímto příkladem, bude vypadat následovně:

2:1     var     "var"
2:5     IDENT   "x"
2:7     IDENT   "int"
2:11    =       ""
2:13    INT     "1"
2:18    +       ""
2:20    INT     "2"
2:22    *       ""
2:24    INT     "3"
2:26    ;       "\n"
2:26    COMMENT "// nejlepší kód"
<EOF>
Poznámka: povšimněte si, že již byly odstraněny například mezery mezi jednotlivými lexikálními prvky jazyka. Ovšem konce řádků, které mají v Go syntaktický význam, jsou zachovány, přesněji jsou reprezentovány tokenem „;“.

Zpracování komentářů je řízeno posledním parametrem předaným do funkce scanner.Init. V případě, že se v tomto parametru předá nulová hodnota, budou komentáře ze zpracovávaného vstupu odstraněny a tudíž nezískáme ani jejich tokeny:

package main
 
import (
        "fmt"
        "go/scanner"
        "go/token"
)
 
// zdrojový kód, který má být tokenizován
const source = `
var x int = 1    + 2 * 3 // nejlepší kód
`
 
func main() {
        // objekt představující scanner
        var s scanner.Scanner
 
        // struktura reprezentující množinu zdrojových kódů
        fset := token.NewFileSet()
 
        // přidání informace o zdrojovém kódu
        file := fset.AddFile("", fset.Base(), len(source))
 
        // inicializace scanneru
        s.Init(file, []byte(source), nil, 0)
 
        // postupné provádění tokenizace a výpis jednotlivých tokenů
        for {
                pos, tok, lit := s.Scan()
                // byl nalezen speciální token reprezentující konec tokenizace
                if tok == token.EOF {
                        fmt.Println("<EOF>")
                        break
                }
                // výpis obsahu tokenu
                fmt.Printf("%s\t%s\t%q\n", fset.Position(pos), tok, lit)
        }
}

Nyní nebude token s komentářem generován:

2:1     var     "var"
2:5     IDENT   "x"
2:7     IDENT   "int"
2:11    =       ""
2:13    INT     "1"
2:18    +       ""
2:20    INT     "2"
2:22    *       ""
2:24    INT     "3"
2:26    ;       "\n"
<EOF>

Tokenizér, resp. scanner, neprovádí žádnou kontrolu syntaxe, takže mu lze předat i zcela nesmyslný zápis:

package main
 
import (
        "fmt"
        "go/scanner"
        "go/token"
)
 
// zdrojový kód, který má být tokenizován
const source = `
var x const < 1 && + 2 * || 3 // nejlepší kód
`
 
func main() {
        // objekt představující scanner
        var s scanner.Scanner
 
        // struktura reprezentující množinu zdrojových kódů
        fset := token.NewFileSet()
 
        // přidání informace o zdrojovém kódu
        file := fset.AddFile("", fset.Base(), len(source))
 
        // inicializace scanneru
        s.Init(file, []byte(source), nil, scanner.ScanComments)
 
        // postupné provádění tokenizace a výpis jednotlivých tokenů
        for {
                pos, tok, lit := s.Scan()
                // byl nalezen speciální token reprezentující konec tokenizace
                if tok == token.EOF {
                        fmt.Println("<EOF>")
                        break
                }
                // výpis obsahu tokenu
                fmt.Printf("%s\t%s\t%q\n", fset.Position(pos), tok, lit)
        }
}

S výsledkem, který je stále platnou sekvencí korektních tokenů (i když je původní kód nysmyslný):

2:1     var     "var"
2:5     IDENT   "x"
2:7     const   "const"
2:13    <       ""
2:15    INT     "1"
2:17    &&      ""
2:20    +       ""
2:22    INT     "2"
2:24    *       ""
2:26    ||      ""
2:29    INT     "3"
2:31    ;       "\n"
2:31    COMMENT "// nejlepší kód"
<EOF>

Dokonce je možné tokenizéru předat i kód obsahující neznámé znaky, resp. přesněji řečeno znaky, které nemají v gramatice jazyka Go žádný význam. Zde konkrétně se jedná o pokus o použití ternárního operátoru známého například z jazyka C:

package main
 
import (
        "fmt"
        "go/scanner"
        "go/token"
)
 
// zdrojový kód, který má být tokenizován
const source = `
var x int = 2 < 3 ? 10 : 20
`
 
func main() {
        // objekt představující scanner
        var s scanner.Scanner
 
        // struktura reprezentující množinu zdrojových kódů
        fset := token.NewFileSet()
 
        // přidání informace o zdrojovém kódu
        file := fset.AddFile("", fset.Base(), len(source))
 
        // inicializace scanneru
        s.Init(file, []byte(source), nil, scanner.ScanComments)
 
        // postupné provádění tokenizace a výpis jednotlivých tokenů
        for {
                pos, tok, lit := s.Scan()
                // byl nalezen speciální token reprezentující konec tokenizace
                if tok == token.EOF {
                        fmt.Println("")
                        break
                }
                // výpis obsahu tokenu
                fmt.Printf("%s\t%s\t%q\n", fset.Position(pos), tok, lit)
        }
 
}

V tomto případě se vypíše i neznámý token, a to včetně jeho hodnoty:

2:1     var     "var"
2:5     IDENT   "x"
2:7     IDENT   "int"
2:11    =       ""
2:13    INT     "2"
2:15    <       ""
2:17    INT     "3"
2:19    ILLEGAL "?"
2:21    INT     "10"
2:24    :       ""
2:26    INT     "20"
2:28    ;       "\n"
Poznámka: teoreticky je tedy možné už na úrovni tokenizéru rozšiřovat syntaxi programovacího jazyka Go o další operátory – i když se na této úrovni abstrakce jedná o relativně složitou operaci, kterou je lepší provádět až na úrovni abstraktního syntaktického stromu neboli AST (pokud je to možné). Podobně je tomu u nástrojů pro kontrolu kódů – některé operace lze efektivně provádět již na úrovni sekvence tokenů, další pak až nad AST.

4. Syntaktická analýza (parsing) a abstraktní syntaktický strom

Již v úvodní kapitole jsme si řekli, že lexikální analýza, jejímž výsledkem je sekvence tokenů, tvoří základ pro syntaktickou analýzu. Nástroj, který syntaktickou analýzu provádí, se většinou nazývá parser a proto se taktéž někdy setkáme s pojmem parsing (ten je ovšem chybně používán i v těch případech, kdy se provádí „pouze“ lexikální analýza). Výsledkem činnosti parseru je vhodně zvolená datová struktura, která popisuje gramatickou strukturu programu – tedy ne již pouhou lineární sekvenci tokenů, ale větší celky programu, které se (typicky rekurzivně) skládají z menších celků (druhým výsledkem může být chyba v případě, že zdrojový obsahuje syntaktickou chybu). Vzhledem k obecně rekurzivnímu charakteru této datové struktury se velmi často setkáme s použitím derivačních stromů nebo (častěji) s abstraktními syntaktickými stromy (abstract syntax tree neboli AST). Vytvořeným stromem je možné procházet různými způsoby, nejčastěji algoritmem prohledávání do hloubky (depth-first search). I tento algoritmus je již ve standardní knihovně programovacího jazyka Go implementován a můžeme ho přímo použít.

5. Syntaktická analýza v Go – balíčky go/token a go/parser

Nyní jsme se již seznámili se základními informacemi o tom, co je to abstraktní syntaktický strom a z jakých dat (prvků, uzlů) je tvořen. Pojďme si tedy ukázat způsob konstrukce abstraktního datového stromu s využitím operací dostupných v základních knihovnách programovacího jazyka Go. První demonstrační příklad z této oblasti zajistí lexikální i syntaktickou analýzu předaného zdrojového kódu a tisk obsahu abstraktního syntaktického stromu na standardní výstup:

package main
 
import (
        "fmt"
        "log"
 
        "go/parser"
        "go/token"
)
 
// zdrojový kód, který se má naparsovat
const source = `
package main
 
var answer int = 42
`
 
func main() {
        // struktura reprezentující množinu zdrojových kódů
        fileSet := token.NewFileSet()
 
        // konstrukce parseru a parsing zdrojového kódu
        f, err := parser.ParseFile(fileSet, "", source, parser.AllErrors)
        if err != nil {
                log.Fatal(err)
        }
 
        // výpis hodnoty typu *ast.File
        fmt.Printf("%#v", f)
}

Obsah abstraktního binárního stromu vypsaného tímto jednoduchým programem je však dosti nečitelný – v podstatě se totiž jedná o tisk metainformací o právě naparsované části kódu:

&ast.File{Doc:(*ast.CommentGroup)(nil), Package:2, Name:(*ast.Ident)(0xc0000c2000), Decls:[]ast.Decl{(*ast.GenDecl)(0xc0000b6080)}, Scope:(*ast.Scope)(0xc00009e290), Imports:[]*ast.ImportSpec(nil), Unresolved:[]*ast.Ident{(*ast.Ident)(0xc0000c2040)}, Comments:[]*ast.CommentGroup(nil)}

6. Čitelný výpis obsahu abstraktního syntaktického stromu

AST je ovšem možné vypsat i způsobem, který je mnohem čitelnější, než předchozí jednořádkový text. K tomuto účelu slouží funkce nazvaná Print z balíčku go/ast. Konkrétní způsob zavolání této funkce vypadá následovně:

// čitelný výpis obsahu abstraktního syntaktického stromu
err = ast.Print(fileSet, f)

Vidíme, že funkci je nutné předat jak strukturu reprezentující množinu zdrojových kódů, tak i vlastní výsledek činnosti parseru.

Nyní je již obsah abstraktního syntaktického stromu zobrazen v čitelnější podobě, a to včetně podrobnějších informací o jednotlivých tokenech, které tvoří uzly tohoto stromu:

     0  *ast.File {
     1  .  Package: 2:1
     2  .  Name: *ast.Ident {
     3  .  .  NamePos: 2:9
     4  .  .  Name: "main"
     5  .  }
     6  .  Decls: []ast.Decl (len = 1) {
     7  .  .  0: *ast.GenDecl {
     8  .  .  .  TokPos: 4:1
     9  .  .  .  Tok: var
    10  .  .  .  Lparen: -
    11  .  .  .  Specs: []ast.Spec (len = 1) {
    12  .  .  .  .  0: *ast.ValueSpec {
    13  .  .  .  .  .  Names: []*ast.Ident (len = 1) {
    14  .  .  .  .  .  .  0: *ast.Ident {
    15  .  .  .  .  .  .  .  NamePos: 4:5
    16  .  .  .  .  .  .  .  Name: "answer"
    17  .  .  .  .  .  .  .  Obj: *ast.Object {
    18  .  .  .  .  .  .  .  .  Kind: var
    19  .  .  .  .  .  .  .  .  Name: "answer"
    20  .  .  .  .  .  .  .  .  Decl: *(obj @ 12)
    21  .  .  .  .  .  .  .  .  Data: 0
    22  .  .  .  .  .  .  .  }
    23  .  .  .  .  .  .  }
    24  .  .  .  .  .  }
    25  .  .  .  .  .  Type: *ast.Ident {
    26  .  .  .  .  .  .  NamePos: 4:12
    27  .  .  .  .  .  .  Name: "int"
    28  .  .  .  .  .  }
    29  .  .  .  .  .  Values: []ast.Expr (len = 1) {
    30  .  .  .  .  .  .  0: *ast.BasicLit {
    31  .  .  .  .  .  .  .  ValuePos: 4:18
    32  .  .  .  .  .  .  .  Kind: INT
    33  .  .  .  .  .  .  .  Value: "42"
    34  .  .  .  .  .  .  }
    35  .  .  .  .  .  }
    36  .  .  .  .  }
    37  .  .  .  }
    38  .  .  .  Rparen: -
    39  .  .  }
    40  .  }
    41  .  Scope: *ast.Scope {
    42  .  .  Objects: map[string]*ast.Object (len = 1) {
    43  .  .  .  "answer": *(obj @ 17)
    44  .  .  }
    45  .  }
    46  .  Unresolved: []*ast.Ident (len = 1) {
    47  .  .  0: *(obj @ 25)
    48  .  }
    49  }

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

package main
 
import (
        "log"
 
        "go/ast"
        "go/parser"
        "go/token"
)
 
// zdrojový kód, který se má naparsovat
const source = `
package main
 
var answer int = 42
`
 
func main() {
        // struktura reprezentující množinu zdrojových kódů
        fileSet := token.NewFileSet()
 
        // konstrukce parseru a parsing zdrojového kódu
        f, err := parser.ParseFile(fileSet, "", source, parser.AllErrors)
        if err != nil {
                log.Fatal(err)
        }
 
        // čitelný výpis obsahu abstraktího syntaktického stromu
        err = ast.Print(fileSet, f)
        if err != nil {
                panic(err)
        }
}

7. Průchod abstraktním syntaktickým stromem

V předchozích kapitolách jsme si řekli, že se abstraktním syntaktickým stromem může procházet, a to dokonce několika různými způsoby. Základní metoda spočívá procházením stromem do šířky (tedy po jednotlivých vrstvách neboli úrovních), druhá metoda pak průchodem do hloubky (vždy se postupuje na potomky právě zpracovávaného vrcholu). A právě průchod do hloubky, který dokáže velmi dobře vizuálně „zviditelnit“ strukturu stromu, je implementován i v základní knihovně programovacího jazyka Go. Tento algoritmus je obsažen v balíčku go/ast, a to konkrétně funkcemi Inspect a Walk:

func Walk(v Visitor, node Node)
func Inspect(node Node, f func(Node) bool)

Nejprve si vyzkoušíme metodu Inspect, které se předá callback funkce, jenž je postupně volaná pro všechny uzly AST. Pokud tato funkce vrátí hodnotu true, zavolá se tato funkce rekurzivně pro potomky daného uzlu. Potomci ovšem mohou mít hodnotu nil, a to v případě, že jejich předek je koncovým uzlem (listem). Postačuje nám tedy testovat, zda je uzel nil či nikoli a podle toho řídit průchod stromem. Nejjednodušší podoba callback funkce tedy může vypadat takto:

func inspectCallback(n ast.Node) bool {
        // dosáhli jsme koncového uzlu?
        if n == nil {
                return false
        }
 
        // tisk typu uzlu
        fmt.Printf("%T\n", n)
        return true
}

Výsledek postupného volání callback funkce nazvané inspectCallback:

*ast.File
*ast.Ident
*ast.GenDecl
*ast.ValueSpec
*ast.Ident
*ast.Ident
*ast.BasicLit

Opět si ukažme úplný zdrojový kód demonstračního příkladu popsaného v této kapitole:

package main
 
import (
        "fmt"
        "log"
 
        "go/ast"
        "go/parser"
        "go/token"
)
 
// zdrojový kód, který se má naparsovat
const source = `
package main
 
var answer int = 42
`
 
// funkce volaná při průchodu AST
func inspectCallback(n ast.Node) bool {
        // dosáhli jsme koncového uzlu?
        if n == nil {
                return false
        }
 
        // tisk typu uzlu
        fmt.Printf("%T\n", n)
        return true
}
 
func main() {
        // struktura reprezentující množinu zdrojových kódů
        fileSet := token.NewFileSet()
 
        // konstrukce parseru a parsing zdrojového kódu
        f, err := parser.ParseFile(fileSet, "", source, parser.AllErrors)
        if err != nil {
                log.Fatal(err)
        }
 
        // zahájení průchodu abstraktním syntaktickým stromem
        ast.Inspect(f, inspectCallback)
}

8. Návrhový vzor Visitor

Abstraktní syntaktické stromy jsou pojmenovány korektně, protože skutečně reprezentují stromovou strukturu. Tuto strukturu je možné vizualizovat, a to různými způsoby. Kromě použití funkce ast.Inspect můžeme použít i funkci ast.Walk, díky níž lze realizovat návrhový vzor Visitor. Funkci ast.Walk se předává objekt typu Visitor, což je datový typ nesoucí informace o hloubce zanoření. Tento datový typ musí mít předepsánu metodu Visit, které se předává uzel stromu a která vrací nový objekt typu Visitor určený pro zpracování dalšího poduzlu:

// nový datový typ implementující rozhraní ast.Visitor
type visitor int
 
// implementace (jediné) funkce předepsané v rozhraní ast.Visitor
func (v visitor) Visit(n ast.Node) ast.Visitor {
        // dosáhli jsme koncového uzlu?
        if n == nil {
                return nil
        }
 
        // ještě jsme nedosáhli jsme koncového uzlu?
        return v + 1
}

V tom nejjednodušším možném případě můžeme zobrazit pouze typ uzlu, tj. o jaký token se jedná (viz zvýrazněný programový řádek):

func (v visitor) Visit(n ast.Node) ast.Visitor {
        // dosáhli jsme koncového uzlu?
        if n == nil {
                return nil
        }
 
        // tisk pozice a typu uzlu
        fmt.Printf("%T\n", n)
        return v + 1
}

Výsledek bude vypadat následovně – zobrazí se skutečně pouze jednotlivé tokeny, nikoli struktura AST:

*ast.File
*ast.Ident
*ast.GenDecl
*ast.ValueSpec
*ast.Ident
*ast.Ident
*ast.BasicLit

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

package main
 
import (
        "fmt"
        "log"
 
        "go/ast"
        "go/parser"
        "go/token"
)
 
// zdrojový kód, který se má naparsovat
const source = `
package main
 
var answer int = 42
`
 
// nový datový typ implementující rozhraní ast.Visitor
type visitor int
 
// implementace (jediné) funkce předepsané v rozhraní ast.Visitor
func (v visitor) Visit(n ast.Node) ast.Visitor {
        // dosáhli jsme koncového uzlu?
        if n == nil {
                return nil
        }
 
        // tisk pozice a typu uzlu
        fmt.Printf("%T\n", n)
        return v + 1
}
 
func main() {
        // struktura reprezentující množinu zdrojových kódů
        fileSet := token.NewFileSet()
 
        // konstrukce parseru a parsing zdrojového kódu
        f, err := parser.ParseFile(fileSet, "", source, parser.AllErrors)
        if err != nil {
                log.Fatal(err)
        }
 
        var v visitor
 
        // zahájení průchodu abstraktním syntaktickým stromem
        ast.Walk(v, f)
}

9. Zobrazení hloubky uzlu v AST

Jeden ze způsobů vylepšeného zobrazení AST spočívá v tom, že postupně vypisujeme jednotlivé uzly stromu, které jsou podle hloubky odlišeny odsazením. Hloubku stromu je navíc možné zvýraznit i celým číslem, přičemž kořen má většinou hodnotu 1, uzly napojené přímo na kořen hodnotu 2 atd.

// implementace (jediné) funkce předepsané v rozhraní ast.Visitor
func (v visitor) Visit(n ast.Node) ast.Visitor {
        // dosáhli jsme koncového uzlu?
        if n == nil {
                return nil
        }
 
        // tisk pozice a typu uzlu
        fmt.Printf("%3d\t", v)
        fmt.Printf("%s%T\n", strings.Repeat("\t", int(v)), n)
        return v + 1
}

S výsledkem, který již skutečně připomíná stromovou strukturu:

  0     *ast.File
  1             *ast.Ident
  1             *ast.GenDecl
  2                     *ast.ValueSpec
  3                             *ast.Ident
  3                             *ast.Ident
  3                             *ast.BasicLit

Opět si ukažme, jak by mohl vypadat úplný zdrojový kód demonstračního příkladu, který AST tímto způsobem zobrazí:

package main
 
import (
        "fmt"
        "log"
        "strings"
 
        "go/ast"
        "go/parser"
        "go/token"
)

// zdrojový kód, který se má naparsovat
const source = `
package main
 
var answer int = 42
`
 
// nový datový typ implementující rozhraní ast.Visitor
type visitor int
 
// implementace (jediné) funkce předepsané v rozhraní ast.Visitor
func (v visitor) Visit(n ast.Node) ast.Visitor {
        // dosáhli jsme koncového uzlu?
        if n == nil {
                return nil
        }
 
        // tisk pozice a typu uzlu
        fmt.Printf("%3d\t", v)
        fmt.Printf("%s%T\n", strings.Repeat("\t", int(v)), n)
        return v + 1
}
 
func main() {
        // struktura reprezentující množinu zdrojových kódů
        fileSet := token.NewFileSet()
 
        // konstrukce parseru a parsing zdrojového kódu
        f, err := parser.ParseFile(fileSet, "", source, parser.AllErrors)
        if err != nil {
                log.Fatal(err)
        }
 
        var v visitor
 
        // zahájení průchodu abstraktním syntaktickým stromem
        ast.Walk(v, f)
}

10. Koncové uzly v AST

Pro zajímavost se podívejme, co se stane, pokud se pokusíme vypsat hodnotu uzlu typu nil. Víme již, že se jedná o (virtuální) potomky koncových uzlů stromu a přístup k nim máme například proto, aby bylo možné AST modifikovat – přidávat do něj další uzly atd. Samotný výpis neexistujících potomků koncových uzlů je triviální a navíc (minimálně v případě programovacího jazyka Go) i bezpečný:

// implementace (jediné) funkce předepsané v rozhraní ast.Visitor
func (v visitor) Visit(n ast.Node) ast.Visitor {
        // dosáhli jsme koncového uzlu?
        if n == nil {
 
                // tisk pozice a typu uzlu
                fmt.Printf("%3d\t", v)
                fmt.Printf("%s%T\n", strings.Repeat("\t", int(v)), n)
                return nil
        }
 
        // tisk pozice a typu uzlu
        fmt.Printf("%3d\t", v)
        fmt.Printf("%s%T\n", strings.Repeat("\t", int(v)), n)
        return v + 1
}
Poznámka: povšimněte si, jak je s využitím funkce strings.Repeat zařízeno odsazení uzlů podle jejich umístění v AST (tedy podle vrstvy, v níž se uzly nachází).

Nyní bude pod každým koncovým uzlem zobrazena ještě informace, že tento uzel již nemá žádné další potomky (nil má vždy o jedničku nižší úroveň, než koncový uzel):

  0     *ast.File
  1             *ast.Ident
  2                     <nil>
  1             *ast.GenDecl
  2                     *ast.ValueSpec
  3                             *ast.Ident
  4                                     <nil>
  3                             *ast.Ident
  4                                     <nil>
  3                             *ast.BasicLit
  4                                     <nil>
  3                             <nil>
  2                     <nil>
  1             <nil>

Následuje výpis zdrojového kódu příkladu, který po svém spuštění zobrazí výše uvedený AST:

package main
 
import (
        "fmt"
        "log"
        "strings"
 
        "go/ast"
        "go/parser"
        "go/token"
)
 
// zdrojový kód, který se má naparsovat
const source = `
package main
 
var answer int = 42
`
 
// nový datový typ implementující rozhraní ast.Visitor
type visitor int
 
// implementace (jediné) funkce předepsané v rozhraní ast.Visitor
func (v visitor) Visit(n ast.Node) ast.Visitor {
        // dosáhli jsme koncového uzlu?
        if n == nil {
 
                // tisk pozice a typu uzlu
                fmt.Printf("%3d\t", v)
                fmt.Printf("%s%T\n", strings.Repeat("\t", int(v)), n)
                return nil
        }
 
        // tisk pozice a typu uzlu
        fmt.Printf("%3d\t", v)
        fmt.Printf("%s%T\n", strings.Repeat("\t", int(v)), n)
        return v + 1
}
 
func main() {
        // struktura reprezentující množinu zdrojových kódů
        fileSet := token.NewFileSet()
 
        // konstrukce parseru a parsing zdrojového kódu
        f, err := parser.ParseFile(fileSet, "", source, parser.AllErrors)
        if err != nil {
                log.Fatal(err)
        }
 
        var v visitor
 
        // zahájení průchodu abstraktním syntaktickým stromem
        ast.Walk(v, f)
}

11. AST zkonstruovaný pro sekvenci příkazů

Abstraktní syntaktický strom je možné zkonstruovat (a zobrazit) pro libovolně komplikovaný zdrojový kód, popř. dokonce i pro celý modul. Ukažme si to na kódu s deklarací package a definicí trojice globálních proměnných, z nichž poslední je inicializována pomocí výrazu:

package main
 
var x int = 6
var y int = 7
var answer int = x * y

Program, který po svém spuštění vypíše AST pro výše uvedený programový kód:

package main
 
import (
        "fmt"
        "log"
        "strings"
 
        "go/ast"
        "go/parser"
        "go/token"
)
 
// zdrojový kód, který se má naparsovat
const source = `
package main
 
var x int = 6
var y int = 7
var answer int = x * y
`
 
// nový datový typ implementující rozhraní ast.Visitor
type visitor int
 
// implementace (jediné) funkce předepsané v rozhraní ast.Visitor
func (v visitor) Visit(n ast.Node) ast.Visitor {
        // dosáhli jsme koncového uzlu?
        if n == nil {
 
                // tisk pozice a typu uzlu
                fmt.Printf("%3d\t", v)
                fmt.Printf("%s%T\n", strings.Repeat("\t", int(v)), n)
                return nil
        }
 
        // tisk pozice a typu uzlu
        fmt.Printf("%3d\t", v)
        fmt.Printf("%s%T\n", strings.Repeat("\t", int(v)), n)
        return v + 1
}
 
func main() {
        // struktura reprezentující množinu zdrojových kódů
        fileSet := token.NewFileSet()
 
        // konstrukce parseru a parsing zdrojového kódu
        f, err := parser.ParseFile(fileSet, "", source, parser.AllErrors)
        if err != nil {
                log.Fatal(err)
        }
 
        var v visitor
 
        // zahájení průchodu abstraktním syntaktickým stromem
        ast.Walk(v, f)
}

Nyní již bude AST relativně komplikovaný. Povšimněte si, že se stále jedná o strom, protože kořenovým uzlem je uzel ast.File (což původně ani není token):

  0     *ast.File
  1             *ast.Ident
  2                     <nil>
  1             *ast.GenDecl
  2                     *ast.ValueSpec
  3                             *ast.Ident
  4                                     <nil>
  3                             *ast.Ident
  4                                     <nil>
  3                             *ast.BasicLit
  4                                     <nil>
  3                             <nil>
  2                     <nil>
  1             *ast.GenDecl
  2                     *ast.ValueSpec
  3                             *ast.Ident
  4                                     <nil>
  3                             *ast.Ident
  4                                     <nil>
  3                             *ast.BasicLit
  4                                     <nil>
  3                             <nil>
  2                     <nil>
  1             *ast.GenDecl
  2                     *ast.ValueSpec
  3                             *ast.Ident
  4                                     <nil>
  3                             *ast.Ident
  4                                     <nil>
  3                             *ast.BinaryExpr
  4                                     *ast.Ident
  5                                             <nil>
  4                                     *ast.Ident
  5                                             <nil>
  4                                     <nil>
  3                             <nil>
  2                     <nil>
  1             <nil>

12. Výrazy se závorkami a s různými prioritami operátorů

Pro aritmetické, logické atd. výrazy se v AST uzly konstruují takovým způsobem, aby poduzly představovaly podvýrazy s nižší prioritou a naopak – nejvyšší uzel v podstromu, který odpovídá výrazu, bude obsahovat aritmetickou či logickou operaci s prioritou nejvyšší. Například pro výraz:

(1 + x) * (2 + y)

By měl příslušný podstrom vypadat takto:

*ast.BinaryExpr
        *ast.ParenExpr
                *ast.BinaryExpr
                        *ast.BasicLit
                                <nil>
                        *ast.Ident
                                <nil>
                        <nil>
                <nil>
        *ast.ParenExpr
                *ast.BinaryExpr
                        *ast.BasicLit
                                <nil>
                        *ast.Ident
                                <nil>
                        <nil>
                <nil>
        <nil>

Tento předpoklad si můžeme snadno otestovat, a to spuštěním následujícího demonstračního příkladu:

package main
 
import (
        "fmt"
        "log"
        "strings"
 
        "go/ast"
        "go/parser"
        "go/token"
)
 
// zdrojový kód, který se má naparsovat
const source = `
package main
 
var x int = 5
var y int = 6
var answer int = (1 + x) * (2 + y)
`
 
// nový datový typ implementující rozhraní ast.Visitor
type visitor int
 
// implementace (jediné) funkce předepsané v rozhraní ast.Visitor
func (v visitor) Visit(n ast.Node) ast.Visitor {
        // dosáhli jsme koncového uzlu?
        if n == nil {
 
                // tisk pozice a typu uzlu
                fmt.Printf("%3d\t", v)
                fmt.Printf("%s%T\n", strings.Repeat("\t", int(v)), n)
                return nil
        }
 
        // tisk pozice a typu uzlu
        fmt.Printf("%3d\t", v)
        fmt.Printf("%s%T\n", strings.Repeat("\t", int(v)), n)
        return v + 1
}
 
func main() {
        // struktura reprezentující množinu zdrojových kódů
        fileSet := token.NewFileSet()
 
        // konstrukce parseru a parsing zdrojového kódu
        f, err := parser.ParseFile(fileSet, "", source, parser.AllErrors)
        if err != nil {
                log.Fatal(err)
        }
 
        var v visitor
 
        // zahájení průchodu abstraktním syntaktickým stromem
        ast.Walk(v, f)
}

S výsledkem:

  0     *ast.File
  1             *ast.Ident
  2                     <nil>
  1             *ast.GenDecl
  2                     *ast.ValueSpec
  3                             *ast.Ident
  4                                     <nil>
  3                             *ast.Ident
  4                                     <nil>
  3                             *ast.BasicLit
  4                                     <nil>
  3                             <nil>
  2                     <nil>
  1             *ast.GenDecl
  2                     *ast.ValueSpec
  3                             *ast.Ident
  4                                     <nil>
  3                             *ast.Ident
  4                                     <nil>
  3                             *ast.BasicLit
  4                                     <nil>
  3                             <nil>
  2                     <nil>
  1             *ast.GenDecl
  2                     *ast.ValueSpec
  3                             *ast.Ident
  4                                     <nil>
  3                             *ast.Ident
  4                                     <nil>
  3                             *ast.BinaryExpr
  4                                     *ast.ParenExpr
  5                                             *ast.BinaryExpr
  6                                                     *ast.BasicLit
  7                                                             <nil>
  6                                                     *ast.Ident
  7                                                             <nil>
  6                                                     <nil>
  5                                             <nil>
  4                                     *ast.ParenExpr
  5                                             *ast.BinaryExpr
  6                                                     *ast.BasicLit
  7                                                             <nil>
  6                                                     *ast.Ident
  7                                                             <nil>
  6                                                     <nil>
  5                                             <nil>
  4                                     <nil>
  3                             <nil>
  2                     <nil>
  1             <nil>

13. Konstrukce AST pro jediný výraz

Prozatím jsme si ukázali, jakým způsobem lze sestrojit AST pro úplný zdrojový kód. Ovšem existují situace, kdy je vhodné sestrojit AST pouze pro jediný výraz. I to je možné, a to náhradou funkce parser.ParseFile:

f, err := parser.ParseFile(fileSet, "", source, parser.AllErrors)

za volání funkce parser.ParseExpr:

f, err := parser.ParseExpr(source)

V obou případech je v konstantě či proměnné source uložen zdrojový kód resp. jediný výraz (ve druhém případě).

Další příklad slouží pro zobrazení AST vytvořeného pro výraz:

(1 + x) * (2 + y)

Zdrojový kód:

package main
 
import (
        "fmt"
        "log"
        "strings"
 
        "go/ast"
        "go/parser"
)
 
// výraz, který se má naparsovat
const source = `
(1 + x) * (2 + y)
`
 
// nový datový typ implementující rozhraní ast.Visitor
type visitor int
 
// implementace (jediné) funkce předepsané v rozhraní ast.Visitor
func (v visitor) Visit(n ast.Node) ast.Visitor {
        // dosáhli jsme koncového uzlu?
        if n == nil {
 
                // tisk pozice a typu uzlu
                fmt.Printf("%3d\t", v)
                fmt.Printf("%s%T\n", strings.Repeat("\t", int(v)), n)
                return nil
        }
 
        // tisk pozice a typu uzlu
        fmt.Printf("%3d\t", v)
        fmt.Printf("%s%T\n", strings.Repeat("\t", int(v)), n)
        return v + 1
}
 
func main() {
        // konstrukce parseru a parsing zdrojového kódu
        f, err := parser.ParseExpr(source)
        if err != nil {
                log.Fatal(err)
        }
 
        var v visitor
 
        // zahájení průchodu abstraktním syntaktickým stromem
        ast.Walk(v, f)
}

Výsledek bude vypadat následovně:

  0     *ast.BinaryExpr
  1             *ast.ParenExpr
  2                     *ast.BinaryExpr
  3                             *ast.BasicLit
  4                                     <nil>
  3                             *ast.Ident
  4                                     <nil>
  3                             <nil>
  2                     <nil>
  1             *ast.ParenExpr
  2                     *ast.BinaryExpr
  3                             *ast.BasicLit
  4                                     <nil>
  3                             *ast.Ident
  4                                     <nil>
  3                             <nil>
  2                     <nil>
  1             <nil>

14. Typy uzlů v AST

V abstraktním syntaktickém stromu se mohou nacházet různé typy uzlů. Některé uzly přímo odpovídají tokenům nalezeným ve zdrojovém kódu, další typy uzlů (například ast.File) jsou vytvořeny automaticky při konstrukci AST. Všechny typy uzlů jsou deklarovány přímo v balíčku go/ast a pro všechny uzly platí, že metodami Pos a End je možné získat jejich umístění v rámci sekvence tokenů (což je v některých případech důležité – prozatím však ne pro nás, alespoň dnes ne).

Jedná se o tyto typy (podrobněji budou popsány příště):

Typ uzlu v AST
ArrayType
AssignStmt
BadDecl
BadExpr
BadStmt
BasicLit
BinaryExpr
BlockStmt
BranchStmt
CallExpr
CaseClause
ChanDir
ChanType
CommClause
Comment
CommentGroup
CompositeLit
Decl
DeclStmt
DeferStmt
Ellipsis
EmptyStmt
Expr
ExprStmt
Field
FieldFilter
FieldList
File
Filter
ForStmt
FuncDecl
FuncLit
FuncType
GenDecl
GoStmt
Ident
IfStmt
ImportSpec
Importer
IncDecStmt
IndexExpr
InterfaceType
KeyValueExpr
LabeledStmt
MapType
MergeMode
Node
ObjKind
Package
ParenExpr
RangeStmt
ReturnStmt
Scope
SelectStmt
SelectorExpr
SendStmt
SliceExpr
Spec
StarExpr
Stmt
StructType
SwitchStmt
TypeAssertExpr
TypeSpec
TypeSwitchStmt
UnaryExpr
ValueSpec

Při průchodu AST lze na základě typu konkrétního uzlu zvolit, jaké informace se vypíšou, popř. jak se daný uzel zpracuje. Nejjednodušší (i když nesnadno rozšiřitelný) je následující přístup spočívající v rozeskoku podle typu uzlu:

switch x := n.(type) {
case *ast.BasicLit:
        s = "Literal: " + x.Value
case *ast.Ident:
        s = "Identifier: " + x.Name
case *ast.BinaryExpr:
        s = "Binary operator: " + x.Op.String()
case *ast.ParenExpr:
        s = "Expression in parenthesis"
}
Poznámka: připomeňme si, že v Go není nutné explicitně použít příkaz break pro ukončení jednotlivých větví.

15. Podrobnější výpis informací o uzlech v AST

V dalším demonstračním příkladu jsou postupně vypisovány jednotlivé uzly z AST, přičemž u čtyř známých typů uzlů (což je konkrétně literál, identifikátor, binární operátor a závorky) jsou vypisovány i podrobnější informace. Opět budeme vypisovat AST pro jednoduchý aritmetický výraz:

(1 + x) * (2 + y)

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

package main
 
import (
        "fmt"
        "log"
        "strings"
 
        "go/ast"
        "go/parser"
)
 
// výraz, který se má naparsovat
const source = `
(1 + x) * (2 + y)
`
 
// nový datový typ implementující rozhraní ast.Visitor
type visitor int
 
// implementace (jediné) funkce předepsané v rozhraní ast.Visitor
func (v visitor) Visit(n ast.Node) ast.Visitor {
        // dosáhli jsme koncového uzlu?
        if n == nil {
                return nil
        }
 
        // tisk pozice a typu uzlu
        fmt.Printf("%3d\t", v)
        var s string
 
        switch x := n.(type) {
        case *ast.BasicLit:
                s = "Literal: " + x.Value
        case *ast.Ident:
                s = "Identifier: " + x.Name
        case *ast.BinaryExpr:
                s = "Binary operator: " + x.Op.String()
        case *ast.ParenExpr:
                s = "Expression in parenthesis"
        }
 
        indent := strings.Repeat("\t", int(v))
        if s != "" {
                fmt.Printf("%s%s\n", indent, s)
        } else {
                fmt.Printf("%s%T\n", indent, n)
        }
        return v + 1
}
 
func main() {
        // konstrukce parseru a parsing zdrojového kódu
        f, err := parser.ParseExpr(source)
        if err != nil {
                log.Fatal(err)
        }
 
        var v visitor
 
        // zahájení průchodu abstraktním syntaktickým stromem
        ast.Walk(v, f)
}

A výsledkem činnosti tohoto příkladu je již velmi čitelný obsah AST:

  0     Binary operator: *
  1             Expression in parenthesis
  2                     Binary operator: +
  3                             Literal: 1
  3                             Identifier: x
  1             Expression in parenthesis
  2                     Binary operator: +
  3                             Literal: 2
  3                             Identifier: y

16. Složitější aritmetické výrazy, zjednodušení zobrazení AST

Aritmetické výrazy mohou být pochopitelně složitější, mohou obsahovat unární operátory atd. Opět si tedy ukážeme příklad převodu výrazu na AST. Tentokrát se bude jednat o tento výraz:

((1 + x * 2) * -(2 + y / -z)) % (x + -y + -z)

Do zdrojového kódu je nutné do rozeskoku (switch) přidat další větev, tentokrát pro unární operátor(y):

case *ast.UnaryExpr:
        s = "Unary operator: " + x.Op.String()

Úplný zdrojový kód:

package main
 
import (
        "fmt"
        "log"
        "strings"
 
        "go/ast"
        "go/parser"
)

// výraz, který se má naparsovat
const source = `
((1 + x * 2) * -(2 + y / -z)) % (x + -y + -z)
`
 
// nový datový typ implementující rozhraní ast.Visitor
type visitor int
 
// implementace (jediné) funkce předepsané v rozhraní ast.Visitor
func (v visitor) Visit(n ast.Node) ast.Visitor {
        // dosáhli jsme koncového uzlu?
        if n == nil {
                return nil
        }
 
        // tisk pozice a typu uzlu
        fmt.Printf("%3d\t", v)
        var s string
 
        switch x := n.(type) {
        case *ast.BasicLit:
                s = "Literal: " + x.Value
        case *ast.Ident:
                s = "Identifier: " + x.Name
        case *ast.UnaryExpr:
                s = "Unary operator: " + x.Op.String()
        case *ast.BinaryExpr:
                s = "Binary operator: " + x.Op.String()
        case *ast.ParenExpr:
                s = "Expression in parenthesis"
        }
 
        indent := strings.Repeat("\t", int(v))
        if s != "" {
                fmt.Printf("%s%s\n", indent, s)
        } else {
                fmt.Printf("%s%T\n", indent, n)
        }
        return v + 1
}
 
func main() {
        // konstrukce parseru a parsing zdrojového kódu
        f, err := parser.ParseExpr(source)
        if err != nil {
                log.Fatal(err)
        }
 
        var v visitor
 
        // zahájení průchodu abstraktním syntaktickým stromem
        ast.Walk(v, f)
}

A výsledek, tedy AST (povšimněte si, že unární operátory mají skutečně jen jediný přímý poduzel):

  e     Binary operator: %
  1             Expression in parenthesis
  2                     Binary operator: *
  3                             Expression in parenthesis
  4                                     Binary operator: +
  5                                             Literal: 1
  5                                             Binary operator: *
  6                                                     Identifier: x
  6                                                     Literal: 2
  3                             Unary operator: -
  4                                     Expression in parenthesis
  5                                             Binary operator: +
  6                                                     Literal: 2
  6                                                     Binary operator: /
  7                                                             Identifier: y
  7                                                             Unary operator: -
  8                                                                     Identifier: z
  1             Expression in parenthesis
  2                     Binary operator: +
  3                             Binary operator: +
  4                                     Identifier: x
  4                                     Unary operator: -
  5                                             Identifier: y
  3                             Unary operator: -
  4                                     Identifier: z

Poměrně často se setkáme se zjednodušenou podobou AST, v níž se u operátorů pouze vypisují jejich jména a u hodnot pouze hodnoty, popř. jména identifikátorů:

  0     %
  1       (
  2         *
  3           (
  4             +
  5               1
  5               *
  6                 x
  6                 2
  3           -
  4             (
  5               +
  6                 2
  6                 /
  7                   y
  7                   -
  8                     z
  1       (
  2         +
  3           +
  4             x
  4             -
  5               y
  3           -
  4             z

Tohoto způsobu zobrazení lze dosáhnout velmi snadno, pouze úpravou příkazů v rozeskoku switch:

switch x := n.(type) {
case *ast.BasicLit:
        s = x.Value
case *ast.Ident:
        s = x.Name
case *ast.UnaryExpr:
        s = x.Op.String()
case *ast.BinaryExpr:
        s = x.Op.String()
case *ast.ParenExpr:
        s = "("
}

Pro úplnost je uveden i celý zdrojový kód takto upraveného demonstračního příkladu:

package main
 
import (
        "fmt"
        "log"
        "strings"
 
        "go/ast"
        "go/parser"
)
 
// výraz, který se má naparsovat
const source = `
((1 + x * 2) * -(2 + y / -z)) % (x + -y + -z)
`
 
// nový datový typ implementující rozhraní ast.Visitor
type visitor int
 
// implementace (jediné) funkce předepsané v rozhraní ast.Visitor
func (v visitor) Visit(n ast.Node) ast.Visitor {
        // dosáhli jsme koncového uzlu?
        if n == nil {
                return nil
        }
 
        // tisk pozice a typu uzlu
        fmt.Printf("%3d\t", v)
        var s string
 
        switch x := n.(type) {
        case *ast.BasicLit:
                s = x.Value
        case *ast.Ident:
                s = x.Name
        case *ast.UnaryExpr:
                s = x.Op.String()
        case *ast.BinaryExpr:
                s = x.Op.String()
        case *ast.ParenExpr:
                s = "("
        }
 
        indent := strings.Repeat("  ", int(v))
        if s != "" {
                fmt.Printf("%s%s\n", indent, s)
        } else {
                fmt.Printf("%s%T\n", indent, n)
        }
        return v + 1
}
 
func main() {
        // konstrukce parseru a parsing zdrojového kódu
        f, err := parser.ParseExpr(source)
        if err != nil {
                log.Fatal(err)
        }
 
        var v visitor
 
        // zahájení průchodu abstraktním syntaktickým stromem
        ast.Walk(v, f)
}

17. Logické výrazy

Samozřejmě je možné vytvořit a nechat si zobrazit AST i pro logický výraz, například pro tento jednoduchý výraz obsahující dvojici logických operací:

a && b || c

Zjednodušená podoba AST by v tomto případě mohla vypadat následovně:

  0     ||
  1       &&
  2         a
  2         b
  1       c

Tento AST byl vypsán následujícím prográmkem. Sami si můžete otestovat, jak se AST změní přidáním negace, závorek atd.:

package main
 
import (
        "fmt"
        "log"
        "strings"
 
        "go/ast"
        "go/parser"
)
 
// výraz, který se má naparsovat
const source = `
a && b || c
`
 
// nový datový typ implementující rozhraní ast.Visitor
type visitor int
 
// implementace (jediné) funkce předepsané v rozhraní ast.Visitor
func (v visitor) Visit(n ast.Node) ast.Visitor {
        // dosáhli jsme koncového uzlu?
        if n == nil {
                return nil
        }
 
        // tisk pozice a typu uzlu
        fmt.Printf("%3d\t", v)
        var s string
 
        switch x := n.(type) {
        case *ast.BasicLit:
                s = x.Value
        case *ast.Ident:
                s = x.Name
        case *ast.UnaryExpr:
                s = x.Op.String()
        case *ast.BinaryExpr:
                s = x.Op.String()
        case *ast.ParenExpr:
                s = "("
        }
 
        indent := strings.Repeat("  ", int(v))
        if s != "" {
                fmt.Printf("%s%s\n", indent, s)
        } else {
                fmt.Printf("%s%T\n", indent, n)
        }
        return v + 1
}
 
func main() {
        // konstrukce parseru a parsing zdrojového kódu
        f, err := parser.ParseExpr(source)
        if err != nil {
                log.Fatal(err)
        }
 
        var v visitor
 
        // zahájení průchodu abstraktním syntaktickým stromem
        ast.Walk(v, f)
}

18. Výrazy obsahující operace s poli či řezy

Ve výrazech, a to jak výrazech aritmetických, tak i logických, je pochopitelně možné použít operace s poli či s řezy (slice). Indexy jsou opět počítány, a to aritmetickým podvýrazem, o čemž se můžeme snadno přesvědčit, pokud si necháme vytvořit AST například pro tento výraz (kde není zřejmé, zda se jedná o součet či konkatenaci):

array1[10] + array2[x] + array3[a*b+c*d]

AST tohoto výrazu by ve své zjednodušené podobě mohl vypadat například takto:

  0     +
  1       +
  2         [
  3           array1
  3           10
  2         [
  3           array2
  3           x
  1       [
  2         array3
  2         +
  3           *
  4             a
  4             b
  3           *
  4             c
  4             d

Aby bylo možné tento AST zobrazit, je nutné opět rozšířit rozvětvení v příkazu switch o novou větev, konkrétně o větev ast.IndexExpr:

Hacking tip

switch x := n.(type) {
case *ast.BasicLit:
        s = x.Value
case *ast.Ident:
        s = x.Name
case *ast.UnaryExpr:
        s = x.Op.String()
case *ast.BinaryExpr:
        s = x.Op.String()
case *ast.IndexExpr:
        s = "["
case *ast.ParenExpr:
        s = "("
}

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

package main
 
import (
        "fmt"
        "log"
        "strings"
 
        "go/ast"
        "go/parser"
)
 
// výraz, který se má naparsovat
const source = `
array1[10] + array2[x] + array3[a*b+c*d]
`
 
// nový datový typ implementující rozhraní ast.Visitor
type visitor int
 
// implementace (jediné) funkce předepsané v rozhraní ast.Visitor
func (v visitor) Visit(n ast.Node) ast.Visitor {
        // dosáhli jsme koncového uzlu?
        if n == nil {
                return nil
        }
 
        // tisk pozice a typu uzlu
        fmt.Printf("%3d\t", v)
        var s string
 
        switch x := n.(type) {
        case *ast.BasicLit:
                s = x.Value
        case *ast.Ident:
                s = x.Name
        case *ast.UnaryExpr:
                s = x.Op.String()
        case *ast.BinaryExpr:
                s = x.Op.String()
        case *ast.IndexExpr:
                s = "["
        case *ast.ParenExpr:
                s = "("
        }
 
        indent := strings.Repeat("  ", int(v))
        if s != "" {
                fmt.Printf("%s%s\n", indent, s)
        } else {
                fmt.Printf("%s%T\n", indent, n)
        }
        return v + 1
}
 
func main() {
        // konstrukce parseru a parsing zdrojového kódu
        f, err := parser.ParseExpr(source)
        if err != nil {
                log.Fatal(err)
        }
 
        var v visitor
 
        // zahájení průchodu abstraktním syntaktickým stromem
        ast.Walk(v, f)
}

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

Zdrojové kódy všech dnes použitých demonstračních příkladů byly uloženy do nového Git repositáře, který je dostupný na adrese https://github.com/tisnik/go-root (stále na GitHubu :-). V případě, že nebudete chtít klonovat celý repositář (ten je ovšem – alespoň prozatím – velmi malý, dnes má přibližně stovku kilobajtů), můžete namísto toho použít odkazy na jednotlivé demonstrační příklady, které naleznete v následující tabulce:

# Příklad/soubor Stručný popis Cesta
1 ast01.go syntaktická analýza v Go – balíčky go/token a go/parser https://github.com/tisnik/go-root/blob/master/article82/ast01.go
2 ast02.go čitelný výpis obsahu abstraktního syntaktického stromu https://github.com/tisnik/go-root/blob/master/article82/ast02.go
3 ast03.go průchod abstraktním syntaktickým stromem https://github.com/tisnik/go-root/blob/master/article82/ast03.go
4 ast04.go návrhový vzor Visitor https://github.com/tisnik/go-root/blob/master/article82/ast04.go
5 ast05.go zobrazení hloubky uzlu v AST https://github.com/tisnik/go-root/blob/master/article82/ast05.go
6 ast06.go koncové uzly v AST https://github.com/tisnik/go-root/blob/master/article82/ast06.go
7 ast07.go AST zkonstruovaný pro sekvenci příkazů https://github.com/tisnik/go-root/blob/master/article82/ast07.go
8 ast08.go výrazy se závorkami a s různými prioritami operátorů https://github.com/tisnik/go-root/blob/master/article82/ast08.go
9 ast09.go konstrukce AST pro jediný výraz https://github.com/tisnik/go-root/blob/master/article82/ast09.go
10 ast10.go typy uzlů v AST https://github.com/tisnik/go-root/blob/master/article82/ast10.go
11 ast11.go podrobnější výpis informací o uzlech v AST https://github.com/tisnik/go-root/blob/master/article82/ast11.go
12 ast12.go složitější aritmetické výrazy, zjednodušení zobrazení AST https://github.com/tisnik/go-root/blob/master/article82/ast12.go
13 ast13.go logické výrazy https://github.com/tisnik/go-root/blob/master/article82/ast13.go
14 ast14.go výrazy obsahující operace s poli či řezy https://github.com/tisnik/go-root/blob/master/article82/ast14.go
       
15 lexer1.go tokenizace zdrojového kódu https://github.com/tisnik/go-root/blob/master/article82/lexer1.go
16 lexer2.go zahození komentářů při tokenizaci https://github.com/tisnik/go-root/blob/master/article82/lexer2.go
17 lexer3.go tokenizace nesmyslné sekvence identifikátorů https://github.com/tisnik/go-root/blob/master/article82/lexer3.go
18 lexer4.go tokenizace kódu s neznámými symboly https://github.com/tisnik/go-root/blob/master/article82/lexer4.go

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. Golang AST Package
    https://golangdocs.com/golang-ast-package
  5. Dokumentace k balíčku go/ast
    https://pkg.go.dev/go/ast
  6. Dokumentace k balíčku go/scanner
    https://pkg.go.dev/go/scanner
  7. Dokumentace k balíčku go/parser
    https://pkg.go.dev/go/parser
  8. Dokumentace k balíčku go/token
    https://pkg.go.dev/go/token
  9. AP8, IN8 Regulární jazyky
    http://statnice.dqd.cz/home:inf:ap8
  10. AP9, IN9 Konečné automaty
    http://statnice.dqd.cz/home:inf:ap9
  11. AP10, IN10 Bezkontextové jazyky
    http://statnice.dqd.cz/home:inf:ap10
  12. AP11, IN11 Zásobníkové automaty, Syntaktická analýza
    http://statnice.dqd.cz/home:inf:ap11
  13. Introduction to YACC
    https://www.geeksforgeeks­.org/introduction-to-yacc/
  14. Introduction of Lexical Analysis
    https://www.geeksforgeeks­.org/introduction-of-lexical-analysis/?ref=lbp
  15. Tvorba grafů a diagramů s využitím doménově specifického jazyka nástroje Graphviz
    https://www.root.cz/clanky/tvorba-grafu-a-diagramu-s-vyuzitim-domenove-specifickeho-jazyka-nastroje-graphviz/
  16. Popis příkazu gofmt
    https://pkg.go.dev/cmd/gofmt
  17. Popis příkazu govet
    https://pkg.go.dev/cmd/vet
  18. Repositář nástroje errcheck
    https://github.com/kisielk/errcheck
  19. Repositář nástroje goconst
    https://github.com/jgautheron/goconst
  20. Repositář nástroje gocyclo
    https://github.com/fzipp/gocyclo
  21. Repositář nástroje ineffassign
    https://github.com/gordon­klaus/ineffassign
  22. Repositář nástroje gosec
    https://github.com/securego/gosec
  23. Repositář nástroje go-critic
    https://github.com/go-critic/go-critic
  24. Seznam testů prováděných nástrojem go-critic
    https://go-critic.com/overview
  25. Welcome go-critic
    https://itnext.io/welcome-go-critic-a26b6e30f1c6
  26. Využití knihovny Pygments (nejenom) pro obarvení zdrojových kódů
    https://www.root.cz/clanky/vyuziti-knihovny-pygments-nejenom-pro-obarveni-zdrojovych-kodu/