Hledáte lex a yacc pro Javu? Neznáš Jacka

Sun vydal Jack, nový nástroj napsaný v Javě, který automaticky generuje analyzátory kompilací specifikace gramatiky na vysoké úrovni uložené v textovém souboru. Tento článek bude sloužit jako úvod do tohoto nového nástroje. První část článku se věnuje krátkému úvodu k automatickému generování syntaktického analyzátoru a mým prvním zkušenostem s nimi. Poté se článek zaměří na Jacka a na to, jak jej můžete použít ke generování analyzátorů a aplikací vytvořených s těmito analyzátory na základě vaší gramatiky na vysoké úrovni.

Automatické generování analyzátoru kompilátoru

Analyzátor je jednou z nejběžnějších součástí počítačové aplikace. Převádí text, který mohou lidé číst, na datové struktury známé jako parsovací stromy, kterým počítač rozumí. Zřetelně si pamatuji můj úvod do automatického generování syntaktického analyzátoru: Na vysoké škole jsem absolvoval třídu o konstrukci kompilátoru. S pomocí své manželky jsem napsal jednoduchý kompilátor, který dokázal proměnit programy napsané v jazyce vytvořeném pro třídu na spustitelné programy. Pamatuji si, že jsem se v tom okamžiku cítil velmi dobře.

Ve své první „skutečné“ práci po vysoké škole jsem dostal přiřazení k vytvoření nového jazyka pro zpracování grafiky, který se bude kompilovat do příkazů pro grafický koprocesor. Začal jsem s čerstvě složenou gramatikou a připravil se na zahájení vícetýdenního projektu sestavení kompilátoru. Potom mi kamarád ukázal nástroje Unixu lex a yacc. Lex sestavil lexikální analyzátory z regulárních výrazů a yacc snížil specifikaci gramatiky na kompilátor řízený tabulkou, který mohl produkovat kód, když úspěšně analyzoval produkce z této gramatiky. Použil jsem lex a yacca za méně než týden byl můj překladač funkční! Později GNU projekt Free Software Foundation vytvořil „vylepšené“ verze systému lex a yacc - pojmenovaný flex a bizon - pro použití na platformách, na nichž nebyl spuštěn derivát operačního systému Unix.

Svět automatického generování syntaktického analyzátoru opět pokročil, když Terrence Parr, tehdy student Purdue University, vytvořil Purdue Compiler Construction Tool Set nebo PCCTS. Dvě součásti PCCTS - DFA a ANTLR - poskytovat stejné funkce jako lex a yacc; ale gramatiky, které ANTLR přijímá gramatiky LL (k) na rozdíl od gramatik LALR používaných yacc. Kromě toho je kód, který generuje PCCTS, mnohem čitelnější než kód generovaný yacc. Generováním kódu, který je snadněji čitelný, PCCTS usnadňuje člověku číst kód, aby pochopil, co různé části dělají. Toto porozumění může být zásadní při pokusu o diagnostiku chyb ve specifikaci gramatiky. PCCTS rychle vyvinulo sled lidí, kteří považovali jeho soubory za jednodušší než yacc.

Síla automatického generování syntaktického analyzátoru spočívá v tom, že umožňuje uživatelům soustředit se na gramatiku a nemusí se starat o správnost implementace. To může být obrovská úspora času u jednoduchých i složitých projektů.

Jack přistoupí k talíři

Hodnotím nástroje podle obecnosti problému, který řeší. Jelikož se požadavek na parsování textu objevuje znovu a znovu, automatické generování syntaktického analyzátoru je v mém panelu nástrojů velmi vysoké. V kombinaci s rychlým vývojovým cyklem Java poskytuje automatické generování syntaktického analyzátoru nástroj pro návrh kompilátoru, který je těžké porazit.

Jack (rýmuje se s yacc) je generátor syntaktického analyzátoru v duchu PCCTS, který společnost Sun zdarma vydala programátorské komunitě Java. Jack je mimořádně snadný nástroj, který lze popsat: Jednoduše řečeno, dáte mu sadu kombinovaných gramatických a lexingových pravidel ve formě souboru .jack a nástroj spustíte a vrátí vám třídu Java, která tuto gramatiku analyzuje. Co může být jednodušší?

Získat Jacka je také docela snadné. Nejprve si stáhnete kopii z domovské stránky Jacka. To pro vás přichází v podobě samoobslužné třídy Java s názvem Nainstalujte. Chcete-li nainstalovat Jacka, musíte to vyvolat Nainstalujte třída, která se na počítači se systémem Windows 95 provádí pomocí příkazu: C:> instalace Java.

Výše uvedený příkaz předpokládá, že Jáva příkaz je ve vaší cestě příkazu a že cesta třídy byla nastavena odpovídajícím způsobem. Pokud výše uvedený příkaz nefunguje, nebo pokud si nejste jisti, zda máte věci správně nastaveny, otevřete okno systému MS-DOS procházením položek nabídky Start -> Programy - MS-DOS. Pokud máte nainstalovaný Sun JDK, můžete zadat tyto příkazy:

