Hlavní navigace

Lexikální a syntaktická analýza zdrojových kódů jazyka Go (2.část)

28. 12. 2021
Doba čtení: 37 minut

Sdílet

 Autor: Go lang
Minule jsme se zabývali balíčky určenými pro lexikální a syntaktickou analýzu. Ukážeme si, jak rekurzivně procházet AST, realizaci algoritmu pro převod výrazů z infixové notace na notaci postfixovou i způsob detekce volání funkcí v AST.

Obsah

1. Lexikální a syntaktická analýza zdrojových kódů jazyka Go (2.část)

2. Automatický průchod AST s výpisem aritmetických výrazů a podvýrazů

3. Explicitní průchod stromem – rekurzivní algoritmus

4. Rekurzivní průchod stromem s rekonstrukcí aritmetického výrazu v infixové podobě

5. Rozšíření předchozího kódu o zpracování výrazů se závorkami

6. Převod výrazů z infixové notace do notace postfixové

7. Převrácená polská notace

8. Algoritmus shunting-yard

9. Realizace algoritmu shunting-yard pro aritmetické výrazy programovacího jazyka Go

10. Realizace výpočtu aritmetického výrazu popsaného pomocí RPN

11. Algoritmus shunting-yard pro logické výrazy doplněné o porovnání (relační operátory)

12. Závorky v logických výrazech

13. Detekce volání funkcí při zpracování AST

14. Základní informace o argumentech volané funkce

15. Podrobnější informace o argumentech volané funkce

16. Informace o argumentech typu pole či řez (nějakého typu)

17. Rozlišení volání funkce od volání metody

18. Obsah navazujícího článku

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 (2.část)

V předchozím článku jsme si řekli základní informace o balíčcích ze standardní knihovny programovacího jazyka Go, které slouží k lexikální i syntaktické analýze zdrojových kódů Go, popř. jednotlivých výrazů. Připomeňme si, že tyto balíčky se jmenují go/scanner, go/ast a go/token. Taktéž jsme si ukázali získání sekvence tokenů ze zdrojového kódu a dokonce i konstrukci AST (abstraktního syntaktického stromu). Umíme též tímto stromem procházet, a to konkrétně pomocí již implementovaného algoritmu pro průchod stromem do hloubky (postačuje tento algoritmus využít; je založen na návrhovém vzoru visitor). Dnes si ukážeme, jakým způsobem je možné rekurzivně procházet AST, dále pak realizaci algoritmu pro převod výrazů z infixové notace na notaci postfixovou (RPN) a nakonec i způsob detekce volání funkcí v AST.

2. Automatický průchod AST s výpisem aritmetických výrazů a podvýrazů

Dnešní první demonstrační příklad, který do značné míry vychází z příkladů, které jsme si uvedli minule, ukazuje, jakým způsobem je možné automaticky procházet AST, přičemž se budou vypisovat informace o těch uzlech, které tvoří aritmetické výrazy obsahující základní aritmetické operace (těch je v Go pět), numerické konstanty a proměnné. Příklad takového výrazu:

1 + 2 * 3 + x + y * z - 1

Po konstrukci AST je možné zahájit průchod AST zavoláním funkce ast.Walk, tj. funkce, která je již předpřipravena ve standardním balíčku go/ast:

// hodnota typu visitor
var v visitor
 
// zahájení průchodu abstraktním syntaktickým stromem
ast.Walk(v, f)

AST se prochází metodou do hloubky a pro každý navštívený uzel stromu se zavolá funkce Visit, které se předá právě zpracovávaný uzel, popř. hodnota nil. Rozeznávat se budou uzly čtyř typů (což je hodně zjednodušené):

Typ uzlu Popis
ast.BasicLit konstanta/číselný literál
ast.Ident identifikátor (typicky identifikátor funkce)
ast.UnaryExpr unární operátor
ast.BinaryExpr binární operátor

Pro lepší pochopení struktury AST se u každého navštíveného uzlu vypisuje i aktuální hloubka stromu a symbol uzlu je odsazen na základě zjištěné hloubky. Následuje ukázka, jakým způsobem bude zobrazen AST odpovídající výše zobrazenému aritmetickému výrazu:

  0     -
  1       +
  2         +
  3           +
  4             1
  4             *
  5               2
  5               3
  3           x
  2         *
  3           y
  3           z
  1       1

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

package main
 
import (
        "fmt"
        "log"
        "strings"
 
        "go/ast"
        "go/parser"
)
 
// výraz, který se má naparsovat
const source = `
1 + 2 * 3 + x + y * z - 1
`
 
// 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
 
        // převod uzlu do tisknutelné podoby
        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()
        }
 
        // tisk obsahu uzlu
        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)
        }
 
        // hodnota typu visitor
        var v visitor
 
        // zahájení průchodu abstraktním syntaktickým stromem
        ast.Walk(v, f)
}

3. Explicitní průchod stromem – rekurzivní algoritmus

Pro lepší pochopení metody (resp. přesněji řečeno metod) průchodu AST nebudeme v dalších příkladech používat funkci ast.Walk z balíčku go/ast. Namísto toho budeme rekurzivní průchod AST realizovat vlastním kódem. To znamená, že po konstrukci AST zavoláme vlastní funkci walk, které se předá kořenový uzel:

// konstrukce parseru a parsing zdrojového kódu
node, err := parser.ParseExpr(source)
if err != nil {
        log.Fatal(err)
}
 
// zahájení průchodu abstraktním syntaktickým stromem
walk(node)

Nyní je nutné rekurzi (neboli zpracování poduzlů) realizovat vlastními silami. To bude prozatím jednoduché – pro unární operátory zpracujeme jeden poduzel, pro binární operátory pak poduzly dva. První poduzel je představován položkou ast.Node.X, druhý pak položkou ast.Node.Y. Rekurzivní volání funkce node v případě uzlů představujících unární a binární operátory je zvýrazněno:

func walk(node ast.Node) {
        ...
        ...
        ...
 
        // převod uzlu do tisknutelné podoby a rekurzivní průchod poduzly
        switch x := node.(type) {
        case *ast.BasicLit:
                s = x.Value
        case *ast.Ident:
                s = x.Name
        case *ast.UnaryExpr:
                s = x.Op.String()
                walk(x.X)
        case *ast.BinaryExpr:
                walk(x.X)
                s = x.Op.String()
                walk(x.Y)
        }
 
        ...
        ...
        ...
}
Poznámka: povšimněte si, na jakém místě je umístěno rekurzivní volání u binárního operátoru. Tuto techniku plně využijeme v následující kapitole.

Opět si pochopitelně ukážeme úplný zdrojový kód dnešního druhého demonstračního příkladu, jenž vypadá následovně:

package main
 
import (
        "fmt"
        "log"
 
        "go/ast"
        "go/parser"
)
 
// výraz, který se má naparsovat
const source = `
1 + 2 * 3 + x + y * z - 1
`
 
func walk(node ast.Node) {
        // dosáhli jsme koncového uzlu?
        if node == nil {
                return
        }
 
        var s string
 
        // převod uzlu do tisknutelné podoby a rekurzivní průchod poduzly
        switch x := node.(type) {
        case *ast.BasicLit:
                s = x.Value
        case *ast.Ident:
                s = x.Name
        case *ast.UnaryExpr:
                s = x.Op.String()
                walk(x.X)
        case *ast.BinaryExpr:
                walk(x.X)
                s = x.Op.String()
                walk(x.Y)
        }
 
        // tisk obsahu uzlu
        if s != "" {
                fmt.Printf("%s ", s)
        } else {
                fmt.Printf("%T ", node)
        }
}
 
