Schrijven over Pratt-parsing zodat ik het me herinner

Je vindt niet veel informatie over Pratt-parsing in een conventioneel computerwetenschappelijk leerpad. Het Dragon Book, ondanks alles wat het over parsing zegt, noemt het niet. Voor zover ik weet, zullen de meeste cursussen programmeertalen waarschijnlijk LR of recursive descent aanleren, afhankelijk van hoe academisch de cursus is (bij mij was dat recursive descent). Pratt-parsing lijkt specifiek gereserveerd voor kringen rondom compiler-ontwikkeling en PLT (Programming Language Theory). De meest mainstream vermelding die ik ken, is in Crafting Interpreters; Wikipedia linkt ook naar een paar andere berichten.

Ik heb de tekst van Crafting Interpreters gebruikt om me te oriënteren, maar ik wilde ook meer oefenen met het lezen van formele papers, dus heb ik zoveel mogelijk geprobeerd de oorspronkelijke paper van Pratt te gebruiken. Het kostte me iets meer tijd dan ik had gewild om te begrijpen hoe de recursie past binnen de operator-precedentie, maar op een gegeven moment klikte het ineens, namelijk toen ik de link legde met het shunting-yard-algoritme. Daarom schrijf ik mijn observaties nu op, zodat ik ze niet vergeet. Misschien is het ook nuttig voor jou.

Shunting Yard

Het shunting-yard-algoritme is, in vergelijking, veel eenvoudiger dan Pratt. Je hebt een output-stream en een operator-stack. Operatoren zijn gedefinieerd met hun binding powers (bindingskracht), waarbij een hogere bindingskracht betekent dat de operator sterker bindt aan zijn argumenten (bijv. * heeft in de rekenkunde een hogere bindingskracht dan +).

In de eenvoudigste beschrijving van shunting yard gebeurt voor elk token in de input-stream het volgende:

• Als het een "standalone" token is (bijv. een identifier of getal), push het dan direct naar de output.
• Als het een operator-token is:
• Als het een hogere bindingskracht heeft dan de bovenste operator op de stack, push het dan op de stack.
• Als het een gelijke of lagere bindingskracht heeft dan de bovenste operator op de stack, pop dan alle operator-tokens met een hogere of gelijke bindingskracht naar de output-stream, voordat je het huidige operator-token op de operator-stack pusht.

Het poppen van alle operatoren met een "hogere of gelijke bindingskracht" gaat ervan uit dat alle operatoren links-associatief zijn. Aan het einde van de token-stream worden alle resterende operatoren naar de output gepopt.

Een zeer primitieve implementatie van shunting yard in C, waarbij expressies worden omgezet naar postfix-notatie, zou er zo uit kunnen zien:

#include <stdio.h>
#include <ctype.h>

typedef struct {
    char ops[32]; // limiet van 32 operatoren
    int idx;      // index van de laatste operator
} Stk;

void push(Stk *s, char op) {
    s->idx += 1;
    s->ops[s->idx] = op;
}

void pop(Stk *s)   { s->idx -= 1; }
char peek(Stk *s)  { return s->ops[s->idx]; }
char empty(Stk *s) { return s->idx == -1; }

int get_bindpower(char op) {
    static const int bps[] = { ['+'] = 1, ['-'] = 1, ['*'] = 2, ['/'] = 2 };
    return bps[op];
}

int main(int argc, char **argv) {
    char *str = argv[1];
    Stk _opstk = (Stk){ .idx = -1 };
    Stk *opstk = &_opstk;

    while (*str != '\0') {
        if (isdigit(*str)) {
            // getal
            printf("EMIT '%c'\n", *str);
        } else {
            // operator (ervan uitgaande dat deze geldig is)
            // get_bindpower(peek(opstk)) is de linker bindingskracht
            // get_bindpower(*str) is de rechter bindingskracht
            while (!empty(opstk) && get_bindpower(peek(opstk)) >= get_bindpower(*str)) {
                printf("EMIT '%c'\n", peek(opstk));
                pop(opstk);
            }
            push(opstk, *str);
        }
        str += 1;
    }

    while (!empty(opstk)) {
        printf("EMIT '%c'\n", peek(opstk));
        pop(opstk);
    }

    return 0;
}

Uitvoer voorbeeld: $ ./a.out '1+52+6' EMIT '1' EMIT '5' EMIT '2' EMIT '' EMIT '+' EMIT '6' EMIT '+'

