Programmering

Sådan bygger du en tolk i Java, del 1: GRUNDLÆGGENDE

Da jeg fortalte en ven, at jeg havde skrevet en BASIC-tolk på Java, lo han så hårdt, at han næsten spildte sodavand, som han holdt over hele sit tøj. "Hvorfor i alverden ville du bygge en BASIC-tolk i Java?" var det forudsigelige første spørgsmål ud af hans mund. Svaret er både enkelt og komplekst. Det enkle svar er, at det var sjovt at skrive en tolk i Java, og hvis jeg skulle skrive en tolk, kunne jeg lige så godt skrive en, som jeg har gode minder om, fra de tidlige dage med personlig computing. På den komplekse side har jeg bemærket, at mange mennesker, der bruger Java i dag, er kommet forbi punktet for at skabe tumlende Duke-applets og går videre til seriøse applikationer. Ofte, når du bygger en applikation, vil du gerne have, at den kan konfigureres. Den valgte mekanisme til omkonfiguration er en slags dynamisk eksekveringsmotor.

Kendt som makro-sprog eller konfigurationssprog, er dynamisk udførelse den funktion, der gør det muligt for en applikation at blive "programmeret" af brugeren. Fordelen ved at have en dynamisk eksekveringsmotor er, at værktøjer og applikationer kan tilpasses til at udføre komplekse opgaver uden at udskifte værktøjet. Java-platformen tilbyder en bred vifte af dynamiske udførelsesmotormuligheder.

HotJava og andre hot-muligheder

Lad os kort udforske nogle af de tilgængelige muligheder for dynamisk udførelsesmotor og derefter se på implementeringen af ​​min tolk i dybden. En dynamisk udførelsesmotor er en indlejret tolk. En tolk har brug for tre faciliteter for at kunne fungere:

  1. Et middel til at blive fyldt med instruktioner
  2. Et modulformat til lagring af instruktioner, der skal udføres
  3. En model eller et miljø til interaktion med værtsprogrammet

HotJava

Den mest berømte integrerede tolk skal være HotJava "applet" -miljøet, der har omformet den måde, folk ser på webbrowsere på.

HotJava "applet" -modellen var baseret på forestillingen om, at en Java-applikation kunne oprette en generisk baseklasse med en kendt grænseflade og derefter dynamisk indlæse underklasser af denne klasse og udføre dem på kørselstid. Disse applets gav nye muligheder og inden for rammerne af baseklassen leverede dynamisk udførelse. Denne dynamiske eksekveringsfunktion er en grundlæggende del af Java-miljøet og en af ​​de ting, der gør det så specielt. Vi vil se nærmere på dette særlige miljø i en senere kolonne.

GNU EMACS

Før HotJava ankom, var måske den mest succesrige applikation med dynamisk udførelse GNU EMACS. Denne redaktørs LISP-lignende makro sprog er blevet en hæfteklammer for mange programmører. Kort fortalt består EMACS LISP-miljøet af en LISP-tolk og mange redigeringstypefunktioner, der kan bruges til at komponere de mest komplekse makroer. Det bør ikke betragtes som overraskende, at EMACS-editoren oprindeligt blev skrevet i makroer designet til en editor kaldet TECO. Tilgængeligheden af ​​et rigt (hvis ulæseligt) makrosprog i TECO gjorde det således muligt at konstruere en helt ny editor. I dag er GNU EMACS base-editor, og hele spil er ikke skrevet mere end EMACS LISP-koden, kendt som el-code. Denne konfigurationsevne har gjort GNU EMACS til en mainstay-editor, mens VT-100-terminalerne, den var designet til at køre på, er blevet blot fodnoter i en forfatterkolonne.

REXX

Et af mine yndlingssprog, der aldrig helt skabte det plask, det fortjente, var REXX, designet af Mike Cowlishaw fra IBM. Virksomheden havde brug for et sprog til at kontrollere applikationer på store mainframes, der kører VM-operativsystemet. Jeg opdagede REXX på Amiga, hvor det var tæt forbundet med en lang række applikationer gennem "REXX-porte." Disse porte gjorde det muligt at køre applikationer eksternt via REXX-tolk. Denne kobling af tolk og applikation skabte et langt mere kraftfuldt system, end det var muligt med dets komponenter. Heldigvis lever sproget videre i NETREXX, en version Mike skrev, der blev samlet til Java-kode.

Da jeg kiggede på NETREXX og et meget tidligere sprog (LISP i Java), slog det mig, at disse sprog udgjorde vigtige dele af Java-applikationshistorien. Hvilken bedre måde at fortælle denne del af historien på end at gøre noget sjovt her - som at genoplive BASIC-80? Vigtigere er det, at det ville være nyttigt at vise en måde, hvorpå man kan skrive script-sprog i Java, og gennem deres integration med Java vise, hvordan de kan forbedre funktionerne i dine Java-applikationer.

