Píšeme vlastní parser. V JavaScriptu. (pokračování)

Popíšeme si abstraktní syntaktický strom našeho λazyka a dokončíme tvorbu parseru.

Seriál: Implementujeme vlastní programovací jazyk. V JavaScriptu. (6 dílů)

  1. Začínáme implementovat vlastní jazyk. V JavaScriptu. 2.2.2017
  2. Píšeme vlastní parser. V JavaScriptu. 13.2.2017
  3. Píšeme vlastní parser. V JavaScriptu. (pokračování) 20.2.2017
  4. Píšeme vlastní interpret. V JavaScriptu. 27.2.2017
  5. Píšeme vlastní interpret. V JavaScriptu. (pokračování) 8.3.2017
  6. Rozšiřujeme náš interpret. V JavaScriptu. 18.4.2017

Popis AST

Jak jsme si už říkali, parser vytváří strukturu, která věrně odráží sémantiku programu. AST je v našem případě prostý JavaScriptový objekt, který má vlastnost “type”, jež určuje, o jaký typ uzlu se jedná, a další informace podle typu uzlu.

Ve stručnosti:

  • num { type: "num", value: NUMBER }
  • str { type: "str", value: STRING }
  • bool { type: "bool", value: true or false }
  • var { type: "var", value: NAME }
  • lambda { type: "lambda", vars: [ NAME... ], body: AST }
  • call { type: "call", func: AST, args: [ AST... ] }
  • if { type: "if", cond: AST, then: AST, else: AST }
  • assign { type: "assign", operator: "=", left: AST, right: AST }
  • binary { type: "binary", operator: OPERATOR, left: AST, right: AST }
  • prog { type: "prog", prog: [ AST... ] }
  • let { type: "let", vars: [ VARS... ], body: AST }

Příklady:

123.5
{ type: "num", value: 123.5 }
"Hello World!"
{ type: "str", value: "Hello World!" }
true
false
{ type: "bool", value: true }

{ type: "bool", value: false }
Identifikátory
foo
{ type: "var", value: "foo" }
Funkce

lambda (x) 10   # nebo
λ (x) 10

Později doplníme volitelnou vlastnost “name”, která umožní vytvářet pojmenované funkce, ale první verze parseru je mít nebude.

{
 type: "lambda",
 vars: [ "x" ],
 body: { type: "num", value: 10 }
}
Volání funkce
foo(a, 1)
{
 "type": "call",
 "func": { 
   "type": "var", 
   "value": "foo" 
 },
 "args": [
  { "type": "var", "value": "a" },
  { "type": "num", "value": 1 }
 ]
}
Podmíněné výrazy
if foo then bar else baz
{
  "type": "if",
  "cond": { "type": "var", "value": "foo" },
  "then": { "type": "var", "value": "bar" },
  "else": { "type": "var", "value": "baz" }
}
Větev else je nepovinná.
if foo then bar
{
  "type": "if",
  "cond": { "type": "var", "value": "foo" },
  "then": { "type": "var", "value": "bar" }
}
Přiřazení
a = 10
{
  "type": "assign",
  "operator": "=",
  "left": { "type": "var", "value": "a" },
  "right": { "type": "num", "value": 10 }
}
Binární výrazy
x + y * z
{
  "type": "binary",
  "operator": "+",
  "left": { "type": "var", "value": "x" },
  "right": {
    "type": "binary",
    "operator": "*",
    "left": { "type": "var", "value": "y" },
    "right": { "type": "var", "value": "z" }
  }
}
Bloky

{
  a = 5;
  b = a * 2;
  a + b;
}
{
  "type": "prog",
  "prog": [
    {
      "type": "assign",
      "operator": "=",
      "left": { "type": "var", "value": "a" },
      "right": { "type": "num", "value": 5 }
    },
    {
      "type": "assign",
      "operator": "=",
      "left": { "type": "var", "value": "b" },
      "right": {
        "type": "binary",
        "operator": "*",
        "left": { "type": "var", "value": "a" },
        "right": { "type": "num", "value": 2 }
      }
    },
    {
      "type": "binary",
      "operator": "+",
      "left": { "type": "var", "value": "a" },
      "right": { "type": "var", "value": "b" }
    }
  ]
}
 

