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
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
19. Repositář s demonstračními příklady
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)
}
}
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 { ...
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
}
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ě:
- 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 %).
- 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í).
- 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 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.
- Na konci bude na zásobníku uložena jediná hodnota, kterou je výsledek.
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ě:
- 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.
- 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í.
- 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á.
- 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í:
- Rozdělení vstupu (v tomto případě řetězce) s RPN výrazem na jednotlivé prvky, které představují buď operátory nebo operandy.
- 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).
- 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).
- 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
}
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:
- Lexikální analýzu standardních výrazů v jazyce Go do podoby sekvence tokenů
- 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ě:
- Algoritmu pro převod výrazu z infixové notace do sekvence tokenů představujících výraz v notaci postfixové
- 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.
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:
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 - Handwritten Parsers & Lexers in Go
https://blog.gopheracademy.com/advent-2014/parsers-lexers/ - 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
ČLÁNKY DO MAILU