jakubův notes – programování a vejšplechty

Někdo znovuobjevuje kolo v podobě frameworků pro PHP. Já na to jdu jinak, já znovuobjevuji parser generátory.

Když jsem narazil na CoffeeScript, popadl mě (opět) nápad začít pracovat na vlastním programovacím jazyce. Takovéhle sklony mám již delší dobu, ale naštěstí se mi to vždycky podaří utlumit a začít pro změnu dělat něco užitečného. Už jsem přešel od svého ideálního dynamického imperativního přes funkcionální dynamicky typovaný až po imperativní staticky typovaný jazyk.

U CoffeeScriptu mě zaujalo hlavně to, že se zkompiluje do JavaScriptu. Takových projektů, jak na JavaScript naroubovat jiný jazyk, je tu více. Dokonce je tu i interpret YARV bytecodu. Jelikož mojí platformou volby je PHP. A PHP není zrovna jeden z jazyků, které by se mi líbily. Je to paradox – dva jazyky se mi opravdu moc nelíbí (PHP a C++) a oba jsou na první příčce seznamu, když chci něco napsat.

Inspirován CoffeeScriptem jsem se rozhodl, že jazyk (až a jestli vůbec někdy bude existovat) bude kompilován do PHP.

Jelikož psát parser (zvlášť u těch složitějších) ručně je zábava na dlouhé zimní večery, rozhodl jsem se, že je potřeba parser generátor. Nebyl bych to PHPčkař, kdybych využil třebas balíček z PEARu, nebo rovnou ANTLR PHP target, a tak jsem napsal pacc.

Je to čistě parser generátor (lexer si musíte dopsat sami) a je ve stádiu „proof of concept“ (bohužel jako většina toho, co napíšu). pacc přijímá na vstupu soubor formátu, který se jistě v budoucnu ještě mnohokrát změní.

Na příklady se podívejte do podadresáře examples/ v repozitáři. Já si tu jeden vezmu a rozeberu ho podrobněji. Bude to kalkulátor (calculator.y):

grammar Calculator

Na začátku souboru je název gramatiky. (Teď uvažuji nad tím, jestli zrovna grammar je to nejvhodnější slovo…) pacc vygeneruje tedy třídu s názvem Calculator. Za deklarací grammar může, ale nemusí být středník.

option (
    eol = "\n";
    indentation = "    ";
    parse = "doParse";
    algorithm = "LR";
)

Složená deklarace option. eol nastavuje, jaký bude znak konce řádku ve vygenerovaném souboru (ve výchozím stavu je to \n), indentation zase, čím se bude odsazovat (defaultně čtyři mezery). parse udává, jak se bude jmenovat metoda, která provede vlastní parsování (výchozí doParse). algorithm je asi nejzajímavější – nastavuje totiž, jaký výstupní typ algoritmu chcete. Zatím jsou implementovány dva – RD (recursive descent) a LR (LR parser, konkrétně canonical LR(1)). Recursive descent je nejjednodušší typ parseru a většinou se píše ručně (třebas parser použitý k naparsování souboru s gramatikou je právě ručně napsaný recursive descent). S LR je to složitější, protože tam jsou potřeba tabulky a ty je nejjednodušší právě vygenerovat.

Stejně jako s grammar deklarací, za option může a nemusí být středník (option ( ... );). Ve složeném optionu středník odděluje jednotlivá nastavení, takže za posledním být může, avšak nemusí.

Krom složeného option je tu i jednoduché. Následující kód je ekvivalentní předchozímu:

option eol = "\n"
option indentation = "    "
option parse = "doParse"
option algorithm = "LR"

Krom řetězce (přičemž řetězec je sled znaků ohraničený uvozovkami, apostrofem, nebo obráceným apostrofem) lze jako option též nastavit PHP kód. Ale pro toto je jednodušší využít syntaktického cukru:

@inner {
    const NUMBER = 1;

    private $expression;
    private $token;

    public function calculate($expression)
    {
        $this->expression = $expression;
        $this->_nextToken();
        return $this->doParse();
    }
}

@footer {
    $calculator = new Calculator;
    echo $calculator->calculate(file_get_contents('php://stdin')) . "\n";
}

PHP kód je vždy ohraničen složenými závorkami. Zavináč, nějaký název a PHP kód nastavuje danou možnost na PHP kód. Kód inner se vloží do těla vygenerované třídy, typicky obsahuje nastavení instančních a třídních proměnných a veřejných metod pro manipulaci s parserem; footer bude umístěn na konec souboru a jeho tu za účelem inicializace, která nelze provést ve třídě (v příkladě s kalkulátorem přečteme standardní vstup a necháme ho vyhodnotit). Ještě je tu header, kterýžto není sice v příkladu uveden, ale v případě, že by byl, tak se vloží nad třídu, může obsahovat např. doc-komentář.

@currentToken {
    return $this->token;
}

@currentTokenType {
    if (preg_match('~^[0-9]+$~', $this->token)) { return self::NUMBER; }
    return NULL;
}

@currentTokenLexeme {
    return $this->token;
}

@nextToken {
    if (!preg_match('~^([0-9]+|\(|\)|\+|-|\*|/)~', $this->expression, $m)) {
        $this->expression = NULL;
        $this->token = NULL;
        return;
    }

    $this->token = $m[1];
    $this->expression = substr($this->expression, strlen($m[1]));
}