let (a = 10, b = a * 10) {
  a + b;
}

První verze parseru nebude tuto funkcionalitu obsahovat, přidáme ji později.

{
  "type": "let",
  "vars": [
    {
    "name": "a",
    "def": { "type": "num", "value": 10 }
    },
    {
      "name": "b",
      "def": {
        "type": "binary",
        "operator": "*",
        "left": { "type": "var", "value": "a" },
        "right": { "type": "num", "value": 10 }
      }
    }
  ],
  "body": {
    "type": "binary",
    "operator": "+",
    "left": { "type": "var", "value": "a" },
    "right": { "type": "var", "value": "b" }
  }
}

Parser

Parser vytváří uzly AST, jak jsme si popsali výše.

Díky práci, kterou jsme odvedli na tokenizéru, pracuje parser nad proudem tokenů, takže se nemusí zabývat jednotlivými znaky. Stále používá spoustu pomocných funkcí, aby byl co nejjednodušší. Zde si probereme hlavní funkce, které se podílejí na parsování. Začneme jednou z vyšších úrovní, lambda parserem:

function parse_lambda() {
 return {
   type: "lambda",
   vars: delimited("(", ")", ",", parse_varname),
   body: parse_expression()
 };
}

Tato funkce je vyvolána pokaždé, když se na vstupu objeví klíčové slovo “lambda”, a to v okamžiku, kdy je toto slovo už ze vstupního proudu “zkonzumované”, takže jediné, o co se stará, je parsování jmen argumentů. Ty jsou v závorkách a oddělené čárkami. Namísto umístění kódu do funkce parse_lambda() preferuju použití funkce delimited(), která má následující argumenty: startovací token, zakončovací token, oddělovač a funkci, která parsuje samotné prvky seznamu. V tomto případě je to parse_varname, která vyhodí chybu pokaždé, když se objeví něco, co nevypadá jako jméno proměnné. Tělo funkce (vlastnost body) je výraz, takže použijeme parse_expression().

Funkce delimited() je o trochu syrovější:

function delimited(start, stop, separator, parser) {
    var a = [], first = true;
    skip_punc(start);
    while (!input.eof()) {
        if (is_punc(stop)) break;
        if (first) first = false; else skip_punc(separator);
        if (is_punc(stop)) break; // poslední oddělovač smí chybět
        a.push(parser());
    }
    skip_punc(stop);
    return a;
}

Jak vidíte, používá další pomocné funkce: is_punc() a skip_punc(). První vrací true, pokud aktuální token odpovídá danému oddělovači (bez jeho “konzumace”), zatímco skip_punc() se ujistí, že aktuální token je daný oddělovač (pokud ne, vyhodí chybu) a odstraní jej ze vstupního proudu.

Funkce, která parsuje celý program, je asi ta nejjednodušší:

function parse_toplevel() {
    var prog = [];
    while (!input.eof()) {
        prog.push(parse_expression());
        if (!input.eof()) skip_punc(";");
    }
    return { type: "prog", prog: prog };
}

Protože nemáme v λazyce žádné příkazy, můžeme jen zavolat parse_expression() a číst výrazy, dokud nedojdeme na konec vstupních dat. Pomocí skip_punc(";") si zajistíme, že mezi těmito výrazy budou středníky.

Další jednoduchý příklad: parse_if():

function parse_if() {
    skip_kw("if");
    var cond = parse_expression();
    if (!is_punc("{")) skip_kw("then");
    var then = parse_expression();
    var ret = { type: "if", cond: cond, then: then };
    if (is_kw("else")) {
        input.next();
        ret.else = parse_expression();
    }
    return ret;
}

