Hlavní navigace

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

4. 1. 2022
Doba čtení: 34 minut

Sdílet

 Autor: Go lang
Dnes se ještě jednou budeme zabývat lexikální a syntaktickou analýzou v Go. Ukážeme si, jak detekovat některé problematické části kódu a taktéž způsob vyhodnocování aritmetických či logických výrazů s jejich mezipřevodem do RPN.

Obsah

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

2. Relační operátor v podmínce programového bloku if

3. Úplný zdrojový kód dnešního prvního demonstračního příkladu

4. Detekce zápisu „Yoda výrazů“

5. Úplný zdrojový kód dnešního druhého demonstračního příkladu

6. Vyhodnocení aritmetických výrazů zapsaných v postfixové notaci

7. Detekce neplatných výrazů

8. Realizace programu pro vyhodnocení výrazů zapsaných v postfixové notaci

9. Implementace zásobníku operandů

10. Úplný zdrojový kód dnešního třetího demonstračního příkladu

11. Vylepšený výpočet postfixových aritmetických výrazů

12. Úplný zdrojový kód dnešního čtvrtého demonstračního příkladu

13. Využití standardního lexikálního analyzátoru pro převod výrazů do postfixové notace

14. Reprezentace tokenů představujících číselnou hodnotu

15. Vlastní převod infixového výrazu do postfixové notace reprezentované sekvencí tokenů

16. Vše pohromadě: korektní vyčíslení aritmetického výrazu zapsaného v notaci kompatibilní s Go

17. Úplný zdrojový kód dnešního pátého demonstračního příkladu

18. Kam dál?

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 (dokončení)

V dnešním článku se ještě jednou budeme zabývat problematikou lexikální a syntaktické analýzy založené na standardních balíčcích umístěných ve jmenném prostoru go (konkrétně se bude jednat o balíčky go/token, go/scanner a go/ast). Ukážeme si především 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. Dále navážeme na kapitoly o postfixové notaci zápisu aritmetických a logických výrazů, protože si ukážeme, jakým způsobem se tyto výrazy vyhodnocují (například v jednoduchém interpretru, šablonovacím systému atd.). Vyhodnocovat přitom budeme jak výrazy zpracovávané vlastním lexikálním analyzátorem (ovšem nutno podotknout, že značně primitivním), tak i standardní knihovnou go/scanner.

2. Relační operátor v podmínce programového bloku if

Nejprve si ukažme, jakým způsobem je možné zjistit, jaký relační operátor (a zda vůbec jaký) je použitý v podmínce uvedené ihned za klíčovým slovem if. Budeme například chtít v následujícím úryvku kódu detekovat zvýrazněné podmínky:

if x > 0 {
}
 
if x != y {
}
 
if 0 < x {
}

Postup je v tomto případě poměrně přímočarý. Nejdříve vytvoříme AST nám již známým způsobem a následně zahájíme průchod jednotlivými uzly tohoto stromu:

// zahájení průchodu abstraktním syntaktickým stromem
ast.Inspect(file, inspectCallback)

Vidíme, že během průchodu je volána callback funkce nazvaná inspectCallback, které je vždy příslušný uzel předán (resp. přesněji řečeno je předán ukazatel na daný uzel). V této callback funkci musíme otestovat, zda se jedná o uzel, kterým začíná podstrom s blokem if. Nejjednodušší podoba této callback funkce by tedy mohla vypadat 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
        ifStatement, found := n.(*ast.IfStmt)
        if found {
                fmt.Print("if statement")
                fmt.Println()
        }
        return true
}

Ovšem ve chvíli, kdy již máme k dispozici uzel typu ast.IfStmt, můžeme pokračovat dále a otestovat, zda zapsaná podmínka (která musí následovat a je uložena v atributu Cond) je představována binárním relačním operátorem s nějakými operandy:

// 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
        ifStatement, found := n.(*ast.IfStmt)
        if found {
                fmt.Print("if statement")
                condition := ifStatement.Cond
                binaryExpr, found := condition.(*ast.BinaryExpr)
                if found {
                        fmt.Print(" with binary condition")
                }
                fmt.Println()
        }
        return true
}

A konečně lze zjistit, jaké jsou operandy právě nalezeného binárního operátoru: může se jednat o numerické hodnoty, proměnnou, složitější výraz atd. V neposlední řadě zjistíme, o jaký binární operand se vlastně jedná:

// 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
        ifStatement, found := n.(*ast.IfStmt)
        if found {
                fmt.Print("if statement")
                condition := ifStatement.Cond
                binaryExpr, found := condition.(*ast.BinaryExpr)
                if found {
                        fmt.Print(" with binary condition")
                        left := getValue(binaryExpr.X)
                        right := getValue(binaryExpr.Y)
                        operand := binaryExpr.Op
                        fmt.Printf(" %s %s %s", left, operand, right)
                }
                fmt.Println()
        }
        return true
}

V předchozím kódu byla volána funkce určená pro získání hodnoty pravého a levého operandu binárního operátoru. V nejjednodušší podobě může tato funkce vypadat takto:

func getValue(n ast.Expr) string {
        switch v := n.(type) {
        case *ast.BasicLit:
                return v.Value
        case *ast.Ident:
                return v.Name
        case *ast.ArrayType:
                if v.Len == nil {
                        return fmt.Sprintf("Slice of %s\n", v.Elt)
                } else {
                        return fmt.Sprintf("Array of %s\n", v.Elt)
                }
        default:
                return fmt.Sprintf("Unrecognized type %T\n", v)
        }
}
Poznámka: v tomto případě se nejedná o žádnou novinku, protože jsme si podobnou funkci ukázali minule. Navíc by správná podoba této funkce měla být rekurzivní, protože samotné podvýrazy tvořící operandy mohou být mnohem komplikovanější.

Po spuštění by se měly zobrazit informace o všech třech zapsaných podmínkách za if:

$ go run condition1.go 
 
