De vertaler diagnosticeert meestal ook fouten, stelt identificatiewoordenboeken samen, produceert programmateksten voor afdrukken, enz.

Uitzending van het programma- transformatie van een programma gepresenteerd in een van de programmeertalen naar een programma in een andere taal en, in zekere zin, gelijkwaardig aan de eerste.

De taal waarin het invoerprogramma wordt gepresenteerd, wordt aangeroepen originele taal, en het programma zelf - broncode. De uitvoertaal wordt aangeroepen doel taal of voorwerp code.

Het concept van vertaling is niet alleen van toepassing op programmeertalen, maar ook op andere computertalen, zoals opmaaktalen, vergelijkbaar met HTML, en natuurlijke talen, zoals Engels of Russisch. Dit artikel gaat echter alleen over programmeertalen; voor natuurlijke talen, zie: Vertaling.

Soorten vertalers

• Adres. Functioneel apparaat, dat het virtuele adres (virtueel adres) omzet in een echt geheugenadres (geheugenadres).
• Dialoog. Biedt het gebruik van een programmeertaal in time-sharing-modus.
• Multi-pass. Vormt een objectmodule over verschillende weergaven van het bronprogramma.
• Rug. Hetzelfde als devertaler. Zie ook: decompiler, disassembler.
• Enkele pas. Vormt een objectmodule in één opeenvolgende weergave van het bronprogramma.
• Optimaliseren. Voert code-optimalisatie uit in de gegenereerde objectmodule.
• Syntactisch georiënteerd (syntactisch gestuurd). Ontvangt als invoer een beschrijving van de syntaxis en semantiek van de taal en tekst in de beschreven taal, die wordt vertaald in overeenstemming met de gegeven beschrijving.
• Test. Een set assembleertaalmacro's waarmee u verschillende foutopsporingsprocedures kunt instellen in programma's die in assembleertaal zijn geschreven.

Implementaties

Het doel van vertalen is om tekst van de ene taal naar de andere om te zetten, wat begrijpelijk is voor de ontvanger van de tekst. Bij vertaalprogramma's is de geadresseerde een technisch apparaat (processor) of tolkprogramma.

Er zijn een aantal andere voorbeelden waarin de architectuur van de ontwikkelde reeks computers gebaseerd was op of sterk afhankelijk was van een bepaald model van programmastructuur. Zo was de GE/Honeywell Multics-serie gebaseerd semantisch model uitvoering van programma's geschreven in de PL/1-taal. In B5500, B6700 ... B7800 was gebaseerd op een model van een runtime-programma geschreven in de uitgebreide ALGOL-taal. ...

De i432-processor is, net als deze eerdere architecturen, ook gebaseerd op een semantisch model van programmastructuur. In tegenstelling tot zijn voorgangers is de i432 echter niet gebaseerd op een specifiek programmeertaalmodel. In plaats daarvan was het belangrijkste doel van de ontwikkelaars om voor beide directe runtime-ondersteuning te bieden abstracte gegevens(dat wil zeggen programmeren met abstracte gegevenstypen), en voor domeinspecifieke besturingssystemen. …

Het voordeel van de compiler: het programma wordt één keer gecompileerd en er zijn geen extra transformaties nodig elke keer dat het wordt uitgevoerd. Dienovereenkomstig is er geen compiler vereist op de doelmachine waarvoor het programma is gecompileerd. Nadeel: een aparte compilatiestap vertraagt ​​het schrijven en debuggen en maakt het moeilijk om kleine, eenvoudige of eenmalige programma's uit te voeren.

Als de brontaal een assembleertaal is (een taal op laag niveau die dicht bij machinetaal ligt), wordt de compiler van zo'n taal genoemd assembler.

De tegenovergestelde implementatiemethode is wanneer het programma wordt uitgevoerd met behulp van tolk helemaal geen uitzending. De interpreter modelleert programmatisch een machine waarvan de ophaal-uitvoeringscyclus werkt met opdrachten in talen hoog niveau, en niet met machineopdrachten. Dit software-modellering creëert een virtuele machine die de taal implementeert. Deze aanpak heet zuivere interpretatie. Pure interpretatie wordt meestal gebruikt voor talen met een eenvoudige structuur (bijvoorbeeld APL of Lisp). Commandoregeltolken verwerken opdrachten in scripts in UNIX of in batchbestanden (.bat) in MS-DOS, meestal ook in pure interpretatiemodus.

Het voordeel van een pure tolk: de afwezigheid van tussenliggende acties voor vertaling vereenvoudigt de implementatie van de tolk en maakt deze handiger in gebruik, ook in dialoogmodus. Het nadeel is dat er een tolk aanwezig moet zijn op de doelmachine waarop het programma moet worden uitgevoerd. En de eigenschap van een pure tolk, dat fouten in het geïnterpreteerde programma alleen worden gedetecteerd als er wordt geprobeerd een opdracht (of regel) met een fout uit te voeren, kan zowel als een nadeel als als een voordeel worden beschouwd.

Er zijn compromissen tussen compilatie en pure interpretatie bij de implementatie van programmeertalen, wanneer de tolk, voordat hij het programma uitvoert, het vertaalt naar een tussentaal (bijvoorbeeld in bytecode of p-code), handiger voor interpretatie (dat wil zeggen: we hebben het over een tolk met ingebouwde vertaler). Deze methode heet gemengde uitvoering. Een voorbeeld van een gemengde taalimplementatie is Perl. Deze aanpak combineert zowel de voordelen van een compiler en tolk (grotere uitvoeringssnelheid en gebruiksgemak) als nadelen (vertaling en opslag van een programma in een tussenliggende taal vereist extra middelen; Er moet een tolk aanwezig zijn om het programma op de doelcomputer uit te voeren.) Ook vereist een gemengde implementatie, net als bij de compiler, dat voordat deze wordt uitgevoerd bron bevatte geen fouten (lexicaal, syntactisch en semantisch).

Met de toename van computerbronnen en de uitbreiding van heterogene netwerken (waaronder het internet) die computers van verschillende typen en architecturen met elkaar verbinden, is er een nieuw type interpretatie ontstaan, waarbij de broncode (of tussencode) direct tijdens runtime in machinecode wordt gecompileerd. , “terloops.” Reeds gecompileerde codegedeelten worden in de cache opgeslagen, zodat ze, wanneer ze opnieuw worden geopend, onmiddellijk controle krijgen, zonder hercompilatie. Deze aanpak heet dynamische compilatie.

Het voordeel van dynamische compilatie is dat de snelheid van programma-interpretatie vergelijkbaar wordt met de snelheid van programma-uitvoering in conventionele gecompileerde talen, terwijl het programma zelf in één enkele vorm wordt opgeslagen en gedistribueerd, onafhankelijk van de doelplatforms. Het nadeel is de grotere complexiteit van de implementatie en grotere middelenvereisten dan in het geval van eenvoudige compilers of zuivere tolken.

Deze methode werkt goed voor

Stuur uw goede werk naar de kennisbank is eenvoudig. Gebruik onderstaand formulier

Goed werk naar de site">

Studenten, promovendi en jonge wetenschappers die de kennisbasis gebruiken in hun studie en werk zullen je zeer dankbaar zijn.

Geplaatst op http://www.allbest.ru

Invoering

1.1 Top-down analyse

1.2 Bottom-upanalyse

1.2.1 LR(k) - grammatica's

1.2.1.1 LR(0) - grammatica's

1.2.2 LALR(1) - grammatica's

2. Ontwikkeling van vertalers

2.1 Analyse van eisen

2.2 Ontwerp

2.2.1 Een lexicale analysator ontwerpen

2.2.4 Software-implementatie van de parser

2.3 Codering

2.4 Testen

Conclusie

Lijst met gebruikte bronnen

Bijlage A. Lijst met tekst van het vertaalprogramma

Bijlage B. Testresultaten

Bijlage B. Vertalerprogrammaschema

Invoering

De tijd dat je, voordat je een programma schreef, tientallen machine-instructies moest begrijpen en onthouden, is al lang voorbij. Moderne programmeur formuleert haar taken in programmeertalen op hoog niveau en gebruikt slechts in uitzonderlijke gevallen assembleertaal. Zoals bekend komen algoritmische talen pas beschikbaar voor de programmeur nadat er vertalers uit deze talen zijn gemaakt.

Programmeertalen verschillen nogal van elkaar qua doel, structuur, semantische complexiteit en implementatiemethoden. Dit legt zijn eigen specifieke kenmerken op aan de ontwikkeling van specifieke vertalers.

Programmeertalen zijn hulpmiddelen voor het oplossen van problemen op verschillende vakgebieden, wat de specifieke kenmerken van hun organisatie en de verschillen in doel bepaalt. Voorbeelden hiervan zijn talen als Fortran, dat gericht is op wetenschappelijke berekeningen, C, dat bedoeld is voor systeemprogrammering, Prolog, dat inferentieproblemen effectief beschrijft, en Lisp, dat wordt gebruikt voor recursieve lijstverwerking. Deze voorbeelden kunnen worden voortgezet. Elk vakgebied stelt zijn eigen eisen aan de organisatie van de taal zelf. Daarom kunnen we de verscheidenheid aan representatievormen van operatoren en uitdrukkingen opmerken, het verschil in de set basisbewerkingen, vermindering van de programmeerefficiëntie bij het oplossen van problemen die geen verband houden met het vakgebied. Taalkundige verschillen komen ook tot uiting in de structuur van vertalers. Lisp en Prolog worden meestal uitgevoerd in de interpretatiemodus vanwege het feit dat ze tijdens berekeningen gebruik maken van dynamische generatie van gegevenstypen. Fortran-vertalers worden gekenmerkt door agressieve optimalisatie van de resulterende machinecode, wat mogelijk wordt vanwege de relatief eenvoudige semantiek van taalconstructies - in het bijzonder vanwege de afwezigheid van mechanismen voor alternatieve naamgeving van variabelen door middel van pointers of referenties. De aanwezigheid van pointers in de C-taal stelt specifieke eisen aan dynamische distributie geheugen.

De structuur van een taal karakteriseert de hiërarchische relaties tussen de concepten ervan, die worden beschreven door syntactische regels. Programmeertalen kunnen sterk van elkaar verschillen in de organisatie van individuele concepten en de relaties daartussen. De programmeertaal PL/1 maakt het willekeurig nesten van procedures en functies mogelijk, terwijl in C alle functies zich op het buitenste nestniveau moeten bevinden. Met de taal C++ kunnen variabelen op elk punt in het programma worden gedefinieerd vóór het eerste gebruik ervan, en in Pascal moeten variabelen worden gedefinieerd in speciaal gebied beschrijvingen. Een nog verdergaande ontwikkeling is PL/1, waarmee een variabele kan worden gedeclareerd nadat deze is gebruikt. Of u kunt de beschrijving helemaal weglaten en de standaardregels gebruiken. Afhankelijk van de genomen beslissing kan de vertaler het programma in één of meerdere passages analyseren, wat de vertaalsnelheid beïnvloedt.

De semantiek van programmeertalen varieert sterk. Ze verschillen niet alleen in de implementatiekenmerken van individuele operaties, maar ook in programmeerparadigma's, die fundamentele verschillen in programma-ontwikkelmethoden bepalen. De bijzonderheden van de implementatie van operaties kunnen zowel betrekking hebben op de structuur van de gegevens die worden verwerkt als op de regels voor het verwerken van dezelfde soorten gegevens. Talen zoals PL/1 en APL ondersteunen matrix- en vectorbewerkingen. De meeste talen werken voornamelijk met scalairen en bieden procedures en functies die door programmeurs zijn geschreven voor het verwerken van arrays. Maar zelfs bij het uitvoeren van de bewerking van het optellen van twee gehele getallen, kunnen talen als C en Pascal zich anders gedragen.

Naast traditioneel procedureel programmeren, ook wel imperatief genoemd, bestaan ​​er paradigma's als functioneel programmeren, logisch programmeren en objectgeoriënteerd programmeren. De structuur van concepten en objecten van talen hangt sterk af van het gekozen paradigma, dat ook de implementatie van de vertaler beïnvloedt.

Zelfs dezelfde taal kan op verschillende manieren worden geïmplementeerd. Dit komt door het feit dat de theorie van formele grammatica's dit mogelijk maakt verschillende methoden dezelfde zinnen ontleden. In overeenstemming hiermee kunnen vertalers op verschillende manieren hetzelfde resultaat (objectprogramma) uit de originele brontekst verkrijgen.

Tegelijkertijd hebben alle programmeertalen er een aantal algemene karakteristieken en parameters. Deze gemeenschappelijkheid bepaalt ook de principes van het organiseren van vertalers die voor alle talen vergelijkbaar zijn.

Programmeertalen zijn ontworpen om het programmeren eenvoudiger te maken. Daarom zijn hun operators en datastructuren krachtiger dan die in machinetalen.

Om de zichtbaarheid van programma's te vergroten, worden in plaats van numerieke codes symbolische of grafische representaties van taalconstructies gebruikt, die handiger zijn voor menselijke perceptie.

Voor elke taal is het gedefinieerd:

- veel symbolen die kunnen worden gebruikt om correcte programma's te schrijven (alfabet), basiselementen,

- veel correcte programma's (syntaxis),

- de “betekenis” van elk correct programma (semantiek).

Ongeacht de specifieke kenmerken van de taal kan elke vertaler worden beschouwd als een functionele converter F, die een unieke mapping van X naar Y biedt, waarbij X een programma in de brontaal is en Y een programma in de uitvoertaal. Daarom kan het vertaalproces zelf formeel vrij eenvoudig en duidelijk worden weergegeven: Y = F(X).

Formeel, elk juiste programma X is een reeks tekens uit een bepaald alfabet A, omgezet in de overeenkomstige reeks Y, samengesteld uit tekens uit het alfabet B.

Een programmeertaal zoals elke andere een complex systeem, wordt gedefinieerd door een hiërarchie van concepten die de relaties tussen de elementen definieert. Deze concepten zijn met elkaar verbonden volgens syntactische regels. Elk programma dat volgens deze regels is gebouwd, heeft een overeenkomstige hiërarchische structuur.

In dit opzicht kunnen bovendien de volgende gemeenschappelijke kenmerken worden onderscheiden voor alle talen en hun programma's: elke taal moet regels bevatten die het mogelijk maken programma's te genereren die overeenkomen met deze taal of de correspondentie tussen geschreven programma's en een bepaalde taal te herkennen.

Een ander kenmerkend kenmerk van alle talen is hun semantiek. Het bepaalt de betekenis van taalbewerkingen en de juistheid van de operanden. Ketens die dezelfde syntactische structuur hebben in verschillende programmeertalen kunnen qua semantiek verschillen (wat bijvoorbeeld wordt waargenomen in C++, Pascal, Basic). Kennis van de semantiek van een taal stelt u in staat deze te scheiden van de syntaxis ervan en deze te gebruiken voor conversie naar een andere taal (om code te genereren).

Het doel van dit cursuswerk is om een ​​educatieve vertaler te ontwikkelen vanuit een vereenvoudigd gegeven tekst taal hoog niveau.

1. Methoden voor grammatica-analyse

Laten we eens kijken naar de basismethoden voor grammaticale ontleding.

1.1 Top-down analyse

Bij het ontleden van boven naar beneden bewegen tussenliggende leads langs de boom in de richting van de wortel naar de bladeren. In dit geval zullen, wanneer de keten van links naar rechts wordt bekeken, uiteraard linkshandige conclusies worden getrokken. Bij deterministisch parseren zal het probleem zijn welke regel moet worden toegepast om de meest linkse niet-terminal op te lossen.

1.1.1 LL(k) - talen en grammatica's

Beschouw de gevolgtrekkingsboom tijdens het verkrijgen van de linkeruitvoer van de keten. De tussenliggende keten in het inferentieproces bestaat uit een keten van terminals w, de meest linkse niet-terminale A, het ondergeconcludeerde deel x:

-S--

/ \

/ -A-x-\

/ | \

-w---u----

Figuur 1

Om door te gaan met parseren, is het noodzakelijk om de niet-terminale A te vervangen volgens een van de regels van de vorm A:y. Als u wilt dat de parsering deterministisch is (geen rendement), moet deze regel worden geselecteerd op een bijzondere manier. Er wordt gezegd dat een grammatica de eigenschap LL(k) heeft als het, om een ​​regel te selecteren, voldoende is om alleen wAx en de eerste k tekens van de niet-onderzochte string u te beschouwen. De eerste letter L (links) verwijst naar het bekijken van de invoerketen van links naar rechts, de tweede verwijst naar de linkeruitvoer die wordt gebruikt.

Laten we twee sets ketens definiëren:

a) FIRST(x) is de set terminalstrings afgeleid van x, afgekort tot k-tekens.

