Zaujíma vás niekedy, ako funguje kompilátor Java? Potrebujete napísať syntaktické analyzátory pre značkovacie dokumenty, ktoré sa neprihlásia na odber štandardných formátov, ako sú HTML alebo XML? Alebo chcete implementovať svoj vlastný malý programovací jazyk len pre sakra? JavaCC vám umožňuje robiť toto všetko v prostredí Java. Takže či už máte záujem dozvedieť sa viac o tom, ako fungujú prekladače a tlmočníci, alebo máte konkrétne ambície vytvoriť nástupcu programovacieho jazyka Java, pripojte sa ku mne pri hľadaní tohto mesiaca preskúmať JavaCC, zvýraznené konštrukciou šikovnej malej kalkulačky príkazového riadku.
Základy konštrukcie prekladača
Programovacie jazyky sa často trochu umelo delia na kompilované a interpretované jazyky, aj keď sa hranice stierajú. Preto sa tým netrápte. Koncepcie tu diskutované platia rovnako dobre pre kompilované ako aj tlmočené jazyky. Použijeme slovo zostavovateľ nižšie, ale pre rozsah tohto článku to bude zahŕňať význam tlmočník.
Ak je prekladačom dodaný text programu (zdrojový kód), musia vykonať tri hlavné úlohy:
- Lexikálna analýza
- Syntaktická analýza
- Generovanie alebo vykonávanie kódu
Väčšina práce kompilátora sa sústreďuje na kroky 1 a 2, ktoré zahŕňajú pochopenie zdrojového kódu programu a zabezpečenie jeho syntaktickej správnosti. Tomu hovoríme proces parsovanie, Ktoré je analyzátor 'zodpovednosť.
Lexikálna analýza (lexing)
Lexikálna analýza zbežne pozrie zdrojový kód programu a rozdelí ho na správny žetóny. Token je významná súčasť zdrojového kódu programu. Príklady tokenov zahŕňajú kľúčové slová, interpunkciu, literály, ako sú čísla a reťazce. Medzi neoprávnené subjekty patrí biele miesto, ktoré sa často ignoruje, ale používa sa na oddelenie tokenov, a komentáre.
Syntaktická analýza (analýza)
Počas syntaktickej analýzy syntaktický analyzátor extrahuje význam zo zdrojového kódu programu zaistením syntaktickej správnosti programu a vytvorením internej reprezentácie programu.
Teória počítačového jazyka hovorí o programy,gramatika a jazykoch. V tomto zmysle je program postupnosťou tokenov. Literál je základný prvok počítačového jazyka, ktorý sa nedá ďalej redukovať. Gramatika definuje pravidlá pre zostavovanie syntakticky správnych programov. Správne sú iba programy, ktoré sa hrajú podľa pravidiel definovaných v gramatike. Jazyk je jednoducho sada všetkých programov, ktoré vyhovujú všetkým vašim gramatickým pravidlám.
Počas syntaktickej analýzy kompilátor skúma zdrojový kód programu s ohľadom na pravidlá definované v gramatike jazyka. Ak dôjde k porušeniu niektorého gramatického pravidla, kompilátor zobrazí chybové hlásenie. Postupom času pri skúmaní programu kompilátor vytvorí ľahko spracovateľnú internú reprezentáciu počítačového programu.
Pravidlá gramatiky počítačového jazyka je možné jednoznačne a úplne špecifikovať pomocou notácie EBNF (Extended Backus-Naur-Form) (viac o EBNF nájdete v časti Zdroje). EBNF definuje gramatiky z hľadiska výrobných pravidiel. Produkčné pravidlo uvádza, že gramatický prvok - buď literály alebo zložené prvky - môže byť zložený z ďalších gramatických prvkov. Literály, ktoré sú neredukovateľné, sú kľúčové slová alebo fragmenty statického textu programu, napríklad interpunkčné symboly. Zložené prvky sa odvodzujú pomocou pravidiel výroby. Pravidlá výroby majú nasledujúci všeobecný formát:
GRAMMAR_ELEMENT: = zoznam gramatických prvkov | alternatívny zoznam gramatických prvkov
Ako príklad sa pozrime na gramatické pravidlá pre malý jazyk, ktorý popisuje základné aritmetické výrazy:
expr: = číslo | expr '+' expr | expr '-' expr | expr '*' expr | expr '/' expr | "(" expr ")" | - expr number: = číslica + („.“ číslica +)? číslica: = '0' | „1“ | „2“ | „3“ | „4“ | „5“ | „6“ | „7“ | „8“ | „9“ Gramatické prvky definujú tri pravidlá výroby:
exprčísločíslica
Jazyk definovaný v tejto gramatike nám umožňuje určiť aritmetické výrazy. An expr je číslo alebo jeden zo štyroch operátorov infix použitých pre dvoch exprs, an expr v zátvorke alebo záporák expr. A číslo je číslo s pohyblivou rádovou čiarkou s voliteľným desatinným zlomkom. Definujeme a číslica byť jednou zo známych desatinných číslic.
Generovanie alebo vykonávanie kódu
Akonáhle syntaktický analyzátor úspešne analyzuje program bez chyby, existuje v internej reprezentácii, ktorú kompilátor ľahko spracuje. Teraz je pomerne ľahké vygenerovať strojový kód (alebo bajtový kód Java) z internej reprezentácie alebo priamo vykonať internú reprezentáciu. Ak urobíme prvé, zostavujeme; v druhom prípade hovoríme o tlmočení.
JavaCC
JavaCC, ktorý je k dispozícii zadarmo, je generátor syntaktického analyzátora. Poskytuje rozšírenie jazyka Java na určenie gramatiky programovacieho jazyka. JavaCC bol pôvodne vyvinutý spoločnosťou Sun Microsystems, ale teraz je udržiavaný programom MetaMata. Ako každý slušný programovací nástroj, JavaCC sa skutočne používalo na určenie gramatiky súboru JavaCC vstupný formát.
Navyše, JavaCC umožňuje definovať gramatiky podobným spôsobom ako EBNF, čo umožňuje ľahký preklad gramatík EBNF do jazyka JavaCC formát. Ďalej JavaCC je najpopulárnejší generátor syntaktických analyzátorov pre Javu s množstvom preddefinovaných JavaCC gramatiky, ktoré je možné použiť ako východiskový bod.
Vývoj jednoduchej kalkulačky
Teraz sa znovu vraciame k nášmu malému aritmetickému jazyku, aby sme vytvorili jednoduchú kalkulačku príkazového riadku v Jave pomocou JavaCC. Najprv musíme preložiť gramatiku EBNF do JavaCC naformátujte a uložte do súboru Arithmetic.jj:
možnosti {LOOKAHEAD = 2; } PARSER_BEGIN (aritmetika) verejná trieda aritmetika {} PARSER_END (aritmetika) SKIP: "\ t" TOKEN: double expr (): {} term () ("+" expr () double term (): {} "/" výraz ()) * double unary (): {} "-" element () double element (): {} "(" expr () ")" Vyššie uvedený kód by vám mal poskytnúť predstavu o tom, ako určiť gramatiku pre jazyk JavaCC. The možnosti časť v hornej časti určuje množinu možností pre danú gramatiku. Zadali sme hľadanú oblasť 2. Ovládanie ďalších možností JavaCCladiace funkcie a ďalšie. Tieto možnosti môžu byť prípadne špecifikované na serveri JavaCC príkazový riadok.
The PARSER_BEGIN klauzula určuje, že nasleduje definícia triedy syntaktického analyzátora. JavaCC generuje jednu triedu Java pre každý syntaktický analyzátor. Voláme triedu parserov Aritmetika. Zatiaľ vyžadujeme iba prázdnu definíciu triedy; JavaCC k nej neskôr pridá vyhlásenia súvisiace s analýzou. Definíciu triedy končíme PARSER_END doložka.
The PRESKOČIŤ časť označuje znaky, ktoré chceme preskočiť. V našom prípade ide o biele znaky. Ďalej definujeme tokeny nášho jazyka v TOKEN oddiel. Čísla a číslice definujeme ako tokeny. Poznač si to JavaCC rozlišuje medzi definíciami tokenov a definíciami pre ďalšie produkčné pravidlá, ktoré sa líšia od EBNF. The PRESKOČIŤ a TOKEN časti špecifikujú túto gramatickú lexikálnu analýzu.
Ďalej definujeme produkčné pravidlo pre expr, gramatický prvok najvyššej úrovne. Všimnite si, ako sa táto definícia výrazne líši od definície expr v EBNF. Čo sa deje? Ukázalo sa, že vyššie uvedená definícia EBNF je nejednoznačná, pretože umožňuje viacnásobné zastúpenie toho istého programu. Preskúmajme napríklad výraz 1+2*3. Môžeme sa vyrovnať 1+2 do expr poddávajúci sa expr * 3, ako na obrázku 1.
Alebo by sme mohli najskôr zápasiť 2*3 do expr vyúsťujúce do 1 + expr, ako je znázornené na obrázku 2.
S JavaCC, musíme jednoznačne určiť gramatické pravidlá. Vo výsledku prelomíme definíciu expr do troch produkčných pravidiel, definujúcich gramatické prvky expr, termín, unárnya element. Teraz výraz 1+2*3 je analyzovaný, ako je znázornené na obrázku 3.
Z príkazového riadku môžeme bežať JavaCC skontrolovať našu gramatiku:
javacc Arithmetic.jj Java Compiler Compiler Verzia 1.1 (generátor analyzátora) Autorské práva (c) 1996-1999 Sun Microsystems, Inc. Autorské práva (c) 1997-1999 Metamata, Inc. (typ „javacc“ bez argumentov o pomoci) Čítanie zo súboru Arithmetic.jj. . . Upozornenie: Kontrola primeranosti Lookahead sa nevykonáva, pretože voľba LOOKAHEAD je viac ako 1. Nastavením možnosti FORCE_LA_CHECK nastavíte hodnotu true na vynútenie kontroly. Analyzátor vygenerovaný s 0 chybami a 1 varovaním.
V nasledujúcom texte sa kontrolujú problémy s definíciou našej gramatiky a generuje sa súbor zdrojových súborov Java:
TokenMgrError.java ParseException.java Token.java ASCII_CharStream.java Arithmetic.java ArithmeticConstants.java ArithmeticTokenManager.java
Spoločne tieto súbory implementujú syntaktický analyzátor v Jave. Tento syntaktický analyzátor môžete vyvolať vytvorením inštancie inštancie súboru Aritmetika trieda:
public class Arithmetic implements ArithmeticConstants {public Arithmetic (java.io.InputStream stream) {...} public Arithmetic (java.io.Reader stream) {...} public Arithmetic (ArithmeticTokenManager tm) {...} static final public double expr () hodí ParseException {...} statické konečné verejné double term () hodí ParseException {...} statické konečné verejné double unary () hodí ParseException {...} statické konečné verejné double element () hodí ParseException {. ..} static public void ReInit (stream java.io.InputStream) {...} static public void ReInit (stream java.io.Reader) {...} public void ReInit (ArithmeticTokenManager tm) {...} statický konečný verejný token getNextToken () {...} statický konečný verejný token getToken (int index) {...} statický konečný verejný ParseException generateParseException () {...} statický konečný verejný neplatný enable_tracing () {...} statický final public void disable_tracing () {...}} Ak ste chceli použiť tento syntaktický analyzátor, musíte vytvoriť inštanciu pomocou jedného z konštruktorov. Konštruktéri vám umožňujú odovzdať buď InputStream, a Čitateľ, alebo ArithmeticTokenManager ako zdroj zdrojového kódu programu. Ďalej zadáte hlavný gramatický prvok vášho jazyka, napríklad:
Aritmetický syntaktický analyzátor = nový Aritmetický (System.in); parser.expr ();
Zatiaľ sa však nič moc nedeje, pretože v Arithmetic.jj definovali sme iba gramatické pravidlá. Zatiaľ sme nepridali kód potrebný na vykonanie výpočtov. Za týmto účelom pridávame do gramatických pravidiel príslušné akcie. Calcualtor.jj obsahuje kompletnú kalkulačku vrátane akcií:
možnosti {LOOKAHEAD = 2; } PARSER_BEGIN (Calculator) public class Calculator {public static void main (String args []) throws ParseException {Calculator parser = new Calculator (System.in); while (true) {parser.parseOneLine (); }}} PARSER_END (kalkulačka) SKIP: "\ t" TOKEN: void parseOneLine (): {double a; } {a = expr () {System.out.println (a); } | | {System.exit (-1); }} double expr (): {double a; dvojité b; } {a = term () ("+" b = expr () {a + = b;} | "-" b = expr () {a - = b;}) * {return a; }} dvojitý výraz (): {double a; dvojité b; } {a = unary () ("*" b = term () {a * = b;} | "/" b = term () {a / = b;}) * {return a; }} dvojité unárne (): {dvojité a; } {"-" a = element () {návrat -a; } | a = element () {return a; }} dvojitý prvok (): {Token t; dvojité a; } {t = {návrat Double.parseDouble (t.toString ()); } | "(" a = expr () ")" {return a; }} Hlavná metóda najskôr vytvorí inštanciu objektu syntaktického analyzátora, ktorý číta zo štandardného vstupu a potom zavolá parseOneLine () v nekonečnej slučke. Metóda parseOneLine () sám je definovaný ďalším pravidlom gramatiky. Toto pravidlo jednoducho definuje, že očakávame každý výraz na riadku sám od seba, že je v poriadku zadávať prázdne riadky a že program ukončíme, ak sa dostaneme na koniec súboru.
Zmenili sme návratový typ pôvodných gramatických prvkov na návrat dvojitý. Vykonáme príslušné výpočty priamo tam, kde ich analyzujeme a výsledky výpočtu odovzdáme do stromu hovoru. Transformovali sme tiež definície gramatických prvkov, aby sme ich výsledky ukladali do lokálnych premenných. Napríklad a = prvok () analyzuje an element a uloží výsledok do premennej a. To nám umožňuje použiť výsledky analyzovaných prvkov v kóde akcií na pravej strane. Akcie sú bloky kódu Java, ktoré sa vykonajú, keď príslušné pravidlo gramatiky nájde zhodu vo vstupnom prúde.
Vezmite prosím na vedomie, ako málo kódu Java sme pridali, aby bola kalkulačka plne funkčná. Navyše je ľahké pridať ďalšie funkcie, napríklad zabudované funkcie alebo dokonca premenné.