Funkce přeskočí klíčové slovo if pomocí skip_kw (vyhodí chybu, pokud je klíčové slovo jiné) a přečte podmínku pomocí parse_expression(). Pokud následující větev nezačíná složenou závorkou {, očekáváme klíčové slovo then (připadalo mi, že bez toho by byla syntax příliš divoká). Jednotlivé větve jsou prostě výrazy, tak opět použijeme parse_expression(). Větev else je nepovinná, proto zkontrolujeme, jestli se vyskytuje příslušné klíčové slovo dřív, než ji začneme parsovat.

Díky tomu, že máme spoustu malých utilit, můžeme udržet kód opravdu jednoduchý. Už jsme skoro napsali stejný parser, jaký bychom získali pomocí jazyků, určených pro parsování. Všechny tyto funkce jsou “vzájemně rekurzivní”, například funkce parse_atom(), která je hlavní funkcí celého parseru a podle aktuálního tokenu volá další funkce. Jedna z nich může být parse_if() (pokud je token if), a ta zase volá parse_expression(). Funkce parse_expression() zase volá parse_atom(). Důvod, proč to celé neskončí v nekonečné smyčce je ten, že tyto funkce postupně “ujídají” tokeny z (konečného) vstupního proudu.

Tento druh se nazývá “analýza rekurzivním sestupem” (recursive descent parser) a je to pravděpodobně ten nejsnazší způsob pro ručně psaný parser.

Nižší úroveň: parse_atom() a parse_expression()

Hlavní práci vykonává funkce parse_atom(), v závislosti na aktuálním tokenu:

function parse_atom() {
    return maybe_call(function(){
        if (is_punc("(")) {
            input.next();
            var exp = parse_expression();
            skip_punc(")");
            return exp;
        }
        if (is_punc("{")) return parse_prog();
        if (is_kw("if")) return parse_if();
        if (is_kw("true") || is_kw("false")) return parse_bool();
        if (is_kw("lambda") || is_kw("λ")) {
            input.next();
            return parse_lambda();
        }
        var tok = input.next();
        if (tok.type == "var" || tok.type == "num" || tok.type == "str")
            return tok;
        unexpected();
    });
}

Pokud vidí otevírací závorku, pak to musí být uzávorkovaný výraz. V takovém případě přeskočí závorku, zavolá parse_expression() a očekává uzavírací závorku. Pokud najde klíčové slovo, zavolá odpovídající parsovací funkci. Pokud narazí na konstantu nebo identifikátor, vrátí ho tak jak je. A pokud všechno toto selže, pomocí unexpected() vyhodí chybu.

Pokud na místě, kde má být atomický výraz, najde složenou závorku, zavolá funkci parse_prog(), která parsuje sekvenci výrazů. Tato funkce je vypsaná níže. Dělá některé drobné optimalizace – pokud je tělo prázdné, vrátí FALSE. Pokud obsahuje jediný výraz, vrátí tento výraz namísto nodu “prog”. V ostatních případech vrací uzel “prog”, který obsahuje všechny výrazy.

// budeme používat nod FALSE v nejrůznějších situacích,
// tak si ho nadefinujeme globálně.
var FALSE = { type: "bool", value: false };

function parse_prog() {
    var prog = delimited("{", "}", ";", parse_expression);
    if (prog.length == 0) return FALSE;
    if (prog.length == 1) return prog[0];
    return { type: "prog", prog: prog };
}

A zde je funkce parse_expression(). Na rozdíl od parse_atom() se tato funkce pokouší stvořit co nejdelší výraz pomocí maybe_binary(), které si vysvětlíme později.

function parse_expression() {
    return maybe_call(function(){
        return maybe_binary(parse_atom(), 0);
    });
}

Funkce maybe_*

Tyto funkce zjišťují, co následuje po aktuálním výrazu, a pomáhají rozhodnout, zda vrátit výraz tak, jak je, nebo vytvořit nový uzel v AST.

maybe_call() je velmi jednoduchá. Jako argument dostává funkci, která by měla parsovat aktuální výraz. Pokud je za tímto výrazem závorka, pak se jedná o volání funkce (uzel “call”), které je rozparsované funkcí parse_call(). Všimněte si, jak se hodí funkce delimited() pro čtení seznamu argumentů.

function maybe_call(expr) {
    expr = expr();
    return is_punc("(") ? parse_call(expr) : expr;
}

function parse_call(func) {
    return {
        type: "call",
        func: func,
        args: delimited("(", ")", ",", parse_expression)
    };
}

Priorita operátorů

Funkce maybe_binary(left, my_prec) slouží ke skládání binárních výrazů typu 1+2*3. Trik k jejich správnému parsování je správná definice priorit operátorů, takže začněme tím:

var PRECEDENCE = {
    "=": 1,
    "||": 2,
    "&&": 3,
    "<": 7, ">": 7, "<=": 7, ">=": 7, "==": 7, "!=": 7,
    "+": 10, "-": 10,
    "*": 20, "/": 20, "%": 20,
};

Zde se říká, že operátor * se váže těsněji než operátor +, tedy výraz 1 + 2 * 3 musí být parsován jako (1 + (2 * 3)), namísto nesprávného ((1 + 2) * 3), což by byl výsledek prostého vyhodnocení zleva doprava.

Trik je v tom, že načteme atomární výraz (pouze jedničku) a předáme ho funkci maybe_binary() (první argument) spolu s aktuální úrovní priority (my_prec). maybe_binary() se podívá, co následuje. Pokud nevidí žádný operátor, nebo pokud má operátor nižší prioritu, pak je první argument vrácen tak, jak je. Pokud následuje operátor s vyšší prioritou, než je my_prec, pak zabalí první argument (left) do nového uzlu typu “binary”, a pro pravou stranu opakuje stejný postup s novou úrovní priority (*):

function maybe_binary(left, my_prec) {
    var tok = is_op();
    if (tok) {
        var his_prec = PRECEDENCE[tok.value];
        if (his_prec > my_prec) {
            input.next();
            var right = maybe_binary(parse_atom(), his_prec) // (*);
            var binary = {
                type     : tok.value == "=" ? "assign" : "binary",
                operator : tok.value,
                left     : left,
                right    : right
            };
            return maybe_binary(binary, my_prec);
        }
    }
    return left;
}

Předtím, než vrátíme binární výraz, musíme znovu zavolat maybe_binary s původní úrovní priority, abychom správně ošetřili situaci, kdy následuje operátor s vyšší prioritou. Pokud jste právě teď zmateni, zkuste si číst kód znovu dokola (třeba si zkuste v duchu vyhodnotit některé výrazy), dokud to celé do sebe nezapadne.

Protože my_prec je na počátku nula, spustí jakýkoli operátor vytváření uzlu “binary” (popřípadě “assign”, pokud je operátor =).

V parseru je ještě několik dalších funkcí, proto jsem celou funkci parse vložil do Gistu (v originále je to soubor ke stažení, já zvolil Gist, pozn. překl.)

Poznámka autora: Ta chvíle, kdy jsem pochopil, jak napsat netriviální parser, nastala při studiu knihovny parse-js (Common Lisp) od Marijna Haverbeke. Výše uvedený kód, i když je určen pro mnohem jednodušší jazyk, je vytvořen podle jeho kódu.

Pokračování příště

V dalším díle začneme psát interpret našeho λazyka.

Přeloženo z originálního tutoriálu, jehož autorem je Mihai Bazon. Překlad vychází s laskavým autorovým svolením.

Začal programovat v roce 1984 s programovatelnou kalkulačkou. Pokračoval k BASICu, assembleru Z80, Forthu, Pascalu, Céčku, dalším assemblerům, před časem v PHP a teď by rád neprogramoval a radši se věnoval starým počítačům.

Věděli jste, že nám můžete zasílat zprávičky? (Jen pro přihlášené.)

Zdroj: https://www.zdrojak.cz/?p=19538