b) FOLLOW(A) - een set eindketens ingekort tot k karakters, die A onmiddellijk kunnen volgen in de uitvoerketens.

Een grammatica heeft de eigenschap LL(k) als, op grond van het bestaan ​​van twee ketens van linkse gevolgtrekkingen:

S:: wAx: wzx:: wu

S:: wAx: wtx:: wv

uit de voorwaarde FIRST(u)=FIRST(v) volgt z=t.

In het geval van k=1 is het, om een ​​regel voor A te kiezen, voldoende om alleen de niet-terminale A en a te kennen - het eerste teken van de keten u:

- regel A:x moet worden geselecteerd als a is opgenomen in FIRST(x),

- regel A:e moet worden geselecteerd als a is opgenomen in FOLLOW(A).

De eigenschap LL(k) legt behoorlijk strenge beperkingen op aan de grammatica. Bijvoorbeeld LL(2) grammatica S: aS | a heeft niet de eigenschap LL(1), omdat EERSTE(aS)=EERSTE(a)=a. In dit geval kunt u de waarde van k verminderen met behulp van “factorisatie” (de factor tussen haakjes plaatsen):

S: aA

A: S | e

Elke LL(k)-grammatica is ondubbelzinnig. Een links-recursieve grammatica behoort voor geen enkele k tot de klasse LL(k). Soms is het mogelijk om een ​​niet-LL(1)-grammatica om te zetten in een gelijkwaardige LL(1)-grammatica door linkse recursie en factorisatie te elimineren. Het probleem van het bestaan ​​van een equivalente LL(k)-grammatica voor een willekeurige niet-LL(k)-grammatica is echter onbeslisbaar.

1.1.2 Recursieve afdalingsmethode

De recursieve afdalingsmethode is gericht op die gevallen waarin de compiler is geprogrammeerd in een van de talen op hoog niveau, waarbij het gebruik van recursieve procedures is toegestaan.

Het belangrijkste idee van recursieve afkomst is dat elke niet-terminale van de grammatica een overeenkomstige procedure heeft die elke keten herkent die door deze niet-terminal wordt gegenereerd. Deze procedures bellen elkaar wanneer dat nodig is.

Recursieve afstamming kan voor elke LL(1)-grammatica worden gebruikt. Elke niet-terminal van de grammatica heeft een overeenkomstige procedure, die begint met een overgang naar het berekende label en code bevat die overeenkomt met elke regel voor deze niet-terminal. Voor die invoersymbolen die tot de selectieset van een bepaalde regel behoren, draagt ​​de berekende transitie de controle over aan de code die overeenkomt met die regel. Voor de overige invoersymbolen wordt de besturing overgedragen naar de foutafhandelingsprocedure.

De code van elke regel bevat bewerkingen voor elk teken dat is opgenomen in rechter zijde reglement. De bewerkingen zijn gerangschikt in de volgorde waarin de symbolen in de regel voorkomen. Na de laatste bewerking bevat de code een return uit de procedure.

Het gebruik van recursieve afkomst in een taal op hoog niveau maakt programmeren en debuggen eenvoudiger.

1.2 Bottom-upanalyse

Laten we eens kijken naar bottom-up parsing, waarbij tussenliggende pinnen langs de boom naar de wortel worden verplaatst. Als je de tekens in de string van links naar rechts leest, ziet de ontleedboom er als volgt uit:

-S--

/ \

/-X-\

/ | \

--w--b--u-

Figuur 2

De tussenliggende uitvoer heeft de vorm xbu, waarbij x een keten van terminals en niet-terminals is, waaruit het bekeken deel van de terminalketen w wordt uitgevoerd, bu het niet-bekeken deel van de terminalketen is en b het volgende symbool is. Om de analyse voort te zetten, kun je óf het teken b toevoegen aan het bekeken deel van de keten (een zogenaamde ‘shift’ uitvoeren), óf aan het einde van x zo’n keten z (x=yz) selecteren dat een van de regels van de grammatica B:z kunnen worden toegepast op z en x vervangen door keten yB (voer de zogenaamde “convolutie uit”):

-S-- -S--

/ \ / \

/-x-b-\ /yB-\

/ | \ / | \

--w--b--u- --w--b--u-

Figuur 3 - Na verschuiving Figuur 4 - Na convolutie

Als convolutie alleen wordt toegepast op laatste karakters x, dan ontvangen we de juiste uitgangen van de keten. Deze parsering wordt LR genoemd, waarbij het symbool L (links, links) verwijst naar het bekijken van de keten van links naar rechts, en R (rechts, rechts) verwijst naar de resulterende uitvoer.

De volgorde van de schuif- en vouwbewerkingen is essentieel. Daarom vereist deterministische parsering op elk moment een keuze tussen verschuiving en convolutie (en verschillende convolutieregels).

1.2.1 LR(k) - grammatica's

Als het tijdens het LR-parseren mogelijk is om een ​​deterministische beslissing te nemen over verschuiving/reductie, waarbij alleen de string x en de eerste k-tekens van het onzichtbare deel van de invoertekenreeks u in aanmerking worden genomen (deze k-tekens worden de voortgangsreeks genoemd ), zou de grammatica de eigenschap LR(k) hebben.

-S--

/ \

/-X-\

--w----u--

Figuur 5

Het verschil tussen LL(k)- en LR(k)-grammatica's in termen van een gevolgtrekkingsboom:

-S-

/ | \

/A\

/ / \ \

-w---v---u-

Figuur 6

In het geval van LL(k)-grammatica's kan de regel die op A wordt toegepast uniek worden bepaald door w en de eerste k-tekens van vu, en in het geval van LR(k)-grammatica's door w,v en de eerste k karakters van u. Deze niet-rigoureuze redenering toont aan dat LL(k)-talen< LR(k)-языки (при k > 0).

1.2.1.1 LR(0) - grammatica's

Laten we eerst de eenvoudigste grammatica's van deze klasse bekijken: LR(0). Bij het parseren van een string in een LR(0)-taal hoeft u de voortgangsketen helemaal niet te gebruiken; de keuze tussen shift en fold wordt gemaakt op basis van de keten x. Omdat het tijdens het parseren alleen vanaf de rechterkant verandert, wordt het een stapel genoemd. Laten we aannemen dat er geen nutteloze symbolen in de grammatica voorkomen en dat het initiële symbool niet aan de rechterkant van de regels verschijnt - dan geeft convolutie naar het initiële symbool de succesvolle voltooiing van het parseren aan. Laten we proberen de reeks ketens van terminals en niet-terminals te beschrijven die op de stapel verschijnen tijdens alle LR-parsing (met andere woorden, alle rechtse gevolgtrekkingen uit de grammatica).

Laten we de volgende sets definiëren:

L(A:v) - linkercontext van regel A:v - set stapelstatussen onmiddellijk voordat v in A wordt gevouwen tijdens alle succesvolle LR-parses. Het is duidelijk dat elke keten in L(A:v) eindigt op v. Als de staart v van al dergelijke ketens wordt afgesneden, krijgen we de reeks ketens die zich links van A voordoen tijdens alle succesvolle rechtse gevolgtrekkingen. Laten we deze verzameling aanduiden als L(A) - de linkercontext van de niet-terminale A.

Laten we een grammatica construeren voor de verzameling L(A). De terminals van de nieuwe grammatica zullen de terminals en niet-terminals van de oorspronkelijke grammatica zijn; de niet-terminals van de nieuwe grammatica zullen worden aangegeven met ,... - hun waarden zullen de linkercontexten zijn van de niet-terminals van de originele grammatica. Als S het initiële symbool is van de originele grammatica, dan zal de grammatica van de linkercontext de regel bevatten : e - de linkercontext S bevat een lege keten. Voor elke regel van de oorspronkelijke grammatica, bijvoorbeeld A: B C d E

en regels toevoegen aan de nieuwe grammatica:

: - L(B) omvat L(A)

: B - L(C) omvat L(A) B

: B C d - L(E) omvat L(A) B C d

De resulterende grammatica heeft speciaal type(dergelijke grammatica's worden linkslineair genoemd), daarom sets van linkse contexten

- normaal. Hieruit volgt dat of een string tot de linkercontext van een niet-terminal behoort, inductief kan worden berekend met behulp van een eindige toestandsmachine, die de string van links naar rechts scant. Laten we dit proces constructief beschrijven.

Laten we een LR(0)-situatie een grammaticaregel noemen met één gemarkeerde positie tussen de symbolen aan de rechterkant van de regel. Voor de grammatica S:A; A:aAA; A:b De volgende LR(0)-situaties bestaan: S:_A; S:A_; A:_aAA; A:a_AA; A:aA_A; A:aAA_; EEN:_b; EEN:b_. (positie wordt aangegeven met een onderstrepingsteken).

We zullen zeggen dat de keten x consistent is met de situatie A:b_c als x=ab en a tot L(A) behoort. (Met andere woorden, de LR-uitvoer kan worden voortgezet x_... = ab_...:: abc_...:: aA_...:: S_.) In deze termen is L(A:b) de verzameling aantal strings consistent met situatie A:b_, L(A)

- kettingen die consistent zijn met situatie A:_b, voor elke regel A:b.

Laat V(u) de verzameling situaties zijn die consistent zijn met u. Laten we aantonen dat de functie V inductief is.

Als de verzameling V(u) de situatie A:b_cd omvat, dan behoort de situatie A:bc_d tot V(uc). (c - terminaal of niet-terminal; b, d - reeksen (mag leeg zijn) van terminals en niet-terminals). Er zijn geen andere situaties van de vorm A:b_d, met niet-lege b in V(uc). Rest ons nog situaties van de vorm C:_... toe te voegen aan V(uc), voor elke niet-terminale C waarvan de linkercontext uc bevat. Als situatie A:..._C... (C-nonterminaal) tot de verzameling V(uc) behoort, dan behoort uc tot L(C) en omvat V(uc) situaties van de vorm C:_... voor alle C-grammaticaregels.

V(e) bevat situaties S:_... (S-beginteken), evenals situaties A:_... als de niet-terminale A onmiddellijk na _ voorkomt in situaties die al in V(e) zijn opgenomen.

Eindelijk zijn we klaar om een ​​LR(0)-grammatica te definiëren. Laat u de inhoud van de stapel zijn tijdens het parseren van LR, en V(u) de verzameling LR(0)-situaties die consistent zijn met u. Als V(u) een situatie bevat van de vorm A:x_ (x-reeks van terminals en niet-terminals), dan behoort u tot L(A:x) en is de convolutie van x naar A toegestaan. ) de situatie A:..._a. .. (a-terminal) bevat, dan is een verschuiving toegestaan. Er wordt gezegd dat er sprake is van een shift-convolutieconflict als zowel shift als convolutie zijn toegestaan ​​voor dezelfde string u. Er is sprake van een convolutie-reductieconflict als convoluties volgens verschillende regels zijn toegestaan.

Een grammatica wordt LR(0) genoemd als er geen shift-reduce- of fold-reduce-conflicten zijn voor alle stapeltoestanden tijdens LR-inferentie.

1.2.1.2 LR(k) - grammatica's

Alleen de status van de stapel wordt gebruikt om te beslissen tussen verschuiven en vouwen bij LR(0)-parsing. LR(k)-parsing houdt ook rekening met de eerste k tekens van het onzichtbare deel van de invoerketen (de zogenaamde voortgangsketen). Om de methode te rechtvaardigen, moet u de redenering van de vorige paragraaf zorgvuldig herhalen en wijzigingen aanbrengen in de definities.

We zullen ook een voortgangsketen opnemen in de linkercontext van de regels. Als de rechter uitgang de uitgang wAu: wvu gebruikt, dan behoort het paar wv,FIRSTk(u) tot Lk(A:v), en het paar w,FIRSTk(u) tot Lk(A). De set linkercontexten, zoals in het geval van LR(0), kan worden berekend met behulp van inductie op de linkerketen. Laten we een LR(k)-situatie een paar noemen: een grammaticaregel met een gemarkeerde positie en een voortbewegingsketen met een lengte van maximaal k. We scheiden de regel van de voortgangsketen met een verticale lijn.

We zullen zeggen dat de keten x consistent is met de situatie A:b_c|t als er een LR-uitvoer is: x_yz = ab_yz:: abc_z:: aA_z:: S_, en FIRSTk(z) = t. De regels voor het inductief berekenen van de reeks toestanden Vk zijn als volgt:

Vk(e) bevat situaties S:_a|e voor alle regels S:a, waarbij S het startteken is. Voor elke situatie A:_Ba|u uit Vk(e), elke regel B:b en keten x die tot FIRSTk(au) behoort, is het noodzakelijk om situatie B:_b|x toe te voegen aan Vk(e).

Als Vк(w) de situatie A:b_cd|u omvat, dan behoort de situatie A:bc_d|u tot Vk(wc). Voor elke situatie A:b_Cd|u uit Vk(wc), elke regel C:f en keten x behorend tot FIRSTk(du) is het noodzakelijk om situatie C:_f|x toe te voegen aan Vk(wc).

We gebruiken de geconstrueerde sets van LR(k)-toestanden om het shift-convolutieprobleem op te lossen. Laat u de inhoud van de stapel zijn en x de upchain. Uiteraard kan convolutie volgens regel A:b worden uitgevoerd als Vk(u) de situatie A:b_|x bevat. Het beslissen of een verschuiving toelaatbaar is, vereist zorgvuldigheid als de grammatica e-regels bevat. In de situatie A:b_c|t (c is niet leeg) is een verschuiving mogelijk als c begint vanaf een terminal en x tot FIRSTk(ct behoort). Informeel gesproken kunt u het meest linkse symbool van de rechterkant van de regel op de stapel schuiven, waardoor de daaropvolgende convolutie wordt voorbereid. Als c begint met een niet-terminal (de situatie lijkt op A:b_Cd|t), dan is het alleen mogelijk om een ​​symbool op de stapel te plaatsen ter voorbereiding op convolutie naar C als C geen lege keten genereert. Bijvoorbeeld in de toestand V(e)= S:_A|e; A:_AaAb|e,a, A:_|e,a er zijn geen toegestane verschuivingen, omdat Bij het afleiden van terminale ketens van A, is het op een gegeven moment vereist om de regel A:e toe te passen op de niet-terminale A die zich aan het linkeruiteinde van de keten bevindt.

Laten we de verzameling EFFk(x) definiëren, bestaande uit alle elementen van de verzameling FIRSTk(x), waarbij bij de afleiding de niet-terminal aan het linkeruiteinde van x (als die er is) niet wordt vervangen door een lege keten. In deze termen is een verschuiving toegestaan ​​als er in de verzameling Vk(u) sprake is van een situatie A:b_c|t, c niet leeg is en x tot EFFk(ct behoort).

Een grammatica wordt een LR(k)-grammatica genoemd als geen enkele LR(k)-toestand twee situaties A:b_|u en B:c_d|v bevat zodat u tot EFFk(dv) behoort. Zo'n paar komt overeen met een fold-reduce-conflict als d leeg is, en een shift-fold-conflict als d niet leeg is.

In de praktijk worden LR(k)-grammatica's niet gebruikt voor k>1. Hiervoor zijn twee redenen. Ten eerste: heel groot aantal LR(k)-toestanden. Ten tweede: voor elke taal die wordt gedefinieerd door een LR(k)-grammatica, bestaat er een LR(1)-grammatica; Bovendien bestaat er voor elke deterministische KS-taal een LR(1)-grammatica.

Het aantal LR(1)-toestanden voor praktisch interessante grammatica's is ook behoorlijk groot. Dergelijke grammatica's hebben zelden de eigenschap LR(0). In de praktijk wordt vaker een methode gebruikt die tussen LR(0) en LR(1) ligt, bekend als LALR(1).

1.2.2 LALR(1) - grammatica's

Deze twee methoden zijn gebaseerd op hetzelfde idee. Laten we een reeks canonieke LR(0)-toestanden van de grammatica construeren. Als deze set geen conflicten bevat, kan de LR(0)-parser worden gebruikt. Anders zullen we proberen de conflicten die zijn ontstaan ​​op te lossen door een voortgangsketen van één karakter te beschouwen. Met andere woorden, laten we proberen een LR(1)-parser te bouwen met veel LR(0)-toestanden.

De LALR(1)-methode (Look Ahead) is als volgt. Laten we een equivalentierelatie introduceren op de verzameling LR(1)-situaties: we zullen twee situaties als gelijkwaardig beschouwen als ze alleen verschillen in hun leidende ketens. De situaties A:Aa_Ab|e en A:Aa_Ab|a zijn bijvoorbeeld gelijkwaardig. Laten we een canonieke reeks LR(1)-toestanden construeren en de toestanden combineren die bestaan ​​uit een reeks equivalente situaties.