func main() {
        // konstrukce parseru a parsing zdrojového kódu
        node, err := parser.ParseExpr(source)
        if err != nil {
                log.Fatal(err)
        }
 
        // zahájení průchodu abstraktním syntaktickým stromem
        walk(node)
}

Vzhledem k tomu, že výpis obsahu navštíveného uzlu je proveden až po průchodu poduzly (samozřejmě jen pokud existují), bude vypsaná struktura do značné míry odpovídat postfixové notaci (RPN), k níž se dnes ještě vrátíme:

1 2 3 * + x + y z * + 1 -

4. Rekurzivní průchod stromem s rekonstrukcí aritmetického výrazu v infixové podobě

Nepatrnou úpravou demonstračního příkladu z předchozí kapitoly je možné zajistit, aby se AST představující naparsovaný aritmetický výraz vypsal v původní infixové podobě. Kostru s rekurzivním průchodem poduzly již máme vytvořenou, takže pouze postačuje zajistit, aby se hodnota uzlu vypsala nikoli po průchodu poduzlem, ale před rekurzivním zavoláním funkce walk pro průchod daným poduzlem. Celá funkce tak bude (poněkud paradoxně) ještě jednodušší:

func walk(node ast.Node) {
        // dosáhli jsme koncového uzlu?
        if node == nil {
                return
        }
 
        // tisk hodnoty uzlu a rekurzivní průchod poduzly
        switch x := node.(type) {
        case *ast.BasicLit:
                fmt.Printf("%s ", x.Value)
        case *ast.Ident:
                fmt.Printf("%s ", x.Name)
        case *ast.UnaryExpr:
                fmt.Printf("%s ", x.Op.String())
                walk(x.X)
        case *ast.BinaryExpr:
                walk(x.X)
                fmt.Printf("%s ", x.Op.String())
                walk(x.Y)
        }
}

Použitím této rekurzivní funkce lze původní aritmetický výraz plně zrekonstruovat do této podoby:

1 + 2 * 3 + x + y * z - 1

Opět si ukažme úplný výpis zdrojového kódu tohoto demonstračního příkladu:

package main
 
import (
        "fmt"
        "log"
 
        "go/ast"
        "go/parser"
)
 
// výraz, který se má naparsovat
const source = `
1 + 2 * 3 + x + y * z - 1
`
 
func walk(node ast.Node) {
        // dosáhli jsme koncového uzlu?
        if node == nil {
                return
        }
 
        // tisk hodnoty uzlu a rekurzivní průchod poduzly
        switch x := node.(type) {
        case *ast.BasicLit:
                fmt.Printf("%s ", x.Value)
        case *ast.Ident:
                fmt.Printf("%s ", x.Name)
        case *ast.UnaryExpr:
                fmt.Printf("%s ", x.Op.String())
                walk(x.X)
        case *ast.BinaryExpr:
                walk(x.X)
                fmt.Printf("%s ", x.Op.String())
                walk(x.Y)
        }
}
 
func main() {
        // konstrukce parseru a parsing zdrojového kódu
        node, err := parser.ParseExpr(source)
        if err != nil {
                log.Fatal(err)
        }
 
        // zahájení průchodu abstraktním syntaktickým stromem
        walk(node)
}

5. Rozšíření předchozího kódu o zpracování výrazů se závorkami

