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.
Existuje projekt lua.js který tento postup používá.
(https://github.com/mherkender/lua.js)
Umožňuje psát v kód v jazyce lua do prohlížeče a tam ho spouštět.
@3 princip je stejný pro jakýkoliv jazyk, od C přes python po js. Akorát se obvykle nepoužívá javascriptové prostředí, ale na začátku zmíněné nástroje (bison, yacc, flex). Případně si můžete všechno vytvořit ručně, ale to je nepěkný, zlý, ošklivá věc (osobní zkušenost ze školy :D).
Já mám osobně docela dobrou zkušenost s technikou Top Down Operator Precedence parsing. Lze jí poměrně dobře implementovat ve skriptovacích jazycích a člověk u toho nemá pocit, že pracuje s nějakou "magickou skříňkou".
(Příklady v Pythonu: http://effbot.org/zone/tdop-index.htm a v JS: http://javascript.crockford.com/tdop/tdop.html)
No já se právě ve škole a po škole zabýval vlastními parsery jazyků a nepřišel jsem na chuť automatizovaným nástrojům. Většinou je to stejně jen o dvou věcech. Lexikální analýza, tj převod textu na symboly, a "rekurzivní sestup" kdy jazyk je popsán LL(1) nebo obecně LL(n) gramatikou a není problém takovou gramatiku přímo přepsat do volání funkcí které obsahují větvení podle následujícího symbolu, nebo prostě jen symbol přijímají a ověřují.
Samotnou interpretaci jsem většinou řešil převodem textu do vyhodnocovacího stromu. Jo, výsledek bylo možné serializovat do bytecode a pak provádět zásobníkovým automatem, ale to už je jen třešnička. Vyhodnocení stromu je v zásadě totéž a často to naprosto dostačuje.
Největší problémy mi teď u návrhu jednoho skriptovacího jazyka dělá paradoxně garbage collecting odhozených proměnných. Ne že bych neuměl napsat GC, ale přijde mi to hodně pomalé.
@14 Jenže takle jednoduše jdou implementovat právě jen ty LL(1), které na mnoho jazyků nestačí. Už si přesně nepamatuju v čem to omezení spočívá, ale tuším, že to má cosi společného s uzavíráním např. bloků po THEN - tedy klíčovým slovem ENDIF. Pokud vím, tak mnohem použitelnější jsou LALR gramatiky, ale na ty už je generátor potřeba.
@18: Byly vytvořeny i nástroje pro generování analyzátorů rekurzivním sestupem z gramatik s levou rekurzí.
Někde jsem viděl srovnání analyzátorů řízených tabulkou a zakódovaných. Ty zakódované vyšly o něco (asi 6x) rychlejší. Takže rekurzivní sestup vs. shift-reduce tabulka by nemuselo vyjít až tak zle.
Ono dost záleží i na tom, jak se ta gramatika napíše a co se děje kolem (lexikální analýza, sémantické akce).
Hmm, naposledy kdyz jsem implementoval parser, nakonec jsem pouzil Parser Combinator knihovnu, prislo mi to o dost intuitivnejsi, primocarejsi a lepe se to debuggovalo. Bylo to tehda ve smalltalku, ale mam za to ze nejaka takova knihovna existuje dnes snad v kazdem pouzivanem jazyce, i kdyz samozrejme podstatne lepe sedne do jazyka ve kterem se snadno zapisuji higher-order konstrukce (nejlepe pokud nativne umi closures). Rekurzivni parsery jsou pro me doufam minulost :) I kdyz napr. *ison muze mit jednu vyhodu - napises parser v jazyce *ison a vysledny parser si muzes nechat vygenerovat v libovolnem podporovanem cilovem jazyce. Pro me je to ovsem spis nevyhoda - radsi si parser napisu v Parser Combinator knihovne ciloveho jazyka, ktery uz jednou umim, muzu ladit kod psany clovekem a ne generovany strojem, malokdy potrebuju gramatiku pouzit ve vice cilovych jazycich..
Mam taky sen a to kompilator jazyka PASCAL vo webovom prehliadaci.
Ak by niekto vedel poradit budem velmi rad a pouzijem to vo svojom projekte tu www.trsek.com
Vopred dakujem
@12 Taky bych doporucil ANTLR. Cca pul roku jsem pouzival boost::spirit (obe verze) a dost jsem bojoval v nedostatkem dokumnetace. Nakonec jsem skoncil na tom ze jsem nenasel kompilator, ktery by byl schopny moje zdrojaky prelozit. Ty sablony jsou tak brutalni, ze ma chvilema gcc exponencialni pametovy naroky.
Takze jsem nakonec misto psani gramatiky bojoval s chybama v kompilatorech.
Prace ANTLR je mnohem produktivnejsi. Vysledny parser ma pres 300000 radek a nedovedu si predstavit, ze bych neco takoveho udrzoval "rucne".
PS: ANTLR verze 4 uz bude umet i levou rekurzi.
@25 Tou gramatikou je Oracle SQL. Ta gramatika je extremne nejednoznacna, obsahuje mnoho klicovych slov, ktere mohou byt zaroven i identifikatory. Kvuli tomu ma vetsina pravidel dlouhy look-ahead. Podobne je to i s jinymi SQL gramatikami, autor ANTLR gramatiky pro ISO SQL 2003 uvadi, ze pro vygenerovani prijimaciho automatu je potreba 8GB Ram a samotny vypocet trva pres pul hodiny.
Zadanim pro me byla referencni prirucka jazyka a nejaky balik testovacich dotazu. Ten balik obsahoval ruzny obskurdni dotazy, ktery referenece nepopisovala. Osetreni tech vyjimek vyzadovalo ruzne refactoringy te gramatiky a pokazde se zvetsila velikost prijimaciho automatu. Kdyby to bylo napsany "rucne" tak by to urcite nemelo tolik radek, ale nespis bych to nemel nikdy hotovy.
Autor se zabývá vývojem kompilátorů a knihoven pro objektově-orientované programovací jazyky.
Přečteno 36 055×
Přečteno 25 240×
Přečteno 23 698×
Přečteno 20 078×
Přečteno 17 774×