Als de resulterende reeks toestanden geen LR(1)-conflicten bevat, en daarom de constructie van een LR(1)-parser toestaat, dan wordt gezegd dat de grammatica de eigenschap LALR(1) heeft.

2. Ontwikkeling van vertalers

2.1 Analyse van eisen

In deze cursus werk het is noodzakelijk om een ​​educatieve vertaler te ontwikkelen in de vorm van een tolk uit een taal die wordt gedefinieerd door de overeenkomstige formele grammatica. Er zijn vier hoofdfasen bij het ontwikkelen van een tolk:

Het ontwerpen van een lexicale analysator;

Ontwerp van een automaat;

Software-implementatie van de parser;

Ontwikkeling van een interpretatiemodule.

De ontwikkeling zal worden uitgevoerd met behulp van de operatiekamer Windows-systemen XP op een IBM-pc met Intel-processor Pentium IV.

Op basis van trends in softwareontwikkeling werd de programmeertaal C# in de Visual Studio 2010-omgeving gekozen om de educatieve vertaler te implementeren.

2.2 Ontwerp

2.1.1 Een lexicale analysator ontwerpen

Lexicaal analyse omvat het scannen van het vertaalde (bron)programma en het herkennen van de lexemen waaruit de zinnen van de brontekst bestaan. Tokens omvatten met name trefwoorden, bewerkingstekens, identificatiegegevens, constanten, speciale tekens, enz.

Het resultaat van het werk van een lexicale analysator (scanner) is een reeks tokens, waarbij elk token gewoonlijk wordt weergegeven door een code met een vaste lengte (bijvoorbeeld een geheel getal), evenals het genereren van berichten over syntactische (lexicale) fouten , indien aanwezig. Als het token bijvoorbeeld een trefwoord is, geeft de code alle benodigde informatie. In het geval van bijvoorbeeld een identificator is bovendien de naam van de erkende identificator vereist, die doorgaans wordt vastgelegd in een tabel met identificatoren, die in de regel aan de hand van lijsten is georganiseerd. Voor constanten is een soortgelijke tabel nodig.

Een lexeme kan worden beschreven door twee hoofdkenmerken. Eén daarvan is of het lexeme tot een bepaalde klasse behoort (variabelen, constanten, bewerkingen, etc.). Het tweede attribuut bepaalt specifiek onderdeel van deze klasse.

De specifieke vorm van de symbooltabel (datastructuur) doet er niet toe voor de lexer of parser. Beiden hoeven alleen de mogelijkheid te bieden om een ​​index te verkrijgen die bijvoorbeeld een bepaalde variabele op unieke wijze identificeert en de indexwaarde terug te geven om informatie over een bepaalde variabelenaam in de symbooltabel aan te vullen.

Het bekijken van de ID-tabel heeft twee hoofdfuncties:

a) het opnemen van een nieuwe naam in de tabel bij het verwerken van variabelebeschrijvingen;

b) zoeken naar een naam die eerder in de tabel is opgenomen.

Hiermee kunt u foutieve situaties identificeren, zoals meerdere beschrijvingen van een variabele en de aanwezigheid van een onbeschreven variabele.

De ontwikkeling van een lexicale analysator bestaat gedeeltelijk uit het modelleren van verschillende automaten om identificatiegegevens, constanten, gereserveerde woorden, enz. te herkennen. Als tokens van verschillende typen met hetzelfde teken of dezelfde reeks tekens beginnen, kan het nodig zijn om hun herkenning te combineren.

Door de lexicale analysator uit te voeren, verdelen we ons programma in tokens, waarna elk token een lengtecontrole doorstaat (een token kan niet meer dan 11 tekens lang zijn). Nadat we deze fase met succes hebben voltooid, controleren we de juiste locatie van de tokens (trefwoorden var, begin, end, for, to, do, end_for). Vervolgens analyseren we variabele lexemen - ze mogen geen getallen bevatten in hun beschrijving en mogen niet worden herhaald. In de laatste fase controleren we de juiste spelling van lexemen ( trefwoorden, onbekende identificatiegegevens). Als ten minste één van de controles mislukt, drukt de lexicale analysator een fout af.

Het diagram van het lexicale analyseprogramma wordt weergegeven in bijlage B in figuur B.1.

2.2.2 Ontwerp van een automaat

Laten we de volgende grammatica definiëren:

G: (Vt, Va, I, R),

waarbij Vt de verzameling terminale symbolen is, Va de verzameling niet-terminale symbolen is, I de begintoestand van de grammatica is, en R de verzameling grammaticaregels is.

Voor deze grammatica definiëren we sets terminale en niet-terminale symbolen:

Laten we de regels voor onze grammatica G opstellen en deze in Tabel 1 presenteren.

Tabel 1 - Grammaticaregels

Regel nr.	Linkerkant van de regel	Rechterkant van de regel
		f ID = EX t EX d LE n;
Vervolg van tabel 1.
Regel nr.	Linkerkant van de regel	Rechterkant van de regel

De aanduidingen van lexemen, de vertaling van lexemen in codes en een lijst met grammaticale aanduidingen worden respectievelijk gegeven in tabellen 2, 3 en 4.

Tabel 2 - Benamingen van lexemen

	Token-aanduiding
	trefwoord “begin” (begin van de beschrijving van acties)
	trefwoord “einde” (beschrijving einde actie)
	trefwoord "var" (variabelebeschrijving)
	trefwoord "lezen" (operator voor gegevensinvoer)
	trefwoord "schrijven" (operator voor gegevensuitvoer)
	trefwoord "for" (lusinstructie)
	trefwoord "naar"
	trefwoord "doen"
	trefwoord "end_case" (einde-van-lus-instructie)
	variabel type "geheel getal"
	toevoeging operatie
	aftrekkingsoperatie
	vermenigvuldigingsoperatie
	scheidingsteken ´´
	scheidingsteken ";"
	scheidingsteken "("
	scheidingsteken ")"
	scheidingsteken ","
	Token-aanduiding
	scheidingsteken "="

Tabel 3 - Vertaling van lexemen in codes

<цифра>
<буква>

Tabel 4 - Lijst met grammaticasymbolen

Aanduiding	Uitleg
	Programma
	Beschrijving van berekeningen
	Beschrijving van variabelen
	Lijst met variabelen
	Exploitant
	Opdracht
	Uitdrukking
	Subexpressie
	Binaire operaties
	Unaire operaties
	Lijst met opdrachten
	Identificatie
	Constante

Laten we een deterministische bottom-up herkenner bouwen.

Beschouw de volgende relaties om een ​​deterministische bottom-up herkenner te construeren:

a) Als er een symbool van groep B bestaat, zodat een grammaticaregel de keten AB omvat en er een symbool xFIRST"(B) is, dan nemen we aan dat de relaties x NA A worden bepaald tussen de symbolen x en A

b) Als er in een bepaalde grammatica een regel B -> bAb A, BV a, b bestaat, dan wordt de relatie A COVER x bepaald tussen A en x.

Al onze grammatica blijft hetzelfde, dat wil zeggen:

G: (Vt, Va, I, R),

en de regels van grammatica G worden gegeven in Tabel 5.

Tabel 5 - Grammaticaregels

Regel nr.	Linkerkant van de regel	Rechterkant van de regel
		f ID = EX t EX d LE n;?
Vervolg van tabel 5.
Regel nr.	Linkerkant van de regel	Rechterkant van de regel

Waar? - markering voor het einde van de ketting.

Laten we enkele gevallen definiëren:

a) De ID bestaat uit vele letters van het Latijnse alfabet, dat wil zeggen dat we aannemen dat u = ( a, b, c, d, e, f,g, h, i,j,k, l,m, n , o, p,q,r,s, t, u, v, w, x, y, z)

b) De CO-constante bestaat uit getallen, dat wil zeggen dat we aannemen dat k = (0,1,2,3,4,5,6,7,8,9)

Wil onze grammatica een gemengde prioriteitsstrategie zijn, dan moet aan de volgende voorwaarden worden voldaan:

a) Gebrek aan e-regels

b) Zijn er regels op grond waarvan x NA A? EEN VERT x = ?

c) A -> bYg

en het is noodzakelijk dat IN NA x? B VERT x = ?

dat wil zeggen dat ze in de grammatica worden uitgevoerd IN NA x of A NA x, waarbij x het predikaatsymbool is van de keten b.

a) EERSTE"(PG)=(PG?)

EERSTE"(RG) = EERSTE(DE) = (RG, v,:, i,;)

EERSTE" (AL) = EERSTE (b LE e)= (AL, b, e)

EERSTE" (DE) = EERSTE (v LV: i;) = (DE, v,:, i,;)

EERSTE" (LV) = EERSTE (ID, LV) = (LV, ID)

EERSTE" (OP) =(OP, ID, CO)

EERSTE" (EQ) = EERSTE(ID = EX;) = (EQ, =,;)

EERSTE" (EX) = (EX, SB, -)

EERSTE" (BO) =(B0, +,*,-)

EERSTE" (SB) = EERSTE((EX)SB) ? EERSTE(OP) ? EERSTE(BO)=(SB, (,), OP, BO);

EERSTE" (LE) = EERSTE(EQ) = (LE, (,), =,;, f, t, d, n, w, r)

EERSTE" (UO) = (UO,-)

EERSTE" (ID)= EERSTE" (u) = (u)

EERSTE" (CO) = EERSTE" (k) = (k)EERSTE" (e) =( e)

EERSTE" (b) =( b)

EERSTE" (e) =( e)

EERSTE" (v) =( v)

EERSTE" (w) =( w)

EERSTE" (r) =( r)

EERSTE" (i) =( ik)

EERSTE" (f) =( f)

EERSTE" (d) =(d)

EERSTE" (n) =( n)

EERSTE" (c) =( c)

EERSTE" (+) =( +)

EERSTE" (*) =( *)

EERSTE" (-) =( -)

EERSTE" (,) =(,)

EERSTE" (;) =(;)

EERSTE" (:) =(:)

EERSTE" (=) = ( = )

EERSTE" (() =( ()

EERSTE" ()) =() )

EERSTE" (u) = (u)

EERSTE" (k) =(k)

b) TRACE `(AL) = (?)? TRACE"(PG)=(?,b,e)

VOLGENDE ` (DE) = (?)?FIRST"(AL)= (?, b, e)

VOLGENDE ` (LV) = (?)?EERSTE"(:)= (?,:)

VOLGENDE ` (OP) = (?)?FIRST"(SB)= (?,;,), d, t, +, -, *)

TRACK ` (EQ) = (?)?FIRST"(LE)=(?, (,),;, f, =, t, d, n,w,r )

TRACK ` (EX) = (?)?FIRST"(t)?FIRST"(d)?FIRST"(;)?FIRST"())=(?, t,d,;,))

VOLGENDE ` (BO) = (?)?FIRST"(SB)= (?, (,), OP, BO)

VOLGENDE ` (UO) = (?)?FIRST"(SB)= (?, (,), OP, BO)

TRACE ` (SB) = (?)? TRACE"(EX)= (?, t,d,;,), +, *, -)

TRACK ` (LE) = (?) ?FIRST"(e) ?FIRST"(n) = (?, e, n)

TRACE `(ID)= (?)? VOLGENDE" (OP) ? EERSTE" (=) =(?,;,), d, t, +, -, *, =)

TRACEER `(CO) = (?)? TRACE" (OP)= (?,;,), d, t, +, -, *, =)

VOLGENDE ` (b) =(?)?FIRST"(LE)= (?, u, =,;)

TRACE ` (e) =(?)? TRACE"(AL)= (?, b)

VOLGENDE ` (v) =(?)?EERSTE"(LV)= (?, u)

VOLGENDE ` (w) =(?)?EERSTE"(()= (?, ()

VOLGENDE ` (r) =(?)?EERSTE"(() = (?, ()

VOLGENDE ` (i) =(?)?EERSTE"(;)= (?,; )

VOLGENDE ` (f) =(?)?EERSTE"(ID) = (?, u)

VOLGENDE ` (d) =(?)?FIRST"(LE)= (?, u, =,;)

VOLGENDE ` (n) =(?)?EERSTE"(i) = (?, i )

TRACE ` (+) =(?)? TRACE"(IN) = (?, +,*,-)

TRACE ` (-) =(?)? TRACE"(IN) = (?, +,*,-)

TRACE ` (*) =(?)? TRACE"(IN) = (?, +,*,-)

TRACK ` (;) =(?)?TRACK" (DE)?TRACK `(LE1)?TRACK" (EQ) = (?, b, e, l, u)

VOLGENDE ` (:) =(?)?EERSTE"(i)= (?, i )

VOLGENDE ` (=) = (?)?FIRST"(EX) = (? (,), u, k, +, -, *)

VOLGENDE ` (() =(?)?FIRST"(DE)= (?, v,:, i,;)

TRACEER ` ()) =(?)? EERSTE"(;) = (?,; )

TRACEER ` (,) =(?)? EERSTE"(LV) = (?, u)

TRACEER `(u) =(?)? EERSTE" (ID)= ( u, ?)