GRUNDLÆGGENDE krav til forbedring af dine Java-apps

BASIC er ganske enkelt et grundlæggende sprog. Der er to tanker om, hvordan man kan gå til at skrive en tolk for det. En tilgang er at skrive en programmeringssløjfe, hvor tolkeprogrammet læser en tekstlinje fra det fortolkede program, analyserer det og derefter kalder en underrutine til at udføre den. Sekvensen af ​​læsning, parsing og udførelse gentages, indtil en af ​​det fortolkede programs udsagn fortæller tolken at stoppe.

Den anden og meget mere interessante måde at tackle projektet på er faktisk at analysere sproget i et parse-træ og derefter udføre parse-træet "på plads." Sådan fungerer tokeniserende tolke, og hvordan jeg valgte at gå videre. Tokeniserende tolke er også hurtigere, da de ikke har brug for at scanne input igen, hver gang de udfører en erklæring.

Som jeg nævnte ovenfor er de tre komponenter, der er nødvendige for at opnå dynamisk udførelse, et middel til at blive indlæst, et modulformat og eksekveringsmiljøet.

Den første komponent, et middel til at blive indlæst, behandles af en Java InputStream. Da input streams er grundlæggende i I / O-arkitekturen i Java, er systemet designet til at læse i et program fra en InputStream og konvertere den til eksekverbar form. Dette repræsenterer en meget fleksibel måde at føre kode ind i systemet. Naturligvis vil protokollen for dataene, der går over inputstrømmen, være BASIC kildekode. Det er vigtigt at bemærke, at ethvert sprog kan bruges; begå ikke den fejl at tro, at denne teknik ikke kan anvendes til din applikation.

Når kildekoden til det fortolkede program er indtastet i systemet, konverterer systemet kildekoden til en intern repræsentation. Jeg valgte at bruge parse-træet som det interne repræsentationsformat til dette projekt. Når parse-træet er oprettet, kan det manipuleres eller udføres.

Den tredje komponent er eksekveringsmiljøet. Som vi får se, er kravene til denne komponent ret enkle, men implementeringen har et par interessante vendinger.

En meget hurtig BASIC tour

For dem af jer, der måske aldrig har hørt om BASIC, giver jeg dig et kort indblik i sproget, så du kan forstå de parsing og udførelsesudfordringer, der ligger foran dig. For mere information om BASIC, anbefaler jeg stærkt ressourcerne i slutningen af ​​denne kolonne.

BASIC står for Beginners All-purpose Symbolic Instructional Code, og det blev udviklet ved Dartmouth University for at undervise i computerkoncepter til studerende. Siden udviklingen har BASIC udviklet sig til en række forskellige dialekter. Den enkleste af disse dialekter bruges som kontrolsprog til industrielle proceskontrollere; de mest komplekse dialekter er strukturerede sprog, der indeholder nogle aspekter af objektorienteret programmering. Til mit projekt valgte jeg en dialekt kendt som BASIC-80, der var populær på CP / M-operativsystemet i slutningen af ​​halvfjerdserne. Denne dialekt er kun moderat mere kompleks end de enkleste dialekter.

Udtalelsessyntaks

Alle udsagnslinjer er af formularen

[ : [ : ... ] ]

hvor "Linie" er et sætningslinjenummer, "Søgeord" er et GRUNDLÆGGENDE sætningsnøgleord, og "Parametre" er et sæt parametre, der er knyttet til dette søgeord.

Linjenummeret har to formål: Det fungerer som en etiket til udsagn, der styrer eksekveringsstrømmen, såsom en gå til erklæring, og den fungerer som et sorteringskode for udsagn indsat i programmet. Som et sorteringskort letter linjenummeret et redigeringsmiljø, hvor redigering og kommandobehandling blandes i en enkelt interaktiv session. Forresten var dette nødvendigt, når alt hvad du havde var en teletype. :-)

Selvom det ikke er meget elegant, giver linjenumre tolkemiljøet muligheden for at opdatere programmet en sætning ad gangen. Denne evne stammer fra det faktum, at en erklæring er en enkelt parset enhed og kan forbindes i en datastruktur med linjenumre. Uden linjenumre er det ofte nødvendigt at parse hele programmet igen, når en linje skifter.

Nøgleordet identificerer BASIC-sætningen. I eksemplet understøtter vores tolk et lidt udvidet sæt BASIC nøgleord, inklusive gå til, gosub, Vend tilbage, Print, hvis, ende, data, gendanne, Læs, , rem, til, Næste, lade, input, hold op, svag, randomisere, tronog troff. Vi går naturligvis ikke over alle disse i denne artikel, men der vil være noget dokumentation online i min næste måneds "Java In Depth", som du kan udforske.