if statement with binary condition x > 0
if statement with binary condition x != y
if statement with binary condition 0 < x

3. Úplný zdrojový kód dnešního prvního demonstračního příkladu

Následuje výpis úplného zdrojového kódu příkladu, jehož nejdůležitější části jsme si ukázali v předchozí kapitole:

package main
 
import (
        "fmt"
        "go/ast"
        "go/parser"
        "go/token"
)
 
// zdrojový kód, který se má naparsovat
const source = `
package main
 
func main() {
    var x = 10
    var y = 20
 
    if x > 0 {
    }
 
    if x != y {
    }
 
    if 0 < x {
    }
}
`
 
func getValue(n ast.Expr) string {
        switch v := n.(type) {
        case *ast.BasicLit:
                return v.Value
        case *ast.Ident:
                return v.Name
        case *ast.ArrayType:
                if v.Len == nil {
                        return fmt.Sprintf("Slice of %s\n", v.Elt)
                } else {
                        return fmt.Sprintf("Array of %s\n", v.Elt)
                }
        default:
                return fmt.Sprintf("Unrecognized type %T\n", v)
        }
}
 
// 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
        ifStatement, found := n.(*ast.IfStmt)
        if found {
                fmt.Print("if statement")
                condition := ifStatement.Cond
                binaryExpr, found := condition.(*ast.BinaryExpr)
                if found {
                        fmt.Print(" with binary condition")
                        left := getValue(binaryExpr.X)
                        right := getValue(binaryExpr.Y)
                        operand := binaryExpr.Op
                        fmt.Printf(" %s %s %s", left, operand, right)
                }
                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)
}

4. Detekce zápisu „Yoda výrazů“

Nyní se již dostáváme ke slíbené praktické části – konkrétně k využití průchodu AST k detekci takzvaných „Yoda výrazů“ v podmínce, tedy výrazů založených na binárním relačním operátoru, přičemž první operand je konstanta (literál) zatímco druhý literál proměnná. Většinou se totiž podmínky píšou přesně naopak – prvním operandem je proměnná a druhým operandem konstanta. Viz rozdíly:

if a == 10 { ...
if 10 == a { ...
Poznámka: původ tohoto pojmenování je pravděpodobně zřejmý.

Postup bude jednoduchý, protože již většinu informací i programového kódu máme k dispozici. Je nutné v AST detekovat blok if (umíme), zapsanou podmínku (taktéž umíme), relační operátor a operandy tohoto operátoru (opět umíme). Pouze musíme zjistit i typy operandů, tj. zda se jedná o literály, jména proměnných či o složitější výraz. Upravíme proto funkci getValue takovým způsobem, aby kromě hodnoty operandu vracela i jeho typ:

const (
        nodeTypeLiteral = iota
        nodeTypeIdentifier
        nodeTypeArray
        nodeTypeUnknown
)
 
func getValueAndType(n ast.Expr) (string, int) {
        switch v := n.(type) {
        case *ast.BasicLit:
                return v.Value, nodeTypeLiteral
        case *ast.Ident:
                return v.Name, nodeTypeIdentifier
        case *ast.ArrayType:
                if v.Len == nil {
                        return fmt.Sprintf("Slice of %s\n", v.Elt), nodeTypeArray
                } else {
                        return fmt.Sprintf("Array of %s\n", v.Elt), nodeTypeArray
                }
        default:
                return fmt.Sprintf("Unrecognized type %T\n", v), nodeTypeUnknown
        }
}

Další úprava programu je již triviální – pouze zjistíme typy operandů v podmínce uvedené za if a vypíšeme varování v případě použití stylu mistra Yody:

// 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
        ifStatement, found := n.(*ast.IfStmt)
        if found {
                fmt.Print("if statement")
                condition := ifStatement.Cond
                binaryExpr, found := condition.(*ast.BinaryExpr)
                if found {
                        fmt.Print(" with binary condition")
                        leftValue, leftType := getValueAndType(binaryExpr.X)
                        rightValue, rightType := getValueAndType(binaryExpr.Y)
                        operand := binaryExpr.Op
                        fmt.Printf(" %s %s %s", leftValue, operand, rightValue)
                        if leftType == nodeTypeLiteral && rightType == nodeTypeIdentifier {
                                fmt.Print(" (Yoda style condition detected)")
                        }
                }
                fmt.Println()
        }
        return true
}
Poznámka: alternativně lze pouze testovat, zda je levý operand literál a pravý operand libovolného typu odlišného od literálu.

Výsledek získaný po spuštění tohoto příkladu:

$ go run condition2.go 
 
if statement with binary condition x > 0
if statement with binary condition x != y
if statement with binary condition 0 < x (Yoda style condition detected)
if statement with binary condition 0 > 1

5. Úplný zdrojový kód dnešního druhého demonstračního příkladu

Následuje výpis úplného zdrojového kódu příkladu, jehož nejdůležitější části jsme si ukázali v předchozí kapitole:

package main
 
import (
        "fmt"
        "go/ast"
        "go/parser"
        "go/token"
)
 
// zdrojový kód, který se má naparsovat
const source = `
package main
 
func main() {
    var x = 10
    var y = 20
 
    if x > 0 {
    }
 
    if x != y {
    }
 
    if 0 < x {
    }
 
    if 0 > 1 {
    }
}
`
 
const (
        nodeTypeLiteral = iota
        nodeTypeIdentifier
        nodeTypeArray
        nodeTypeUnknown
)
 
func getValueAndType(n ast.Expr) (string, int) {
        switch v := n.(type) {
        case *ast.BasicLit:
                return v.Value, nodeTypeLiteral
        case *ast.Ident:
                return v.Name, nodeTypeIdentifier
        case *ast.ArrayType:
                if v.Len == nil {
                        return fmt.Sprintf("Slice of %s\n", v.Elt), nodeTypeArray
                } else {
                        return fmt.Sprintf("Array of %s\n", v.Elt), nodeTypeArray
                }
        default:
                return fmt.Sprintf("Unrecognized type %T\n", v), nodeTypeUnknown
        }
}
 
// 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
        ifStatement, found := n.(*ast.IfStmt)
        if found {
                fmt.Print("if statement")
                condition := ifStatement.Cond
                binaryExpr, found := condition.(*ast.BinaryExpr)
                if found {
                        fmt.Print(" with binary condition")
                        leftValue, leftType := getValueAndType(binaryExpr.X)
                        rightValue, rightType := getValueAndType(binaryExpr.Y)
                        operand := binaryExpr.Op
                        fmt.Printf(" %s %s %s", leftValue, operand, rightValue)
                        if leftType == nodeTypeLiteral && rightType == nodeTypeIdentifier {
                                fmt.Print(" (Yoda style condition detected)")
                        }
                }
                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)
}