TRACEER `(k) =(?)? EERSTE (CO)= (?, k)

c) PG ->DE AL

AL NA DE = (b,e) NA DE = ((b DE), (e DE) )

e NA LE = ((e LE))

LE NA b = ((,), =,;, f, t, d, n, w, r) NA b = (((b), ()b), (=b), (;b), ( f b), (t b), (d b), (n b), (w b), (r b))

;NA ik = ((; ik))

ik NA: = ( (ik:) )

: NA LV = ( (: LV) )

LV NA v = ((ID, v) )

LV NA, = ((ID,))

NA ID = ((,u))

LE NA EQ = ((,), =,;, f, t, d, n, w, r ) NA EQ = (((EQ), () EQ), (= EQ), (; EQ), ( f EQ), (t EQ), (d EQ), (n EQ), (w EQ), (r EQ))

LE -> r (DE);

; NA) = ((;)))

) NA DE = (((DE))

DE NA (= (= ((v)), (:)), (i)), (;)), (e)))

(NA r = (((r))

LE -> w (DE);

; NA) = ((;)))

) LAATSTE DE = (((DE))

DE NA (= ((v)), (:)), (i)), (;)), (e)))

(NA w = (((w))

LE -> f ID = EX t EX d LE n;

; NA n = ((;n))

n NA LE = ( (n, LE))

LE NA d = (((,), =,;, f, t, d, n, w, r)) ? NA d = (((d), ()d), (;d), (f d), (t d), (d d), (n d), (w d), (r d))

d NA EX = ((d, EX))

EX NA t = (BO, -) ? NA t = ((BO t), (- t))

t NA EX = ( t EX)

EX NA = = ((BO, -) ? NA = = ((BO =), (- =))

NA ID = ((= ID))

ID NA f = ((ID f))

EQ -> ID = EX;

; NA EX = ((; EX )

EX NA = = (BO, -) ? NA = = ((BO =), (- =))

NA u = ( (=u))

SB NA UO = ( (,), OP, BO ) NA UO = (((UO), (OP UO), (BO UO) )

) NA EX = (()EX) )

EX NA (= (BO, -) ? NA (= ((BO (), (- ())

SB->SB BO SB

SB NA BO = ((,), OP, BO) NA BO = (((BO), ()BO), (OP BO), (BO BO))

BO NA SB = (+,*,-) NA SB = ((+SB), (*SB), (-SB))

ID NA u = ((u, u))

G) PG ->DE AL

AL COLLECTIE PG = AL COLLECTIE TRACE" (PG) = ((AL ?))

e COLLECTIE AL = e COLLECTIE TRACE"(AL)= ((eb), (e?))

=; VERZAMELTRACK"(DE) = ((;b), (;?))

LV COLLECTIE LV = LV COLLECTIETRAIL" (LV) = ((LV:), (LV?))

ID-VERZAMELING LV = ID-VERZAMELINGSTRACK" (LV) = ((ID:), (ID ?))

; SAMENVATTEN LE =; VERZAMELTRACK" (LE) = ((; e), (;?), (; n))

LE -> f ID = EX t EX d LE n;

; SAMENVATTEN LE =; VERZAMELTRACK" (LE) = ((; e), (;?), (; n))

EQ COLLECTION LE = EQ COVER TRACE" (LE) = ((EQ e), (EQ?), (EQ n))

EQ -> ID = EX;

; COLLAPSE EQ =; VERZAMELTRACK" (EQ) = ((; (), (;)), (;;), (;f), (;?), (;=), (;t), (;d), (; n), (;w), (;r))

SB-COLLECTIE EX = SB COVER TRACE" (EX) = ((SB t), (SB?), (SB d), (SB)), (SB;), (SB(), (SB=), (SBf ), (SBn), (SBw), (SBr) )

) COLLECTIE SB = SB COLLECTIE TRACE" (SB) = (() t), ()?), () d), ())), ();))

OP COLLECTIE SB = OP COLLECTIE TRACE" (SB) = ((OP t), (OP ?), (OP d), (OP)), (OP;))

SB->SB BO SB

SB-COLLECTIE SB = SB COVER TRACE" (SB) = ((SB, t), (SBd), (SB;). (SB)), (SB+), (SB-), (SB*), (SB? ) }

COLLECTIE UO = - COLLECTIETRACK" (UO) = ( (-?), (--))

COLLECTIE BO = + COLLECTIETRACK" (BO) = ((++), (+?), (+*), (+-))

* COLLECTIE BO = * COLLECTIETRACK" (BO) = ((*+), (*?), (**), (*-))

COLLECTIE BO = - COLLECTIETRACK" (BO) = ((-+), (-?), (-*), (--))

ID-VERZAMELING OP = ID-DEKKING TRACE" (OP) = ((ID+), (ID?), (ID*), (ID-))

CO-DEKSEL OP = CO-DEKSEL TRACE" (OP) = ((CO+), (CO?), (CO*), (CO-), (CO;), (COd), (COt), (CO)))

ID VERZAMELING ID = ID VERZAMELTRACK" (ID) = ((ID)), (ID ?), (ID k), (ID+), (ID-), (ID*), (ID=), (IDt) , (IDd)))

u COLLECTIE-ID = l VERZAMELTRACK" (ID) = ((u)), (u?), (uk), (u+), (u-), (u*), (u=), (ut), (ud)))

CO-DEKSEL CO = CO-DEKSEL TRACE" (CO) = (CO+), (CO?), (CO*), (CO-), (CO;), (COd), (COt), (CO)))

k COLLECTIE CO = k COLLECTIE TRACE" (CO) = (k+), (k?), (k*), (k-), (k;), (kd), (kt), (k)))

Eén gevonden conflictsituatie wanneer de regels worden verworpen

OP -> ID en ID -> u ID

We voeren ID1 -> ID in, daarom herschrijven we de regel ID1 -> u ID

Daarom zullen we convolutiebewerkingen uitvoeren.

ID1 VERZAMELING ID = ID1 VERZAMELTRACK" (ID) = ((ID1)), (ID1 ?), (ID1 k), (ID1+), (ID1-), (ID1*), (ID1=), (ID1t) , (ID1d)))

Voor elk paar (x, A)? x NA A construeren we een transitiefunctie die de overdrachtsactie bepaalt??(S 0 , x, A) = (S 0 , A)

? (S0, b, DE) = (S0, DEb)

? (S0, e, DE) = (S0, DEe)

? (S0, e, LE) = (S0, LEe)

? (S0,), b) = (S0, b))

? (S0,;, b) = (S0, b;)

? (S0, (, b) = (S0, b()

? (S0, =, b) = (S0, b=)

? (S0, f, b) = (S0, bf)

? (S0, t, b) = (S0, bt)

? (S0, d, b) = (S0, bd)

? (S0, n, b) = (S0, miljard)

? (S0, w, b) = (S0, bw)

? (S0, r, b) = (S0, br)

? (S0,;, ik) = (S0, ik;)

? (S0, ik,:) = (S0, ik:)

? (S0,:LV) = (S0,LV:)

? (S0, ID, v) = (S0, vID)

? (S0,ID,) = (S0,ID)

? (S0, u) = (S0, u,)

? (S0, (, EQ)= (S0, EQ()

? (S0,), EQ)= (S0, EQ))

? (S0, =, EQ)= (S0, EQ=)

? (S0,;, EQ)= (S0, EQ;)

? (S0, f, EQ)= (S0, EQf)

? (S0, t, EQ)= (S0, EQt)

? (S0, d, EQ)= (S0, EQd)

? (S0, n, EQ)= (S0, EQn)

? (S0, w, EQ)= (S0, EQw)

? (S0, r, EQ)= (S0, EQr)

? (S0,;,)) = (S0,);)

? (S0, (, DE) = (S0, DE()

? (S0,v,)) = (S0,)v)

? (S0,;,)) = (S0,);)

? (S0, ik,)) = (S0,) ik)

? (S0,:,)) = (S0,):)

? (S0,e,)) = (S0,)e)

? (S0, (, r) = (S0, r()

? (S0, (, w) = (S0, w()

? (S0,;, n) = (S0, n;)

? (S0, n, LE) = (S0, LEn)

? (S0, (, d) = (S0, d()

? (S0,),d) = (S0,d))

? (S0,;,d) = (S0,d;)

? (S0, f, d) = (S0, df)

? (S0, t, d) = (S0, dt)

? (S0, d, d) = (S0, dd)

? (S0, n, d) = (S0, dn)

? (S0, w, d) = (S0, dw)

? (S0, r, d) = (S0, dr)

? (S0, d, EX) = (S0, EXd)

? (S0, BO, t) = (S0, tBO)

? (S0, -, t) = (S0, t-)

? (S0, t, EX) = (S0, EXt)

? (S0, BO, =) = (S0, =BO)

? (S0, -, =) = (S0, =-)

? (S0, =, ID) = (S0, ID=)

? (S0, ID, f) = (S0, fID)

? (S0,;, EX) = (S0, EX;)

? (S0, =, u) = (S0, u =)

? (S0, (, UO) = (S0, UO()

? (S0, OP, UO) = (S0, UO OP)

? (S0, BO, UO) = (S0, UO BO)

? (S0,), EX) = (S0, EX))

? (S0, BO, () = (S0, (BO))

? (S0, BO, -) = (S0, -BO)

? (S0, (, BO) = (S0, BO()

? (S0,),BO) = (S0,)BO)

? (S0, OP, BO) = (S0, BOOP)

? (S0, +, SB) = (S0, SB+)

? (S0, *, SB) = (S0, SB*)

? (S0, -, SB) = (S0, SB-)

? (S0, u, u) = (S0, uu)

Voor elk paar (x, A)? En CONVERT x bouwen we een overgangsfunctie die de actie van convolutie bepaalt? * (S 0 , x, bA) = (S 0 , B), waarbij B->bA

? * (S 0, AL, ?) = (S 0, PG)

? * (S 0, e, b) = (S 0, AL)

? * (S0, n, ?) = (S0, AL)

? * (S 0 ,;, b) = (S 0 , DE)

? * (S 0,;, ?) = (S 0, DE)

? * (S 0,;, e) = (S 0, DE)

? * (S 0, LV,:) = (S 0, LV)

? * (S 0, LV, ?) = (S 0, LV)

? * (S 0, ID, ?) = (S 0, LV)

? * (S 0, ID, e) = (S 0, LV)

? * (S 0,;, e) = (S 0, LE)

? * (S 0,;, ?) = (S 0, LE)

? * (S 0 ,;, n) = (S 0 , LE)

? * (S 0, EQ, n) = (S 0, LE)

? * (S 0, EQ, e) = (S 0, LE)

? * (S 0, EQ, ?) = (S 0, LE)

? * (S 0,;, e) = (S 0, LE)

? * (S 0,;, ?) = (S 0, LE)

? * (S 0,;, () = (S 0, EQ)

? * (S 0,;,)) = (S 0, EQ)

? * (S 0,;, f) = (S 0, EQ)

? * (S 0,;, =) = (S 0, EQ)

? * (S 0,;, t) = (S 0, EQ)

? * (S 0,;, d) = (S 0, EQ)

? * (S 0,;, n) = (S 0, EQ)

? * (S 0,;, w) = (S 0, EQ)

? * (S 0,;, r) = (S 0, EQ)

? * (S 0, SB, ?) = (S 0, EX)

? * (S 0, SB, d) = (S 0, EX)

? * (S 0, SB,)) = (S 0, EX)

? * (S0, SB,;) = (S0, EX)

? * (S 0, SB, w) = (S 0, EX)

? * (S 0, SB, r) = (S 0, EX)

? * (S 0, SB, f) = (S 0, EX)

? * (S 0, SB, =) = (S 0, EX)

? * (S 0, SB, t) = (S 0, EX)

? * (S 0, SB, ?) = (S 0, SB)

? * (S 0, SB, () = (S 0, SB)

? * (S 0, SB,)) = (S 0, SB)

? * (S 0, SB, u) = (S 0, SB)

? * (S 0, SB, k) = (S 0, SB)

? * (S0, SB, +) = (S0, SB)

? * (S 0, SB, -) = (S 0, SB)

? * (S 0, SB, *) = (S 0, SB)

? * (S 0, SB, e) = (S 0, SB)

? * (S 0,), t) = (S 0, SB)

? * (S 0,), ?) = (S 0, SB)

? * (S 0,), t) = (S 0, SB)

(S 0,),)) = (S 0, SB)

? * (S 0,),;) = (S 0, SB)

? * (S 0, -, ?) = (S 0, UO)

? * (S 0, -, -) = (S 0, UO)

? * (S0, +, +) = (S0, BO)

? * (S0, +,?) = (S0, BO)

? * (S 0 , +, *) = (S 0 , BO)

? * (S 0, -, +) = (S 0, BO)

? * (S 0, -, ?) = (S 0, BO)

? * (S 0, -, *) = (S 0, BO)

? * (S 0, -, -)) = (S 0, BO)

? * (S 0 , *, +) = (S 0 , BO)

? * (S 0, *, ?) = (S 0, BO)

? * (S 0 , *, *) = (S 0 , BO)

? * (S 0, *, -)) = (S 0, BO)

? * (S 0, u, +) = (S 0, BO)

? * (S 0, u, ?)= (S 0, BO)

? * (S 0, u, *) = (S 0, BO)

? * (S 0, u, -)) = (S 0, BO)

? * (S 0, k, +) = (S 0, BO)

? * (S 0, k, ?) = (S 0, BO)

? * (S 0, k, *) = (S 0, BO)

? * (S 0, k, -)) = (S 0, BO)

? * (S 0, CO, ?) = (S 0, OP)

? * (S0, CO, +) = (S0, OP)

? * (S 0, CO, *) = (S 0, OP)

? * (S 0, CO, -) = (S 0, OP)

? * (S 0, CO,;) = (S 0, OP)

? * (S 0, CO, d) = (S 0, OP)

? * (S 0 , CO, t) = (S 0 , OP)

? * (S 0, ID, -) = (S 0, OP)

? * (S 0, ID, *) = (S 0, OP)

? * (S 0, ID, ?) = (S 0, OP)

? * (S 0, ID, () = (S 0, OP)

? * (S 0, ID,)) = (S 0, OP)

? * (S 0, ID, u) = (S 0, OP)

? * (S 0, ID, k) = (S 0, OP)

? * (S 0, ID, -) = (S 0, OP)

? * (S 0, ID, +) = (S 0, OP)

? * (S 0, u,)) = (S 0, I OP)

? * (S 0, ID1, *) = (S 0, ID)

? * (S 0, ID1, ?) = (S 0, ID)

? * (S 0, ID1, () = (S 0, ID)

? * (S 0, ID1,)) = (S 0, ID)

? * (S 0, ID1, u) = (S 0, ID)

? * (S 0, ID1, k) = (S 0, ID)

? * (S 0, ID1, -) = (S 0, ID)

? * (S 0, ID1, +) = (S 0, ID)

? * (S 0, u,)) = (S 0, ID)

? * (S 0, u, ?) = (S 0, BO)

? * (S 0, u, k) = (S 0, ID)

? * (S 0, u, *)) = (S 0, ID)

? * (S 0, u, -)) = (S 0, ID)

? * (S 0, u, +)) = (S 0, ID)

? * (S 0, u, d)) = (S 0, ID)

? * (S 0, u, t)) = (S 0, ID)

? * (S 0, u, =)) = (S 0, ID)

? * (S 0, CO, ?) = (S 0, CO)

? * (S0, CO, +) = (S0, CO)

? * (S0, CO, -) = (S0, CO)

? * (S0, CO, *) = (S0, CO)

? * (S0, CO,;) = (S0, CO)

? * (S0, CO, d) = (S0, CO)

? * (S0, CO, t) = (S0, CO)

? * (S0, CO,)) = (S0, CO)

? * (S0, k, +) = (S0, CO)

? * (S0, k, -) = (S0, CO)

? * (S 0, k, *) = (S 0, CO)

? * (S 0, k,;) = (S 0, CO)

?? * (S 0, k, d) = (S 0, CO)

? * (S 0, k, t) = (S 0, CO)

? * (S 0, k,)) = (S 0, CO)

? * (S0, k, () = (S0, CO)

2.2.3 Software-implementatie van de parser

De syntactische analysator (parser) leest het lexeme-bestand dat door de lexicale analysator is gegenereerd, voert grammaticale parsering uit en geeft berichten uit over syntaxisfouten indien beschikbaar, en creëert een tussenvorm voor het opnemen van het originele programma. De basis voor de ontwikkeling van een parser is het ontwerp en de implementatie van de bijbehorende magazijnmachine.

Voor bottom-up-parsering voor een deterministische bottom-up-parser na het reduceren tot het juiste type Met de functies AFTER en COVER is het nodig om een ​​winkelmachine te ontwerpen met een gedetailleerde beschrijving van alle transities binnen de transitiefunctie.

Bij het ontwikkelen van een verkoopautomaat hebben we overgangsfuncties gebouwd die de basis zullen vormen van de parser. Alle overgangsfuncties kunnen in twee typen worden verdeeld:

De werkingscyclus van een magazijnmachine zonder het invoersymbool te lezen (lege cyclus);

Tact van de bediening van een magazijnmachine met het lezen van het invoersymbool.

Bij de implementatie van de lexicale analysator hebben we het programma in lexemen verdeeld en deze in een lijst geschreven. Deze lijst verwerken we vervolgens in de parser. We sturen ons programma (lijst), het initiële symbool (PG) en de onderste markering van de opslagmachine (h0) naar de ingang, waarna de gewenste overgangsfunctie wordt geselecteerd en een recursieve oproep wordt gedaan.

Het diagram van het parserprogramma wordt weergegeven in bijlage B in figuur B.2.

2.2.4 Ontwikkeling van de tolkmodule

Bij het ontwikkelen van een interpretatiemodule als tussenvorm van het oorspronkelijke programma De postfix-notatievorm wordt het vaakst gebruikt, wat het vrij eenvoudig maakt om het proces van het uitvoeren (interpreteren) van het vertaalde programma te implementeren.

Laten we eens kijken naar de basisprincipes van het vormen en uitvoeren van de postfix-vorm van schrijfuitdrukkingen.

De basisregels voor het converteren van een infix-expressie naar een postfix-expressie zijn als volgt.

De leesoperands worden toegevoegd aan de postfix-notatie en de bewerkingen worden naar de stapel geschreven.

Als de bewerking bovenaan de stapel een hogere (of gelijke) prioriteit heeft dan de momenteel gelezen bewerking, wordt de bewerking op de stapel toegevoegd aan het postfix-item en wordt de huidige bewerking op de stapel geduwd. Anders (bij een lagere prioriteit) wordt alleen de huidige bewerking op de stapel geplaatst.

Het leesopeningshaakje wordt op de stapel geduwd.

Nadat de accolade sluiten is gelezen, worden alle bewerkingen tot aan de eerste accolade voor openen van de stapel gehaald en aan de postfix-invoer toegevoegd, waarna zowel de accolades voor openen als sluiten worden weggegooid, d.w.z. worden niet op een postfix-record of op de stapel geplaatst.

Nadat de volledige expressie is gelezen, worden de resterende bewerkingen op de stapel toegevoegd aan de postfix-invoer.

Dankzij de postfix-notatie van een uitdrukking kan deze als volgt worden berekend.

Als het token een operand is, wordt het naar de stapel geschreven. Als het token een bewerking is, wordt de opgegeven bewerking uitgevoerd op de laatste elementen (laatste element) die naar de stapel zijn geschreven, en worden die elementen (element) op de stapel vervangen door het resultaat van de bewerking.

Als de lexicale en syntactische analyses succesvol zijn afgerond, gaan we over tot interpretatie. Eerst maken we zinnen van de woorden, vervolgens vertalen we de uitdrukkingen in postfix-notatie en berekenen we.

Het werkingsschema van de tolk wordt weergegeven in bijlage B in figuur B.3.

2.3 Codering

Het programma wordt in de omgeving C# geïmplementeerd Visuele programmering Studio 2010. De tekst van het programma is opgenomen in bijlage A.

Het programma bevat vijf lessen. De gebruikersinterface wordt geïmplementeerd met behulp van de MainForn-klasse. Met behulp van de klasse LexAnalysis wordt een lexicale analysemodule geïmplementeerd, SynAnalysis is een syntactische analysemodule, Intepreter is een interpretatiemodule, ProgramisciJakPolska is een hulpklasse voor het vertalen van uitdrukkingen in omgekeerde Poolse notatie (postfix).

Het doel van de procedures en functies die in het programma zijn geïmplementeerd, wordt beschreven in de tabellen 6,7,8.

Tabel 6 - Doel van procedures en functies van lexicale analyse

Soortgelijke documenten

Vertaler als programma of technische middelen, die het programma uitzendt. Beschouwing van de belangrijkste kenmerken van de constructie van een lexicale analysator. Inleiding tot de stadia van het ontwikkelen van een vertaler uit een beperkte subset van een taal op hoog niveau.

cursuswerk, toegevoegd op 08/06/2013


Ontwerp van lexicale en syntactische analysatoren voor educatieve taal. Regels voor het converteren van logische expressies naar POLYZ. Vorming van drieklanken, optimalisatie van hun lijst. Logische structuur programma's. Vertaler-tolkmodules testen.

cursuswerk, toegevoegd op 28/05/2013


Algemene kenmerken en beoordeling van de mogelijkheden van de programmeertaal C-Sharp, de vergelijkbare en onderscheidende kenmerken van C++ en Java. Ontwikkeling van een lexicale en syntactische analysator met behulp van deze programmeertaal. Het samenstellen van parseertabellen.

cursuswerk, toegevoegd op 06/11/2010


Het ontwerpen van een analyseprogramma dat uit twee delen bestaat: een lexicale analyser die de brontekst van het programma in lexemen opsplitst en een tabel met namen invult; een parser die de tekst controleert op naleving van een bepaalde grammatica.

cursuswerk, toegevoegd op 14-06-2010


Het schrijven van een programma dat lexicale en syntactische analyses uitvoert van de invoerprogrammeertaal, een tabel met lexemen genereert die hun typen en waarden aangeven, en ook een syntaxisboom bouwt; de tekst van de invoertaal wordt via het toetsenbord ingevoerd.

cursuswerk, toegevoegd op 23-02-2012


Methodologie voor de ontwikkeling en gedeeltelijke implementatie van een vertaler voor de C-taal die de C++-taal gebruikt, die de oorspronkelijke reeks karakters opsplitst in minimaal ondeelbare taalconstructies op basis van de woordenschat van de taal. Analyse van de werking van het programma.

cursuswerk, toegevoegd op 19-03-2012


Structuur, classificatie en vereisten voor implementatie van compiler. Ontwerp en implementatie van het analysegedeelte van de C++-taalcompiler. Methoden voor het implementeren van lexicale analyse. Algoritme voor de werking van de parser. Principes van software-implementatie.

cursuswerk, toegevoegd op 26-01-2013


Creatie van een vertaler die programmacode in Pascal verwerkt en, met behulp van gelijkwaardige operatoren, een programma in C genereert. Kenmerken van de externe specificatie en werking van de lexicale analysator. Programmastructuur, resultaten weergeven op het scherm.

cursuswerk, toegevoegd op 07/02/2011


Methoden voor grammaticale analyse. Ontwikkeling van de structuur van een educatieve vertaler in de basisprogrammeertaal Object Pascal in de objectgeoriënteerde visuele programmeeromgeving Borland DELPHI 6.0 met behulp van het Windows XP-besturingssysteem.

cursuswerk, toegevoegd op 12-05-2013


Software-implementatie van een desktopapplicatie met behulp van de programmeertaal C#. Ontwerp en structuur gebruikersomgeving, eisen eraan en beoordeling van de functionaliteit. Ontwikkeling van een gebruikershandleiding en het gebruik ervan.

• Adres. Een functioneel apparaat dat een virtueel adres omzet in een echt adres.
• Dialoog. Biedt het gebruik van een programmeertaal in time-sharing-modus.
• Multi-pass. Vormt een objectmodule over verschillende weergaven van het bronprogramma.
• Rug. Hetzelfde als devertaler. Zie ook: decompiler, disassembler.
• Enkele pas. Vormt een objectmodule in één opeenvolgende weergave van het bronprogramma.
• Optimaliseren. Voert code-optimalisatie uit in de gegenereerde objectmodule.
• Syntactisch georiënteerd (syntactisch gestuurd). Ontvangt als invoer een beschrijving van de syntaxis en semantiek van de taal en tekst in de beschreven taal, die wordt vertaald in overeenstemming met de gegeven beschrijving.
• Test. Een set macroopdrachten in assembleertaal waarmee u verschillende foutopsporingsprocedures kunt instellen in programma's die in assembleertaal zijn geschreven.

Doel van de uitzending- tekst omzetten van de ene taal naar de andere, wat begrijpelijk is voor de ontvanger van de tekst. Bij vertaalprogramma's is de geadresseerde een technisch apparaat (processor) of een tolkprogramma.

De taal van processors (machinecode) is meestal laagdrempelig. Er zijn platforms die machinetaal op hoog niveau gebruiken (bijvoorbeeld iAPX-432), maar deze vormen een uitzondering op de regel vanwege hun complexiteit en hoge kosten. Er wordt een vertaler aangeroepen die programma's omzet in machinetaal die rechtstreeks door de processor wordt ontvangen en uitgevoerd compiler.

Het compilatieproces bestaat doorgaans uit verschillende fasen: lexicale, syntactische en semantische analyse (Engelse semantische analyse), generatie van tussencode, optimalisatie en generatie van de resulterende machinecode. Bovendien is een programma doorgaans afhankelijk van diensten die worden geleverd door het besturingssysteem en bibliotheken van derden (bijvoorbeeld bestands-I/O of een grafische interface), en moet de machinecode van het programma aan deze diensten worden gekoppeld. Het koppelen met statische bibliotheken gebeurt door een linker of linker (dit kan een afzonderlijk programma zijn of een onderdeel van een compiler), terwijl het koppelen met het besturingssysteem en dynamische bibliotheken gebeurt wanneer de lader het programma begint uit te voeren.

Het voordeel van de compiler: het programma wordt één keer gecompileerd en er zijn geen extra transformaties nodig elke keer dat het wordt uitgevoerd. Dienovereenkomstig is er geen compiler vereist op de doelmachine waarvoor het programma is gecompileerd. Nadeel: een aparte compilatiestap vertraagt ​​het schrijven en debuggen en maakt het moeilijk om kleine, eenvoudige of eenmalige programma's uit te voeren.

Een andere implementatiemethode is wanneer het programma wordt uitgevoerd met behulp van tolk helemaal geen uitzending. De tolksoftware modelleert een machine waarvan de ophaal-uitvoercyclus werkt op basis van instructies in talen op hoog niveau, in plaats van op machine-instructies. Deze softwaresimulatie creëert een virtuele machine die de taal implementeert. Deze benadering wordt pure interpretatie genoemd. Pure interpretatie wordt meestal gebruikt voor talen met een eenvoudige structuur (bijvoorbeeld APL of Lisp). Tolken opdrachtregel procesopdrachten in scripts in UNIX of in batchbestanden (.bat) in MS-DOS, meestal ook in pure interpretatiemodus.

Het voordeel van een pure tolk: de afwezigheid van tussenliggende acties voor vertaling vereenvoudigt de implementatie van de tolk en maakt deze handiger in gebruik, ook in dialoogmodus. Het nadeel is dat er een tolk aanwezig moet zijn op de doelmachine waarop het programma moet worden uitgevoerd.

Er zijn compromissen tussen compilatie en pure interpretatie bij de implementatie van programmeertalen, wanneer de tolk, voordat hij het programma uitvoert, het vertaalt naar een tussentaal (bijvoorbeeld in bytecode of p-code), handiger voor interpretatie (dat wil zeggen: we hebben het over een tolk met ingebouwde vertaler). Deze methode wordt gemengde implementatie genoemd. Een voorbeeld van een gemengde taalimplementatie is Perl. Deze aanpak combineert zowel de voordelen van een compiler als een tolk ( hoge snelheid uitvoering en gebruiksgemak) en nadelen (vertaling en opslag van een programma in een tussentaal vereisen extra middelen; er moet een tolk beschikbaar zijn om het programma op de doelmachine uit te voeren). Ook vereist een gemengde implementatie, net als in het geval van een compiler, dat de broncode vóór uitvoering vrij is van fouten (lexicaal, syntactisch en semantisch).

Uitzending En interpretatie - verschillende processen: Vertaling houdt zich bezig met de vertaling van programma's van de ene taal naar de andere, terwijl tolken verantwoordelijk is voor de uitvoering van programma's. Omdat het doel van vertaling echter meestal is om het programma voor te bereiden op tolking, worden deze processen meestal samen beschouwd. Programmeertalen worden bijvoorbeeld vaak gekarakteriseerd als "gecompileerd" of "geïnterpreteerd", afhankelijk van de vraag of compilatie of interpretatie het gebruik van de taal domineert. Bovendien vrijwel alle programmeertalen laag niveau en talen van de derde generatie, zoals assembler, C of Modula-2, worden gecompileerd, terwijl talen van een hoger niveau, zoals Python of SQL, worden geïnterpreteerd.

Aan de andere kant is er sprake van een onderlinge penetratie van vertaal- en interpretatieprocessen: tolken kunnen compileren (inclusief dynamische compilatie), en vertalers kunnen interpretatie nodig hebben voor metaprogrammeringsconstructies (bijvoorbeeld voor macro's in assembleertaal, voorwaardelijke compilatie in C, of ​​voor sjablonen in C++).

Bovendien kan dezelfde programmeertaal zowel vertaald als geïnterpreteerd worden, en moet deze in beide gevallen aanwezig zijn algemene fasen analyse en herkenning van constructies en richtlijnen van de brontaal. Dit geldt voor zowel software- als hardware-implementaties - bijvoorbeeld processors van de x86-familie voeren, voordat ze machinetaalinstructies uitvoeren, hun decodering uit, waarbij in de opcodes de velden van operanden (registers, geheugenadressen, onmiddellijke waarden), bitdiepte, enz. worden benadrukt. ., en in Pentium-processors bij de NetBurst-architectuur wordt machinecode doorgaans vertaald in een reeks microbewerkingen voordat deze in de interne cache wordt opgeslagen.

Doelen en doelstellingen van het vakgebied. Basisconcepten en definities. Algemene kenmerken programmeertalen en vertalers. Algemene structuur van de vertaler. Opties voor interactie van vertaalblokken.

Doelen en doelstellingen van het vakgebied

Momenteel kunstmatige talen, die een tekstuele weergave gebruiken om een ​​onderwerpgebied te beschrijven, worden niet alleen veel gebruikt bij het programmeren, maar ook op andere gebieden. Met hun hulp wordt de structuur van allerlei soorten documenten driedimensionaal virtuele werelden, grafische interfaces gebruiker en vele andere objecten die in modellen en in de echte wereld worden gebruikt. Om ervoor te zorgen dat deze tekstbeschrijvingen correct worden samengesteld en vervolgens correct worden herkend en geïnterpreteerd, worden speciale methoden voor hun analyse en transformatie gebruikt. De methoden zijn gebaseerd op de theorie van talen en formele grammatica's, evenals op de theorie van automaten. Softwaresystemen die zijn ontworpen om teksten te analyseren en interpreteren, worden vertalers genoemd.

Ondanks het feit dat er tot nu toe duizenden verschillende talen en hun vertalers zijn ontwikkeld, stopt het proces van het creëren van nieuwe applicaties op dit gebied niet. Dit hangt samen met de ontwikkeling van productietechnologie computersystemen, en met de noodzaak om steeds complexere toegepaste problemen op te lossen. Bovendien zijn elementen van de taaltheorie en formele grammatica van toepassing op andere uiteenlopende gebieden, bijvoorbeeld bij het beschrijven van datastructuren, bestanden en afbeeldingen, die niet in tekst, maar in binair formaat worden gepresenteerd. Deze methoden zijn ook nuttig bij het ontwikkelen van uw eigen vertalers, zelfs als er al overeenkomstige analogen bestaan. Een dergelijke ontwikkeling kan verschillende redenen hebben, met name functionele beperkingen, gebrek aan lokalisatie en lage efficiëntie. Een van de nieuwste ontwikkelingen van Microsoft is bijvoorbeeld de programmeertaal C#, en een van de redenen voor de oprichting ervan is de wens om de populariteit van de programmeertaal Java te verminderen. Er zijn nog veel meer voorbeelden waarbij het ontwikkelen van een eigen vertaler relevant kan zijn. Daarom zijn de basisprincipes van de taaltheorie en formele grammatica's, evenals praktische methoden de ontwikkeling van vertalers ligt aan de basis van het ingenieursonderwijs in de informatica en computer technologie.

Het voorgestelde materiaal raakt aan de basisprincipes van methoden voor het ontwikkelen van vertalers en bevat informatie die nodig is om de logica van hun functioneren, het gebruikte wiskundige apparaat (theorie formele talen en formele grammatica's, metatalen). Het wordt gebruikt als onderdeel van semesterlange hoorcolleges voor verschillende specialismen aan de Faculteit Informatica en Computerwetenschappen van de Technische Staatsuniversiteit van Krasnojarsk. Tijdens laboratoriumwerk wordt directe kennis gemaakt met individuele methoden voor het maken van vertalers.

Het doel van de discipline: kennis verschaffen over de basisprincipes van de taaltheorie en formele grammatica, de theorie van automaten, methoden voor het ontwikkelen van vertalers.

Om dit doel te bereiken, worden tijdens het lesgeven in het vakgebied de volgende taken opgelost:

1. De hoorcollegecursus onderzoekt de algemene principes van het organiseren van het vertaalproces en de structuur van vertalers. De fundamenten van de theorie van het construeren van vertalers worden bestudeerd.
2. In laboratoriumlessen en tijdens zelfstandig werk wordt praktische consolidatie van de verworven theoretische kennis uitgevoerd: er wordt een vertaler voor ontwikkeld eenvoudige taal programmeren.

Basisconcepten en definities

De meeste van de beschouwde definities zijn ontleend aan [ARNFTS Engels-Russisch-Duits-Frans verklarend woordenboek over computertechnologie en gegevensverwerking, 4132 termen. Onder. red. AA Dorodnitsyna. M.: 1978. 416 blz.) ].

Vertaler - een serviceprogramma dat het bronprogramma in de invoerprogrammeertaal omzet naar werk programma, weergegeven in objecttaal.

De bovenstaande definitie is van toepassing op alle soorten uitzendprogramma's. Elk van deze programma's kan echter zijn eigen kenmerken hebben bij het organiseren van het uitzendproces. Momenteel zijn vertalers onderverdeeld in drie hoofdgroepen: assembleurs, compilers en tolken.

Monteur - een systeemhulpprogramma dat symbolische constructies omzet in machinetaalinstructies. Een specifiek kenmerk van assembleurs is dat ze een woordelijke vertaling van één symbolische instructie naar één machine-instructie uitvoeren. Daarom is assembleertaal (ook wel autocode genoemd) ontworpen om de perceptie van het computerbesturingssysteem te vergemakkelijken en het programmeren in dit commandosysteem te versnellen. Het is voor een programmeur veel gemakkelijker om de geheugensteun van machine-instructies te onthouden dan de binaire code ervan. Daarom wordt de belangrijkste winst niet behaald door de kracht van individuele commando's te vergroten, maar door de efficiëntie van hun perceptie te vergroten.

Tegelijkertijd bevat assembleertaal, naast analogen van machineopdrachten, veel aanvullende richtlijnen die met name het beheer van computerbronnen vergemakkelijken, het schrijven van herhalende fragmenten en het bouwen van programma's met meerdere modules. Daarom is de expressiviteit van de taal veel rijker dan alleen een symbolische codeertaal, wat de programmeerefficiëntie aanzienlijk verbetert.

Compiler - is een serviceprogramma dat een programma dat in de bronprogrammeertaal is geschreven, vertaalt naar machinetaal. Net als een assembler converteert een compiler een programma van de ene taal naar de andere (meestal naar de taal van een specifieke computer). Tegelijkertijd verschillen brontaalopdrachten qua organisatie en kracht aanzienlijk van machinetaalopdrachten. Er zijn talen waarin één commando van de brontaal wordt vertaald in 7-10 machineopdrachten. Er zijn echter ook talen waarin elke opdracht 100 of meer machineopdrachten kan hebben (bijvoorbeeld Prolog). Bovendien gebruiken de brontalen vrij vaak strikte gegevenstypering, uitgevoerd via hun voorlopige beschrijving. Programmeren berust mogelijk niet op het coderen van een algoritme, maar op het zorgvuldig nadenken over datastructuren of klassen. Het vertaalproces vanuit dergelijke talen wordt meestal compilatie genoemd, en de brontalen zijn meestal programmeertalen op hoog niveau (of talen op hoog niveau). De abstractie van een programmeertaal van het computerbesturingssysteem leidde tot de onafhankelijke creatie van een grote verscheidenheid aan talen gericht op het oplossen van specifieke problemen. Er zijn talen verschenen voor wetenschappelijke berekeningen, economische berekeningen, toegang tot databases en meer.

Tolk - een programma of apparaat dat de vertaling en uitvoering van het originele programma per operator uitvoert. In tegenstelling tot een compiler produceert een tolk geen programma in machinetaal. Nadat het een commando in de brontaal heeft herkend, voert het het onmiddellijk uit. Zowel compilers als tolken gebruiken dezelfde methoden voor het analyseren van de broncode van een programma. Maar met de tolk kunt u beginnen met het verwerken van gegevens nadat u zelfs maar één opdracht hebt geschreven. Dit maakt het proces van het ontwikkelen en debuggen van programma's flexibeler. Bovendien maakt de afwezigheid van uitvoermachinecode het mogelijk om externe apparaten niet te "vervuilen" met extra bestanden, en de tolk zelf kan vrij gemakkelijk worden aangepast aan elke machine-architectuur, omdat deze slechts één keer is ontwikkeld in een veelgebruikte programmeertaal. Daarom zijn geïnterpreteerde talen zoals Java Script en VB Script wijdverbreid geworden. Het nadeel van tolken is lage snelheid uitvoering van programma's. Typisch geïnterpreteerde programma's worden 50-100 keer uitgevoerd langzamere programma's geschreven in machinecode.

Emulator- een programma of software- en hardwaretool dat de mogelijkheid biedt om, zonder herprogrammering, op een bepaalde computer een programma uit te voeren dat codes of methoden gebruikt voor het uitvoeren van bewerkingen die verschillen van die op de gegeven computer. Een emulator lijkt op een tolk, omdat deze rechtstreeks een programma uitvoert dat in een bepaalde taal is geschreven. Meestal is het echter machinetaal of tussencode. Beide vertegenwoordigen instructies in binaire code die onmiddellijk kunnen worden uitgevoerd nadat de bewerkingscode is herkend. In tegenstelling tot tekstprogramma's is het niet nodig de programmastructuur te herkennen of operanden te selecteren.

Emulators worden vrij vaak voor verschillende doeleinden gebruikt. Bij het ontwikkelen van nieuwe computersystemen wordt bijvoorbeeld eerst een emulator gemaakt die programma's uitvoert die zijn ontwikkeld voor computers die nog niet bestaan. Hiermee kunt u het commandosysteem evalueren en de basis ontwikkelen software zelfs voordat de bijbehorende apparatuur is gemaakt.

Heel vaak wordt een emulator gebruikt om oude programma's op nieuwe uit te voeren. computers. Nieuwere computers zijn doorgaans sneller en hebben betere randapparatuur. Hierdoor kunt u oudere programma's efficiënter emuleren dan deze op oudere computers uit te voeren. Een voorbeeld van deze aanpak is de ontwikkeling van emulators thuis computer ZX Spectrum met Z80-microprocessor. Er zijn nog steeds mensen die graag games spelen op een emulator die verouderd zijn, maar hun vroegere aantrekkingskracht nog steeds niet hebben verloren. spelprogramma's. De emulator kan ook worden gebruikt als een goedkoper analoog van modern computersystemen, terwijl het aanvaardbare prestaties levert die gelijkwaardig zijn aan die van low-end modellen van een bepaalde familie van architecturen. Een voorbeeld zijn IBM PC-emulators compatibele computers, geïmplementeerd op krachtigere Apple-computers. Een aantal emulators die voor de IBM-pc zijn geschreven, vervangen met succes verschillende gameconsoles.

De tussenliggende representatie-emulator en de tolk kunnen eenvoudig van de ene computerarchitectuur naar de andere worden overgebracht, waardoor mobiele software kan worden gemaakt. Het is deze eigenschap die het succes van de Java-programmeertaal, van waaruit het programma in tussencode wordt vertaald, vooraf heeft bepaald. De virtuele Java-machine die deze code uitvoert, is niets meer dan een emulator die onder elk modern besturingssysteem draait.

Transcoder - programma of software-apparaat, het vertalen van programma's die in de machinetaal van de ene computer zijn geschreven naar programma's in de machinetaal van een andere computer. Als de emulator een minder intelligente analoog van de tolk is, handelt de transcoder in dezelfde hoedanigheid ten opzichte van de compiler. Op dezelfde manier wordt broncode (en meestal binaire) machinecode of een tussenrepresentatie omgezet in andere soortgelijke code met een enkele instructie en zonder enige algemene analyse van de structuur van het bronprogramma. Transcoders zijn handig bij het overbrengen van programma's van de ene computerarchitectuur naar de andere. Ze kunnen ook worden gebruikt om programmatekst op hoog niveau te reconstrueren op basis van bestaande binaire code.

Macroprocessor - een programma dat de ene reeks tekens vervangt door een andere[Bruin]. Dit is een soort compiler. Het genereert uitvoertekst door verwerking speciale inzetstukken, gelegen in brontekst. Deze inserts zijn op een speciale manier ontworpen en behoren tot constructies van een taal die macrotaal wordt genoemd. Macroprocessors worden vaak gebruikt als add-ons voor programmeertalen functionaliteit programmeersystemen. Bijna elke assembler bevat een macroprocessor, die de efficiëntie van het ontwikkelen van machineprogramma's verhoogt. Dergelijke programmeersystemen worden gewoonlijk macroassemblers genoemd.

Macroprocessors worden ook gebruikt bij talen op hoog niveau. Ze vergroten de functionaliteit van talen zoals PL/1, C, C++. Macroprocessors worden vooral veel gebruikt in C en C++, waardoor het gemakkelijker wordt om programma's te schrijven. Een voorbeeld van het wijdverbreide gebruik van macroprocessors is de klassenbibliotheek Microsoft Foundation Classes (MFC). Het implementeert message maps en andere programmaobjecten via macro-inserts. Tegelijkertijd verhogen macroprocessors de programmeerefficiëntie zonder de syntaxis en semantiek van de taal te veranderen.

Syntaxis - een reeks regels van een bepaalde taal die de vorming van de elementen ervan bepalen. Met andere woorden: dit een reeks regels voor de vorming van semantisch significante reeksen karakters in een bepaalde taal. Syntaxis wordt gespecificeerd met behulp van regels die de concepten van een taal beschrijven. Voorbeelden van concepten zijn: variabele, expressie, operator, procedure. De volgorde van concepten en hun acceptabele gebruik in regels bepaalt de syntactisch correcte structuren waaruit programma's bestaan. Het is de hiërarchie van objecten, en niet hoe ze met elkaar omgaan, die wordt gedefinieerd door middel van syntaxis. Een statement kan bijvoorbeeld alleen voorkomen in een procedure, een expressie in een statement, een variabele kan bestaan ​​uit een naam en optionele indices, etc. De syntaxis wordt in het programma niet geassocieerd met verschijnselen als ‘naar een niet-bestaand label springen’ of ‘een variabele met de opgegeven naam is niet gedefinieerd’. Dit is wat semantiek doet.

Semantiek - regels en voorwaarden die de relatie tussen taalelementen en hun semantische betekenissen bepalen, evenals de interpretatie van de betekenisvolle betekenis van syntactische constructies van de taal. Objecten van een programmeertaal worden niet alleen volgens een bepaalde hiërarchie in de tekst geplaatst, maar zijn ook nog eens met elkaar verbonden via andere concepten die verschillende associaties vormen. Een variabele, waarvoor de syntaxis alleen in declaraties en sommige instructies een geldige locatie definieert, heeft bijvoorbeeld een specifiek type, kan met een beperkt aantal bewerkingen worden gebruikt, heeft een adres en een grootte en moet worden gedeclareerd voordat deze kan worden gedeclareerd. worden gebruikt in het programma.

Syntactische analysator - een compilercomponent die broninstructies controleert op naleving van de syntactische regels en semantiek van een bepaalde programmeertaal. Ondanks zijn naam controleert de analysator zowel de syntaxis als de semantiek. Het bestaat uit verschillende blokken, die elk hun eigen problemen oplossen. Het zal in meer detail worden besproken bij het beschrijven van de structuur van de vertaler.

Algemene kenmerken van programmeertalen en vertalers

Programmeertalen verschillen nogal van elkaar qua doel, structuur, semantische complexiteit en implementatiemethoden. Dit legt zijn eigen specifieke kenmerken op aan de ontwikkeling van specifieke vertalers.

Programmeertalen zijn hulpmiddelen voor het oplossen van problemen op verschillende vakgebieden, wat de specifieke kenmerken van hun organisatie en de verschillen in doel bepaalt. Voorbeelden hiervan zijn talen als Fortran, dat gericht is op wetenschappelijke berekeningen, C, dat bedoeld is voor systeemprogrammering, Prolog, dat inferentieproblemen effectief beschrijft, en Lisp, dat wordt gebruikt voor recursieve lijstverwerking. Deze voorbeelden kunnen worden voortgezet. Elk vakgebied stelt zijn eigen eisen aan de organisatie van de taal zelf. Daarom kunnen we de verscheidenheid aan representatievormen van operators en uitdrukkingen opmerken, het verschil in de reeks basisbewerkingen en de afname van de programmeerefficiëntie bij het oplossen van problemen die geen verband houden met het onderwerpgebied. Taalkundige verschillen komen ook tot uiting in de structuur van vertalers. Lisp en Prolog worden meestal uitgevoerd in de interpretatiemodus vanwege het feit dat ze tijdens berekeningen gebruik maken van dynamische generatie van gegevenstypen. Fortran-vertalers worden gekenmerkt door agressieve optimalisatie van de resulterende machinecode, wat mogelijk wordt vanwege de relatief eenvoudige semantiek van taalconstructies - in het bijzonder vanwege de afwezigheid van mechanismen voor alternatieve naamgeving van variabelen door middel van pointers of referenties. De aanwezigheid van pointers in de C-taal stelt specifieke eisen aan dynamische geheugentoewijzing.

De structuur van een taal karakteriseert de hiërarchische relaties tussen de concepten ervan, die worden beschreven door syntactische regels. Programmeertalen kunnen sterk van elkaar verschillen in de organisatie van individuele concepten en de relaties daartussen. De programmeertaal PL/1 maakt het willekeurig nesten van procedures en functies mogelijk, terwijl in C alle functies zich op het buitenste nestniveau moeten bevinden. Met de taal C++ kunnen variabelen op elk punt in het programma worden gedeclareerd vóór het eerste gebruik ervan, terwijl in Pascal variabelen moeten worden gedefinieerd in een speciaal declaratiegebied. Een nog verdergaande ontwikkeling is PL/1, waarmee een variabele kan worden gedeclareerd nadat deze is gebruikt. Of u kunt de beschrijving helemaal weglaten en de standaardregels gebruiken. Afhankelijk van de genomen beslissing kan de vertaler het programma in één of meerdere passages analyseren, wat de vertaalsnelheid beïnvloedt.

De semantiek van programmeertalen varieert sterk. Ze verschillen niet alleen in de implementatiekenmerken van individuele operaties, maar ook in programmeerparadigma's, die fundamentele verschillen in programma-ontwikkelmethoden bepalen. De bijzonderheden van de implementatie van operaties kunnen zowel betrekking hebben op de structuur van de gegevens die worden verwerkt als op de regels voor het verwerken van dezelfde soorten gegevens. Talen zoals PL/1 en APL ondersteunen matrix- en vectorbewerkingen. De meeste talen werken voornamelijk met scalairen en bieden procedures en functies die door programmeurs zijn geschreven voor het verwerken van arrays. Maar zelfs bij het uitvoeren van de bewerking van het optellen van twee gehele getallen, kunnen talen als C en Pascal zich anders gedragen.

Naast traditioneel procedureel programmeren, ook wel imperatief genoemd, bestaan ​​er paradigma's als functioneel programmeren, logisch programmeren en objectgeoriënteerd programmeren. Ik hoop dat het procedureel-parametrische programmeerparadigma dat ik heb voorgesteld zijn plaats zal innemen in deze serie [Legalov2000]. De structuur van concepten en objecten van talen hangt sterk af van het gekozen paradigma, dat ook de implementatie van de vertaler beïnvloedt.

Zelfs dezelfde taal kan op verschillende manieren worden geïmplementeerd. Dit komt door het feit dat de theorie van formele grammatica's verschillende methoden toestaat om dezelfde zinnen te ontleden. In overeenstemming hiermee kunnen vertalers op verschillende manieren hetzelfde resultaat (objectprogramma) uit de originele brontekst verkrijgen.

Tegelijkertijd hebben alle programmeertalen een aantal gemeenschappelijke kenmerken en parameters. Deze gemeenschappelijkheid bepaalt ook de principes van het organiseren van vertalers die voor alle talen vergelijkbaar zijn.

1. Programmeertalen zijn ontworpen om het programmeren eenvoudiger te maken. Daarom zijn hun operators en datastructuren krachtiger dan die in machinetalen.
2. Om de zichtbaarheid van programma's te vergroten, worden in plaats van numerieke codes symbolische of grafische representaties van taalconstructies gebruikt, die handiger zijn voor menselijke perceptie.
3. Voor elke taal is het gedefinieerd:

• Veel symbolen die kunnen worden gebruikt om correcte programma's te schrijven (alfabet), basiselementen.
• Veel correcte programma's (syntaxis).
• De "betekenis" van elk correct programma (semantiek).

Ongeacht de specifieke kenmerken van de taal kan elke vertaler worden beschouwd als een functionele converter F, die een unieke mapping van X naar Y biedt, waarbij X een programma in de brontaal is en Y een programma in de uitvoertaal. Daarom kan het vertaalproces zelf formeel vrij eenvoudig en duidelijk worden gepresenteerd:

Formeel is elk correct programma X een keten van symbolen uit een bepaald alfabet A, getransformeerd in de overeenkomstige keten Y, samengesteld uit symbolen van het alfabet B.

Een programmeertaal wordt, zoals elk complex systeem, gedefinieerd door een hiërarchie van concepten die de relaties tussen de elementen definieert. Deze concepten zijn met elkaar verbonden volgens syntactische regels. Elk programma dat volgens deze regels is gebouwd, heeft een overeenkomstige hiërarchische structuur.

In dit opzicht kunnen bovendien de volgende gemeenschappelijke kenmerken worden onderscheiden voor alle talen en hun programma's: elke taal moet regels bevatten die het mogelijk maken programma's te genereren die overeenkomen met deze taal of de correspondentie tussen geschreven programma's en een bepaalde taal te herkennen.

De relatie tussen programmastructuur en programmeertaal wordt genoemd syntactische mapping.

Beschouw als voorbeeld de relatie tussen een hiërarchische structuur en een reeks symbolen die de volgende rekenkundige uitdrukking definiëren:

In de meeste programmeertalen deze uitdrukking definieert een hiërarchie van programmaobjecten, die als een boom kan worden weergegeven (Fig. 1.1.):

De cirkels vertegenwoordigen symbolen die worden gebruikt als elementaire structuren, en de rechthoeken vertegenwoordigen samengestelde concepten die een hiërarchische en mogelijk recursieve structuur hebben. Deze hiërarchie wordt gedefinieerd met behulp van syntactische regels die zijn geschreven in een speciale taal die een metataal wordt genoemd (metatalen zullen in meer detail worden besproken bij het bestuderen van formele grammatica's):

<выражение> ::= <слагаемое> | <выражение> + <слагаемое>

<слагаемое> ::= <множитель> | <слагаемое> * <множитель>

<множитель> ::= <буква> | (<выражение>)

<буква>

Opmerking. Het teken "::=" wordt gelezen als "dit is". Pijp "|" leest als "of".

Als de regels anders zijn geschreven, dan is de hiërarchische structuur. Een voorbeeld is volgende methode regelinvoer:

<выражение> ::= <операнд> | <выражение> + < операнд > | <выражение> * < операнд >

<операнд> ::= <буква> | (<выражение>)

<буква>::= een | b | c | d | ik | f | g | h | ik | j | k | ik | m | n | o | p | q | r | s | t | jij | v | w | x | j | z

Als resultaat van het parseren van hetzelfde rekenkundige uitdrukking er zal een hiërarchische structuur worden opgebouwd, getoond in Fig. 1.2.

Opgemerkt moet worden dat de hiërarchische structuur in het algemene geval op geen enkele manier gerelateerd mag zijn aan de semantiek van de uitdrukking. In beide gevallen kan de prioriteit van bewerkingen worden geïmplementeerd in overeenstemming met algemeen aanvaarde regels, wanneer vermenigvuldiging voorafgaat aan optelling (of omgekeerd: alle bewerkingen kunnen onder elke reeks regels dezelfde prioriteit hebben). De eerste structuur ondersteunt echter duidelijk de verdere implementatie van de algemeen aanvaarde prioriteit, terwijl de tweede meer geschikt is om operaties met dezelfde prioriteit uit te voeren en deze van rechts naar links uit te voeren.

Het proces van het vinden van syntactische structuur gegeven programma genaamd ontleden.

Een syntactische structuur die in de ene taal correct is, kan in een andere taal onjuist zijn. In de Forth-taal wordt de gegeven uitdrukking bijvoorbeeld niet herkend. Voor deze taal is de juiste postfix-expressie echter:

De syntactische structuur wordt beschreven door de regels:

<выражение> ::= <буква> | <операнд> <операнд> <операция>

< операнд > ::= < буква > | < выражение >

< операция > ::= + | *

<буква>::= een | b | c | d | ik | f | g | h | ik | j | k | ik | m | n | o | p | q | r | s | t | jij | v | w | x | j | z

De hiërarchische boom die de syntactische structuur definieert, wordt weergegeven in Fig. 1.3.

Een ander kenmerkend kenmerk van alle talen is hun semantiek. Het bepaalt de betekenis van taalbewerkingen en de juistheid van de operanden. Ketens die dezelfde syntactische structuur hebben in verschillende programmeertalen kunnen qua semantiek verschillen (wat bijvoorbeeld wordt waargenomen in C++, Pascal, Basic voor het bovenstaande fragment van een rekenkundige uitdrukking).

Kennis van de semantiek van een taal stelt u in staat deze te scheiden van de syntaxis ervan en deze te gebruiken voor conversie naar een andere taal (om code te genereren).

Beschrijving van de semantiek en erkenning van de juistheid ervan is meestal het meest arbeidsintensieve en omvangrijke deel van de vertaler, omdat het noodzakelijk is om veel opties voor geldige combinaties van bewerkingen en operanden op te sommen en te analyseren.

Gegeneraliseerde vertalerstructuur

Gemeenschappelijke eigenschappen en patronen zijn inherent aan zowel verschillende programmeertalen als vertalers uit deze talen. Ze ondergaan vergelijkbare processen voor het converteren van de brontekst. Ondanks het feit dat de interactie van deze processen op verschillende manieren kan worden georganiseerd, is het mogelijk functies te identificeren waarvan de implementatie tot dezelfde resultaten leidt. Laten we dergelijke functies fasen van het vertaalproces noemen.

Laten we, gezien de gelijkenis tussen de compiler en de interpreter, eens kijken naar de fasen die in de compiler bestaan. Het benadrukt:

1. Lexicale analysefase.
2. Parseerfase bestaande uit:

• herkenning van syntactische structuur;
• semantische analyse, waarbij met tabellen wordt gewerkt, waarbij een tussenliggende semantische representatie wordt gegenereerd of objectmodel taal.

Fase voor het genereren van code, die:

• semantische analyse van componenten van een tussenrepresentatie of objectmodel van een taal;
• het vertalen van een tussenrepresentatie of objectmodel naar objectcode.

Naast de hoofdfasen van het vertaalproces zijn er ook aanvullende fasen mogelijk:

2a. Tussenliggende representatieverkennings- en optimalisatiefase, bestaande uit:

2a.1. het analyseren van de juistheid van de tussenrepresentatie;
2a.2. optimalisatie van de tussenrepresentatie.

3a. Fase van optimalisatie van objectcode.

De tolk verschilt doordat de fase van het genereren van code gewoonlijk wordt vervangen door de fase van het emuleren van elementen van een tussenrepresentatie of objectmodel van de taal. Bovendien optimaliseert de tolk de tussenrepresentatie meestal niet, maar emuleert deze onmiddellijk.

Bovendien is het mogelijk een proces van analyse en correctie van fouten in de verwerkte brontekst van het programma te onderscheiden dat uniform is voor alle fasen.

De algemene structuur van de compiler, rekening houdend met de fasen die erin bestaan, wordt weergegeven in Fig. 1.4.

Het bestaat uit een lexicale analysator, een parser, een codegenerator en een foutenanalysator. In plaats van een codegenerator gebruikt de tolk een emulator (Fig. 1.5), waarin, naast de elementen van de tussenrepresentatie, de brongegevens worden overgedragen. De uitvoer van de emulator is het resultaat van de berekeningen.

Een lexicale analysator (ook wel scanner genoemd) leest de invoerreeks van tekens en groepeert deze in elementaire structuren die lexemen worden genoemd. Elk token heeft een klasse en een betekenis. Kandidaten voor de rol van lexemen zijn doorgaans elementaire taalconstructies, bijvoorbeeld identificatie, reëel getal, commentaar. De resulterende tokens worden doorgegeven aan de parser. De scanner is geen verplicht onderdeel van de vertaler. U kunt er echter wel mee de efficiëntie van het vertaalproces verhogen. Lexicale analyse wordt in meer detail besproken in het onderwerp: “Organisatie van lexicale analyse.”

De parser ontleedt het bronprogramma met behulp van binnenkomende lexemen, construeert de syntactische structuur van het programma en semantische analyse met de vorming van een objectmodel van de taal. Het objectmodel vertegenwoordigt een syntactische structuur, aangevuld met semantische relaties tussen bestaande concepten. Deze verbindingen kunnen zijn:

• verwijzingen naar variabelen, gegevenstypen en procedurenamen die in naamtabellen zijn geplaatst;
• verbindingen die de volgorde van opdrachtuitvoering bepalen;
• verbindingen die het nesten van elementen van het taalobjectmodel en andere bepalen.

Dus de parser is behoorlijk complex blok vertaler. Daarom kan het worden onderverdeeld in de volgende componenten:

• herkenner;
• semantisch analyseblok;
• een objectmodel, of tussenrepresentatie, bestaande uit een tabel met namen en een syntactische structuur.

De algemene structuur van de parser wordt getoond in Fig. 1.6.

De herkenner ontvangt een reeks lexemen en voert op basis daarvan een parsering uit volgens de gebruikte regels. Tokens worden, na succesvol parseren van de regels, overgebracht naar de semantische analysator, die een tabel met namen opbouwt en fragmenten van de syntactische structuur registreert. Bovendien worden aanvullende semantische verbindingen vastgelegd tussen de namentabel en de syntactische structuur. Als gevolg hiervan wordt een objectmodel van het programma gevormd, bevrijd van binding aan de syntaxis van de programmeertaal. Heel vaak wordt in plaats van een syntactische structuur die de hiërarchie van taalobjecten volledig kopieert, een vereenvoudigde analoog gecreëerd, die een tussenrepresentatie wordt genoemd.

De foutanalysator ontvangt informatie over fouten die optreden in verschillende blokken vertaler. Met behulp van de ontvangen informatie genereert het berichten naar de gebruiker. Daarnaast, dit blok kan proberen de fout te corrigeren om de analyse verder voort te zetten. Tevens is hij verantwoordelijk voor acties die verband houden met het correct afwerken van het programma in het geval dat het niet mogelijk is de uitzending voort te zetten.

De codegenerator bouwt objectmachinecode op basis van analyse van het objectmodel of tussenrepresentatie. De constructie van de code gaat gepaard met extra semantische analyse, geassocieerd met de noodzaak om algemene opdrachten om te zetten in codes van een specifieke computer. In het stadium van een dergelijke analyse wordt uiteindelijk de mogelijkheid van transformatie bepaald en worden effectieve opties geselecteerd. Het genereren van code zelf is het hercoderen van het ene commando in het andere.

Opties voor interactie van vertaalblokken

De organisatie van vertaalprocessen, die de uitvoering van de hoofdfasen bepalen, kan op verschillende manieren worden uitgevoerd. Dit wordt bepaald door verschillende opties voor de interactie van vertaalblokken: lexicale analysator, parser en codegenerator. Ondanks hetzelfde eindresultaat bieden verschillende opties voor interactie met vertaalblokken verschillende opties voor het opslaan van tussentijdse gegevens. Er zijn twee hoofdopties voor de interactie van vertaalblokken:

• multi-pass-organisatie, waarbij elke fase een onafhankelijk proces is dat de controle pas overdraagt ​​aan de volgende fase na volledige verwerking van de gegevens;
• single-pass-organisatie, waarbij alle fasen één enkel proces vertegenwoordigen en gegevens in kleine fragmenten naar elkaar overbrengen.

Op basis van de twee hoofdopties kunt u er ook verschillende combinaties van maken.

Multi-pass organisatie van interactie tussen vertaalblokken

Deze versie van de interactie van blokken, waarbij de compiler als voorbeeld wordt gebruikt, wordt weergegeven in figuur 1.7.

De lexicale analysator verwerkt de brontekst volledig en vormt een uitvoerketen die bestaat uit alle ontvangen lexemen. Pas daarna wordt de controle overgedragen aan de parser. De parser ontvangt de gegenereerde keten van lexemen en vormt op basis daarvan een tussenrepresentatie of objectmodel. Na ontvangst van het volledige objectmodel geeft het de besturing door aan de codegenerator. De codegenerator bouwt op basis van het taalobjectmodel de benodigde machinecode

De voordelen van deze aanpak zijn onder meer:

1. Isolatie van individuele fasen, waardoor hun onafhankelijke implementatie en gebruik mogelijk is.
2. De mogelijkheid om gegevens die zijn verkregen als gevolg van de werking van elke fase op externe opslagapparaten op te slaan en deze indien nodig te gebruiken.
3. De mogelijkheid om de hoeveelheid RAM die nodig is om de vertaler te bedienen te verminderen door fasen opeenvolgend aan te roepen.

De nadelen zijn onder meer:

1. De aanwezigheid van grote hoeveelheden tussentijdse informatie, waaruit dit moment Er is slechts een klein deel van de tijd nodig.
2. Vertraging van de uitzendsnelheid als gevolg van opeenvolgende uitvoering van fasen en het gebruik van externe opslagapparaten om RAM te besparen.

Deze aanpak kan handig zijn bij het construeren van vertalers uit programmeertalen met een complexe syntactische en semantische structuur (bijvoorbeeld PL/I). In dergelijke situaties is vertaling moeilijk in één keer uit te voeren, dus is het gemakkelijker om de resultaten van eerdere passages weer te geven als aanvullende tussentijdse gegevens. Opgemerkt moet worden dat de complexe semantische en syntactische structuren van de taal kunnen resulteren in extra passages die nodig zijn om de vereiste afhankelijkheden vast te stellen. Het totale aantal passen kan meer dan tien zijn. Het aantal passen kan ook worden beïnvloed door het gebruik van specifieke taalfuncties door het programma, zoals het declareren van variabelen en procedures nadat ze zijn gebruikt, het toepassen van standaarddeclaratieregels, enzovoort.

Single-pass organisatie van interactie tussen vertaalblokken

Een van de opties voor interactie van compilerblokken met een single-pass-organisatie wordt gepresenteerd in Fig. 1.8.

In dit geval verloopt het vertaalproces als volgt. De lexicale analysator leest een fragment van de brontekst dat nodig is om één lexeme te verkrijgen. Nadat het token is gevormd, wordt de parser aangeroepen en wordt het gemaakte token als parameter doorgegeven. Als de parser het volgende element van de tussenrepresentatie kan construeren, doet hij dat en geeft hij het geconstrueerde fragment door aan de codegenerator. Anders geeft de parser de controle terug aan de scanner, waardoor duidelijk wordt dat het volgende token is verwerkt en dat er nieuwe gegevens nodig zijn.

De codegenerator werkt op een vergelijkbare manier. Gebaseerd op het ontvangen fragment van de tussenrepresentatie, creëert het het overeenkomstige fragment van de objectcode. Hierna keert de controle terug naar de parser.

Na voltooiing van de brontekst en voltooiing van de verwerking van alle tussenliggende gegevens door elk van de blokken, initieert de lexicale analysator het programmabeëindigingsproces.

Meestal gebruiken single-pass-vertalers een ander besturingsschema, waarbij de parser de rol van het hoofdblok speelt (Fig. 1.9).

De lexicale analysator en codegenerator fungeren als subroutines die worden opgeroepen. Zodra de parser nog een token nodig heeft, roept hij de scanner aan. Bij ontvangst van een fragment van een tussenrepresentatie wordt een oproep gedaan naar de codegenerator. De voltooiing van het vertaalproces vindt plaats nadat het laatste token is ontvangen en verwerkt en wordt geïnitieerd door de parser.

De voordelen van een single-pass-schema zijn onder meer de afwezigheid van grote hoeveelheden tussentijdse gegevens, een hoge verwerkingssnelheid als gevolg van de combinatie van fasen in een enkel proces en de afwezigheid van toegang tot externe opslagapparaten.

De nadelen zijn onder meer: ​​de onmogelijkheid om een ​​dergelijk vertaalschema te implementeren voor talen met complexe structuren en het gebrek aan tussenliggende gegevens die kunnen worden gebruikt voor complexe analyse en optimalisatie.

Dit schema wordt vaak gebruikt voor programmeertalen die eenvoudig zijn in semantische en syntactische structuren, zowel in compilers als in interpreters. Voorbeelden van dergelijke talen zijn Basic en Pascal. Een klassieke tolk wordt meestal gebouwd met behulp van een one-pass-schema, omdat directe uitvoering wordt uitgevoerd op het niveau van individuele fragmenten van de tussenrepresentatie. De organisatie van de interactie tussen blokken van een dergelijke tolk wordt getoond in Fig. 1.10.

Gecombineerde interacties van vertaalblokken

Combinaties van multi-pass en single-pass vertaalschema's geven aanleiding tot een verscheidenheid aan gecombineerde opties, waarvan er vele met succes worden gebruikt. Als voorbeeld kunnen we er enkele beschouwen.

In afb. Figuur 1.11 toont een diagram van de interactie van vertaalblokken, waarbij het hele proces in twee fasen wordt verdeeld. De eerste doorgang genereert een volledige tussenweergave van het programma, en de tweede genereert code. Met een dergelijk schema kunt u de vertaler eenvoudig van het ene computersysteem naar het andere overbrengen door de codegenerator te herschrijven.

Bovendien is het in plaats van een codegenerator eenvoudig om een ​​tussenliggende representatie-emulator aan te sluiten, waarmee u eenvoudigweg een programmeersysteem in een bepaalde taal kunt ontwikkelen, gericht op verschillende uitvoeringsomgevingen. Een voorbeeld van een dergelijke organisatie van interactie tussen vertaalblokken wordt getoond in Fig. 1.12.

Naast schema's waarbij de codegenerator wordt vervangen door een emulator, zijn er vertalers die dit toestaan delen. Een van dergelijke schema's wordt getoond in Fig. 1.13.

Het vertaalproces, inclusief het genereren van code, kan in een willekeurig aantal passages worden voltooid (in het voorbeeld wordt de eerder gepresenteerde vertaling in één passage gebruikt). De gegenereerde objectcode wordt echter niet op het betreffende computersysteem uitgevoerd, maar geëmuleerd op een computer met een andere architectuur. Dit schema wordt gebruikt in een omgeving die rond een taal is opgebouwd Java-programmering. De vertaler genereert zelf de code Virtuele Java-machine, waarvan de emulatie met speciale middelen wordt uitgevoerd, zowel autonoom als in een internetbrowseromgeving.

Het gepresenteerde schema kan ook een bredere interpretatie hebben in relatie tot elke compiler die machinecode genereert. Het punt is dat de meeste moderne computers worden geïmplementeerd met behulp van microprogrammabesturing. Een kan worden beschouwd als een programma dat machinecode emuleert. Dit stelt ons in staat om te praten over het wijdverbreide gebruik van het laatst gepresenteerde schema.

Testvragen en opdrachten

1. Noem de verschillen:

• tolk van de compiler;
• compiler van assembler;
• vertaler transcoder;
• emulator van tolk;
• syntaxis van semantiek.

1. Vertel ons over de nieuwste ontwikkelingen op het gebied van programmeertalen die u kent. Geef de belangrijkste kenmerken van deze talen.
2. Brengen specifieke voorbeelden gebruik van vertaalmethoden op gebieden die geen verband houden met programmeertalen.
3. Geef specifieke voorbeelden van gecompileerde programmeertalen.
4. Geef specifieke voorbeelden van geïnterpreteerde programmeertalen.
5. Geef specifieke voorbeelden van programmeertalen waarvoor zowel compilers als tolken beschikbaar zijn.
6. De belangrijkste voor- en nadelen van compilers.
7. De belangrijkste voor- en nadelen van tolken.
8. Beschrijf de belangrijkste verschillen in de syntaxis van de twee programmeertalen die je kent.
9. Beschrijf de belangrijkste verschillen in de semantiek van de twee programmeertalen die je kent.
10. Noem de belangrijkste fasen van het vertaalproces en hun doel.
11. Noem de specifieke kenmerken van single-pass vertaling.
12. Noem de specifieke kenmerken van multi-pass vertaling.
13. Geef voorbeelden van mogelijke combinaties van single-pass en multi-pass vertaling. Vertel ons over praktisch gebruik deze schema's.

Programmeertalen kunnen worden onderverdeeld in gecompileerd en geïnterpreteerd.

Een programma in een gecompileerde taal wordt, met behulp van een speciaal compilerprogramma, omgezet (gecompileerd) in een reeks instructies voor een bepaald type processor (machinecode) en vervolgens geschreven in een uitvoerbare module, die kan worden gestart voor uitvoering als apart programma. Met andere woorden: de compiler vertaalt de programmabroncode van een programmeertaal op hoog niveau naar binaire codes van processorinstructies.

Als een programma in een geïnterpreteerde taal is geschreven, voert (interpreteert) de tolk de brontekst rechtstreeks uit, zonder voorafgaande vertaling. In dit geval blijft het programma in de oorspronkelijke taal en kan het niet zonder tolk worden gestart. We kunnen zeggen dat een computerprocessor een tolk van machinecode is.

Kortom, de compiler vertaalt de broncode van het programma onmiddellijk en in zijn geheel naar machinetaal, terwijl er een aparte uitvoerbaar programma, en de tolk voert de brontekst rechtstreeks uit tijdens de uitvoering van het programma.

De indeling in gecompileerde en geïnterpreteerde talen is enigszins willekeurig. Dus voor elke traditioneel gecompileerde taal, zoals Pascal, kun je een tolk schrijven. Bovendien voeren de meeste moderne "pure" tolken taalconstructies niet rechtstreeks uit, maar compileren ze deze eerder in een tussenrepresentatie op hoog niveau (bijvoorbeeld met dereferentie van variabelen en macro-uitbreiding).

Voor elke geïnterpreteerde taal kan een compiler worden gemaakt - de Lisp-taal, die native wordt geïnterpreteerd, kan bijvoorbeeld zonder enige beperking worden gecompileerd. Code die tijdens de uitvoering van een programma wordt gegenereerd, kan ook tijdens de uitvoering dynamisch worden gecompileerd.

In de regel worden gecompileerde programma's sneller uitgevoerd en zijn er geen extra programma's voor nodig, omdat ze al in machinetaal zijn vertaald. Tegelijkertijd moet elke keer dat de programmatekst wordt gewijzigd, deze opnieuw worden samengesteld, wat problemen veroorzaakt tijdens de ontwikkeling. Bovendien kan het gecompileerde programma alleen worden uitgevoerd op hetzelfde type computer, en meestal onder hetzelfde besturingssysteem, waarvoor de compiler is ontworpen. Om een ​​uitvoerbaar bestand voor een ander type machine te maken, is een nieuwe compilatie vereist.

Geïnterpreteerde talen hebben een aantal specifieke kenmerken extra functies(zie hierboven), bovendien kunnen programma's daarover onmiddellijk na de verandering worden gelanceerd, wat de ontwikkeling vergemakkelijkt. Vaak kan een programma in een geïnterpreteerde taal worden uitgevoerd verschillende soorten auto's en besturingssystemen zonder extra inspanning.

Geïnterpreteerde programma's werken echter merkbaar langzamer dan gecompileerde programma's, en ze kunnen niet worden uitgevoerd zonder een extra tolkprogramma.

Sommige talen, zoals Java en C#, bevinden zich tussen gecompileerd en geïnterpreteerd. Het programma wordt namelijk niet gecompileerd in machinetaal, maar in machine-onafhankelijke code op laag niveau, bytecode. De bytecode wordt vervolgens uitgevoerd door de virtuele machine. Meestal wordt interpretatie gebruikt om bytecode uit te voeren, hoewel afzonderlijke delen ervan tijdens de uitvoering van het programma direct in machinecode kunnen worden vertaald met behulp van Just-in-time compilatie (JIT) om het programma te versnellen. Voor Java wordt de bytecode uitgevoerd door de Java Virtual Machine (JVM), voor C# door de Common Language Runtime.

Met deze aanpak kunt u in zekere zin gebruikmaken van de voordelen van zowel tolken als compilers. Het is ook de moeite waard om de originele Forth-taal te vermelden, die zowel een tolk als een compiler heeft.

Omdat tekst geschreven in een programmeertaal onbegrijpelijk is voor een computer, moet deze worden vertaald in machinecode. Een dergelijke vertaling van een programma van een programmeertaal naar een machinecodetaal wordt vertaling genoemd en wordt uitgevoerd speciale programma's- vertalers.

Een vertaler is een serviceprogramma dat een bronprogramma in de invoerprogrammeertaal omzet in een werkprogramma dat in een objecttaal wordt gepresenteerd.

Momenteel zijn vertalers onderverdeeld in drie hoofdgroepen: assembleurs, compilers en tolken.

Een assembler is een systeemhulpprogramma dat symbolische structuren omzet in machinetaalopdrachten. Een specifiek kenmerk van assembleurs is dat ze een woordelijke vertaling van één symbolische instructie naar één machine-instructie uitvoeren. Daarom is assembleertaal (ook wel autocode genoemd) ontworpen om de perceptie van het computerbesturingssysteem te vergemakkelijken en het programmeren in dit commandosysteem te versnellen. Het is voor een programmeur veel gemakkelijker om de geheugensteun van machine-instructies te onthouden dan de binaire code ervan.

Tegelijkertijd bevat assembleertaal, naast analogen van machineopdrachten, veel aanvullende richtlijnen die met name het beheer van computerbronnen vergemakkelijken, het schrijven van herhalende fragmenten en het bouwen van programma's met meerdere modules. Daarom is de expressiviteit van de taal veel rijker dan alleen een symbolische codeertaal, wat de programmeerefficiëntie aanzienlijk verbetert.

Een compiler is een serviceprogramma dat een programma dat in de bronprogrammeertaal is geschreven, vertaalt naar machinetaal. Net als een assembler converteert een compiler een programma van de ene taal naar de andere (meestal naar de taal van een specifieke computer). Tegelijkertijd verschillen brontaalopdrachten qua organisatie en kracht aanzienlijk van machinetaalopdrachten. Er zijn talen waarin één commando van de brontaal wordt vertaald in 7-10 machineopdrachten. Er zijn echter ook talen waarin elke opdracht 100 of meer machineopdrachten kan hebben (bijvoorbeeld Prolog). Bovendien gebruiken de brontalen vrij vaak strikte gegevenstypering, uitgevoerd via hun voorlopige beschrijving. Programmeren berust mogelijk niet op het coderen van een algoritme, maar op het zorgvuldig nadenken over datastructuren of klassen. Het vertaalproces vanuit dergelijke talen wordt meestal compilatie genoemd, en de brontalen worden meestal geclassificeerd als programmeertalen op hoog niveau (of talen op hoog niveau). De abstractie van een programmeertaal van het computerbesturingssysteem leidde tot de onafhankelijke creatie van een grote verscheidenheid aan talen gericht op het oplossen van specifieke problemen. Er zijn talen verschenen voor wetenschappelijke berekeningen, economische berekeningen, toegang tot databases en meer.

Tolk - een programma of apparaat dat de vertaling en uitvoering van het bronprogramma per operator uitvoert. In tegenstelling tot een compiler produceert een tolk geen machinetaalprogramma als uitvoer. Nadat het een commando in de brontaal heeft herkend, voert het het onmiddellijk uit. Zowel compilers als tolken gebruiken dezelfde methoden voor het analyseren van de broncode van een programma. Maar met de tolk kunt u beginnen met het verwerken van gegevens nadat u zelfs maar één opdracht hebt geschreven. Dit maakt het proces van het ontwikkelen en debuggen van programma's flexibeler. Bovendien maakt de afwezigheid van uitvoermachinecode het mogelijk om externe apparaten niet te "vervuilen" met extra bestanden, en de tolk zelf kan vrij gemakkelijk worden aangepast aan elke machine-architectuur, omdat deze slechts één keer is ontwikkeld in een veelgebruikte programmeertaal. Daarom zijn geïnterpreteerde talen zoals Java Script en VB Script wijdverbreid geworden. Het nadeel van tolken is de lage snelheid van programma-uitvoering. Normaal gesproken draaien geïnterpreteerde programma's 50 tot 100 keer langzamer dan native programma's.

Een emulator is een programma of software- en hardwaretool die de mogelijkheid biedt om, zonder herprogrammering, op een bepaalde computer een programma uit te voeren dat codes of methoden gebruikt voor het uitvoeren van bewerkingen die verschillen van die op de gegeven computer. Een emulator lijkt op een tolk, omdat deze rechtstreeks een programma uitvoert dat in een bepaalde taal is geschreven. Meestal is het echter machinetaal of tussencode. Beide vertegenwoordigen instructies in binaire code die onmiddellijk kunnen worden uitgevoerd nadat de bewerkingscode is herkend. In tegenstelling tot tekstprogramma's is het niet nodig de programmastructuur te herkennen of operanden te selecteren.

Emulators worden vrij vaak voor verschillende doeleinden gebruikt. Bij het ontwikkelen van nieuwe computersystemen wordt bijvoorbeeld eerst een emulator gemaakt die programma's uitvoert die zijn ontwikkeld voor computers die nog niet bestaan. Hierdoor kunt u het besturingssysteem evalueren en de basissoftware ontwikkelen nog voordat de bijbehorende hardware is gemaakt.

Heel vaak wordt een emulator gebruikt om oude programma's op nieuwe computers uit te voeren. Nieuwere computers zijn doorgaans sneller en hebben betere randapparatuur. Hierdoor kunt u oudere programma's efficiënter emuleren dan deze op oudere computers uit te voeren.

Een transcoder is een programma of softwareapparaat dat programma's die in de machinetaal van de ene computer zijn geschreven, vertaalt naar programma's in de machinetaal van een andere computer. Als de emulator een minder intelligente analoog van de tolk is, handelt de transcoder in dezelfde hoedanigheid ten opzichte van de compiler. Op dezelfde manier wordt broncode (en meestal binaire) machinecode of een tussenrepresentatie omgezet in andere soortgelijke code met een enkele instructie en zonder enige algemene analyse van de structuur van het bronprogramma. Transcoders zijn handig bij het overbrengen van programma's van de ene computerarchitectuur naar de andere. Ze kunnen ook worden gebruikt om programmatekst op hoog niveau te reconstrueren op basis van bestaande binaire code.

Een macroprocessor is een programma dat de ene reeks tekens vervangt door een andere. Dit is een soort compiler. Het genereert uitvoertekst door speciale invoegingen in de brontekst te verwerken. Deze inserts zijn op een speciale manier ontworpen en behoren tot constructies van een taal die macrotaal wordt genoemd. Macroprocessors worden vaak gebruikt als add-ons voor programmeertalen, waardoor de functionaliteit van programmeersystemen wordt vergroot. Bijna elke assembler bevat een macroprocessor, die de efficiëntie van het ontwikkelen van machineprogramma's verhoogt. Dergelijke programmeersystemen worden gewoonlijk macroassemblers genoemd.

Macroprocessors worden ook gebruikt bij talen op hoog niveau. Ze vergroten de functionaliteit van talen zoals PL/1, C, C++. Macroprocessors worden vooral veel gebruikt in C en C++, waardoor het gemakkelijker wordt om programma's te schrijven. Macroprocessors verbeteren de programmeerefficiëntie zonder de syntaxis of semantiek van de taal te veranderen.

Syntaxis is een reeks regels van een taal die de vorming van de elementen ervan bepalen. Met andere woorden: dit is een reeks regels voor de vorming van semantisch significante reeksen symbolen in een bepaalde taal. Syntaxis wordt gespecificeerd met behulp van regels die de concepten van een taal beschrijven. Voorbeelden van concepten zijn: variabele, expressie, operator, procedure. De volgorde van concepten en hun acceptabele gebruik in regels bepaalt de syntactisch correcte structuren waaruit programma's bestaan. Het is de hiërarchie van objecten, en niet hoe ze met elkaar omgaan, die wordt gedefinieerd door middel van syntaxis. Een statement kan bijvoorbeeld alleen voorkomen in een procedure, een expressie in een statement, een variabele kan bestaan ​​uit een naam en optionele indices, etc. De syntaxis wordt in het programma niet geassocieerd met verschijnselen als ‘naar een niet-bestaand label springen’ of ‘een variabele met de opgegeven naam is niet gedefinieerd’. Dit is wat semantiek doet.

Semantiek - regels en voorwaarden die de relaties tussen taalelementen en hun semantische betekenissen bepalen, evenals de interpretatie van de betekenisvolle betekenis van syntactische constructies van de taal. Objecten van een programmeertaal worden niet alleen volgens een bepaalde hiërarchie in de tekst geplaatst, maar zijn ook nog eens met elkaar verbonden via andere concepten die verschillende associaties vormen. Een variabele, waarvoor de syntaxis alleen in declaraties en sommige instructies een geldige locatie definieert, heeft bijvoorbeeld een specifiek type, kan met een beperkt aantal bewerkingen worden gebruikt, heeft een adres en een grootte en moet worden gedeclareerd voordat deze kan worden gedeclareerd. worden gebruikt in het programma.

Een parser is een compilercomponent die broninstructies controleert op naleving van de syntactische regels en semantiek van een bepaalde programmeertaal. Ondanks zijn naam controleert de analysator zowel de syntaxis als de semantiek. Het bestaat uit verschillende blokken, die elk hun eigen problemen oplossen. Het zal in meer detail worden besproken bij het beschrijven van de structuur van de vertaler. vertaler compiler taalprogrammering

Elke vertaler voert de volgende hoofdtaken uit:

• - analyseert het vertaalde programma, en bepaalt met name of het syntaxisfouten bevat;
• - genereert een uitvoerprogramma (vaak een objectprogramma genoemd) in machineopdrachttaal;
• - wijst geheugen toe voor het objectprogramma.1.1 Tolken

Een vaak genoemd voordeel van de interpretatieve implementatie is dat deze een "onmiddellijke modus" mogelijk maakt. In de directe modus kunt u de computer een taak als PRINT 3.14159*3/2.1 vragen en krijgt u het antwoord terug zodra u op drukt Enter toets(Hierdoor kan een computer van $ 3.000 worden gebruikt als rekenmachine van $ 10). Bovendien hebben tolken speciale kenmerken die het debuggen eenvoudiger maken. U kunt bijvoorbeeld de verwerking van een tolkprogramma onderbreken, de inhoud van bepaalde variabelen weergeven, het programma doorbladeren en vervolgens doorgaan met de uitvoering.

Wat programmeurs het leukst vinden aan tolken, is de mogelijkheid om snel antwoord te krijgen. Compilatie is hier niet nodig, omdat de tolk altijd klaar staat om zich met uw programma te bemoeien. Typ RUN en het resultaat van uw meest recente wijziging verschijnt op het scherm.

Tolktalen hebben echter nadelen. Het is bijvoorbeeld noodzakelijk om te allen tijde een kopie van de tolk in het geheugen te hebben, terwijl veel van de mogelijkheden van de tolk, en dus zijn mogelijkheden, misschien niet nodig zijn voor de uitvoering van een bepaald programma.

Een subtiel nadeel van tolken is dat ze de neiging hebben een goede programmeerstijl te ontmoedigen. Omdat opmerkingen en andere geformaliseerde details een aanzienlijke hoeveelheid programmageheugen in beslag nemen, zijn mensen geneigd deze niet te gebruiken. De duivel is minder woedend dan een programmeur die in tolk BASIC werkt en probeert een programma van 120K in 60K geheugen te krijgen. maar het ergste is dat de tolken traag zijn.

Ze besteden te veel tijd aan het uitzoeken wat ze moeten doen, in plaats van het werk daadwerkelijk te doen. Bij het optreden programma-exploitanten, moet de tolk eerst elke verklaring scannen om de inhoud ervan te lezen (wat vraagt ​​deze persoon mij te doen?) en vervolgens de gevraagde handeling uit te voeren. Operators in lussen worden overmatig gescand.

Beschouw het programma: in interpreter BASIC 10 FOR N=1 TO 1000 20 PRINT N,SQR(N) 30 NEXT N De eerste keer dat u dit programma doorloopt, moet de BASIC Interpreter uitzoeken wat regel 20 betekent:

• 1. converteer numerieke variabele N naar string
• 2. stuur een string naar het scherm
• 3. ga naar het volgende afdrukgebied
• 4. bereken de vierkantswortel van N
• 5. converteer het resultaat naar een string
• 6. stuur een string naar het scherm

Tijdens de tweede passage van de cyclus wordt al dit oplossen opnieuw herhaald, omdat alle resultaten van het bestuderen van deze lijn enkele milliseconden geleden volledig zijn vergeten. En zo verder voor alle volgende 998-passen. Het is duidelijk dat als je de fase van scannen/begrijpen op de een of andere manier zou kunnen scheiden van de fase van uitvoering, je meer zou hebben snel programma. En dit is precies waar compilers voor zijn.