PEG.js: Generátor parserů pro JavaScript

Dnešní webové aplikace jsou stále závislejší na JavaScriptu. Spousta věcí, které se dřív dělaly na serveru, se nyní řeší na straně klienta. Jedním z takových úkolů je i zpracování nejrůznějších formátů dat.

V JavaScriptu není problém zpracovat běžné formáty jako JSON nebo XML, ale s jakýmkoliv složitějším formátem, nebo dokonce jazykem, přijdou potíže. Obvykle je třeba buď najít nějakou chytrou knihovnu, nebo si napsat vlastní parser.

Parsery se dnes běžně píšou pomocí generátorů, které parser vygenerují z gramatiky zpracovávaného jazyka. Když jsem ale před časem potřeboval takový generátor v JavaScriptu použít, narazil jsem – nenašel jsem totiž žádný dostatečně dobrý. Existující generátory jsou vesměs založeny na variacích na téma LR parsing (který nemám rád a navíc má různá omezení), mají ošklivé zápisy gramatik, neumí dobře ošetřovat chyby a mají i jiné další neduhy. A tak se nevyhnutelně stalo, že jsem si napsal generátor vlastní.

Uvítejte PEG.js

PEG.js je generátor parserů pro JavaScript. Je založen na formalismu parsing expression grammar (PEG), což vám asi nic neřekne, ale znamená to několik věcí:

Pro další informace o PEG doporučuji přečíst článek Parsing Expression Grammars: A Recognition-Based Syntactic Foundation (PDF).

K těmto vlastnostem plynoucích z použitého formalismu přidává PEG.js především kvalitní chybová hlášení při parsování – poloha chyby je přesně určena a hlášení je srozumitelné pro člověka.

Jak PEG.js funguje?

PEG.js je klasický generátor, z gramatiky tedy vygeneruje kus kódu, který zpracovává popisovaný jazyk. Zda z jednotlivých prvků jazyka postavíte syntaktický strom, vypíšete je na výstup, nebo nějak zpracujete, je plně na vás – PEG.js umožňuje v libovolném okamžiku zavolat kód v JavaScriptu, kterému je předána část zpracovaného vstupu v podobě javascriptových hodnot. Kód může tyto hodnoty libovolně ztransformovat.

Parser je možné vygenerovat z příkazové řádky (stačí pokud máte nainstalovanou Javu – využíván je interpret JavaScriptu Rhino) a nebo online na stránkách projektu. Druhý způsob se může hodit při ladění a také umožňuje si vygenerovaný parser hned vyzkoušet na různých vstupech přímo v prohlížeči. Jednodušší snad už tvorba parseru ani být nemůže.

Začlenění vygenerovaného parseru např. do webové aplikace je otázka přidání dvou elementů <script> (pro parser samotný a pro malý (2 kB) runtime, který potřebuje k svému běhu).

Schéma práce PEG.js

Zaujalo?

Zaujal vás PEG.js? Pokud ano, budu rád, když si ho vyzkoušíte. Narazíte-li na nějakou chybu či nedostatek, dejte mi vědět (nejlépe napsat do diskuzní skupiny nebo použít issue tracker). V tuto chvíli je projekt v relativně rané fázi vývoje a lecos se ještě může změnit (např. formát gramatiky), rád bych ale generátor postupně vyladil a stabilizoval tak, aby nebyl problém ho nasadit na reálných projektech. Když už kvůli ničemu jinému, tak proto, že ho chci sám používat.

Odkazy

Mar 15, 2010 – 13:00

Comments

David Majda

[2] Levá rekurze: Všiml jsem si, že ji v phpeg máš implementovanou. Nestihl jsem ještě nastudovat, jak to udělat, ale mám v plánu se na to podívat.

Parsování Python-like odsazování jsem nikdy neřešil. Python samotný to má AFAIK řešené na úrovní lexeru, který na příslušná místa vkládá speciální tokeny (INDENT a DEDENT). V PEG by to asi šlo řešit přes uchovávání stavu odsazení někde bokem a simulace INDENT a DEDENT pomocí akcí/predikátů s kódem, což ale není moc čisté a mám pocit, že při hlubším zamyšlení by se možná narazilo na nějaké háčky.

Add comment

It is not possible to add comments to posts older than one month.