Píšeme vlastní parser. V JavaScriptu.

V minulém díle jsme představili návrh našeho λazyka. Nyní pro něj začneme vytvářet parser. V JavaScriptu.

Seriál: Implementujeme vlastní programovací jazyk. V JavaScriptu. (5 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

Psaní parseru

Psaní parseru je, v závislosti na jazyce, poměrně komplexní úkol. V podstatě musí přetransformovat kus kódu (na který nahlížíme jako na pole znaků) do “abstraktního syntaktického stromu” (AST). AST je struktura, která reprezentuje daný program, a je “abstraktní” v tom smyslu, že není podstatné, jaké znaky ve zdrojovém kódu jej stvořily, ale že věrně odráží jeho sémantickou složku. Popis AST naleznete v dalším díle.

Kupříkladu pro následující kód:

sum = lambda(a, b) {
  a + b;
};
print(sum(1, 2));

náš parser vytvoří takovýto AST ve formě JavaScriptového objektu:

{
  type: "prog",
  prog: [
    // first line:
    {
      type: "assign",
      operator: "=",
      left: { type: "var", value: "sum" },
      right: {
        type: "lambda",
        vars: [ "a", "b" ],
        body: {
          // body by měl být "prog", ale protože jde o 
          // jeden jediný výraz, tak jej parser
          // redukuje právě na tento jediný výraz.
          type: "binary",
          operator: "+",
          left: { type: "var", value: "a" },
          right: { type: "var", value: "b" }
        }
      }
    },
    // second line:
    {
      type: "call",
      func: { type: "var", value: "print" },
      args: [{
        type: "call",
        func: { type: "var", value: "sum" },
        args: [ { type: "num", value: 1 },
                { type: "num", value: 2 } ]
      }]
    }
  ]
}


Hlavní obtíž při psaní parseru spočívá v riziku, že neudržíte svůj kód organizovaný. Parser by měl pracovat na vyšší úrovni, než je čtení znaků z řetězce. Zde je pár tipů, jak udržet složitost kódu na přijatelné úrovni.

  • Pište hodně funkcí a udržujte je malé. V každé funkci dělejte jen jednu věc, a dělejte ji dobře.
  • Nepokoušejte se použít regulární výrazy pro parsování. Nefungují. Regulární výrazy mohou být užitečné v lexerech, ale doporučuju, abyste je používali pouze pro jednoduché úlohy.
  • Nepokoušejte se hádat a domýšlet za programátora. Když si nejste jisti, jak něco zparsovat, vyhoďte výjimku a ujistěte se, že obsahuje informace o tom, kde k chybě došlo (řádek / sloupec)

Pro jednoduchost jsem kód rozdělil na tři části, a každá se dál dělí na menší funkce:

  1. Vstupní proud znaků
  2. Tokenizér (lexer)
  3. Parser

Vstupní proud znaků

Toto je nejmenší část. Vytvoříme “stream object”, který nabídne operace pro čtení znaků ze vstupního řetězce. Náš objekt bude mít čtyři metody:

  • peek() – vrátí další znak, ale ponechá ho ve vstupním řetězci
  • next() – vrátí další znak a odstraní ho ze vstupního řetězce
  • eof() – vrátí true, pokud je vstupní řetězec prázdný
  • croak(msg) – vyhodí výjimku pomocí throw new Error(msg)

Důvod, proč jsem zařadil poslední funkci, je ten, že stream snadno udržuje informace o pozici ve vstupním proudu (řádek / sloupec), což je důležité pro chybová hlášení.

Klidně si přidejte další metody dle svých potřeb, ale pro můj tutoriál stačí tyto čtyři.

Vstupní řetězec obsahuje znaky, proto jsou návratovými hodnotami funkcí peek() a next() právě znaky (dobře, protože JavaScript nemá typ “char”, jsou to řetězce s délkou jeden znak).

Zde je kompletní kód našeho objektu, který jsem nazval InputStream. Je malý a neměli byste mít žádný problém s jeho pochopením:

function InputStream(input) {
   var pos = 0, line = 1, col = 0;
   return {
       next  : next,
       peek  : peek,
       eof   : eof,
       croak : croak,
   };
   function next() {
       var ch = input.charAt(pos++);
       if (ch == "\n") line++, col = 0; else col++;
       return ch;
   }
   function peek() {
       return input.charAt(pos);
   }
   function eof() {
       return peek() == "";
   }
   function croak(msg) {
       throw new Error(msg + " (" + line + ":" + col + ")");
   }
}

Všimněte si, že nejde o standardní objekt, který byste si tvořili pomocí new. Prostě napíšete var stream = InputStream(string) a získáte zmíněný objekt.

Teď je načase nad tímto objektem napsat další vrstvu abstrakce: tokenizér.

Tokenizér (lexer)

Tokenizér pracuje nad vstupním proudem znaků a vrací objekt se stejným rozhraním, ale s tím rozdílem, že hodnotami metod next() / peek() jsou tokeny. Token je objekt s dvěma vlastnostmi: typem a hodnotou (type a value). Pár příkladů podporovaných tokenů:

{ type: "punc", value: "(" }           // oddělovače: závorka, čárka, středník atd.
{ type: "num", value: 5 }              // čísla
{ type: "str", value: "Hello World!" } // řetězce
{ type: "kw", value: "lambda" }        // klíčová slova
{ type: "var", value: "a" }            // identifikátory
{ type: "op", value: "!=" }            // operátory

Bílé znaky (mezera, tabelátor, konec řádku) a komentáře jsou přeskočeny a nevrací žádný token.

Před psaním tokenizéru se musíme podívat zblízka na syntax našeho jazyka. Základní myšlenka je, že na základě aktuálního znaku (vráceného přes input.peek()) dokážeme určit, jaký druh tokenu čteme:

  • Nejprve ignorujeme případné bílé znaky
  • Pokud input.eof(), vrátíme null
  • Pokud je to znak mřížka (#), přeskočíme komentář (a zkusíme znovu po konci řádku)
  • Pokud to jsou uvozovky, pak čteme řetězec
  • Pokud je to číslice, budeme číst číslo.
  • Pokud je to písmeno, pak jde buď o identifikátor, nebo klíčové slovo
  • Pokud je to oddělovač, vrátíme token pro oddělovač
  • Pokud je to některý znak pro operátor, vrátíme operátor
  • Pokud to není nic z výše uvedeného, vyhodíme výjimku pomocí input.croak().

Zde je funkce read_next, srdce celého tokenizéru, která implementuje výše uvedené:

function read_next() {
    read_while(is_whitespace);
    if (input.eof()) return null;
    var ch = input.peek();
    if (ch == "#") {
        skip_comment();
        return read_next();
    }
    if (ch == '"') return read_string();
    if (is_digit(ch)) return read_number();
    if (is_id_start(ch)) return read_ident();
    if (is_punc(ch)) return {
        type  : "punc",
        value : input.next()
    };
    if (is_op_char(ch)) return {
        type  : "op",
        value : read_while(is_op_char)
    };
    input.croak("Can't handle character: " + ch);
}

Toto je hlavní funkce, která je volána metodou next(), když je potřeba získat další token. Všimněte si, že používá spoustu utilit, které jsou zaměřené na jednotlivé typy tokenů, jako read_string(), read_number() apod. Není důvod, abychom si hlavní funkci v tomto místě zbytečně komplikovali kódem těchto funkcí, i když je nikdy nebudeme volat z jiného místa kódu.

Další věc, které si povšimněte, je, že nekonzumujeme celý vstupní řetězec v jednom kroku. Pokaždé, když parser potřebuje další token, přečteme jeden token. Pokud dojde k chybě, nedostaneme se ke konci vstupního souboru.

Funkce read_ident() bude číst znaky tak dlouho, dokud budou splňovat podmínku “mohou být v identifikátoru” (is_id). Identifikátory musí začínat písmenem nebo znaky λ a _, a mohou pokračovat opět některým z těchto znaků, nebo číslicí, nebo znaky ?!-<>=. Proto foo-bar nebude čteno jako tři tokeny, ale jako jeden identifikátor (token “var”). Důvod, proč to tak je, je že chci mít možnost pojmenovávat funkce jmény jako is-pair? nebo string>= (pardon, to je ten Lispař ve mně).

Mimo to funkce read_ident() zkontroluje, jestli načtený identifikátor neodpovídá náhodou nějakému klíčovému slovu. Pokud ano, vrátí místo tokenu “var” token “kw”.

Myslím, že kód v tuto chvíli dokáže mluvit za sebe, takže zde je kompletní tokenizér pro náš jazyk. Pár poznámek naleznete pod výpisem.

function TokenStream(input) {
    var current = null;
    var keywords = " if then else lambda λ true false ";
    return {
        next  : next,
        peek  : peek,
        eof   : eof,
        croak : input.croak
    };
    function is_keyword(x) {
        return keywords.indexOf(" " + x + " ") >= 0;
    }
    function is_digit(ch) {
        return /[0-9]/i.test(ch);
    }
    function is_id_start(ch) {
        return /[a-zλ_]/i.test(ch);
    }
    function is_id(ch) {
        return is_id_start(ch) || "?!-<>=0123456789".indexOf(ch) >= 0;
    }
    function is_op_char(ch) {
        return "+-*/%=&|<>!".indexOf(ch) >= 0;
    }
    function is_punc(ch) {
        return ",;(){}[]".indexOf(ch) >= 0;
    }
    function is_whitespace(ch) {
        return " \t\n".indexOf(ch) >= 0;
    }
    function read_while(predicate) {
        var str = "";
        while (!input.eof() && predicate(input.peek()))
            str += input.next();
        return str;
    }
    function read_number() {
        var has_dot = false;
        var number = read_while(function(ch){
            if (ch == ".") {
                if (has_dot) return false;
                has_dot = true;
                return true;
            }
            return is_digit(ch);
        });
        return { type: "num", value: parseFloat(number) };
    }
    function read_ident() {
        var id = read_while(is_id);
        return {
            type  : is_keyword(id) ? "kw" : "var",
            value : id
        };
    }
    function read_escaped(end) {
        var escaped = false, str = "";
        input.next();
        while (!input.eof()) {
            var ch = input.next();
            if (escaped) {
                str += ch;
                escaped = false;
            } else if (ch == "\\") {
                escaped = true;
            } else if (ch == end) {
                break;
            } else {
                str += ch;
            }
        }
        return str;
    }
    function read_string() {
        return { type: "str", value: read_escaped('"') };
    }
    function skip_comment() {
        read_while(function(ch){ return ch != "\n" });
        input.next();
    }
    function read_next() {
        read_while(is_whitespace);
        if (input.eof()) return null;
        var ch = input.peek();
        if (ch == "#") {
            skip_comment();
            return read_next();
        }
        if (ch == '"') return read_string();
        if (is_digit(ch)) return read_number();
        if (is_id_start(ch)) return read_ident();
        if (is_punc(ch)) return {
            type  : "punc",
            value : input.next()
        };
        if (is_op_char(ch)) return {
            type  : "op",
            value : read_while(is_op_char)
        };
        input.croak("Can't handle character: " + ch);
    }
    function peek() {
        return current || (current = read_next());
    }
    function next() {
        var tok = current;
        current = null;
        return tok || read_next();
    }
    function eof() {
        return peek() == null;
    }
}
  • Funkce next() nevolá vždycky read_next(), protože hodnota mohla být už dříve vyzvednuta (v takovém případě už byla funkce read_next() vyvolána a potřebné znaky z řetězce zkonzumované). Proto používáme proměnnou current, která udrží informace o aktuálním tokenu.
  • Podporujeme pouze decimální čísla v obvyklé notaci (žádné věci jako 1E5, žádné hex, žádné oct). Ale pokud se rozhodneme, že to tak chceme, stačí změnit jen funkci read_number().
  • Na rozdíl od JavaScriptu jediný znak, který se nesmí objevit v řetězci neošetřený, je znak uvozovek a zpětného lomítka. Musíte je “backslashovat” (zapsat se zpětným lomítkem). Jinak mohou řetězce obsahovat cokoli. Neinterpretujeme žádné znaky jako \n, \t apod. Změnit to bude opět velmi jednoduché.

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

Teď máme dostatečně silnou sadu nástrojů k tomu, abychom napsali samotný parser. Začneme popisem AST.

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=19501