Nepatrnou úpravou demonstračního příkladu popsaného v předchozí kapitole lze zajistit, aby se korektně zpracovaly i aritmetické výrazy obsahující závorky, které pochopitelně mění prioritu a tím i tvar vytvořeného AST, kterým se prochází. V případě, že se narazí na uzel představující závorky (což je konkrétně uzel typu ast.ParenExpr, postačuje vypsat levou závorku, rekurzivně zpracovat (jediný) poduzel a následně vypsat pravou závorku:

// tisk hodnoty uzlu a rekurzivní průchod poduzly
switch x := node.(type) {
case *ast.BasicLit:
        fmt.Printf("%s ", x.Value)
case *ast.Ident:
        fmt.Printf("%s ", x.Name)
case *ast.UnaryExpr:
        fmt.Printf("%s ", x.Op.String())
        walk(x.X)
case *ast.BinaryExpr:
        walk(x.X)
        fmt.Printf("%s ", x.Op.String())
        walk(x.Y)
case *ast.ParenExpr:
        fmt.Printf("(")
        walk(x.X)
        fmt.Printf("\b) ")
}
Poznámka: řídicí znak \b je vypsán proto, aby se smazala mezera za posledním operátorem (jedná se o špinavý trik).

Následuje ukázka, jak bude vypadat výsledný výraz vypsaný rekurzivní funkcí walk, jejíž nejdůležitější část jsme si právě popsali:

1 + 2 * (3 + x) + y * (z - 1)

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

package main
 
import (
        "fmt"
        "log"
 
        "go/ast"
        "go/parser"
)
 
// výraz, který se má naparsovat
const source = `
1 + 2 * (3 + x) + y * (z - 1)
`
 
func walk(node ast.Node) {
        // dosáhli jsme koncového uzlu?
        if node == nil {
                return
        }
 
        // tisk hodnoty uzlu a rekurzivní průchod poduzly
        switch x := node.(type) {
        case *ast.BasicLit:
                fmt.Printf("%s ", x.Value)
        case *ast.Ident:
                fmt.Printf("%s ", x.Name)
        case *ast.UnaryExpr:
                fmt.Printf("%s ", x.Op.String())
                walk(x.X)
        case *ast.BinaryExpr:
                walk(x.X)
                fmt.Printf("%s ", x.Op.String())
                walk(x.Y)
        case *ast.ParenExpr:
                fmt.Printf("(")
                walk(x.X)
                fmt.Printf("\b) ")
        }
}
 
func main() {
        // konstrukce parseru a parsing zdrojového kódu
        node, err := parser.ParseExpr(source)
        if err != nil {
                log.Fatal(err)
        }
 
        // zahájení průchodu abstraktním syntaktickým stromem
        walk(node)
}

6. Převod výrazů z infixové notace do notace postfixové

Ve druhé části dnešního článku se poněkud odkloníme od technik založených na zpracování AST. Ukážeme si totiž, jakým způsobem je možné provádět převody aritmetických a logických výrazů z infixové notace do notace postfixové (neboli použít RPN – převrácenou polskou notaci). Tato operace může být užitečná například při implementaci vlastního interpretru, virtuálního stroje atd.

Na začátek si připomeňme, jaké operátory vlastně v programovacím jazyce Go existují, aby bylo patrné, na jaké problémy lze při převodu výrazů narazit:

Konstanta Odpovídající operátor
ADD +
SUB
MUL *
QUO /
REM %
   
AND &
OR |
XOR ^
SHL <<
SHR >>
AND_NOT &^
   
LAND &&
LOR ||
ARROW <-
INC ++
DEC --
   
EQL ==
LSS <
GTR >
ASSIGN =
NOT !
   
NEQ !=
LEQ <=
GEQ >=
DEFINE :=

Výše uvedené operátory se od sebe odlišují především prioritou a taktéž asociativitou, tj. pořadím provedení operací se stejnou prioritou – zda se postupuje směrem zleva doprava (většina klasických binárních operátorů) či zprava doleva (operátory s přiřazením).

7. Převrácená polská notace

V předchozím textu jsme se krátce zmínili o RPN neboli o převrácené (reverzní) polské notaci, která se taktéž nazývá notace postfixová. Jedná se o jednotný způsob zápisu matematických výrazů, v němž vždy operátor následuje až za všemi svými operandy. Tím se, kromě dalších věcí, odstraňuje nutnost použití závorek, které určují prioritu, protože v RPN je priorita určena způsobem řazení operandů a operátorů. Dále je v RPN zcela přesně určeno, kdy se operace vykoná – konkrétně ihned poté, co je přijat její token. RPN má své (prakticky) nezastupitelné místo v informatice, protože se používá například v oblasti překladačů, v instrukčních sadách některých virtuálních strojů atd. Aritmetické i logické výrazy zapsané s využitím RPN se navíc velmi snadno programově vyhodnocují, takže RPN může být použita i jako mezistupeň v interpretrech nebo například v SW kalkulačkách.

Ukažme si jednoduchý příklad dvou aritmetických výrazů zapsaných s využitím infixové notace:

a+b×c
(a+b)×c

Při použití postfixové notace však nejsou závorky ve výrazech nikdy zapotřebí, protože se priorita operací vyjadřuje přímo posloupností operátorů. Výše uvedené dva výrazy lze tedy do postfixové notace přepsat následovně:

a b c * +   nebo též   b c * a +
a b + c *   nebo též   c a b + *

Povšimněte si, že u výše uvedených RPN výrazů s proměnnými a, b a c napsaných na levé straně se oproti infixové notaci nemění pořadí operátorů. Toho se velmi často využívá při algoritmickém převodu mezi infixovou a postfixovou notací a také při ručním zápisu RPN výrazů. Tento převod provádí vlastně mnohý překladač či interpret programovacího jazyka, a to buď přímo (mimochodem většinou opět s využitím zásobníku, do kterého jsou ukládány kódy požadovaných matematických operací a pozice závorek – viz další odstavce), nebo takzvaným rekurzivním sestupem podle gramatických pravidel daného jazyka.

8. Algoritmus shunting-yard

Podívejme se tedy, jakým způsobem je možné převést aritmetický výraz odpovídající syntaxi programovacího jazyka Go do postfixové notace. Samotný algoritmus převodu mezi běžnou infixovou notací a notací postfixovou navrhl E. Dijkstra a nazývá se algoritmus shunting-yard (česky snad seřaďovací nádraží, konkrétně by se jednalo o nádraží vybavené úvratí). Tento algoritmus je založen na postupném načítání tokenů reprezentujících jak aritmetické/logické operace, tak i jejich operandy a popř. i volání funkcí a závorky ovlivňující prioritu prováděných operací. Tyto tokeny jsou v případě operandů posílány přímo na výstup, ovšem tokeny reprezentující operandy, závorky a funkce jsou zpracovávány odlišně – buď jsou odloženy na zásobník (jehož reálnou obdobou je právě úvrať na seřaďovacím nádraží) nebo naopak zajistí postupné vyzvedávání starších operandů z tohoto zásobníku a jejich poslání na výstup. Úplný popis tohoto algoritmu, který naleznete například zde, obsahuje i rozlišení operátorů asociativních zleva a zprava.

Poznámka: důležitá je zde zmínka o tom, že tento algoritmus pracuje nad sekvencí tokenů. Není tedy nutné vůbec konstruovat AST a dokonce se tokeny ze sekvence vždy pouze načítají, nikdy nevrací (naopak některé jiné algoritmy mohou vyžadovat vrácení posledního tokenu do vstupní sekvence).

9. Realizace algoritmu shunting-yard pro aritmetické výrazy programovacího jazyka Go

Výše popsaný algoritmus shunting-yard můžeme zjednodušit v případě, že není nutné rozlišit mezi použitím operátorů asociativních zleva a zprava. Příkladem je opět programovací jazyk Go, který v sadě základních aritmetických operátorů má pouze operátory asociativní zleva (není zde například operátor pro umocnění atd.). Navíc může algoritmus pracovat přímo nad tokeny získanými již minule popsanou tokenizací – tedy výsledkem práce balíčku nazvaného go/scanner (a jak již víme: bez vracení tokenů). Jedna z možných implementací algoritmu shunting-yard tedy může vypadat následovně. Všechny části jsou poměrně dopodrobna okomentovány:

package main
 
import (
        "fmt"
 
        "go/scanner"
        "go/token"
)
 
// výraz, který se má převést na RPN
const source = `
1 + 2 * (3 + x) + y * (z - 1)
`
 
func toRPN(s scanner.Scanner) {
        var operators = map[token.Token]int{
                token.MUL: 2,
                token.QUO: 2,
                token.REM: 2,
                token.ADD: 1,
                token.SUB: 1,
        }
 
        // interně používaný zásobník pro operátory s nižší prioritou
        var stack []token.Token
 
        // postupné provádění tokenizace a zpracování jednotlivých tokenů
loop:
        for {
                _, tok, lit := s.Scan()
                switch tok {
                case token.INT:
                        // celé číslo přímo vypsat
                        fallthrough
                case token.FLOAT:
                        // číslo s plovoucí čárkou přímo vypsat
                        fallthrough
                case token.IDENT:
                        // identifikátor taktéž přímo vypsat
                        fmt.Printf("%v ", lit)
                case token.LPAREN:
                        // levá závorka se uloží na zásobník (bez výpisu)
                        stack = append(stack, tok)
                case token.RPAREN:
                        // pravá závorka zahájí zpracování zásobníku až do první nalezené levé závorky
                        var tok token.Token
                        for {
                                // přečtení prvku ze zásobníku - operace POP
                                tok, stack = stack[len(stack)-1], stack[:len(stack)-1]
                                if tok == token.LPAREN {
                                        // odstranění levé závorky
                                        break
                                }
                                // ostatní tokeny získané ze zásobníku se vypíšou
                                fmt.Printf("%v ", tok)
                        }
                case token.EOF:
                        // speciální token reprezentující konec tokenizace
                        break loop
                default:
                        priority1, isOperator := operators[tok]
                        if isOperator {
                                // průchod prvky na zásobníku
                                for len(stack) > 0 {
                                        // operace TOP
                                        tok := stack[len(stack)-1]
                                        // získat prioritu operátoru přečteného ze zásobníku
                                        priority2 := operators[tok]
 
                                        if priority1 > priority2 {
                                                // větší priorita nového operátoru -> konec
                                                // (pouze ho později uložíme na zásobník)
                                                break
                                        }
 
                                        // menší či stejná priorita nového operátoru ->
                                        // vypsat předchozí operátor nalezený na zásobníku
                                        // a odstranit tento operátor ze zásobníku
                                        stack = stack[:len(stack)-1] // POP
                                        fmt.Printf("%s ", tok)
                                }
 
                                // uložit nově načtený operátor na zásobník
                                stack = append(stack, tok)
                        }
                }
        }
        // vyprázdnění obsahu zásobníku
        for len(stack) > 0 {
                fmt.Printf("%s ", stack[len(stack)-1])
                stack = stack[:len(stack)-1]
        }
}
 
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)
 
        // převod výrazu do RPN
        toRPN(s)
}

Po spuštění demonstračního příkladu se provede převod následujícího výrazu zapsaného s využitím klasické infixové notace:

1 + 2 * (3 + x) + y * (z - 1)

Do notace postfixové neboli RPN:

1 2 3 x + * + y z 1 - * +

