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

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ánku o programovací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.

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í.

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.

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

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"

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
}

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ě):

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"
}

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:

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:

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/