6. Vyhodnocení aritmetických výrazů zapsaných v postfixové notaci

V předchozím článku jsme se kromě dalších věcí seznámili i s tím, jakým způsobem lze převést aritmetický či logický výraz zapsaný v klasické infixové notaci na totožný výraz, ovšem nyní zapsaný v notaci postfixové (označované taktéž zkratkou RPN). 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, ve kterém okamžiku se operace vykoná – konkrétně ihned poté, co je přijat její token. Z praktického pohledu je ovšem neméně důležité, že aritmetické i logické výrazy zapsané s využitím RPN se 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. A právě výpočtem výrazů zapsaných v postfixové notaci se budeme zabývat v navazujícím textu.

O tom, jak bude realizován výpočet postfixově zapsaného aritmetického nebo logického výrazu, jsme si taktéž řekli. Celý algoritmus je založen na použití zásobníku operandů (mimochodem – na zásobníku je založen i převod z infixové notace do notace postfixové, což je zvláštní shoda). Operandy (tj. numerické hodnoty, popř. hodnoty proměnných) jsou totiž nejdříve odkládány na tento zásobník a teprve poté, co je přijat operátor, jsou operandy (popř. jeden operand) získány ze zásobníku operandů, a to operací typu pop, která tyto hodnoty ze zásobníku současně i odstraní. Celý výpočet by mohl probíhat následovně:

  1. Je načten token obsahující hodnotu symbolu z výrazu reprezentovaného v postfixové notaci (RPN). Jedná se buď o numerickou hodnotu, jméno proměnné nebo symbol operátoru (+, -, *, / a řekněme %).
  2. V případě, že se jedná o číselnou hodnotu, je tato hodnota uložena na zásobník (nazývaný, jak již víme, 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 binární operátor, jsou ze zásobníku (přesněji řečeno ze zásobníku operandů) vyzvednuty oba operandy, operace se provede a výsledek se opět uloží na zásobník. U unárního operátoru (změna znaménka atd.) se pochopitelně pracuje pouze s jediným operandem.
  5. Na konci bude na zásobníku uložena jediná hodnota, kterou je výsledek.
Poznámka: existují i další rozšíření, například pro podporu volání funkcí, provádění speciálních zásobníkových operací (dup, drop, rot, swap, over) atd.

7. Detekce neplatných výrazů

Užitečná je i detekce neplatných výrazů. I pokud budeme předpokládat, že vždy budeme přijímat korektní tokeny (tj. nepřečteme například token představující pravou kulatou závorku atd.), mohou nastat následující stavy značící, že vstupní výraz není zapsán korektně:

  1. Je přijat token představující unární operátor a současně je zásobník operandů prázdný. V takovém případě není pochopitelně možné danou operaci provést.
  2. Je přijat token představující binární operátor (například operátor součtu) a zásobník operandů je buď prázdný (viz výše) nebo obsahuje pouze jeden operand. I toto je pochopitelně stav, který může nastat jen ve chvíli, kdy je vstupní výraz nekorektní.
  3. Na konci, tedy po příjmu a zpracování posledního tokenu, je na zásobníku operandů uloženo větší množství hodnot. V korektním případě by zde měla být uložena hodnota jediná.
  4. Teoreticky může být na konci (tedy po příjmu a zpracování posledního tokenu) zásobník operandů prázdný. To však nastane jen ve chvíli, kdy je i vstupní výraz prázdný. Binární operátory totiž sice snižují počet hodnot uložených na zásobníku operandů o jeden prvek, ale nikdy se nemohou dostat až k prázdnému zásobníku.

8. Realizace programu pro vyhodnocení výrazů zapsaných v postfixové notaci

Nyní se již můžeme zabývat další praktickou částí, konkrétně vlastní implementací algoritmu určeného pro vyhodnocení aritmetických, popř. logických výrazů zapsaných v postfixové notaci. První z těchto demonstračních příkladů je rozdělen do několika částí:

  1. Rozdělení vstupu (v tomto případě řetězce) s RPN výrazem na jednotlivé prvky, které představují buď operátory nebo operandy.
  2. Postupné načítání těchto prvků, jejich převod z řetězcové podoby na obdobu tokenů (první dva kroky tedy zhruba odpovídají lexikální analýze).
  3. Vyhodnocování podle pravidel algoritmu RPN uvedeného v předchozím textu. Přitom je použita velmi jednoduchá implementace zásobníku operandů založená na řezu (slice).
  4. Na konci je obsah zásobníku operandů vypsán na standardní výstup. Teoreticky by měl být vypsán pouze jediný výsledek, ovšem i když bude výraz zapsán chybně, dojde k výpisu obsahu celého zásobníku operandů.

Nyní se podrobněji na jednotlivé části celého programu podíváme. Začneme rozdělením vstupu s RPN výrazem na jednotlivé prvky, které by měly představovat buď operátory nebo operandy. Pokud budeme předpokládat, že jsou jednotlivé prvky ve vstupním řetězci odděleny alespoň jednou mezerou (což ovšem v RPN nemusí být pravda!), je tato operace implementovaná v jazyku Go triviální, protože již existuje ve formě funkce ze základní knihovny:

// rozdělení původního výrazu na jednotlivé části
parts := strings.Fields(expr)

Nejzajímavější část celého programu se stará o vlastní vyhodnocování výrazů. Základní postup již známe – v případě, že je načtena numerická konstanta, je vždy uložena na zásobník operandů. Pokud je naopak načten operátor, jsou ze zásobníku získány operandy a je provedena zvolená operace:

// postupné zpracování jednotlivých částí původního výrazu
for _, part := range parts {
        // test, zda se jedná o operátor
        _, isOperator := operators[part]
        if isOperator {
                // našli jsme operátor
                // -> provést zvolenou operaci
                //    + uložit výsledek na zásobník
                err := performArithmeticOperation(&stack, part)
                if err != nil {
                        return stack, err
                }
        } else {
                // nejedná se o operátor
                // -> zkusíme tedy vstup zpracovat jako číslo
                val, err := strconv.Atoi(part)
                if err != nil {
                        // neočekávaný vstup
                        return stack, fmt.Errorf("Incorrect input: %s", part)
                } else {
                        // našli jsme číselnou hodnotu
                        // ta se uloží na zásobník operandů
                        stack.Push(val)
                }
        }
}

Realizace zvolené operace je v první verzi algoritmu „zadrátovaná“ přímo do zdrojového kódu. Nejedná se ani zdaleka o to nejelegantnější řešení, ovšem je snadno přenositelné i do těch programovacích jazyků, v nichž nejsou funkce plnohodnotnými datovými typy:

// provedení vybrané aritmetické operace
func performArithmeticOperation(stack *Stack, operator string) error {
        // získat druhý operand ze zásobníku
        y, err := stack.Pop()
        if err != nil {
                return err
        }
 
        // získat první operand ze zásobníku
        x, err := stack.Pop()
        if err != nil {
                return err
        }
 
        var result int
 
        // vlastní provedení operace
        switch operator {
        case "+":
                result = x + y
        case "-":
                result = x - y
        case "*":
                result = x * y
        case "/":
                result = x / y
        }
 
        // uložení výsledku operace zpět na zásobník
        stack.Push(result)
 
        return nil
}
Poznámka: povšimněte si, který operand načítaný ze zásobníku operandů je při vyhodnocování „levý“ a který „pravý“. U těch operací, které jsou komutativní (což je součet a součin) na pořadí operandů pochopitelně nezáleží, ale u operací nekomutativních (rozdíl, podíl, podíl modulo) již ano.

Nakonec nám pouze zbývá vypsat obsah zásobníku operandů. Pokud se zobrazí jeden výsledek, byl výraz zapsán korektně, ovšem při nekorektním zápisu může nastat situace, kdy bude zásobník operandů prázdný, popř. naopak bude obsahovat větší množství hodnot (ty budou taktéž vypsány, což je ostatně ze zdrojového kódu jasně patrné):

// tisk obsahu zásobníku operandů
func printStack(stack Stack) {
        if stack.Empty() {
                fmt.Println("Empty stack!")
                return
        }
 
        // zásobník není prázdný, proto postupně vytiskneme uložené operandy
        for !stack.Empty() {
                value, _ := stack.Pop()
                fmt.Printf("%d\n", value)
        }
}

9. Implementace zásobníku operandů

Některé části programu popsaného výše vyžadují implementaci zásobníku operandů. Pro jednoduchost můžeme použít implementaci založenou na řezu (slice), ovšem s tím, že se zdaleka nemusí jednat o implementaci nejrychlejší (záleží na algoritmu pro alokaci prvků řezu – v tomto případě by bylo výhodnější provést prealokaci pro řekněme šestnáct číselných hodnot s případnou realokací):

// primitivní neoptimalizovaná varianta zásobníku
type Stack struct {
        stack []int
}

Implementace zásobníku jakožto nového datového typu je v jazyce Go triviální, stejně jako podporované operace představované metodami:

// uložení hodnoty na zásobník
func (stack *Stack) Push(value int) {
        stack.stack = append(stack.stack, value)
}
 
// přečtení hodnoty ze zásobníku s kontrolou, zda není zásobník prázdný
func (stack *Stack) Pop() (int, error) {
        if stack.Empty() {
                return -1, fmt.Errorf("Empty stack")
        }
 
        // index nejvyššího prvku na zásobníku
        tos := len(stack.stack) - 1
 
        // přečtení elementru ze zásobníku
        element := stack.stack[tos]
 
        // odstranění elementu ze zásobníku
        stack.stack = stack.stack[:tos]
        return element, nil
}
 
// test, zda je zásobník prázdný
func (stack *Stack) Empty() bool {
        return len(stack.stack) == 0
}

10. Úplný zdrojový kód dnešního třetího demonstračního příkladu

Následuje výpis úplného zdrojového kódu příkladu, jehož nejdůležitější části jsme si popsali v předchozích dvou kapitolách:

package main
 
import (
        "fmt"
        "strconv"
        "strings"
)
 
// původní výraz v infixové notaci
// 1 + 2 * (3 + 4) + 5 * (6 - 7)
 
// výraz převedený do postfixové notace
const expr = "1 2 3 4 + * + 5 6 7 - * +"
 
// primitivní neoptimalizovaná varianta zásobníku
type Stack struct {
        stack []int
}
 
// uložení hodnoty na zásobník
func (stack *Stack) Push(value int) {
        stack.stack = append(stack.stack, value)
}
 
// přečtení hodnoty ze zásobníku s kontrolou, zda není zásobník prázdný
func (stack *Stack) Pop() (int, error) {
        if stack.Empty() {
                return -1, fmt.Errorf("Empty stack")
        }
 
        // index nejvyššího prvku na zásobníku
        tos := len(stack.stack) - 1
 
        // přečtení elementru ze zásobníku
        element := stack.stack[tos]
 
        // odstranění elementu ze zásobníku
        stack.stack = stack.stack[:tos]
        return element, nil
}
 
// test, zda je zásobník prázdný
func (stack *Stack) Empty() bool {
        return len(stack.stack) == 0
}
 
// vyhodnocení výrazu zapsaného v postfixové notaci
func evaluate(expr string) (Stack, error) {
        // všechny dostupné aritmetické operátory
        operators := map[string]interface{}{
                "+": nil,
                "-": nil,
                "*": nil,
                "/": nil,
        }
 
        // rozdělení původního výrazu na jednotlivé části
        parts := strings.Fields(expr)
 
        // zásobník operandů (na začátku prázdný)
        var stack Stack
 
        // postupné zpracování jednotlivých částí původního výrazu
        for _, part := range parts {
                // test, zda se jedná o operátor
                _, isOperator := operators[part]
                if isOperator {
                        // našli jsme operátor
                        // -> provést zvolenou operaci
                        //    + uložit výsledek na zásobník
                        err := performArithmeticOperation(&stack, part)
                        if err != nil {
                                return stack, err
                        }
                } else {
                        // nejedná se o operátor
                        // -> zkusíme tedy vstup zpracovat jako číslo
                        val, err := strconv.Atoi(part)
                        if err != nil {
                                // neočekávaný vstup
                                return stack, fmt.Errorf("Incorrect input: %s", part)
                        } else {
                                // našli jsme číselnou hodnotu
                                // ta se uloží na zásobník operandů
                                stack.Push(val)
                        }
                }
        }
 
        // nyní by měl zásobník operandů obsahovat jedinou hodnotu
        return stack, nil
}
 
// provedení vybrané aritmetické operace
func performArithmeticOperation(stack *Stack, operator string) error {
        // získat druhý operand ze zásobníku
        y, err := stack.Pop()
        if err != nil {
                return err
        }
 
        // získat první operand ze zásobníku
        x, err := stack.Pop()
        if err != nil {
                return err
        }
 
        var result int
 
        // vlastní provedení operace
        switch operator {
        case "+":
                result = x + y
        case "-":
                result = x - y
        case "*":
                result = x * y
        case "/":
                result = x / y
        }
 
        // uložení výsledku operace zpět na zásobník
        stack.Push(result)
 
        return nil
}
 
// tisk obsahu zásobníku operandů
func printStack(stack Stack) {
        if stack.Empty() {
                fmt.Println("Empty stack!")
                return
        }
 
        // zásobník není prázdný, proto postupně vytiskneme uložené operandy
        for !stack.Empty() {
                value, _ := stack.Pop()
                fmt.Printf("%d\n", value)
        }
}
 
func main() {
        stack, err := evaluate(expr)
        if err != nil {
                fmt.Println(err)
                return
        }
        printStack(stack)
}

11. Vylepšený výpočet postfixových aritmetických výrazů

Jak jsme se již naznačili v předchozím textu, není realizace výpočtů postfixových výrazů realizována tím nejefektivnějším způsobem. Tuto část můžeme ovšem relativně snadno upravit, a to například tak, že se (anonymní) funkce pro výpočet jednotlivých operací uloží do mapy operandů, kterou jsme až doposud používali ve funkci množiny (set):

// funkce provádějící výpočet na základě použitého operátoru
type Operator func(int, int) int

Takto vytvořená mapa je do značné míry v programovacím jazyku Go idiomatická:

// všechny dostupné aritmetické operátory
operators := map[string]Operator{
        "+": func(x int, y int) int { return x + y },
        "-": func(x int, y int) int { return x - y },
        "*": func(x int, y int) int { return x * y },
        "/": func(x int, y int) int { return x / y },
}

Díky tomu, že u každého operandu máme k dispozici i přímo funkci pro vlastní výpočet, je další část programového kódu jednodušší, než tomu bylo v předchozím demonstračním příkladu (navíc je automaticky rozšiřitelná o další operátory):

// provedení vybrané aritmetické operace
func performArithmeticOperation(stack *Stack, operator Operator) error {
        // získat druhý operand ze zásobníku
        y, err := stack.Pop()
        if err != nil {
                return err
        }
 
        // získat první operand ze zásobníku
        x, err := stack.Pop()
        if err != nil {
                return err
        }
 
        // vlastní provedení operace
        result := operator(x, y)
 
        // uložení výsledku operace zpět na zásobník
        stack.Push(result)
 
        return nil
}

12. Úplný zdrojový kód dnešního čtvrtého demonstračního příkladu

Jen pro úplnost si ukažme, jak vypadá celý zdrojový kód čtvrtého demonstračního příkladu:

package main
 
import (
        "fmt"
        "strconv"
        "strings"
)
 
// původní výraz v infixové notaci
// 1 + 2 * (3 + 4) + 5 * (6 - 7)
 
// výraz převedený do postfixové notace
const expr = "1 2 3 4 + * + 5 6 7 - * +"
 
// primitivní neoptimalizovaná varianta zásobníku
type Stack struct {
        stack []int
}
 
// uložení hodnoty na zásobník
func (stack *Stack) Push(value int) {
        stack.stack = append(stack.stack, value)
}
 
// přečtení hodnoty ze zásobníku s kontrolou, zda není zásobník prázdný
func (stack *Stack) Pop() (int, error) {
        if stack.Empty() {
                return -1, fmt.Errorf("Empty stack")
        }
 
        // index nejvyššího prvku na zásobníku
        tos := len(stack.stack) - 1
 
        // přečtení elementru ze zásobníku
        element := stack.stack[tos]
 
        // odstranění elementu ze zásobníku
        stack.stack = stack.stack[:tos]
        return element, nil
}
 
// test, zda je zásobník prázdný
func (stack *Stack) Empty() bool {
        return len(stack.stack) == 0
}
 
// funkce provádějící výpočet na základě použitého operátoru
type Operator func(int, int) int
 
// vyhodnocení výrazu zapsaného v postfixové notaci
func evaluate(expr string) (Stack, error) {
        // všechny dostupné aritmetické operátory
        operators := map[string]Operator{
                "+": func(x int, y int) int { return x + y },
                "-": func(x int, y int) int { return x - y },
                "*": func(x int, y int) int { return x * y },
                "/": func(x int, y int) int { return x / y },
        }
 
        // rozdělení původního výrazu na jednotlivé části
        parts := strings.Fields(expr)
 
        // zásobník operandů (na začátku prázdný)
        var stack Stack
 
        // postupné zpracování jednotlivých částí původního výrazu
        for _, part := range parts {
                // test, zda se jedná o operátor
                operator, isOperator := operators[part]
                if isOperator {
                        // našli jsme operátor
                        // -> provést zvolenou operaci
                        //    + uložit výsledek na zásobník
                        err := performArithmeticOperation(&stack, operator)
                        if err != nil {
                                return stack, err
                        }
                } else {
                        // nejedná se o operátor
                        // -> zkusíme tedy vstup zpracovat jako číslo
                        val, err := strconv.Atoi(part)
                        if err != nil {
                                // neočekávaný vstup
                                return stack, fmt.Errorf("Incorrect input: %s", part)
                        } else {
                                // našli jsme číselnou hodnotu
                                // ta se uloží na zásobník operandů
                                stack.Push(val)
                        }
                }
        }
 
        // nyní by měl zásobník operandů obsahovat jedinou hodnotu
        return stack, nil
}
 
// provedení vybrané aritmetické operace
func performArithmeticOperation(stack *Stack, operator Operator) error {
        // získat druhý operand ze zásobníku
        y, err := stack.Pop()
        if err != nil {
                return err
        }
 
        // získat první operand ze zásobníku
        x, err := stack.Pop()
        if err != nil {
                return err
        }
 
        // vlastní provedení operace
        result := operator(x, y)
 
        // uložení výsledku operace zpět na zásobník
        stack.Push(result)
 
        return nil
}
 
// tisk obsahu zásobníku operandů
func printStack(stack Stack) {
        if stack.Empty() {
                fmt.Println("Empty stack!")
                return
        }
 
        // zásobník není prázdný, proto postupně vytiskneme uložené operandy
        for !stack.Empty() {
                value, _ := stack.Pop()
                fmt.Printf("%d\n", value)
        }
}
 
func main() {
        stack, err := evaluate(expr)
        if err != nil {
                fmt.Println(err)
                return
        }
        printStack(stack)
}

13. Využití standardního lexikálního analyzátoru pro převod výrazů do postfixové notace

V předchozích dvou příkladech jsme použili vlastní velmi jednoduchý lexikální analyzátor, který ze vstupního řetězce vytvořil prvky, jež můžeme považovat za tokeny. Alternativně je však možné použít i lexikální analyzátor realizovaný ve standardním balíčku go/scanner. A navíc – můžeme lexikální analýzu spojit s převodem infixových výrazů do výrazů postfixových, což jsme si již ukázali minule. V dalším kódu tedy budeme provádět následující operace:

  1. Lexikální analýzu standardních výrazů v jazyce Go do podoby sekvence tokenů
  2. Převod této sekvence tokenů do postfixové notace

14. Reprezentace tokenů představujících číselnou hodnotu

Při převodu výrazů budeme pracovat se třemi skupinami tokenů. Jedná se o tokeny představující nějaký aritmetický operátor, dále o tokeny reprezentující pravou či levou závorku a konečně o tokeny představující číselnou hodnotu. A právě u třetí skupiny tokenů si budeme muset zapamatovat i konkrétní hodnotu – v balíčku go/scanner totiž token představuje pouze typ lexikální jednotky a nikoli již její konkrétní hodnotu!

Jedna z možností je reprezentace tokenu s hodnotou pomocí uživatelské struktury:

type TokenWithValue struct {
        Token token.Token
        Value int
}

Pomocné konstruktory této struktury, a to jak pro token představující operátor, tak i pro token představující číselnou hodnotu:

func ValueToken(tok token.Token, value int) TokenWithValue {
        return TokenWithValue{
                Token: tok,
                Value: value,
        }
}
 
func OperatorToken(tok token.Token) TokenWithValue {
        return TokenWithValue{
                Token: tok,
        }
}

15. Vlastní převod infixového výrazu do postfixové notace reprezentované sekvencí tokenů

V tento okamžik již můžeme upravit demonstrační příklad z předchozího článku do takové podoby, že výsledkem nebude přímo text s postfixovým výrazem, ale sekvence tokenů, přesněji řečeno sekvence struktur TokenWithValue:

package main
 
import (
        "fmt"
        "strconv"
 
        "go/scanner"
        "go/token"
)
 
// výraz, který se má převést na RPN
const source = `
1 + 2 * (3 + 4) + 5 * (6 - 7)
`
 
type TokenWithValue struct {
        Token token.Token
        Value int
}
 
func ValueToken(tok token.Token, value int) TokenWithValue {
        return TokenWithValue{
                Token: tok,
                Value: value,
        }
}
 
func OperatorToken(tok token.Token) TokenWithValue {
        return TokenWithValue{
                Token: tok,
        }
}
 
func toRPN(s scanner.Scanner) []TokenWithValue {
        var operators = map[token.Token]int{
                token.MUL: 2,
                token.QUO: 2,
                token.REM: 2,
                token.ADD: 1,
                token.SUB: 1,
        }
 
        var stack []token.Token
 
        var output []TokenWithValue
 
        // postupné provádění tokenizace a zpracování jednotlivých tokenů
loop:
        for {
                _, tok, value := s.Scan()
                switch tok {
                case token.INT:
                        // celé číslo přímo předat na výstup
                        intValue, _ := strconv.Atoi(value)
                        output = append(output, ValueToken(tok, intValue))
                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 předají na výstup
                                output = append(output, OperatorToken(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 ->
                                        // zpracovat nalezený na zásobníku
                                        // a odstranit tento operátor ze zásobníku
                                        stack = stack[:len(stack)-1] // POP
                                        output = append(output, OperatorToken(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 {
                output = append(output, OperatorToken(stack[len(stack)-1]))
                stack = stack[:len(stack)-1]
        }
 
        return output
}
 
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
        postfixExpression := toRPN(s)
 
        // tisk všech operandů a operátorů postfixového výrazu
        for i, tok := range postfixExpression {
                // oddělení jednotlivých členů a operátorů
                if i > 0 {
                        fmt.Print(" ")
                }
 
                // tisk číselné hodnoty popř. tokenu představujícího operátor
                if tok.Token == token.INT {
                        fmt.Printf("%d", tok.Value)
                } else {
                        fmt.Printf("%s", tok.Token)
                }
        }
}

Výsledek, který získáme po spuštění:

1 2 3 4 + * + 5 6 7 - * +

16. Vše pohromadě: korektní vyčíslení aritmetického výrazu zapsaného v notaci kompatibilní s Go

Nyní již máme k dispozici implementaci dvou algoritmů, a to konkrétně:

  1. Algoritmu pro převod výrazu z infixové notace do sekvence tokenů představujících výraz v notaci postfixové
  2. Algoritmu umožňujícího výpočet (resp. přesněji řečeno vyhodnocení) výrazu v postfixové notaci

Nezbývá nám tedy nic jiného, než obě realizace algoritmů spojit, což se ukazuje být velmi snadné, jak to ostatně bude patrné ze zdrojového kódu uvedeného v následující kapitole.

ICTZ23

17. Úplný zdrojový kód dnešního pátého demonstračního příkladu

package main
 
import (
        "fmt"
        "strconv"

        "go/scanner"
        "go/token"
)
 
// výraz, který se má převést na RPN a následně vyhodnotit
const source = `
1 + 2 * (3 + 4) + 5 * (6 - 7)
`
 
// primitivní neoptimalizovaná varianta zásobníku operandů
type Stack struct {
        stack []int
}
 
// uložení hodnoty na zásobník
func (stack *Stack) Push(value int) {
        stack.stack = append(stack.stack, value)
}
 
// přečtení hodnoty ze zásobníku s kontrolou, zda není zásobník prázdný
func (stack *Stack) Pop() (int, error) {
        if stack.Empty() {
                return -1, fmt.Errorf("Empty stack")
        }
 
        // index nejvyššího prvku na zásobníku
        tos := len(stack.stack) - 1
 
        // přečtení elementru ze zásobníku
        element := stack.stack[tos]
 
        // odstranění elementu ze zásobníku
        stack.stack = stack.stack[:tos]
        return element, nil
}
 
// test, zda je zásobník prázdný
func (stack *Stack) Empty() bool {
        return len(stack.stack) == 0
}
 
// funkce provádějící výpočet na základě použitého operátoru
type Operator func(int, int) int
 
type TokenWithValue struct {
        Token token.Token
        Value int
}
 
func ValueToken(tok token.Token, value int) TokenWithValue {
        return TokenWithValue{
                Token: tok,
                Value: value,
        }
}
 
func OperatorToken(tok token.Token) TokenWithValue {
        return TokenWithValue{
                Token: tok,
        }
}
 
func toRPN(s scanner.Scanner) []TokenWithValue {
        var operators = map[token.Token]int{
                token.MUL: 2,
                token.QUO: 2,
                token.REM: 2,
                token.ADD: 1,
                token.SUB: 1,
        }
 
        var stack []token.Token
 
        var output []TokenWithValue
 
        // postupné provádění tokenizace a zpracování jednotlivých tokenů
loop:
        for {
                _, tok, value := s.Scan()
                switch tok {
                case token.INT:
                        // celé číslo přímo předat na výstup
                        intValue, _ := strconv.Atoi(value)
                        output = append(output, ValueToken(tok, intValue))
                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 předají na výstup
                                output = append(output, OperatorToken(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 ->
                                        // zpracovat nalezený na zásobníku
                                        // a odstranit tento operátor ze zásobníku
                                        stack = stack[:len(stack)-1] // POP
                                        output = append(output, OperatorToken(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 {
                output = append(output, OperatorToken(stack[len(stack)-1]))
                stack = stack[:len(stack)-1]
        }
 
        return output
}
 
// vyhodnocení výrazu převedeného do sekvence tokenů v postfixové notaci
func evaluate(expr []TokenWithValue) (Stack, error) {
        // všechny dostupné aritmetické operátory
        operators := map[token.Token]Operator{
                token.ADD: func(x int, y int) int { return x + y },
                token.SUB: func(x int, y int) int { return x - y },
                token.MUL: func(x int, y int) int { return x * y },
                token.QUO: func(x int, y int) int { return x / y },
                token.REM: func(x int, y int) int { return x % y },
        }
 
        // zásobník operandů (na začátku prázdný)
        var stack Stack
 
        // postupné zpracování jednotlivých částí původního výrazu reprezentovaných tokeny
        for _, tok := range expr {
                // test, zda se jedná o operátor
                operator, isOperator := operators[tok.Token]
                if isOperator {
                        // našli jsme operátor
                        // -> provést zvolenou operaci
                        //    + uložit výsledek na zásobník
                        err := performArithmeticOperation(&stack, operator)
                        if err != nil {
                                return stack, err
                        }
                } else {
                        // nejedná se o operátor
                        // -> zkusíme tedy vstup zpracovat jako číslo
                        if tok.Token == token.INT {
                                // našli jsme číselnou hodnotu
                                // ta se uloží na zásobník operandů
                                stack.Push(tok.Value)
                        } else {
                                // neočekávaný vstup
                                return stack, fmt.Errorf("Incorrect input token: %s", tok)
                        }
                }
        }
 
        // nyní by měl zásobník operandů obsahovat jedinou hodnotu
        return stack, nil
}
 
// provedení vybrané aritmetické operace
func performArithmeticOperation(stack *Stack, operator Operator) error {
        // získat druhý operand ze zásobníku
        y, err := stack.Pop()
        if err != nil {
                return err
        }
 
        // získat první operand ze zásobníku
        x, err := stack.Pop()
        if err != nil {
                return err
        }
 
        // vlastní provedení operace
        result := operator(x, y)
 
        // uložení výsledku operace zpět na zásobník
        stack.Push(result)
 
        return nil
}
 
// tisk obsahu zásobníku operandů
func printStack(stack Stack) {
        if stack.Empty() {
                fmt.Println("Empty stack!")
                return
        }
 
        // zásobník není prázdný, proto postupně vytiskneme uložené operandy
        for !stack.Empty() {
                value, _ := stack.Pop()
                fmt.Printf("%d\n", value)
        }
}
 
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
        postfixExpression := toRPN(s)
 
        // vyhodnocení výrazu v postfixové notaci
        stack, err := evaluate(postfixExpression)
        if err != nil {
                fmt.Println(err)
                return
        }
 
        // výpis obsahu zásobníku operandů
        printStack(stack)
}

18. Kam dál?

Možnosti poskytované standardními balíčky go/scanner a go/ast doplněnými o balíček go/token jsou sice ještě širší, než jsme si doposud popsali, ovšem na druhou stranu jsou již z principu omezeny na zpracování bloků kódu či jednotlivých výrazů odpovídajících syntaxi programovacího jazyka Go. V případě, že budete potřebovat zpracovávat zdrojové kódy, šablony či „jen“ DSL či konfigurační soubory s odlišnou syntaxí, nebudou tyto balíčky dostačovat a je nutné se poohlédnout po jiných řešeních, a to jak pro lexikální analyzátor (lexer), tak i pro analyzátor syntaktický (parser). K některým postupům se vrátíme v dalších článcích o programovacím jazyce Go.

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

Zdrojové kódy všech předminule, 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/article84/con­dition1.go
32 condition2.go praktický příklad: detekce zápisu „yoda výrazů“ https://github.com/tisnik/go-root/blob/master/article84/con­dition2.go
       
33 rpn_calculator1.go vyhodnocení výrazu v infixové notaci, základní řešení https://github.com/tisnik/go-root/blob/master/article84/rpn_cal­culator1.go
34 rpn_calculator2.go vyhodnocení výrazu v infixové notaci, vylepšené řešení založené na předchozím příkladu https://github.com/tisnik/go-root/blob/master/article84/rpn_cal­culator2.go
35 rpn_from_infix.go převod aritmetického výrazu z infixové notace do sekvence tokenů v postfixové notaci https://github.com/tisnik/go-root/blob/master/article84/rpn_from_in­fix.go
36 rpn_calculator3.go vyhodnocení výrazu v infixové notaci, kombinace předchozích dvou příkladů https://github.com/tisnik/go-root/blob/master/article84/rpn_cal­culator3.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. Handwritten Parsers & Lexers in Go
    https://blog.gopheracademy.com/advent-2014/parsers-lexers/
  4. Code generation in Go using abstract syntax trees (AST)
    https://blog.stein.wtf/posts/go-abstract-syntax-tree-code-generation
  5. Shunting-yard algorithm
    https://en.wikipedia.org/wiki/Shunting-yard_algorithm
  6. Abstract syntax tree
    https://en.wikipedia.org/wi­ki/Abstract_syntax_tree
  7. Lexical analysis
    https://en.wikipedia.org/wi­ki/Lexical_analysis
  8. Parser
    https://en.wikipedia.org/wi­ki/Parsing#Parser
  9. Golang AST Package
    https://golangdocs.com/golang-ast-package
  10. Dokumentace k balíčku go/ast
    https://pkg.go.dev/go/ast
  11. Dokumentace k balíčku go/scanner
    https://pkg.go.dev/go/scanner
  12. Dokumentace k balíčku go/parser
    https://pkg.go.dev/go/parser
  13. Dokumentace k balíčku go/token
    https://pkg.go.dev/go/token
  14. AP8, IN8 Regulární jazyky
    http://statnice.dqd.cz/home:inf:ap8
  15. AP9, IN9 Konečné automaty
    http://statnice.dqd.cz/home:inf:ap9
  16. AP10, IN10 Bezkontextové jazyky
    http://statnice.dqd.cz/home:inf:ap10
  17. AP11, IN11 Zásobníkové automaty, Syntaktická analýza
    http://statnice.dqd.cz/home:inf:ap11
  18. Introduction to YACC
    https://www.geeksforgeeks­.org/introduction-to-yacc/
  19. Introduction of Lexical Analysis
    https://www.geeksforgeeks­.org/introduction-of-lexical-analysis/?ref=lbp
  20. 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/
  21. Popis příkazu gofmt
    https://pkg.go.dev/cmd/gofmt
  22. Popis příkazu govet
    https://pkg.go.dev/cmd/vet
  23. Repositář nástroje errcheck
    https://github.com/kisielk/errcheck
  24. Repositář nástroje goconst
    https://github.com/jgautheron/goconst
  25. Repositář nástroje gocyclo
    https://github.com/fzipp/gocyclo
  26. Repositář nástroje ineffassign
    https://github.com/gordon­klaus/ineffassign
  27. Repositář nástroje gosec
    https://github.com/securego/gosec
  28. Repositář nástroje go-critic
    https://github.com/go-critic/go-critic
  29. Seznam testů prováděných nástrojem go-critic
    https://go-critic.com/overview
  30. Welcome go-critic
    https://itnext.io/welcome-go-critic-a26b6e30f1c6
  31. Využití knihovny Pygments (nejenom) pro obarvení zdrojových kódů
    https://www.root.cz/clanky/vyuziti-knihovny-pygments-nejenom-pro-obarveni-zdrojovych-kodu/
  32. LR syntaktický analyzátor
    https://cs.wikipedia.org/wi­ki/LR_syntaktick%C3%BD_ana­lyz%C3%A1tor
  33. 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.