10. Realizace výpočtu aritmetického výrazu popsaného pomocí RPN

Následný výpočet takto získaného výrazu (1 2 3 x + * + y z 1 – * +) by probíhal následovně:

  1. Je načten token obsahující hodnotu symbolu z výrazu reprezentovaného v postfixové notaci (RPN).
  2. V případě, že se jedná o číselnou hodnotu, je tato hodnota uložena na zásobník (nazývaný zásobník operandů, protože obsahuje operandy prováděných operací).
  3. Pokud se jedná o proměnnou, je její jméno uloženo na zásobník (při skutečném vyhodnocování výrazů lze v tomto okamžiku nahradit jméno proměnné jejím obsahem buď nyní, nebo až v dalším kroku).
  4. V případě, že se jedná o operátor, jsou ze zásobníku (přesněji ze zásobníku operandů) vyzvednuty oba operandy, operace se provede a výsledek se opět uloží na zásobník.
  5. Na konci bude na zásobníku uložena jediná hodnota, kterou je výsledek.
Poznámka: realizace tohoto algoritmu může být v objektovém kódu realizována v pouhých několika desítkách bajtů; proto ostatně nalezneme RPN v mnoha virtuálních strojích.

11. Algoritmus shunting-yard pro logické výrazy doplněné o porovnání (relační operátory)

Programovací jazyk Go nenabízí programátorům pouze aritmetické operátory, ale například i operátory určené pro provádění logických operací, operátory pro operace bitové atd. Všechny podporované operátory jsou vypsány v následující tabulce:

aritmetické + * / %  
aritmetické s přiřazením += -= *= /= %=  
logické && || !      
posuny a bitové operace << >> & | ^ &^
posuny a bitové operace s přiřazením <<= >>= &= |= ^= &^=
relační == != < <= > >=
operace s adresami * &        
unární operátory + ^      
další operátory <- :=        

Často se setkáme s logickými operacemi, které mohou obsahovat i porovnávání (komparaci) hodnot realizované relačními operátory. V programovacím jazyku Go nalezneme tři operátory, které jsou aplikovatelné na logické (pravdivostní) hodnoty true a false. Jedná se o logickou negaci, logický součin a logický součet. Tyto tři operátory se zapisují následujícím způsobem (u binárních operátorů existuje i možnost jejich kombinace s přiřazením):

Operátor Kombinace s přiřazením Význam
!   negace pravdivostní hodnoty
     
&& &&= logický součin dvou pravdivostních hodnot
|| ||= logický součet dvou pravdivostních hodnot

Nabídka relačních operátorů v programovacím jazyce Go by nás neměla ničím nepřekvapit: k dispozici je všech šest základních operátorů pro test na rovnost, nerovnost, větší než, menší než a kombinací větší nebo rovno a menší nebo rovno. Těchto šest operátorů lze použít pro všechny celočíselné datové typy i pro datové typy s plovoucí řádovou čárkou. Kromě toho ovšem můžeme porovnávat i řetězce.

Nicméně se nyní vraťme k poněkud jednoduššímu problému, konkrétně k převodu logických výrazů, v nichž se mohou vyskytovat i porovnání, do postfixové notace neboli do RPN. Podobně jako u aritmetických operací, i u operací logických se rozlišují priority. Nejvyšší prioritu má logický součin, nižší prioritu pak logický součet. Asociativita je v obou případech zleva doprava. Porovnání (relační operátory) mají vyšší prioritu než operátory logické a jejich asociativita je opět zleva doprava, čímž se nám situace zjednodušuje, neboť můžeme použít prakticky stejný algoritmus, jako u aritmetických operací – vlastně se změní pouze tabulky s podporovanými operátory (resp. jejich tokeny). To je ostatně velmi dobře patrné i při pohledu na zdrojový kód dalšího demonstračního příkladu:

package main
 
import (
        "fmt"
 
        "go/scanner"
        "go/token"
)
 
// výraz, který se má převést na RPN
const source = `
a<0 || b>10 && c!=0
`
 
func toRPN(s scanner.Scanner) {
        var operators = map[token.Token]int{
                token.EQL:  3,
                token.LSS:  3,
                token.GTR:  3,
                token.NEQ:  3,
                token.LEQ:  3,
                token.GEQ:  3,
                token.LAND: 2,
                token.LOR:  1,
        }
 
        // interně používaný zásobník pro operátory s nižší prioritou
        var stack []token.Token
 
        // postupné provádění tokenizace a zpracování jednotlivých tokenů
loop:
        for {
                _, tok, lit := s.Scan()
                switch tok {
                case token.INT:
                        // celé číslo přímo vypsat
                        fallthrough
                case token.FLOAT:
                        // číslo s plovoucí čárkou přímo vypsat
                        fallthrough
                case token.IDENT:
                        // identifikátor taktéž přímo vypsat
                        fmt.Printf("%v ", lit)
                case token.LPAREN:
                        // levá závorka se uloží na zásobník (bez výpisu)
                        stack = append(stack, tok)
                case token.RPAREN:
                        // pravá závorka zahájí zpracování zásobníku až do první nalezené levé závorky
                        var tok token.Token
                        for {
                                // přečtení prvku ze zásobníku - operace POP
                                tok, stack = stack[len(stack)-1], stack[:len(stack)-1]
                                if tok == token.LPAREN {
                                        // odstranění levé závorky
                                        break
                                }
                                // ostatní tokeny získané ze zásobníku se vypíšou
                                fmt.Printf("%v ", tok)
                        }
                case token.EOF:
                        // speciální token reprezentující konec tokenizace
                        break loop
                default:
                        priority1, isOperator := operators[tok]
                        if isOperator {
                                // průchod prvky na zásobníku
                                for len(stack) > 0 {
                                        // operace TOP
                                        tok := stack[len(stack)-1]
                                        // získat prioritu operátoru přečteného ze zásobníku
                                        priority2 := operators[tok]
 
                                        if priority1 > priority2 {
                                                // větší priorita nového operátoru -> konec
                                                // (pouze ho později uložíme na zásobník)
                                                break
                                        }
 
                                        // menší či stejná priorita nového operátoru ->
                                        // vypsat předchozí operátor nalezený na zásobníku
                                        // a odstranit tento operátor ze zásobníku
                                        stack = stack[:len(stack)-1] // POP
                                        fmt.Printf("%s ", tok)
                                }
 
                                // uložit nově načtený operátor na zásobník
                                stack = append(stack, tok)
                        }
                }
        }
        // vyprázdnění obsahu zásobníku
        for len(stack) > 0 {
                fmt.Printf("%s ", stack[len(stack)-1])
                stack = stack[:len(stack)-1]
        }
}
 
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)
 
        // převod výrazu do RPN
        toRPN(s)
}

Výsledkem získaným po spuštění tohoto příkladu bude výraz v postfixové notaci:

a 0 < b 10 > c 0 != && ||

12. Závorky v logických výrazech

Pochopitelně je možné i v logických výrazech používat závorky a měnit tak prioritu prováděných operací. Můžeme si to snadno vyzkoušet, a to konkrétně náhradou následujícího logického výrazu:

a<0 || b>10 && c!=0

za výraz:

(a<0 || b>10) && c!=0

Výsledky, tj. generovaný výraz zapsaný v převrácené polské notaci, se budou odlišovat. Původní výraz bez závorek bude převeden na:

a 0 < b 10 > c 0 != && ||

Výraz se závorkami bude naopak převeden na:

