Notat 3: Sammensætning af oversættere og fortolkere vha. T-diagrammer

© 2000, Henning Christiansen

T-diagrammer

T-diagrammer (Earley, Sturgis, 1970; Bratman, 1961) er en grafisk notation til at beskrive systemer sammensat af oversættere og fortolkere, som ellers kan være svære at hitte hovede og hale i. I dette notat indføres notation kort med henblik på at beskrive de sproglige lag og sammensætninger af dem, som optræder i (Tanenbaum, 1999), kapitel 4 om mikroprogrammering; for en mere grundig beskrivelse af T-diagrammer henvises til (Earley, Sturgis, 1970). Notationen kan forstås som en slags dominospil, hvor hver brik repræsenterer et program eller en »primitiv« fortolker. I figuren nedenfor gengiver de forskellige typer af brikker. Den første slags repræsenterer applikationsprogrammer, som implementerer en eller anden funktionalitet f, og som er skrevet i et sprog S. Funktionaliteten i det, vi kalder applikationsprogrammer fremgår ikke nærmere af den grafiske notation, men nogle typer programmer har en særlig status, nemlig oversættere og fortolkere, jvf. figuren.

Vi har to slags primitive fortolkere, fysiske processorer, som fremstår ved en trekant, og abstrakte maskiner, som vi betragter som kanoniske. At en abstrakt maskine er kanonisk betyder, at vi betragter den som havende en veldefineret semantik, som vi ikke ønsker at analysere nærmere i den aktuelle sammenhæng. Når vi f.eks. betragter definerende fortolkere (Christiansen, 2000; afsnit 4.4.2) skrevet i Prolog, opfatter vi Prolog som værende kanonisk. Brikkerne bygges sammen til strukturer, således at sider, som støder mod hinanden er navngivet med samme sprog, jvf. eksemplerne nedenfor. Hvis en struktur når er »afsluttet i bunden« med trekanter, betyder det at alle indgående programmer (incl. eventuelle applikationsprogrammer) kan observeres at være kørende som virtuelle maskiner. Hvis en struktur afsluttes i bunden med otte-kanter betyder det, at alle indgående programmers funktionalitet modtager en definition (og kan ydermere observeres at være kørende som virtuelle maskiner, såfremt de indgående kanoniske sprog/maskiner har denne egenskab). Otte-kanten for de kanoniske sprop/abstrakte maskiner er vor egen opfindelse, men ellers er notationen som beskrevet hos (Earley, Sturgis, 1970).

T-diagrammer for definerende fortolkere og oversūttere m.v.

I nedenstående figur er illustreret definerende fortolkere for Mini-stak-og-variabel-maskinen(s sprog) og for while-sproget beskrevet i (Christiansen, 2000), kap. 6. T'et svarer til oversætteren fra while-programmer til sekvenser af instruktioner til Mini-stak-og-variabel-maskinen. Det sammensatte diagram viser hvordan et givet applikationsprogram er implementeret; sammenlign med (Christiansen, 2000) side 98.

T-diagrammer i (og over) Tanenbaums mikroarkitektur

Figuren nedenfor har til formål at fremvise de sproglige lag, som optræder, når et givet applikationsprogram skrevet i Java udføres på en maskine baseret på Tanenbaums Mic-1-maskine. Applikationsprogrammet fremstår som en champignon, hvor der står »App« på hovedet (svarende til en eller anden funktionalitet) og »Java« på stokken for at indikere, at der er tale om et program skrevet i Java.

Først oversættes applikationsprogrammet til et såkaldt assemblersprog, kaldet IJVM-asm, som er lagt oven på sproget bestående af IJVM-instruktioner. Der findes en god dansk betegnelse, som beskriver »assemblersprog« meget præcist: »symbolsk maskinsprog«. Der er, om man så må sige, lagt et syntaktiske sukkerlag af (nogenlunde) sigende koder i bogstaver og tal, ligesom der kan arbejdes med symbolske etiketter. Resultatat af oversættelsen er nu en oversættelse, som repræsenterer selvsamme funktionalitet, men nu i form af et program skrevet i IJVM-asm.

Dette IJVM-asm-program køres nu gennem nok en oversætter (2. T fra venstre), en såkaldt assembler, som producerer en binært program — i det sprog, vi kalder IJVM-binær — som stadig repræsenterer »App«.

Dette binære program fortolkes nu af den fortolker for IJVM-binær, som fremgår af Tanenbaums figur 4-17, side 234-236. Teksten er lidt utydelig i scanningen, men det burde fremgå, at der er tale om en fortolker for IJVM-binær skrevet i (dvs. foreligger som et program i) Mic-1-asm, som er det symbolske maskinsprog (assemblersprog) Tanenbaum har lagt ovenpå det binære Mic-1-maskinsprog, dvs. det binære mikroprogrammeringssprog.

For at fuldende virtualiseringen af vores oprindelige applikationsprogram, er vi nødt til først at oversætte bemeldte fortolker til binære Mic-1-maskinsprog (Mac-1 binær) — og det kan endeligt fortolkes af den fysiske Mic-1-arkitektur, der fremstår her som en trekant »Mic-1« (og som svarer til Tanenbaums figur 4-6, side 214). Sammensætningen af de to fortolkere yderst til højre er således istand til at fortolke vor applikation, der forelå som et program i IJVM-binær (champignonen, som er »parallelforskudt« til det øverste højre hjørne af figuren).

Vi har ikke taget nærmere stilling til, hvilket sprog de tre oversættere måtte være skrevet i, og hvilken fysiske maskine, de måtte være realiseret af i den sidste ende. Oversætterne kunne f.eks. være skrevet i Java, og den fysiske maskine kunne vūre Mic-1. (Interesserede læsere kan overveje at fylde detaljerne på tegningen).

Litteratur

Bratman, H., An alternate form of “UNCOL diagram” Communications of the ACM, vol. 4, no. 3. s. 142, 1961.

Christiansen, H., Sprog og abstrakte maskiner, 3. rev. udgave, Datalogiske Noter 18, Roskilde Universitetscenter, Datalogiafd., 2000.

Earley, J., Sturgis, H., A formalism for translator interaction, Communications of the ACM, vol. 13, no. 10. s. 607-616, 1970.

Tanenbaum, A.S., Structured Computer Organization, Fourth edition Prentice-Hall, 1999.


Henning Christiansen, 22. februar 2000