Recursive descent - 4. díl vlastní kalkulačky

Article in English can be found on dev.to/arxeiss/recursive-descent-parser-5581

Tento článek patří do seriálu Vlastní kalkulačka s výrazy. Ostatní články seriálu:

• Lexer - 1. díl vlastní kalkulačky s výrazy
• Shunting yard algoritmus - 2. díl vlastní kalkulačky
• Evaluator AST - 3. díl vlastní kalkulačky
• Recursive descent - 4. díl vlastní kalkulačky

---

Podle názvu je jasné, že rekurze je to, na čem celý parser stojí. Každá funkce nejčastěji zpracovává jedno pravidlo gramatiky, viz níže, a tyto funkce se volají navzájem. Pro pochopení a správný návrh parseru je prvně nutné pochopit co jsou bezkontextové gramatiky a jak parser ovlivňují. 

Kompletní zdrojový kód včetně testů je na github.com/arxeiss/go-expression-calculator, kde lze spustit také REPL (interaktivní mód). Teorie gramatik je sice nudná akademická záležitost, ale parser přímo zrcadlí danou gramatiku, proto doporučuji alespoň základní pochopení.

LL(k) gramatiky

Podrobněji jsou gramatiky popsány na Wiki - LL analyzátor, nyní ale stačí základy. Parser totiž následně zrcadlí strukturu této gramatiky. Třída gramatiky LL(k) značí, že daná gramatika neobsahuje levou rekurzi. A programu stačí znát max k následujících tokenů, aby se rozhodl, jak dále pokračovat. U kalkulačky by se mohlo jednat o LL(1) gramatiku. Problém nastane v případě, kdy na začátku vstupu je proměnná. Následující token může být operátor + - * / ... nebo dosazení =. V těchto případech bude následovat jiné volání, proto se jedná o LL(2) gramatiku. 

Bez levé rekurze

LL(k) nesmí obsahovat levou rekurzi. Přesná definice je opět na Wiki - Levá rekurze. Lepší je ale vysvětlení na konkrétním případě, včetně ukázky kódu, který vlastně nepůjde úplně dokončit.

// S je vstup (počáteční neterminál), lze jej tedy přepsat dále pomocí daných pravidel.

S -> S + N | N // S lze přepsat rekurzivně na S + N, nebo přímo na N

N -> number // N lze přepsat na libovolné číslo

U neterminálu S vzniká levá rekurze. Stačí si zkusit napsat v parser pro tuto gramatiku. Pro představu vstup může vypadat takto 8 + 7 + 5 + 9. Pro zjednodušení se jedná o pseudo kód.

func (p Parser) parseNumber() {

    return p.expect(Number) // Očekává číslo, nebo vrátí chybu

}

func (p Parser) parseExpression() {

    if p.has(???) { // Tuto podmínku nelze dokončit

        left, err := parserExpression() // Zde dojde k zacyklení

        operator, err := p.parseOperator()

        right, err := parserNumber()

    } else {

        return p.parseNumber()

    }

}

Z kódu lze vidět, kde dojde k zacyklení. Důvodem je právě levá rekurze v gramatice. Ani podmínku nelze dokončit. Protože pokud je vstup správný, p.has(Number) by vždy vrátila true. A tedy není zřejmé, zda je potřeba dalšího zacyklení nebo stačí zpracovat číslo. Stačí však gramatiku přepsat tak, aby měla rekurzi vpravo. Přepis ale může měnit samotnou gramatiku. Více je opět popsáno na Wiki - Odstraňování levé rekurze. Pro tuto kalkulačku je však přepis více než jednoduchý.

Pokud někoho napadlo, že by se použilo něco jako p.has(Numer) && p.hasNext(Operator), při rekurzivním zavolání parseExpression() by však interní ukazatel stále ukazoval na začátek. Došlo by opět k zacyklení. Navíc u složitějších gramatik by to nešlo. A pokud bychom toto číslo a operátor parsovali a následně se zanořili, již by se jednalo o pravou rekurzi. A ta je níže.

// Rekurze je nyní vpravo u neterminálu S

S -> N + S | N // S lze přepsat rekurzivně na N + S, nebo přímo na N
N -> number // N lze přepsat na libovolné číslo

// Protože prvně je zpracováno číslo a poté je zkontrolován operátor, nedojde k zacyklení.

// V případě že operand nebo operátor nelze zpracovat, je vrácena chyba

func (p Parser) parseExpression() {

    left, err := p.parseNumber()
    if p.has(Addition) {
        operator, err := p.parseOperator()
        right, err := parserExpression()
    }
}

Parser s volitelnou prioritou i asociativitou

Recursive descent parser je typ parseru, který přímo vychází z dané gramatiky. Krásný příklad kódu i implementace je na Wiki - Analýza rekurzivním sestupem. Samotná implementace parseru by nebyla příliš složitá. Jenže popisovaná kalkulačka má možnost nastavovat různou prioritu a asociativitu operátorů. To komplikuje základní myšlenku algoritmu.

Řešením je použití jedné hlavní funkce. Ta je volána stejně rekurzivně jako v případě klasické implementace. V prvním kroku dojde k nejhlubšímu možnému zanoření. Poté je zkontrolováno, jestli aktuální operátor má danou prioritu. Následně je buď zpracován, nebo se postupuje zpětně k nižším prioritám. Níže je opět zjednodušený kód takové implementace, kompletní řešení včetně testů je na github.com/arxeiss/go-expression-calculator.

func (p *parserInstance) parseExpression(currentPrecedence parser.TokenPrecedence) (ast.Node, error) {
	var leftNode ast.Node
	var err error

	// Stejně jako v běžné implementace dojde k nejhlubšímu zanoření
	// viz příklad na https://cs.wikipedia.org/wiki/Analýza_rekurzivním_sestupem
	if currentPrecedence < p.maxPrecedence {
		leftNode, err = p.parseExpression(p.parser.priorities.NextPrecedence(currentPrecedence))
	}

	// Pokud není nic vráceno z hlubšího zanoření, lze očekávat (, číslo nebo identifikátor
	if leftNode == nil {
		switch {
		case p.has(lexer.LPar, lexer.Identifier, lexer.Number):
			leftNode, err = p.parseTerm()
		// Zde by se ještě řešily unární operátory

	// Iterovat přes následující tokeny, dokud jsou stejné priority
	for p.getPrecedence(p.current().Type()) == currentPrecedence {
		// Nyní musí přijít operátor
		operatorToken, err := p.expect(binaryOperators...)
		// Zde by se ještě řešily unární operátory

		// Pokud je operátor asociativní zprava, ponechat stejnou prioritu, protože pravá strana musí být níže
		// v AST. Další iterace se stejnou prioritou zaručí dřívější zpracování pravé strany
		nextPrecedence := currentPrecedence
		if p.getAssociativity(operatorToken.Type()) == parser.LeftAssociativity {
			nextPrecedence = p.parser.priorities.NextPrecedence(currentPrecedence)
		}
		rightNode, err := p.parseExpression(nextPrecedence)
		return ast.NewBinaryNode(tokenTypeToOperation(operatorToken.Type()), leftNode, rightNode, operatorToken), nil
	}
	return leftNode, err
}

---

Nápady, postřehy či zkušenosti můžete s ostatními čtenáři sdílet v komentářích