a 0 < b 10 > || c 0 != &&

Vše si opět snadno otestujeme:

package main
 
import (
        "fmt"
 
        "go/scanner"
        "go/token"
)
 
// výraz, který se má převést na RPN
const source = `
(a<0 || b>10) && c!=0
`
 
func toRPN(s scanner.Scanner) {
        var operators = map[token.Token]int{
                token.EQL:  3,
                token.LSS:  3,
                token.GTR:  3,
                token.NEQ:  3,
                token.LEQ:  3,
                token.GEQ:  3,
                token.LAND: 2,
                token.LOR:  1,
        }
 
        // interně používaný zásobník pro operátory s nižší prioritou
        var stack []token.Token
 
        // postupné provádění tokenizace a zpracování jednotlivých tokenů
loop:
        for {
                _, tok, lit := s.Scan()
                switch tok {
                case token.INT:
                        // celé číslo přímo vypsat
                        fallthrough
                case token.FLOAT:
                        // číslo s plovoucí čárkou přímo vypsat
                        fallthrough
                case token.IDENT:
                        // identifikátor taktéž přímo vypsat
                        fmt.Printf("%v ", lit)
                case token.LPAREN:
                        // levá závorka se uloží na zásobník (bez výpisu)
                        stack = append(stack, tok)
                case token.RPAREN:
                        // pravá závorka zahájí zpracování zásobníku až do první nalezené levé závorky
                        var tok token.Token
                        for {
                                // přečtení prvku ze zásobníku - operace POP
                                tok, stack = stack[len(stack)-1], stack[:len(stack)-1]
                                if tok == token.LPAREN {
                                        // odstranění levé závorky
                                        break
                                }
                                // ostatní tokeny získané ze zásobníku se vypíšou
                                fmt.Printf("%v ", tok)
                        }
                case token.EOF:
                        // speciální token reprezentující konec tokenizace
                        break loop
                default:
                        priority1, isOperator := operators[tok]
                        if isOperator {
                                // průchod prvky na zásobníku
                                for len(stack) > 0 {
                                        // operace TOP
                                        tok := stack[len(stack)-1]
                                        // získat prioritu operátoru přečteného ze zásobníku
                                        priority2 := operators[tok]
 
                                        if priority1 > priority2 {
                                                // větší priorita nového operátoru -> konec
                                                // (pouze ho později uložíme na zásobník)
                                                break
                                        }
 
                                        // menší či stejná priorita nového operátoru ->
                                        // vypsat předchozí operátor nalezený na zásobníku
                                        // a odstranit tento operátor ze zásobníku
                                        stack = stack[:len(stack)-1] // POP
                                        fmt.Printf("%s ", tok)
                                }
 
                                // uložit nově načtený operátor na zásobník
                                stack = append(stack, tok)
                        }
                }
        }
        // vyprázdnění obsahu zásobníku
        for len(stack) > 0 {
                fmt.Printf("%s ", stack[len(stack)-1])
                stack = stack[:len(stack)-1]
        }
}
 
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)
 
        // převod výrazu do RPN
        toRPN(s)
}

13. Detekce volání funkcí při zpracování AST

Ve třetí části dnešního článku si ukážeme, jakým způsobem je možné průchodem AST zjistit, jaké funkce, popř. metody se volají a jaké mají parametry. Pro jednoduchost budeme počítat s tím, že se volají implicitně dostupné funkce, tj. funkce, které jsou standardní a u nichž není nutné uvádět název balíčku. Příklad takového kódu:

package main
 
var answer int = 42
var x []int = make([]int, 10)
var y = len(x)
var z = cap(x)
var w = len(x) + cap(x)
var a = append(x, 10)

Vidíme, že v tomto jednoduchém příkladu jsou funkce volány ve chvíli, kdy je zapotřebí (pochopitelně v runtime) vypočítat hodnotu nějakého výrazu. Některé z volaných funkcí mají jediný parametr, další funkce pak dva parametry. Poněkud speciálním případem je volání funkce make, které se v prvním parametru předává přímo datový typ, podobně jako je tomu u funkce new (tyto funkce byly před Go verze 1.17 vlastně pseudofunkcemi, protože je nebylo možné plně deklarovat). Pro jednoduchost začneme pouze detekcí volání funkce, bez zpracování informací o parametrech, popř. o objektu, pro který je volaná metoda.

V AST je volání funkce reprezentováno uzlem typu CallExpr, který obsahuje jméno volané funkce v atributu Fun informace o volané funkci (tedy mj. i její jméno). Pokud budeme potřebovat pouze vytisknout jména volaných funkcí, bude průchod AST dosti triviální:

// funkce volaná při průchodu AST
func inspectCallback(n ast.Node) bool {
        // pokud se jedná o volání funkce, vrátí se hodnota + true
        funcCall, ok := n.(*ast.CallExpr)
        if ok {
                // výpis základní informace o volané funkci
                fmt.Println(funcCall.Fun)
        }
        return true
}
Poznámka: relativně snadno lze příklad rozšířit i o další případ. Tím je volání funkce ve chvíli, kdy je zapotřebí vypočítat parametr jiné funkce. Jedná se tedy například o následující programový kód:
x = foo(bar(a), baz(b))

Úplný zdrojový kód demonstračního příkladu, který zjistí všechna volání funkcí, může vypadat následovně:

package main
 
import (
        "fmt"
        "go/ast"
        "go/parser"
        "go/token"
)
 
// zdrojový kód, který se má naparsovat
const source = `
package main
 
var answer int = 42
var x []int = make([]int, 10)
var y = len(x)
var z = cap(x)
var w = len(x) + cap(x)
var a = append(x, 10)
`
 
// funkce volaná při průchodu AST
func inspectCallback(n ast.Node) bool {
        // pokud se jedná o volání funkce, vrátí se hodnota + true
        funcCall, ok := n.(*ast.CallExpr)
        if ok {
                // výpis základní informace o volané funkci
                fmt.Println(funcCall.Fun)
        }
        return true
}
 
func main() {
        // struktura reprezentující množinu zdrojových kódů
        fileSet := token.NewFileSet()
 
        // konstrukce parseru a parsing zdrojového kódu
        file, err := parser.ParseFile(fileSet, "", source, parser.ParseComments)
        if err != nil {
                panic(err)
        }
 
        // zahájení průchodu abstraktním syntaktickým stromem
        ast.Inspect(file, inspectCallback)
}

Výsledek:

make
len
cap
len
cap
append

14. Základní informace o argumentech volané funkce

Každé volání funkce je v AST reprezentováno tímto uzlem:

type CallExpr struct {
        Fun      Expr      // function expression
        Lparen   token.Pos // position of "("
        Args     []Expr    // function arguments; or nil
        Ellipsis token.Pos // position of "..." (token.NoPos if there is no "...")
        Rparen   token.Pos // position of ")"
}

Z atributů tohoto uzlu lze snadno zjistit, že kromě jména funkce (a dalších informací o volané funkci) můžeme přečíst informaci o argumentech předávaných volané funkci. Tyto argumenty jsou uloženy v řezu Args. V případě, že se funkci žádné argumenty nepředávají (například funkci println), bude v tomto atributu uložena hodnota nil. Základní informace o předávaných argumentech – tedy o jejich pozici (indexu), názvu a typu, lze při průchodu AST vypsat následovně:

// funkce volaná při průchodu AST
func inspectCallback(n ast.Node) bool {
        // pokud se jedná o volání funkce, vrátí se hodnota + true
        funcCall, ok := n.(*ast.CallExpr)
        if ok {
                // výpis podrobnějších informací o volané funkci
                fmt.Printf("Function: %s ", funcCall.Fun)
                fmt.Printf("with %d arguments:\n", len(funcCall.Args))
                // výpis informací o argumentech funkce
                for i, arg := range funcCall.Args {
                        fmt.Printf("\t%d\t%T\t%s\n", i, arg, arg)
                }
                fmt.Println()
        }
        return true
}

Výsledek pro všechny volané funkce ve zpracovávaném úseku zdrojového kódu:

Function: make with 2 arguments:
        0       *ast.ArrayType  &{%!s(token.Pos=55)  int}
        1       *ast.BasicLit   &{%!s(token.Pos=62) INT 10}
 
Function: len with 1 arguments:
        0       *ast.Ident      x
 
Function: cap with 1 arguments:
        0       *ast.Ident      x
 
Function: len with 1 arguments:
        0       *ast.Ident      x
 
Function: cap with 1 arguments:
        0       *ast.Ident      x
 
Function: append with 2 arguments:
        0       *ast.Ident      x
        1       *ast.BasicLit   &{%!s(token.Pos=138) INT 10}

Opět si pro úplnost ukažme celý zdrojový kód tohoto demonstračního příkladu:

package main
 
import (
        "fmt"
        "go/ast"
        "go/parser"
        "go/token"
)
 
// zdrojový kód, který se má naparsovat
const source = `
package main
 
var answer int = 42
var x []int = make([]int, 10)
var y = len(x)
var z = cap(x)
var w = len(x) + cap(x)
var a = append(x, 10)
`
 
// funkce volaná při průchodu AST
func inspectCallback(n ast.Node) bool {
        // pokud se jedná o volání funkce, vrátí se hodnota + true
        funcCall, ok := n.(*ast.CallExpr)
        if ok {
                // výpis podrobnějších informací o volané funkci
                fmt.Printf("Function: %s ", funcCall.Fun)
                fmt.Printf("with %d arguments:\n", len(funcCall.Args))
                // výpis informací o argumentech funkce
                for i, arg := range funcCall.Args {
                        fmt.Printf("\t%d\t%T\t%s\n", i, arg, arg)
                }
                fmt.Println()
        }
        return true
}
 
func main() {
        // struktura reprezentující množinu zdrojových kódů
        fileSet := token.NewFileSet()
 
        // konstrukce parseru a parsing zdrojového kódu
        file, err := parser.ParseFile(fileSet, "", source, parser.ParseComments)
        if err != nil {
                panic(err)
        }
 
        // zahájení průchodu abstraktním syntaktickým stromem
        ast.Inspect(file, inspectCallback)
}

15. Podrobnější informace o argumentech volané funkce

Argumenty volané funkce jsou obecně zapsány formou výrazu, takže pro jeho „rozklíčování“ by bylo nutné provést rekurzivní analýzu poduzlů uložených v funcCall.Args. Nicméně prozatím se můžeme spokojit s rozlišením jednodušších typů argumentů, konkrétně s argumenty předávanými formou konstanty (resp. literálu) a argumenty uloženými v proměnných. Hodnoty resp. jména proměnných lze vypsat velmi snadno, a to nepatrnou úpravou programové smyčky, v níž se argumenty vypisují:

for i, arg := range funcCall.Args {
        fmt.Printf("\t%d\t", i+1)
        switch v := arg.(type) {
        case *ast.BasicLit:
                fmt.Printf("Constant: %s\n", v.Value)
        case *ast.Ident:
                fmt.Printf("Variable: '%s'\n", v.Name)
        default:
                fmt.Println("Unrecognized type")
        }
}

Úplný kód upraveného demonstračního příkladu bude vypadat takto:

package main
 
import (
        "fmt"
        "go/ast"
        "go/parser"
        "go/token"
)
 
// zdrojový kód, který se má naparsovat
const source = `
package main
 
var answer int = 42
var x []int = make([]int, 10)
var y = len(x)
var z = cap(x)
var w = len(x) + cap(x)
var a = append(x, 10)
`
 
// funkce volaná při průchodu AST
func inspectCallback(n ast.Node) bool {
        // pokud se jedná o volání funkce, vrátí se hodnota + true
        funcCall, ok := n.(*ast.CallExpr)
        if ok {
                // výpis podrobnějších informací o volané funkci
                fmt.Printf("Function: %s ", funcCall.Fun)
                fmt.Printf("with %d arguments:\n", len(funcCall.Args))
                // výpis informací o argumentech funkce
                for i, arg := range funcCall.Args {
                        fmt.Printf("\t%d\t", i+1)
                        switch v := arg.(type) {
                        case *ast.BasicLit:
                                fmt.Printf("Constant: %s\n", v.Value)
                        case *ast.Ident:
                                fmt.Printf("Variable: '%s'\n", v.Name)
                        default:
                                fmt.Println("Unrecognized type")
                        }
                }
                fmt.Println()
        }
        return true
}
 
func main() {
        // struktura reprezentující množinu zdrojových kódů
        fileSet := token.NewFileSet()
 
        // konstrukce parseru a parsing zdrojového kódu
        file, err := parser.ParseFile(fileSet, "", source, parser.ParseComments)
        if err != nil {
                panic(err)
        }
 
        // zahájení průchodu abstraktním syntaktickým stromem
        ast.Inspect(file, inspectCallback)
}

Výsledek:

Function: make with 2 arguments:
        1       Unrecognized type
        2       Constant: 10
 
Function: len with 1 arguments:
        1       Variable: 'x'
 
Function: cap with 1 arguments:
        1       Variable: 'x'
 
Function: len with 1 arguments:
        1       Variable: 'x'
 
Function: cap with 1 arguments:
        1       Variable: 'x'
 
Function: append with 2 arguments:
        1       Variable: 'x'
        2       Constant: 10

16. Informace o argumentech typu pole či řez (nějakého typu)

Nyní si ukážeme, jakým způsobem lze zjistit volání funkcí, jimž se předávají pole nebo řezy. Analyzovat budeme tento (umělý) úsek zdrojového kódu, který vznikl rozšířením kódu z předchozích dvou kapitol:

package main
 
var answer int = 42
 
var x []int = make([]int, 10)
var x2 []float = make([]float, 10)
var x3 []T = make([]T, 20)
 
var y = len(x)
var z = cap(x)
var w = len(x) + cap(x)
var a = append(x, 10)
var b = foo([10]int)
var c = bar(x, y, z, 1, 1.0, 1i, "foo", 'b')
 
var d = c.baz(1, 2, x)

V případě, že se předává hodnota typu pole nebo řez, bude takový argument představován uzlem ast.ArrayType. Tento uzel obsahuje i položku nazvanou Len. V případě, že je argumentem pole, bude tato položka obsahovat (podle očekávání) délku pole, ovšem v případě řezu je položka rovna nil, aby bylo možné rozlišit mezi polem s nulovou délkou a řezem. Navíc je v položce Elt uložen typ prvků předávaného řezu nebo pole:

// výpis informací o argumentech funkce
for i, arg := range funcCall.Args {
        fmt.Printf("\t%d\t", i+1)
        switch v := arg.(type) {
        case *ast.BasicLit:
                fmt.Printf("Constant %s of type %s\n", v.Value, v.Kind)
        case *ast.Ident:
                fmt.Printf("Variable %s\n", v.Name)
        case *ast.ArrayType:
                if v.Len == nil {
                        fmt.Printf("Slice of %s\n", v.Elt)
                } else {
                        fmt.Printf("Array of %s\n", v.Elt)
                }
        default:
                fmt.Printf("Unrecognized type %T\n", v)
        }
}