C:> cesta C: \ java \ bin;% cesta% C:> nastavit CLASSPATH = .; c: \ java \ lib \ classes.zip 

Pokud je nainstalována aplikace Symantec Cafe verze 1.2 nebo novější, můžete zadat tyto příkazy:

C:> cesta C: \ cafe \ java \ bin;% path% 

Cesta ke třídě by měla být již nastavena v souboru s názvem sc.ini v adresáři bin Cafe.

Dále zadejte instalace Java příkaz shora. Instalační program se vás zeptá, do kterého adresáře chcete instalovat, a pod ním se vytvoří podadresář Jack.

Pomocí Jacka

Jack je napsán výhradně v jazyce Java, takže mít třídy Jack znamená, že tento nástroj je okamžitě k dispozici na každé platformě, která podporuje virtuální stroj Java. To však také znamená, že v polích Windows musíte Jacka spustit z příkazového řádku. Řekněme, že jste vybrali název adresáře JavaTools, když jste nainstalovali Jack do vašeho systému. Abyste mohli použít Jacka, budete muset na cestu ke třídě přidat Jackovy třídy. Můžete to udělat ve svém autoexec.bat souboru nebo ve vašem souboru .cshrc soubor, pokud jste uživatelem systému Unix. Kritický příkaz je něco jako řádek zobrazený níže:

C:> set CLASSPATH = .; C: \ JavaTools \ Jack \ java; C: \ java \ lib \ classes.zip 

Uživatelé Symantec Cafe mohou upravovat sc.ini soubor a zahrnout tam Jackovy třídy, nebo mohou nastavit CLASSPATH výslovně, jak je uvedeno výše.

Nastavení proměnné prostředí, jak je uvedeno výše, umístí třídy Jack do CLASSPATH mezi „.“ (aktuální adresář) a základní systémové třídy pro Javu. Hlavní třída pro Jacka je COM.sun.labs.jack.Hlavní. Velká písmena jsou důležitá! V příkazu jsou přesně čtyři velká písmena („C“, „O“, „M“ a další „M“). Chcete-li Jack spustit ručně, zadejte příkaz:

C:> java COM.sun.labs.jack.Main parser-input.jack

Pokud na cestě ke třídě nemáte soubory Jack, můžete použít tento příkaz:

C:> java -classpath.; C: \ JavaTools \ Jack \ java; c: \ java \ lib \ classes.zip COM.sun.labs.jack.Hlavní parser-input.jack 

Jak vidíte, bude to trochu delší. Abych minimalizoval psaní, dal jsem vyvolání do a .netopýr soubor s názvem Jack.bat. V určitém okamžiku v budoucnosti bude k dispozici jednoduchý program C wrapper, možná dokonce i při čtení. Dostupnost tohoto a dalších programů naleznete na domovské stránce společnosti Jack.

Když je Jack spuštěn, vytvoří v aktuálním adresáři několik souborů, které později zkompilujete do svého analyzátoru. Většina z nich má buď předponu se jménem vašeho analyzátoru, nebo je společná pro všechny analyzátory. Jeden z nich však ASCII_CharStream.java, se mohou srazit s jinými analyzátory, takže je pravděpodobně dobrý nápad začít v adresáři obsahujícím pouze soubor .zvedák soubor, který použijete ke generování analyzátoru.

Jakmile spustíte Jacka, pokud generace proběhla hladce, budete mít spoustu .Jáva soubory v aktuálním adresáři s různými zajímavými názvy. To jsou vaši analyzátoři. Doporučuji vám otevřít je s editorem a prohlédnout si je. Až budete připraveni, můžete je zkompilovat pomocí příkazu

C:> javac -d. ParserName.java

kde Název analyzátoru je jméno, které jste dali svému analyzátoru ve vstupním souboru. O tom trochu víc. Pokud se všechny soubory pro váš analyzátor nezkompilují, můžete použít metodu hrubé síly psaní:

C:> javac * .java 

Tím se zkompiluje vše v adresáři. V tomto okamžiku je váš nový analyzátor připraven k použití.

Popisy Jack Parser

Soubory popisu Jack Parser mají příponu .zvedák a jsou rozděleny do tří základních částí: opce a základní třída; lexikální žetony; a neterminály. Podívejme se na jednoduchý popis analyzátoru (je obsažen v příklady adresář, který je dodáván s Jackem).

možnosti {LOOKAHEAD = 1; } PARSER_BEGIN (Jednoduché1) veřejná třída Jednoduché1 {public static void main (String args []) hodí ParseError { Jednoduché1 analyzátor = nový Jednoduché1(System.in); parser.Input (); }} PARSER_END (Jednoduché1) 