Hvert nøgleord har et sæt juridiske nøgleordsparametre, der kan følge det. F.eks gå til nøgleordet skal følges af et linjenummer, hvis udsagn skal efterfølges af et betinget udtryk såvel som nøgleordet derefter -- og så videre. Parametrene er specifikke for hvert nøgleord. Jeg dækker et par af disse parameterlister i detaljer lidt senere.

Udtryk og operatører

Ofte er en parameter specificeret i en erklæring et udtryk. Den version af BASIC, jeg bruger her, understøtter alle de standard matematiske operationer, logiske operationer, eksponentiering og et simpelt funktionsbibliotek. Den vigtigste komponent i udtrykket grammatik er evnen til at kalde funktioner. Selve udtrykkene er ret standard og ligner dem, der er analyseret af eksemplet i min tidligere StreamTokenizer-kolonne.

Variabler og datatyper

En del af grunden til, at BASIC er et så simpelt sprog, er, at det kun har to datatyper: tal og strenge. Nogle scripting-sprog, såsom REXX og PERL, skelner ikke engang denne datatype, før de bruges. Men med BASIC bruges en simpel syntaks til at identificere datatyper.

Variable navne i denne version af BASIC er strenge af bogstaver og tal, der altid starter med et bogstav. Variabler er ikke store og små bogstaver. Således er A, B, FOO og FOO2 alle gyldige variabelnavne. Desuden svarer variablen FOOBAR i BASIC til FooBar. For at identificere strenge føjes et dollartegn ($) til variabelnavnet; variablen FOO $ er således en variabel, der indeholder en streng.

Endelig understøtter denne version af sproget arrays ved hjælp af svag nøgleord og en variabel syntaks af formularen NAME (index1, index2, ...) for op til fire indekser.

Programstruktur

Programmer i BASIC starter som standard på den laveste nummererede linje og fortsætter, indtil der enten ikke er flere linjer at behandle eller hold op eller ende nøgleord udføres. Et meget simpelt BASIC-program er vist nedenfor:

100 REM Dette er sandsynligvis det kanoniske BASIC eksempel 110 REM-program. Bemærk, at REM-udsagn ignoreres. 120 PRINT "Dette er et testprogram." 130 UDSKRIV "Summing af værdierne mellem 1 og 100" 140 LET i alt = 0 150 FOR I = 1 TIL 100 160 LET i alt = total + i 170 NÆSTE I 180 UDSKRIV "Samlet antal cifre mellem 1 og 100 er" i alt 190 END 

Linjenumrene ovenfor angiver udsagnens leksikale rækkefølge. Når de køres, udskriver linier 120 og 130 meddelelser til output, linje 140 initialiserer en variabel, og sløjfen i linier 150 til 170 opdaterer værdien af ​​denne variabel. Endelig udskrives resultaterne. Som du kan se, er BASIC et meget simpelt programmeringssprog og derfor en ideel kandidat til undervisning i computerkoncepter.

Organisering af tilgangen

BASIC er typisk for scripting-sprog og involverer et program sammensat af mange udsagn, der kører i et bestemt miljø. Designudfordringen er derfor at konstruere objekterne til at implementere et sådant system på en nyttig måde.

Da jeg kiggede på problemet, sprang en ligetil datastruktur ret ud på mig. Denne struktur er som følger:

Den offentlige grænseflade til skriptsproget skal bestå af

  • En fabriksmetode, der tager kildekoden som input og returnerer et objekt, der repræsenterer programmet.
  • Et miljø, der giver den ramme, hvor programmet udføres, inklusive "I / O" -enheder til tekstinput og tekstoutput.
  • En standard måde at ændre objektet på, måske i form af en grænseflade, der gør det muligt at kombinere programmet og miljøet for at opnå nyttige resultater.

Internt var tolkens struktur lidt mere kompliceret. Spørgsmålet var, hvordan man skal tage fat på de to aspekter af manussproget, parsing og udførelse? Tre grupper af klasser resulterede - en til parsing, en til den strukturelle ramme for at repræsentere parsede og eksekverbare programmer og en, der dannede basismiljøklassen til udførelse.

I parsingsgruppen kræves følgende objekter:

  • Lexikal analyse til behandling af koden som tekst
  • Parsing af udtryk for at konstruere parse-træer af udtrykkene
  • Parsing af erklæring for at konstruere parse-træer af selve udsagnene
  • Fejlklasser til rapportering af fejl i parsing

Rammegruppen består af objekter, der indeholder parstræerne og variablerne. Disse inkluderer:

  • Et udsagnsobjekt med mange specialiserede underklasser, der repræsenterer parsede udsagn
  • Et udtryk objekt til at repræsentere udtryk til evaluering
  • Et variabelt objekt med mange specialiserede underklasser, der repræsenterer atomforekomster af data
$config[zx-auto] not found$config[zx-overlay] not found