Po těchto úpravách dostaneme ještě přesnější informace o předávaných argumentech volané funkci:

Function: make with 2 arguments:
        1       Slice of int
        2       Constant 10 of type INT
 
Function: make with 2 arguments:
        1       Slice of float
        2       Constant 10 of type INT
 
Function: make with 2 arguments:
        1       Slice of T
        2       Constant 20 of type INT
 
Function: len with 1 arguments:
        1       Variable x
 
Function: cap with 1 arguments:
        1       Variable x
 
Function: len with 1 arguments:
        1       Variable x
 
Function: cap with 1 arguments:
        1       Variable x
 
Function: append with 2 arguments:
        1       Variable x
        2       Constant 10 of type INT
 
Function: foo with 1 arguments:
        1       Array of int
 
Function: bar with 8 arguments:
        1       Variable x
        2       Variable y
        3       Variable z
        4       Constant 1 of type INT
        5       Constant 1.0 of type FLOAT
        6       Constant 1i of type IMAG
        7       Constant "foo" of type STRING
        8       Constant 'b' of type CHAR
 
Function: &{c baz} with 3 arguments:
        1       Constant 1 of type INT
        2       Constant 2 of type INT
        3       Variable x

Úplný zdrojový kód takto upraveného příkladu:

package main
 
import (
        "fmt"
        "go/ast"
        "go/parser"
        "go/token"
)
 
// zdrojový kód, který se má naparsovat
const source = `
package main
 
var answer int = 42
 
var x []int = make([]int, 10)
var x2 []float = make([]float, 10)
var x3 []T = make([]T, 20)
 
var y = len(x)
var z = cap(x)
var w = len(x) + cap(x)
var a = append(x, 10)
var b = foo([10]int)
var c = bar(x, y, z, 1, 1.0, 1i, "foo", 'b')
 
var d = c.baz(1, 2, x)
`
 
// funkce volaná při průchodu AST
func inspectCallback(n ast.Node) bool {
        // pokud se jedná o volání funkce, vrátí se hodnota + true
        funcCall, ok := n.(*ast.CallExpr)
        if ok {
                // výpis podrobnějších informací o volané funkci
                fmt.Printf("Function: %s ", funcCall.Fun)
                fmt.Printf("with %d arguments:\n", len(funcCall.Args))
                // výpis informací o argumentech funkce
                for i, arg := range funcCall.Args {
                        fmt.Printf("\t%d\t", i+1)
                        switch v := arg.(type) {
                        case *ast.BasicLit:
                                fmt.Printf("Constant %s of type %s\n", v.Value, v.Kind)
                        case *ast.Ident:
                                fmt.Printf("Variable %s\n", v.Name)
                        case *ast.ArrayType:
                                if v.Len == nil {
                                        fmt.Printf("Slice of %s\n", v.Elt)
                                } else {
                                        fmt.Printf("Array of %s\n", v.Elt)
                                }
                        default:
                                fmt.Printf("Unrecognized type %T\n", v)
                        }
                }
                fmt.Println()
        }
        return true
}
 
func main() {
        // struktura reprezentující množinu zdrojových kódů
        fileSet := token.NewFileSet()
 
        // konstrukce parseru a parsing zdrojového kódu
        file, err := parser.ParseFile(fileSet, "", source, parser.ParseComments)
        if err != nil {
                panic(err)
        }
 
        // zahájení průchodu abstraktním syntaktickým stromem
        ast.Inspect(file, inspectCallback)
}

17. Rozlišení volání funkce od volání metody

Předchozí příklady je pochopitelně možné ještě dále rozšiřovat, například rozlišit, kdy se volá běžná funkce a kdy metoda:

var c = bar(x, y, z, 1, 1.0, 1i, "foo", 'b')
 
var d = c.baz(1, 2, x)

Pokud rozlišení provádět nebudeme, vypíše se při volání metody:

Function: &{c baz} with 3 arguments:
        1       Constant 1 of type INT
        2       Constant 2 of type INT
        3       Variable x

