Hlavní navigace

Postavte si jazyk

21. 12. 2011 0:16 | zboj

Vývojáři jsou lid kreativní, a jak lépe vybít svou kreativitu, než vytvořením vlastního jazyka? Teď nechci nabádat k vynalézání kola, sám jsem vymyslel v životě kdysi dávno jen jeden jazyk, a to jen proto, že to bylo nutnou podmínkou pro zápočet, všechny ostatní překladače, které jsem kdy napsal, měly za cíl jazyky již existující a nanejvýš mírně upravené. Zde stručně popíšu, jak jednoduše napsat vlastní parser a s ním interpret nebo transpiler.

Nemusíte vědět, kdo je Noam Chomsky, ale měli byste tušit, co je formální gramatika. Regulární jazyky zná asi každý, kdo programuje, tak vězte, že bezkontextové gramatiky jsou něco podobného, jen mají větší generativní sílu. Profíci používají flex a yacc nebo bison či podobné nástroje. Mnohem snazší je ale začít s nějakým skriptovacím jazykem. Vezměme Javascript (JS).

Javascript bez prohlížeče

Kopií bisonu pro JS je jison (snadno vygooglíte). Následuje jednoduchá gramatika pro aritmetické výrazy.

var Parser = require("jison").Parser; var grammar = { "lex": { "rules": [ ["\\s+", "/* skip whitespace */"], ["[0-9]+(?:\\.[0-9]+)?\\b", "return 'NUMBER';"], ["\*", "return '*';"], ["\\/", "return '/';"], ["-", "return '-';"], ["\\+", "return '+';"], ["\\^", "return '^';"], ["\\(", "return '(';"], ["\)", "return ')';"], ["PI\\b", "return 'PI';"], ["E\\b", "return 'E';"], ["$", "return 'EOF';"] ] }, "operators": [ ["left", "+", "-"], ["left", "*", "/"], ["left", "^"], ["left", "UMINUS"] ], "bnf": { "expressions": [["e EOF", "return $1;"]], "e": [["e + e", "$$ = $1 + $3;"], ["e - e", "$$ = $1 - $3;"], ["e * e", "$$ = $1 * $3;"], ["e / e", "$$ = $1 / $3;"], ["e ^ e", "$$ = Math.pow($1, $3);"], ["- e", "$$ = -$2;", { "prec": "UMINUS"}], ["( e )", "$$ = $2;"], ["NUMBER", "$$ = Number(yytext);"], ["E", "$$ = Math.E;"], ["PI", "$$ = Math.PI;"]] } };

První řádek předpokládá, že již máte nainstalovaný jison. Ten funguje například s narwhalem (pomalý, nedoporučuji) nebo s nodejs (to je interpret JS postavený nad superrychlým V8 od Googlu, opět snadno vygooglíte). Gramatiku můžete velice jednoduše interpretovat takto:

var parser = new Parser(grammar); var result = parser.parse("2 + 3"); console.log(result);

Teď máme prakticky zadarmo interpret, možná si ale říkáte, že nutnost mít nodejs (nebo něco podobného) je svazující. To je v podstatě pravda, ale jakmile gramatiku odladíte, není nic snazšího než použít metodu generate:

parser.generate();

Výslednému kódu sice asi nebudete rozumět, ale podstatné je, že se tak zbavíte závislostí na nodejs. Vygenerovaný kód v JS bez problémů interpretuje libovolný moderní prohlížeč, dokonce i MSIE 6 (ten ovšem trošku pomaleji).

Parsing mimo prohlížeč

Kromě prohlížečů můžete kód použít i v nativní aplikaci. Jednou z možností je využít V8, což je interpret JS od Google, zadarmo a rychlý. Vlastně ani ne interpret, většina kódu se totiž překládá do nativního kódu pro Intel nebo ARM. V8 můžete ke své aplikaci staticky přilinkovat (osobně vyzkoušeno pro iOS), nevýhodou je jen větší velikost binárky.

V aplikacích pro Windows můžete využít JScript.NET. K vygenerovanému kódu přidáte toto:

import System; package ParserDemo { public class Parser { public function Parse(s:String) { return parser.parse(s); } } var p = new ParserDemo.Parser(); Console.WriteLine(p.Parse("2 * 3"));

Překladač jsc vygeneruje spustitelný soubor, můžete také vygenerovat dynamickou knihovnu (DLL) a tu volat z kódu v C#, VB, C++/CLI atd. V tomto případě můžete použít volbu /fast+, což znamená, že výsledkem překladu bude čistý MSIL (CIL) kód, tedy žádný interpretovaný JS, ale plnohodnotný bajtkód, jejž JIT před spuštěním přeloží do nativního kódu.

Jak vidíte, napsat si jednoduchý interpret nebo transpiler není vůbec složité. Do nástrojů jako Google Web Toolkit (GWT) to má sice prozatím daleko, ale první krok bychom již měli.