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é
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
19. Repositář s demonstračními příklady
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)
}
...
...
...
}
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 až 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) ")
}
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.
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ě:
- Je načten token obsahující hodnotu symbolu z výrazu reprezentovaného v postfixové notaci (RPN).
- 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í).
- 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).
- 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.
- Na konci bude na zásobníku uložena jediná hodnota, kterou je výsledek.
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
}
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:
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:
20. Odkazy na Internetu
- Cool Stuff With Go’s AST Package Pt 1
https://medium.com/swlh/cool-stuff-with-gos-ast-package-pt-1–981460cddcd7 - Cool Stuff With Go’s AST Package Pt 2
https://medium.com/swlh/cool-stuff-with-gos-ast-package-pt-2-e4d39ab7e9db - Code generation in Go using abstract syntax trees (AST)
https://blog.stein.wtf/posts/go-abstract-syntax-tree-code-generation - Shunting-yard algorithm
https://en.wikipedia.org/wiki/Shunting-yard_algorithm - Abstract syntax tree
https://en.wikipedia.org/wiki/Abstract_syntax_tree - Lexical analysis
https://en.wikipedia.org/wiki/Lexical_analysis - Parser
https://en.wikipedia.org/wiki/Parsing#Parser - Golang AST Package
https://golangdocs.com/golang-ast-package - Dokumentace k balíčku go/ast
https://pkg.go.dev/go/ast - Dokumentace k balíčku go/scanner
https://pkg.go.dev/go/scanner - Dokumentace k balíčku go/parser
https://pkg.go.dev/go/parser - Dokumentace k balíčku go/token
https://pkg.go.dev/go/token - AP8, IN8 Regulární jazyky
http://statnice.dqd.cz/home:inf:ap8 - AP9, IN9 Konečné automaty
http://statnice.dqd.cz/home:inf:ap9 - AP10, IN10 Bezkontextové jazyky
http://statnice.dqd.cz/home:inf:ap10 - AP11, IN11 Zásobníkové automaty, Syntaktická analýza
http://statnice.dqd.cz/home:inf:ap11 - Introduction to YACC
https://www.geeksforgeeks.org/introduction-to-yacc/ - Introduction of Lexical Analysis
https://www.geeksforgeeks.org/introduction-of-lexical-analysis/?ref=lbp - 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/ - Popis příkazu gofmt
https://pkg.go.dev/cmd/gofmt - Popis příkazu govet
https://pkg.go.dev/cmd/vet - Repositář nástroje errcheck
https://github.com/kisielk/errcheck - Repositář nástroje goconst
https://github.com/jgautheron/goconst - Repositář nástroje gocyclo
https://github.com/fzipp/gocyclo - Repositář nástroje ineffassign
https://github.com/gordonklaus/ineffassign - Repositář nástroje gosec
https://github.com/securego/gosec - Repositář nástroje go-critic
https://github.com/go-critic/go-critic - Seznam testů prováděných nástrojem go-critic
https://go-critic.com/overview - Welcome go-critic
https://itnext.io/welcome-go-critic-a26b6e30f1c6 - Využití knihovny Pygments (nejenom) pro obarvení zdrojových kódů
https://www.root.cz/clanky/vyuziti-knihovny-pygments-nejenom-pro-obarveni-zdrojovych-kodu/ - LR syntaktický analyzátor
https://cs.wikipedia.org/wiki/LR_syntaktick%C3%BD_analyz%C3%A1tor - Kategorie:Algoritmy syntaktické analýzy
https://cs.wikipedia.org/wiki/Kategorie:Algoritmy_syntaktick%C3%A9_anal%C3%BDzy