Čtveřice kódů, které slouží pro komunikaci s lexerem. U kalkulátoru žádný speciální lexer není, a tak tyto kódy jsou vlastně lexerem. Každý z těchto kódů bude ve výsledku metodou ve třídě, akorát s podtržítkem na začátku (currentToken bude _currentToken, currentTokenType bude _currentTokenType atd.).

currentToken by měl vracet něco (je jedno co), co reprezentuje aktuální token. V tomto případě je to řetězec. currentTokenType typ aktuálního tokenu a currentTokenLexeme obsah, řetězcovou hodnotu aktuálního tokenu (jak to má konkrétně s těmito metodami být povím u vysvětlování pravidel). Po zavolání nextToken by všechny předchozí metody měly vracet další token / informace o dalším tokenu v streamu.

Nyní již k samotným pravidlům:

expression
    : /* nothing */ { $$ = 0; }
    | component { $$ = $1; }
    | expression '+' component { $$ = $1 + $3; }
    | expression '-' component { $$ = $1 - $3; }
    ;

component
    : factor { $$ = $1; }
    | component '*' factor { $$ = $1 * $3; }
    | component '/' factor { $$ = $1 / $3; }
    ;

factor
    : NUMBER { $$ = intval($1); }
    | '(' expression ')' { $$ = $2; }
    ;

Bezkontextové gramatiky se popisují řadou produkcí s jedním neterminálem na levé straně a žádným, či více neterminály a/nebo terminály na straně pravé. Produkce navíc může mít na levé i pravé straně stejný neterminál, což znamená, že je produkce rekurzivní. Jedno pravidlo se skládá z levé strany produkcí (tedy neterminálu), poté dvojtečky, jedné nebo více pravých stran produkcí oddělených svislítkem (|) a je ukončené středníkem. U každé pravé stranu produkce může být navíc přidružen speciální PHP kód.

pacc používá Bison(-like) notaci pro zápis pravidel, což je právě ta popsaná výše. Neterminály jsou všechny řetězce vyhovující regulárnímu výrazu [a-z][a-z0-9_], terminály jsou ohraničené řetězce jako v případě nastavování optionů, nebo sekvence znaků vyhovující [A-Z][A-Z0-9_]. Pokud je u neterminálu použit ohraničený řetězec, porovnává se s hodnotou vrácenou z metody currentTokenLexeme, jestliže se jedná o druhý případ, porovnává se s hodnotou vrácenou z currentTokenType. Pokud currentToken, currentTokenLexeme i currentTokenType vrací NULL, znamená to konec streamu.

K samotným pravidlům. Začněme od factor. factor je (dvojtečku můžeme číst jako „je“) buď terminál NUMBER (porovnává se s currentTokenType), nebo (svislítko můžeme číst jako „nebo“) výraz ohraničený kulatými závorkami.

Co je toto?

$$ = intval($1);

currentToken kalkulátoru vrací vrací číslo vypreparované z řetězce určeného k vyhodnocení. Funkce intval() převede řetězec na číslo. Proměnná s názvem 1 je speciální proměnná, ve které je uložen první symbol z pravé strany produkce; analogicky 2 je druhý, 3 je třetí atd. Dolarová proměnná je výsledek produkce – tedy neterminál na levé straně. A tak výraz výše znamená, že výsledkem produkce je číselná hodnota prvního symbolu. První symbol je terminál NUMBER, který je reprezentován číselným tokenem, takže výsledkem produkce je číselná hodnota tohoto tokenu. V případě druhé větve pravidla factor, je výsledkem hodnota druhého symbolu, tedy expression.

Stejně je to s dalšími pravidly. PHP kód u pravé strany produkce nemusí být přítomen. V tomto případě je výsledkem produkce hodnota prvního symbolu.

Kalkulátor si můžete vyzkoušet. Stáhnětě si zdrojové kódy z repozitáře, přejděte do adresáře s nimi a spusťte:

$ ./bin/pacc -i ./examples/calculator.y -fo ./calculator.php
$ echo "22*2-2" | php -f ./calculator.php
42

Praktičtější z příkladů je parser JSONu, který se může hodit v případě, že na serveru není nainstalován PHP json modul.

V budoucích verzích bych chtěl vychytat co nejvíce mušek (nepředpokládám, že by jich tam bylo zrovna málo) a nakonec ručně psaný parser pro tento formát souboru úplně nahradit parserem generovaným paccem. Taky se mi zrovna nelíbí metody currentToken apod., takže tohle může doznat dramatických změn. Psát lexery mě už taky nebaví, takže podpora jeho generování může do paccu přibýt. Dalším omezením je, že první pravidlo v souboru se nesmí jmenovat grammar, nebo option – parser by pak nepoznal, že se jedná o pravidlo a myslel si, že je to nějaká direktiva, což by skončilo parser errorem. Alternativou k tomuto omezení by bylo buď všechny deklarace něčím prefixovat, nebo pravidla do něčeho obalit. Jedno horší jak druhé, takže tu tohle omezení zůstane. Vývoj bude pravděpodobně nadále probíhat na LR parseru a RD algoritmus bude nakonec odstraněn.