Het probleem met shunting yard is dat het niet erg uitbreidbaar is voor nieuw gedrag. Het algoritme heeft bijvoorbeeld geen concept van "subexpressies" in recursieve zin; het toevoegen van haakjes betekent dat er speciale functionaliteit moet worden gekoppeld aan het ) token om de stack te poppen tot de bijbehorende ( is bereikt. Dat is op zich niet moeilijk, maar complexer gedrag zoals unaire operatoren, rechts-associatieve expressies, functies met variabele argumenten, enz. wordt snel onoverzichtelijk. Hier komt de transformatie naar Pratt-parsing om de hoek kijken.

Van Shunting naar Pratt

De belangrijkste transformatie die het shunting-yard-algoritme verandert in een Pratt-parser is: in plaats van een expliciete stack voor operatoren te gebruiken, wordt de call stack (aanroepstack) gebruikt om subexpressies te betreden zodra operatoren die nodig hebben.

Hiermee geef je de "linker bindingskracht" van infix/postfix-operatoren door aan die recursieve aanroepen. Je keert terug wanneer je een bindingskracht tegenkomt van een infix/postfix-operator die lager is dan de linker bindingskracht. Het "ontwinden" (unwinding) van de stack bij het tegenkomen van een lagere bindingskracht in shunting yard is dus hetzelfde als het terugkeren uit de recursieve aanroep in een Pratt-parser.

Een mooi aspect hiervan is dat je, in tegenstelling tot recursive descent, niet voor elke expressie calls nest door elk niveau van precedentie, maar alleen nest wanneer je subexpressies betreedt. Dit is tegelijkertijd efficiënter en overzichtelijker.

Helaas is er geen eenvoudige "tussenstap" voor dit proces. Je moet het eigenlijk gewoon proberen en naar de output kijken. Hier is de eenvoudigste Pratt-stijl parser die ik in C kan laten zien, equivalent aan de eerdere shunting yard parser:

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>

int get_bindpower(char op) {
    // het eind-token ('\0') is nu gedefinieerd in de bind power array
    static const int bps[] = {
        ['\0'] = 0,
        ['+'] = 1, ['-'] = 1, ['*'] = 2, ['/'] = 2
    };
    return bps[op];
}

typedef struct {
    char *str;
} Parser;

char cur(Parser *p) { return *p->str; }
void bump(Parser *p) { p->str += 1; }

void expr(Parser *parser, int left_bindpower) {
    // alle expressies *moeten* beginnen met een "prefix" token
    // dit is wat Pratt "nuds" noemt in zijn oorspronkelijke paper.
    // in dit geval zijn onze enige prefix-tokens cijfers
    if (isdigit(cur(parser))) {
        printf("EMIT '%c'\n", cur(parser));
    } else {
        fprintf(stderr, "expressie begint niet met een getal\n");
        abort();
    }
    bump(parser);

    // op dit punt zijn we bij een infix/postfix operator.
    // dit is wat Pratt "leds" noemt in zijn oorspronkelijke paper.
    // wanneer deze check onwaar is, is het vergelijkbaar met het "ontwinden" van de stack in shunting yard.
    while (left_bindpower < get_bindpower(cur(parser))) {
        // ervan uitgaande dat dit een geldige operator is (zoals in de shunting yard code)
        // er is een expressie aan de rechterkant van binaire operatoren. parse deze eerst.
        // dit is vergelijkbaar met het pushen naar de operator-stack in shunting yard.
        int new_left_bindpower = get_bindpower(cur(parser));
        char op = cur(parser);
        bump(parser);
        expr(parser, new_left_bindpower);
        printf("EMIT '%c'\n", op);
    }
}

int main(int argc, char **argv) {
    Parser parser = (Parser){ .str = argv[1] };
    expr(&parser, 0);
    return 0;
}

Uitvoer voorbeeld: $ ./a.out '1+52+6' EMIT '1' EMIT '5' EMIT '2' EMIT '' EMIT '+' EMIT '6' EMIT '+'

Op zichzelf ziet dit er misschien niet zo spannend uit; ik heb de stack impliciet gemaakt. Maar er zijn twee interessante dingen aan deze aanpak:

1. "Prefix"-operatoren hebben nu een eersteklas behandeling in het eerste deel van expr(). Deze worden "nuds" genoemd in de originele paper van Pratt. Het tweede deel van expr() is bedoeld voor het afhandelen van wat ik "infix/postfix"-operatoren noem, of "leds" in de paper van Pratt.
2. We hebben de mogelijkheid om willekeurige code toe te wijzen aan elke individuele operator zodra de operator wordt gezien, net als bij recursive descent.

Deze combinatie maakt eenvoudige en directe uitbreidbaarheid mogelijk. Dit is alles wat nodig is om haakjes toe te voegen:

int get_bindpower(char op) {
    // voeg '(' toe aan bps
    static const int bps[] = {
        ['\0'] = 0,
        ['('] = 0,
        ['+'] = 1, ['-'] = 1, ['*'] = 2, ['/'] = 2
    };
    return bps[op];
}

// ...
// forward-declare expr() en voeg de paren() subroutine toe.
// dit hoeft niet eens een subroutine te zijn; je kunt dit inlinen in de expr() functie.
// maar dit is overzichtelijker :)
void expr(Parser *parser, int left_bindpower);

void paren(Parser *parser) {
    expr(parser, get_bindpower('('));
    if (cur(parser) != ')') {
        puts("geen matching ')'");
        abort();
    }
}

// ...
// voeg de if '(' conditie hier toe; de rest is hetzelfde
void expr(Parser *parser, int left_bindpower) {
    if (cur(parser) == '(') {
        bump(parser);
        paren(parser);
    } else if (isdigit(cur(parser))) {
        printf("EMIT '%c'\n", cur(parser));
    } else {
        puts("expressie begint niet met een geldig prefix token");
        abort();
    }
    // ... rest van de functie
}

Uitvoer voorbeeld: $ ./a.out '1+5(2+6)' EMIT '1' EMIT '5' EMIT '2' EMIT '6' EMIT '+' EMIT '' EMIT '+'

Wil je nog meer operatoren toevoegen? Combineer de get_bindpower() functie dan met het kiezen van de subroutine die moet worden uitgevoerd, waarbij je "regels" opslaat als een struct met de bindingskracht, de prefix-subroutine en de postfix-subroutine. De kern blijft simpel, terwijl alle operatoren in hun eigen kleine functies draaien. Ik ga hier geen extra blok code plakken, maar deze opzet wordt beschreven in het hoofdstuk over Pratt-parsing in Crafting Interpreters. Het is erg elegant.

Update: Ik heb ook een gestructureerd voorbeeld gemaakt in mijn snippets-repo. Dit is voor grotendeels dezelfde expressie-grammatica met een paar uitbreidingen (unaire +, -, en een postfix !), om te laten zien hoe het kan worden uitgebreid naar een meer realistische en onderhoudbare vorm voor een codebase.

Ik hoop dat dit anderen helpt. Veel plezier met parsen!