V případě, že je uzel představující volanou funkci typu ast.SelectorExpr, bude se jednat o volání metody a tento uzel bude obsahovat položky Sel.Name se jménem metody a X s typem (protože ast.SelectorExpr je odvozen od typu ast.Expr. Můžeme tedy provést test na typ uzlu a na základě výsledku buď vypsat informace o volané metodě nebo o běžné funkci:

method, ok := funcCall.Fun.(*ast.SelectorExpr)
if ok {
        fmt.Printf("Method: %s for type %s ", method.Sel.Name, method.X)
} else {
        fmt.Printf("Function: %s ", funcCall.Fun)
}

Výše uvedenou podmínku jednoduše zapracujeme do existujícího kódu:

package main
 
import (
        "fmt"
        "go/ast"
        "go/parser"
        "go/token"
)
 
// zdrojový kód, který se má naparsovat
const source = `
package main
 
var answer int = 42
 
var x []int = make([]int, 10)
var x2 []float = make([]float, 10)
var x3 []T = make([]T, 20)
 
var y = len(x)
var z = cap(x)
var w = len(x) + cap(x)
var a = append(x, 10)
var b = foo([10]int)
var c = bar(x, y, z, 1, 1.0, 1i, "foo", 'b')
 
var d = c.baz(1, 2, x)
`
 
// funkce volaná při průchodu AST
func inspectCallback(n ast.Node) bool {
        // pokud se jedná o volání funkce, vrátí se hodnota + true
        funcCall, ok := n.(*ast.CallExpr)
        if ok {
                method, ok := funcCall.Fun.(*ast.SelectorExpr)
                if ok {
                        fmt.Printf("Method: %s for type %s ", method.Sel.Name, method.X)
                } else {
                        fmt.Printf("Function: %s ", funcCall.Fun)
                }
                // výpis podrobnějších informací o volané funkci
                fmt.Printf("with %d arguments:\n", len(funcCall.Args))
                // výpis informací o argumentech funkce
                for i, arg := range funcCall.Args {
                        fmt.Printf("\t%d\t", i+1)
                        switch v := arg.(type) {
                        case *ast.BasicLit:
                                fmt.Printf("Constant %s of type %s\n", v.Value, v.Kind)
                        case *ast.Ident:
                                fmt.Printf("Variable %s\n", v.Name)
                        case *ast.ArrayType:
                                if v.Len == nil {
                                        fmt.Printf("Slice of %s\n", v.Elt)
                                } else {
                                        fmt.Printf("Array of %s\n", v.Elt)
                                }
                        default:
                                fmt.Printf("Unrecognized type %T\n", v)
                        }
                }
                fmt.Println()
        }
        return true
}
 
func main() {
        // struktura reprezentující množinu zdrojových kódů
        fileSet := token.NewFileSet()
 
        // konstrukce parseru a parsing zdrojového kódu
        file, err := parser.ParseFile(fileSet, "", source, parser.ParseComments)
        if err != nil {
                panic(err)
        }
 
        // zahájení průchodu abstraktním syntaktickým stromem
        ast.Inspect(file, inspectCallback)
}

Výsledkem bude korektní rozlišení, že se volá funkce resp. metoda:

ICTZ23

Function: make with 2 arguments:
        1       Slice of int
        2       Constant 10 of type INT
 
Function: make with 2 arguments:
        1       Slice of float
        2       Constant 10 of type INT
 
Function: make with 2 arguments:
        1       Slice of T
        2       Constant 20 of type INT
 
Function: len with 1 arguments:
        1       Variable x
 
Function: cap with 1 arguments:
        1       Variable x
 
Function: len with 1 arguments:
        1       Variable x
 
Function: cap with 1 arguments:
        1       Variable x
 
Function: append with 2 arguments:
        1       Variable x
        2       Constant 10 of type INT
 
Function: foo with 1 arguments:
        1       Array of int
 
Function: bar with 8 arguments:
        1       Variable x
        2       Variable y
        3       Variable z
        4       Constant 1 of type INT
        5       Constant 1.0 of type FLOAT
        6       Constant 1i of type IMAG
        7       Constant "foo" of type STRING
        8       Constant 'b' of type CHAR
 
Method: baz for type c with 3 arguments:
        1       Constant 1 of type INT
        2       Constant 2 of type INT
        3       Variable x

18. Obsah navazujícího článku

V navazujícím článku se ještě jednou budeme zabývat problematikou lexikální a syntaktické analýzy založené na balíčcích umístěných ve jmenném prostoru go. Ukážeme si praktické příklady, například to, jakým způsobem je možné detekovat některé problematické části kódu stylem, jakým to provádí nástroj gocritic, který byl popsán v článku Kontrola potenciálních chyb ve zdrojových kódech Go nástroji gosec a go-critic.

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

Zdrojové kódy všech minule i 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
       
19 walk1.go automatický průchod AST s výpisem aritmetických výrazů a podvýrazů https://github.com/tisnik/go-root/blob/master/article83/walk1.go
20 walk2.go explicitní průchod stromem – rekurzivní algoritmus https://github.com/tisnik/go-root/blob/master/article83/walk2.go
21 walk3.go rekurzivní průchod stromem s rekonstrukcí aritmetického výrazu v infixové podobě https://github.com/tisnik/go-root/blob/master/article83/walk3.go
22 walk4.go rozšíření předchozího kódu o zpracování výrazů se závorkami https://github.com/tisnik/go-root/blob/master/article83/walk4.go
       
23 rpn1.go převod aritmetických výrazů z infixové notace do notace postfixové https://github.com/tisnik/go-root/blob/master/article83/rpn1.go
24 rpn2.go převod logických výrazů z infixové notace do notace postfixové https://github.com/tisnik/go-root/blob/master/article83/rpn2.go
25 rpn3.go nepatrná úprava – logický výraz se závorkami https://github.com/tisnik/go-root/blob/master/article83/rpn3.go
       
26 func_call1.go detekce volání funkcí při zpracování AST https://github.com/tisnik/go-root/blob/master/article83/fun­c_call1.go
27 func_call2.go základní informace o argumentech volané funkce https://github.com/tisnik/go-root/blob/master/article83/fun­c_call2.go
28 func_call3.go podrobnější informace o argumentech volané funkce https://github.com/tisnik/go-root/blob/master/article83/fun­c_call3.go
29 func_call4.go informace o argumentech typu pole či řez (nějakého typu) https://github.com/tisnik/go-root/blob/master/article83/fun­c_call4.go
30 func_call5.go rozlišení volání funkce od volání metody https://github.com/tisnik/go-root/blob/master/article83/fun­c_call5.go
       
31 condition1.go praktický příklad: detekce zápisu „yoda výrazů“ https://github.com/tisnik/go-root/blob/master/article83/con­dition1.go
32 condition2.go praktický příklad: detekce zápisu „yoda výrazů“ https://github.com/tisnik/go-root/blob/master/article83/con­dition2.go

20. Odkazy na Internetu

  1. Cool Stuff With Go’s AST Package Pt 1
    https://medium.com/swlh/cool-stuff-with-gos-ast-package-pt-1–981460cddcd7
  2. Cool Stuff With Go’s AST Package Pt 2
    https://medium.com/swlh/cool-stuff-with-gos-ast-package-pt-2-e4d39ab7e9db
  3. Code generation in Go using abstract syntax trees (AST)
    https://blog.stein.wtf/posts/go-abstract-syntax-tree-code-generation
  4. Shunting-yard algorithm
    https://en.wikipedia.org/wiki/Shunting-yard_algorithm
  5. Abstract syntax tree
    https://en.wikipedia.org/wi­ki/Abstract_syntax_tree
  6. Lexical analysis
    https://en.wikipedia.org/wi­ki/Lexical_analysis
  7. Parser
    https://en.wikipedia.org/wi­ki/Parsing#Parser
  8. Golang AST Package
    https://golangdocs.com/golang-ast-package
  9. Dokumentace k balíčku go/ast
    https://pkg.go.dev/go/ast
  10. Dokumentace k balíčku go/scanner
    https://pkg.go.dev/go/scanner
  11. Dokumentace k balíčku go/parser
    https://pkg.go.dev/go/parser
  12. Dokumentace k balíčku go/token
    https://pkg.go.dev/go/token
  13. AP8, IN8 Regulární jazyky
    http://statnice.dqd.cz/home:inf:ap8
  14. AP9, IN9 Konečné automaty
    http://statnice.dqd.cz/home:inf:ap9
  15. AP10, IN10 Bezkontextové jazyky
    http://statnice.dqd.cz/home:inf:ap10
  16. AP11, IN11 Zásobníkové automaty, Syntaktická analýza
    http://statnice.dqd.cz/home:inf:ap11
  17. Introduction to YACC
    https://www.geeksforgeeks­.org/introduction-to-yacc/
  18. Introduction of Lexical Analysis
    https://www.geeksforgeeks­.org/introduction-of-lexical-analysis/?ref=lbp
  19. 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/
  20. Popis příkazu gofmt
    https://pkg.go.dev/cmd/gofmt
  21. Popis příkazu govet
    https://pkg.go.dev/cmd/vet
  22. Repositář nástroje errcheck
    https://github.com/kisielk/errcheck
  23. Repositář nástroje goconst
    https://github.com/jgautheron/goconst
  24. Repositář nástroje gocyclo
    https://github.com/fzipp/gocyclo
  25. Repositář nástroje ineffassign
    https://github.com/gordon­klaus/ineffassign
  26. Repositář nástroje gosec
    https://github.com/securego/gosec
  27. Repositář nástroje go-critic
    https://github.com/go-critic/go-critic
  28. Seznam testů prováděných nástrojem go-critic
    https://go-critic.com/overview
  29. Welcome go-critic
    https://itnext.io/welcome-go-critic-a26b6e30f1c6
  30. Využití knihovny Pygments (nejenom) pro obarvení zdrojových kódů
    https://www.root.cz/clanky/vyuziti-knihovny-pygments-nejenom-pro-obarveni-zdrojovych-kodu/
  31. LR syntaktický analyzátor
    https://cs.wikipedia.org/wi­ki/LR_syntaktick%C3%BD_ana­lyz%C3%A1tor
  32. Kategorie:Algoritmy syntaktické analýzy
    https://cs.wikipedia.org/wi­ki/Kategorie:Algoritmy_syn­taktick%C3%A9_anal%C3%BDzy

Autor článku

Pavel Tišnovský vystudoval VUT FIT a v současné době pracuje ve společnosti Red Hat, kde vyvíjí nástroje pro OpenShift.io.