Prvních několik řádků výše popisuje možnosti analyzátoru; v tomto případě DÍVAT SE DOPŘEDU je nastavena na 1. Zde lze nastavit i další možnosti, jako je diagnostika, zpracování Java Unicode atd. V návaznosti na možnosti přichází základní třída analyzátoru. Tyto dvě značky PARSER_BEGIN a PARSER_END držte třídu, která se stane základním kódem Java pro výsledný analyzátor. Všimněte si, že název třídy použitý ve specifikaci analyzátoru musí být stejné na začátku, uprostřed a na konci této části. Ve výše uvedeném příkladu jsem dal název třídy tučně, abych to objasnil. Jak vidíte v kódu výše, tato třída definuje statickou hlavní metoda, takže třída může být vyvolána interpretem Java na příkazovém řádku. The hlavní metoda jednoduše vytvoří instanci nového analyzátoru se vstupním proudem (v tomto případě System.in) a poté vyvolá Vstup metoda. The Vstup metoda je v naší gramatice neterminální a je definována ve formě prvku EBNF. EBNF znamená Extended Backus-Naur Form. Forma Backus-Naur je metoda pro určení bezkontextových gramatik. Specifikace se skládá z a terminál na levé straně produkční symbol, který je obvykle „:: =“, a jeden nebo více produkce na pravé straně. Použitý zápis je obvykle něco takového:

 Klíčové slovo :: = "-li" | "pak" | "jiný" 

Dalo by se to číst jako: „The Klíčové slovo terminál je jedním z řetězcových literálů „if“, „then“ nebo „else.“ „V Jacku je tento formulář rozšířen tak, aby umožňoval reprezentaci levé části metodou, a alternativní expanze mohou být reprezentovány regulární výrazy nebo jiné neterminály. Pokračování našeho jednoduchého příkladu obsahuje soubor následující definice:

void Input (): {} {MatchedBraces () "\ n"} void MatchedBraces (): {} {"{" [MatchedBraces ()] "}"} 

Tento jednoduchý analyzátor analyzuje níže uvedenou gramatiku:

Kurzívou jsem ukázal ne-terminály na pravé straně produkce a tučné písmo pro zobrazení literálů. Jak vidíte, gramatika jednoduše analyzuje párované sady složených závorek „{“ a „}“ znaků. K popisu této gramatiky jsou v Jackově souboru dvě produkce. První terminál, Vstup, je definován touto definicí jako tři položky v pořadí: a Odpovídající závorky terminál, znak nového řádku a token konce souboru. The token je definován Jackem, takže ho nemusíte specifikovat pro svou platformu.

Při generování této gramatiky se levá strana inscenací promění na metody uvnitř Jednoduché1 třída; při sestavování Jednoduché1 třída čte znaky z Systém.v a ověří, že obsahují odpovídající sadu složených závorek. Toho lze dosáhnout vyvoláním vygenerované metody Vstup, který je procesem generování transformován na metodu, která analyzuje Vstup nekoncový. Pokud analýza selže, metoda vyvolá výjimku ParseError, které může hlavní rutina zachytit a poté si stěžovat, pokud se tak rozhodne.

Samozřejmě je toho víc. Blok vymezený znaky „{“ a „}“ za názvem terminálu - který je v tomto příkladu prázdný - může obsahovat libovolný kód Java, který je vložen na začátek generované metody. Potom po každé expanzi existuje další volitelný blok, který může obsahovat libovolný kód Java, který se má provést, když analyzátor úspěšně odpovídá této expanzi.

Složitější příklad

A co příklad, který je trochu komplikovanější? Zvažte následující gramatiku, opět rozdělenou na kousky. Tato gramatika je navržena k interpretaci matematických rovnic pomocí čtyř základních operátorů - sčítání, násobení, odčítání a dělení. Zdroj najdete zde:

možnosti {LOOKAHEAD = 1; } PARSER_BEGIN (Calc1) veřejná třída Calc1 {public static void main (String args []) hodí ParseError {Calc1 parser = nový Calc1 (System.in); while (true) {System.out.print ("Zadejte výraz:"); System.out.flush (); try {switch (parser.one_line ()) {case -1: System.exit (0); výchozí: konec; }} catch (ParseError x) {System.out.println ("Ukončeno."); hod x; }}}} PARSER_END (Calc1) 

První část je téměř stejná jako Jednoduché1kromě toho, že hlavní rutina nyní volá terminál one_line opakovaně, dokud se nepodaří analyzovat. Dále přichází následující kód:

IGNORE_IN_BNF: {} "" TOKEN: {} {} TOKEN: / * OPERATORS * / {} TOKEN: {} 

Tyto definice pokrývají základní terminály, ve kterých je specifikována gramatika. První, pojmenovaný IGNORE_IN_BNF, je speciální token. Jakékoli tokeny čtené analyzátorem, které odpovídají znakům definovaným v IGNORE_IN_BNF token jsou tiše zahozeny. Jak můžete vidět v našem příkladu, způsobí to, že analyzátor ve vstupu ignoruje mezery, tabulátory a znaky návratu na začátek řádku.