• Adres. Een functioneel apparaat dat een virtueel adres (Engels virtueel adres) omzet in een echt adres.
• Dialoogvenster. Biedt het gebruik van een programmeertaal in timesharing-modus.
• multipass. Genereert een objectmodule over verschillende weergaven van het bronprogramma.
• Rug. Zelfde als relais. Zie ook: decompiler, disassembler.
• enkele pas. Genereert een objectmodule in één sequentiële scan van het bronprogramma.
• Optimaliseren. Voert code-optimalisaties uit in de gegenereerde objectmodule.
• Syntactisch georiënteerd (syntaxisgestuurd). Het ontvangt als invoer een beschrijving van de syntaxis en semantiek van de taal en de tekst in de beschreven taal, die wordt vertaald in overeenstemming met de opgegeven beschrijving.
• test. Een set assembler-macro's waarmee u verschillende foutopsporingsprocedures kunt instellen in programma's die in assembler zijn geschreven.

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

Processortaal (machinecode) is meestal laag niveau. Er zijn platforms die machinetaal op hoog niveau gebruiken (bijvoorbeeld iAPX-432), maar deze vormen een uitzondering op de regel vanwege de complexiteit en de kosten. Een vertaler die programma's omzet in machinetaal die direct door de processor wordt geaccepteerd en uitgevoerd, wordt genoemd compiler.

Het compilatieproces bestaat meestal uit verschillende fasen: lexicale, syntactische en semantische analyses (Engelse semantische analyse), generatie van intermediaire code, optimalisatie en generatie van de resulterende machinecode. Bovendien is het programma meestal afhankelijk van services die worden geleverd door het besturingssysteem en bibliotheken van derden (bijvoorbeeld bestands-I/O of een grafische interface), en de systeemeigen code van het programma moet aan deze services worden gekoppeld. Het koppelen met statische bibliotheken wordt gedaan door de linker of linker (dit kan een op zichzelf staand programma zijn of onderdeel van de compiler), terwijl het koppelen met het besturingssysteem en dynamische bibliotheken wordt gedaan wanneer de loader het programma begint uit te voeren.

Compilervoordeel: het programma wordt één keer gecompileerd en er zijn geen extra transformaties nodig voor elke uitvoering. Dienovereenkomstig is er geen compiler vereist op de doelcomputer waarvoor het programma wordt 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: tolk helemaal geen vertaling. De tolk simuleert programmatisch een machine waarvan de fetch-execute-lus werkt op instructies in talen op hoog niveau in plaats van machine-instructies. Dergelijke softwaremodellering creëert een virtuele machine die de taal implementeert. Deze benadering wordt pure interpretatie genoemd. Zuivere tolken wordt meestal gebruikt voor talen met een eenvoudige structuur (bijvoorbeeld APL of Lisp). Opdrachtregelinterpreters verwerken opdrachten in scripts op UNIX of in batchbestanden (.bat) op MS-DOS, meestal ook in pure interpretatiemodus.

Het voordeel van een pure tolk: de afwezigheid van tussenhandelingen voor vertaling vereenvoudigt de implementatie van de tolk en maakt het gebruiksvriendelijker, ook in de interactieve modus. Het nadeel is dat de interpreter beschikbaar moet zijn op de doelcomputer waarop het programma moet worden uitgevoerd.

Er zijn opties voor de implementatie van programmeertalen die gecompromitteerd zijn tussen compilatie en pure interpretatie, wanneer de tolk, voordat hij het programma uitvoert, het vertaalt in een tussentaal (bijvoorbeeld in bytecode of p-code), wat meer is handig voor tolken (dat wil zeggen, we hebben het over een tolk met een ingebouwde vertaler) . Deze methode wordt gemengde implementatie genoemd. Perl is een voorbeeld van een gemengde taalimplementatie. Deze benadering combineert zowel de voordelen van een compiler als een interpreter (hoge uitvoeringssnelheid en gebruiksgemak) en nadelen (er zijn extra middelen nodig om het programma in een tussentaal te vertalen en op te slaan; er moet een tolk worden geleverd om het programma op de doelmachine). Ook, zoals in het geval van een compiler, vereist een gemengde implementatie dat de broncode vóór uitvoering geen fouten bevat (lexicaal, syntactisch en semantisch).

Uitzending en interpretatie- verschillende processen: vertaling houdt zich bezig met het vertalen van programma's van de ene taal naar de andere, en vertolking is verantwoordelijk voor de uitvoering van programma's. Aangezien het doel van vertalen echter meestal is om het programma voor te bereiden op vertolking, worden deze processen meestal samen beschouwd. Zo worden programmeertalen vaak gekenmerkt als "gecompileerd" of "geïnterpreteerd", afhankelijk van of het gebruik van de taal wordt gedomineerd door compilatie of interpretatie. Bovendien worden bijna alle programmeertalen van een laag niveau en van de derde generatie, zoals assembler, C of Modula-2, gecompileerd en worden talen van een hoger niveau, zoals Python of SQL, geïnterpreteerd.

Aan de andere kant is er een vervlechting van vertaal- en interpretatieprocessen: tolken kunnen compileren (ook met dynamische compilatie), en vertalers kunnen interpretatie nodig hebben voor metaprogrammeringsconstructies (bijvoorbeeld voor macro's in assembler, voorwaardelijke compilatie in C, of voor sjablonen in C++).

Bovendien kan dezelfde programmeertaal zowel vertaald als geïnterpreteerd worden, en in beide gevallen moeten er gemeenschappelijke stadia zijn van analyse en herkenning van constructies en richtlijnen van de brontaal. Dit geldt voor zowel software- als hardware-implementaties - bijvoorbeeld processors van de x86-familie, voordat ze machinetaalinstructies uitvoeren, ze decoderen, operandvelden (registers, geheugenadressen, directe waarden), bitdiepte, enz. in opcodes en in processors Pentium met NetBurst-architectuur, wordt machinecode over het algemeen vertaald in een reeks micro-operaties voordat deze wordt opgeslagen in de interne cache.

Elke computer heeft zijn eigen programmeertaal - instructietaal of machinetaal - en kan alleen programma's uitvoeren die in die taal zijn geschreven. Met behulp van machinetaal is het in principe mogelijk om elk algoritme te beschrijven, maar de programmeerkosten zullen extreem hoog zijn. Dit komt door het feit dat u met de machinetaal alleen primitieve gegevensstructuren kunt beschrijven en verwerken - bit, byte, woord. Programmeren in machinecodes vereist buitensporige programmadetails en is alleen beschikbaar voor programmeurs die het ontwerp en de werking van de computer goed kennen. Deze moeilijkheid werd overwonnen door talen op hoog niveau (Fortran, PL/1, Pascal, C, Ada, enz.) Met geavanceerde datastructuren en middelen om ze te verwerken, onafhankelijk van de taal van een bepaalde computer.

Algoritmische talen op hoog niveau stellen de programmeur in staat om algoritmen te beschrijven voor het eenvoudig en gemakkelijk oplossen van veel toegepaste problemen. Zo'n beschrijving heet origineel programma, en de taal op hoog niveau is invoertaal.

taalverwerker verwijst naar een machinetaalprogramma waarmee een computer programma's in de invoertaal kan begrijpen en uitvoeren. Er zijn twee hoofdtypen taalverwerkers: tolken en vertalers.

Tolk is een programma dat een programma in de invoertaal als invoer accepteert en, naarmate de invoertaalconstructies worden herkend, deze implementeert, waarbij aan de uitvoer de resultaten worden geproduceerd van de berekeningen die door het bronprogramma zijn voorgeschreven.

Vertaler is een programma dat een bronprogramma aan de ingang toelaat en aan de uitgang een programma genereert dat functioneel equivalent is aan het originele, genaamd voorwerp. Een objectprogramma is geschreven in een objecttaal. In een bepaald geval kan de machinetaal als objecttaal dienen en in dit geval kan het aan de output van de vertaler verkregen programma onmiddellijk op een computer worden uitgevoerd (geïnterpreteerd). In dit geval is de computer een vertolker van het objectprogramma in machinecodes. Over het algemeen hoeft de objecttaal geen machinetaal of in de buurt daarvan te zijn (autocode). Een objecttaal kan wat zijn tussentaal is een taal die tussen de invoer- en machinetalen ligt.

Als een tussentaal als objecttaal wordt gebruikt, zijn er twee opties voor het construeren van een vertaler.

De eerste optie is dat er voor de tussentaal een andere vertaler is (of wordt ontwikkeld) van de tussentaal naar de machinetaal, en deze wordt gebruikt als het laatste blok van de geprojecteerde vertaler.

De tweede optie voor het bouwen van een vertaler met een tussentaal is om een ​​intermediaire taalcommando-interpreter te bouwen en deze als het laatste blok van de vertaler te gebruiken. Het voordeel van tolken komt tot uiting in foutopsporing en dialoogvertalers die het werk van de gebruiker in dialoogmodus leveren, tot het aanbrengen van wijzigingen in het programma zonder het opnieuw volledig opnieuw te vertalen.

Tolken worden ook gebruikt bij programma-emulatie, d.w.z. uitvoering op een technologische machine van programma's die zijn geschreven voor een andere (objectieve) machine. Deze optie wordt met name gebruikt bij het debuggen van universele computerprogramma's die op een gespecialiseerde computer worden uitgevoerd.

Een vertaler die een bijna-machinetaal (autocode of assembler) als invoertaal gebruikt, wordt traditioneel genoemd assembler. De vertaler voor een taal op hoog niveau heet compiler.

Het bouwen van compilers heeft de afgelopen jaren aanzienlijke vooruitgang geboekt. De eerste compilers gebruikten de zogenaamde directe uitzendmethoden- dit zijn overwegend heuristische methoden, waarbij op basis van een algemeen idee voor elke taalconstructie een eigen algoritme werd ontwikkeld voor het vertalen naar een machine-equivalent. Deze methoden waren traag en niet structureel van aard.

De ontwerpmethodologie voor moderne compilers is gebaseerd op: compositie-syntaxisgestuurde methode taalverwerking. Samengesteld in de zin dat het proces van het converteren van een bronprogramma naar een objectprogramma wordt geïmplementeerd door het samenstellen van functioneel onafhankelijke afbeeldingen met expliciet onderscheiden invoer- en uitvoergegevensstructuren. Deze mappings zijn opgebouwd uit het beschouwen van het bronprogramma als een samenstelling van de belangrijkste aspecten (niveaus) van de beschrijving van de invoertaal: woordenschat, syntaxis, semantiek en pragmatiek, en het identificeren van deze aspecten van het bronprogramma tijdens de compilatie. Laten we deze aspecten eens bekijken om een ​​vereenvoudigd compilermodel te krijgen.

De basis van elke natuurlijke of kunstmatige taal is: alfabet– een reeks elementaire tekens die in de taal zijn toegestaan ​​(letters, cijfers en speciale tekens). Tekens kunnen worden gecombineerd in: de woorden- elementaire constructies van de taal, in de tekst (programma) beschouwd als ondeelbare symbolen die een bepaalde betekenis hebben.

Een woord kan ook een enkel teken zijn. In de Pascal-taal zijn woorden bijvoorbeeld id's, trefwoorden, constanten en scheidingstekens, in het bijzonder tekens van rekenkundige en logische bewerkingen, haakjes, komma's en andere symbolen. De woordenschat van de taal, samen met een beschrijving van hoe ze worden weergegeven, is vocabulaire taal.

Woorden in de taal worden gecombineerd tot complexere structuren - zinnen. In programmeertalen is de eenvoudigste zin de verklaring. Zinnen zijn opgebouwd uit woorden en eenvoudiger zinnen volgens de regels van de syntaxis. Syntaxis taal is een beschrijving van de juiste zinnen. Beschrijving van de betekenis van zinnen, d.w.z. betekenissen van woorden en hun interne verbindingen, is semantiek taal. Bovendien merken we op dat een bepaald programma enig effect heeft op de vertaler - pragmatisme. Samen vormen de syntaxis, semantiek en pragmatisme van de taalvorm semiotiek taal.

Het vertalen van een programma van de ene taal naar de andere bestaat in het algemeen uit het veranderen van het alfabet, de woordenschat en de syntaxis van de programmataal met behoud van de semantiek. Het proces van het vertalen van een bronprogramma naar een object is meestal verdeeld in verschillende onafhankelijke subprocessen (vertaalfasen), die worden geïmplementeerd door de overeenkomstige blokken van de vertaler. Het is handig om de belangrijkste fasen van vertaling te beschouwen als lexicale analyse, syntactische analyse, semantische analyse en

synthese van een objectprogramma. In veel echte compilers zijn deze fasen echter onderverdeeld in verschillende subfasen, en er kunnen ook andere fasen zijn (zoals optimalisatie van objectcode). Op afb. 1.1 toont een vereenvoudigd functioneel model van de vertaler.

Volgens dit model wordt het invoerprogramma allereerst onderworpen aan lexicale verwerking. Het doel van lexicale analyse is om het bronprogramma te vertalen in de interne taal van de compiler, waarin trefwoorden, identifiers, labels en constanten in hetzelfde formaat worden gebracht en vervangen door voorwaardelijke codes: numeriek of symbolisch, die descriptors worden genoemd. Elke descriptor bestaat uit twee delen: de klasse (type) van het token en een pointer naar het geheugenadres waar informatie over een bepaald token is opgeslagen. Meestal is deze informatie georganiseerd in tabellen. Gelijktijdig met de vertaling van het bronprogramma in de interne taal, in het stadium van lexicale analyse, lexicale controle- Identificatie van ontoelaatbare woorden in het programma.

De parser neemt de uitvoer van de lexicale analysator en vertaalt de reeks tokenpatronen in de vorm van een tussenprogramma. Een tussenprogramma is in wezen een weergave van de syntaxisstructuur van het programma. Dit laatste weerspiegelt de structuur van het oorspronkelijke programma, d.w.z. orde en communicatie tussen de operators. Tijdens de constructie van de syntaxisboom, syntaxis controle- detectie van syntactische fouten in het programma.

De feitelijke uitvoer van de ontleding kan een reeks opdrachten zijn die nodig zijn om een ​​tussenprogramma te bouwen, toegang te krijgen tot de opzoektabellen en indien nodig een diagnostisch bericht af te geven.

Rijst. 1.1. Vereenvoudigd functioneel model van de vertaler

De synthese van een objectprogramma begint in de regel met de toewijzing en toewijzing van geheugen voor de hoofdprogramma-objecten. Vervolgens wordt elke zin van het bronprogramma onderzocht en worden semantisch equivalente zinnen van de objecttaal gegenereerd. De syntaxisboom van het programma en de uitvoertabellen van de lexicale analysator worden hier gebruikt als invoerinformatie - de tabel met identifiers, de tabel met constanten en andere. Met boomanalyse kunt u de volgorde van gegenereerde opdrachten van het objectprogramma identificeren, en de tabel met identifiers bepaalt de soorten opdrachten die geldig zijn voor de waarden van de operanden in de gegenereerde opdrachten (bijvoorbeeld welke opdrachten moeten worden gegenereerd: vaste of drijvende komma, enz.).

De eigenlijke generatie van het objectprogramma wordt vaak voorafgegaan door: semantische analyse, die verschillende soorten semantische verwerking omvat. Eén type is het controleren van semantische conventies in een programma. Voorbeelden van dergelijke overeenkomsten: de uniciteit van de beschrijving van elke identifier in het programma, de definitie van een variabele wordt gemaakt voordat deze wordt gebruikt, enz. Semantische analyse kan worden uitgevoerd in latere vertaalfasen, zoals de programma-optimalisatiefase, die ook in de vertaler kan worden opgenomen. Het doel van optimalisatie is om de tijd of RAM-bronnen te verminderen die nodig zijn om een ​​objectprogramma uit te voeren.

Dit zijn de belangrijkste aspecten van het vertaalproces uit hogere talen. De organisatie van de verschillende fasen van vertaling en de bijbehorende praktische methoden voor hun wiskundige beschrijving worden hieronder in meer detail besproken.

Om van de ene taal naar de andere te vertalen, hebben programma's, net als mensen, een vertaler of, wetenschappelijk gezien, een vertaler nodig.

Vertaler: basisconcepten

Zo'n programma als vertaler is een taalkundige weergave van de berekeningen I ->P ->P (i). Een interpreter is een programma dat als invoer een programma P met enkele invoergegevens X neemt. Het voert P uit op X: I(P, x)=P(x). formeel systeem). Dit is een zeer belangrijke en diepgaande ontdekking van Turing. De processor is een tolk van programma's in machinetaal. Het is meestal te duur om tolken te schrijven voor talen op hoog niveau, dus worden ze vertaald in een vorm die gemakkelijker te interpreteren is. Sommige soorten vertalers hebben hele vreemde namen. Het programma vertaalt assembler-programma's naar machinetaal. Met de compiler kunt u vertalen van een taal op hoog niveau naar een taal op een lager niveau. Een vertaler is een programma dat een programma in een taal S als invoer neemt en na bewerking een programma in taal T produceert. Ze hebben dus allebei dezelfde semantiek: P->X->Q. Dus voor elke xP(x)=Q(x). Als je het hele programma vertaalt naar iets dat geïnterpreteerd wordt, dan wordt dit pre-execution compilatie of AOT-compilatie genoemd. AOT-compilers kunnen consistent worden gebruikt. De laatste hiervan is vaak assembler. Overweeg dus een voorbeeld: Broncode -> Compiler (vertaler) -> Assembler-code -> Assembler (vertaler) -> Machinecode -> CPU (tolk). Dynamische of online compilatie vindt plaats wanneer een deel van een programma wordt vertaald terwijl andere eerder gecompileerde delen worden uitgevoerd. JIT-vertalers onthouden wat ze al hebben gedaan, zodat ze de broncode niet steeds opnieuw hoeven te herhalen. Ze zijn zelfs in staat adaptieve compilatie en hercompilatie uit te voeren, die gebaseerd is op het gedrag van de runtime-omgeving van het programma. Veel talen bieden de mogelijkheid om code uit te voeren tijdens het vertalen en om nieuwe code te compileren tijdens de uitvoering van het programma.

Uitzending: podia

Het vertaalproces bestaat uit fasen van synthese en analyse. Schematisch ziet dit proces er als volgt uit: Broncode -> Analyser -> Conceptuele weergave -> Synthesizer (generator) -> Doelcode. Dit komt door de volgende redenen:

- elke andere methode past gewoon niet;

De vertaling werkt gewoon niet.

U kunt de volgende technische oplossing gebruiken: als u vertalers moet schrijven voor M brontalen en N doeltalen, hoeft u alleen M + N eenvoudige programma's (semi-compilers) te schrijven en geen MxN volledige (complexe) vertalers. In de praktijk is de conceptuele representatie echter zelden expressief en krachtig genoeg om alle bestaande doel- en brontalen te dekken. Hoewel sommige gebruikers er in de buurt hebben kunnen komen. Echte compilers doorlopen veel verschillende stadia. Wanneer u uw eigen compiler maakt, hoeft u niet al het harde werk opnieuw te doen dat programmeurs al hebben gedaan bij het maken van generatoren en views. U kunt uw taal rechtstreeks in JavaScript of C vertalen en bestaande C-compilers en JavaScript-engines gebruiken om de rest te doen. U kunt ook bestaande tussenaanzichten en virtuele machines gebruiken.

Opname van vertaler

Een vertaler kan een technisch hulpmiddel zijn of een programma dat drie talen gebruikt: bron, doel, basis. Je kunt ze in de T-vorm schrijven, waarbij je de bron aan de linkerkant, het doel aan de rechterkant en de basis eronder plaatst. Er zijn in totaal drie soorten compilers.

1. Een vertaler is een zelfcompiler als de brontaal overeenkomt met de basistaal.
2. Een compiler wordt self-resident genoemd als de doeltaal gelijk is aan de basistaal.
3. Als de doel- en basistalen verschillend zijn, dan is de vertaler een cross-compiler.

Waarom is het belangrijk om onderscheid te maken tussen dit soort compilers? Zelfs als je nooit een echt goede compiler bouwt, is het goed om meer te weten te komen over de technologie erachter, omdat alle concepten die voor dit doel worden gebruikt alomtegenwoordig zijn in databasequerytalen, tekstopmaak, geavanceerde computerarchitecturen, grafische interfaces, generieke taken. machinevertalingen, controllers en virtuele machines. Als u preprocessors, loaders, assemblers, debuggers of profilers moet schrijven, moet u dezelfde stappen doorlopen als bij het schrijven van een compiler. U kunt ook leren over de beste manier om programma's te schrijven, want het ontwikkelen van een vertaler voor een programmeertaal betekent een beter begrip van alle dubbelzinnigheden en subtiliteiten. Door de algemene principes van vertalen te leren, kunt u een goede taalontwerper worden. Maar maakt het echt uit? Hoe cool is een taal als deze niet efficiënt kan worden geïmplementeerd?

schaal technologie

Compilertechnologie bestrijkt een breed scala van verschillende gebieden van de informatica. Het omvat formele taaltheorie, grammatica, computerarchitectuur, parsing, berekenbaarheid, instructiesets, CISC of RISC, pipelining, klokcycli, kernels, enz., evenals sequentiecontrole, recursies, voorwaardelijke uitvoering, functionele decompositie, iteratie, modulariteit, synchronisatie, metaprogrammering, constanten, bereik, sjablonen, uitvoertype, annotaties, prototypes, streams, mailboxen, monaden, wildcards, voortzettingen, transactiegeheugen, reguliere expressies, polymorfisme, overerving, parametermodi, enz. . Om een ​​compiler te maken, moet je ook abstracte programmeertalen, algoritmen en datastructuren, reguliere expressies, grafische algoritmen en dynamisch programmeren begrijpen.

Ontwerp van de compiler. Mogelijke problemen bij het maken van een echte vertaler

Welke problemen kunnen zich voordoen met de brontaal? Is het makkelijk te compileren? Is hier een preprocessor voor? Hoe worden typen behandeld? Welke groepering van compilerpassen wordt gebruikt - single of multi-pass? Ook de gewenste mate van optimalisatie verdient bijzondere aandacht. Een snelle en onzuivere vertaling van een programma met weinig tot geen optimalisatie kan normaal zijn. Overoptimalisatie kan de compiler vertragen, maar tijdens runtime kan betere code de moeite waard zijn.

De mate van foutdetectie. Moet de vertaler al stoppen bij de eerste fout? Wanneer moet hij stoppen? Moet de compiler worden vertrouwd om fouten te corrigeren?

Vereiste set gereedschappen

Als in jouw geval de brontaal niet te klein is, dan zijn de analysergenerator en scanner een must. Er zijn ook speciale codegeneratoren, maar deze worden niet veel gebruikt.

Wat betreft het type doelcode dat moet worden gegenereerd, is het noodzakelijk om te kiezen uit pure, verbeterde of virtuele machinecode. Je kunt ook een frontend schrijven die populaire tussenliggende views creëert, zoals LLVM, JVM, RTL. U kunt ook van broncode naar broncode vertalen in Java Script of C. Als we het hebben over het formaat van de doelcode, kunt u hier draagbare machinecode, geheugenbeeldmachinecode, assembleertaal selecteren.

retargeting

Bij gebruik van een groot aantal generatoren zou het prettig zijn om een ​​gemeenschappelijk invoergedeelte te hebben. Ook om deze reden is het beter om één oscillator te hebben voor veel inputparts.

Compilercomponenten

We noemen de belangrijkste functionele componenten van een vertaler die machinecode genereert als het uitvoerprogramma een programma is dat is geschreven in C of een virtuele machine:

- het invoerprogramma komt de lexicale analysator binnen, of op een andere manier de scanner, die het omzet in een stroom tokens;

- een parser (parser) bouwt er een abstracte syntaxisboom van;

— de semantische analysator ontleedt de semantische informatie en controleert de knooppunten van de boom op fouten;

- als resultaat wordt een semantische grafiek gebouwd. Deze term wordt opgevat als een abstracte syntaxisboom met gevestigde koppelingen en aanvullende eigenschappen;

- de tussencodegenerator bouwt een stroomdiagram (tupels zijn gegroepeerd in hoofdblokken);

- Een machine-onafhankelijke optimizer voert lokale en globale optimalisatie uit, maar blijft meestal binnen het raamwerk van subroutines, terwijl berekeningen worden vereenvoudigd en overtollige code wordt verminderd. Het resultaat zou een gewijzigde stroomgrafiek moeten zijn;

— om de basisblokken te koppelen tot een lineaire code met besturingsoverdracht, wordt een doelcodegenerator gebruikt. Het creëert een objectbestand in assembler met visuele registers, misschien niet erg efficiënt;

- Een machine-afhankelijke optimizer-linker wordt gebruikt om geheugen tussen virtuele registers toe te wijzen en instructieplanning uit te voeren. Het converteert ook een programma dat in assembler is geschreven naar echte assembler met behulp van pipelining.

— er worden subsystemen voor foutdetectie en symbooltabelbeheer gebruikt;

— scannen en lexicale analyse. De scanner wordt gebruikt om de tekenstroom van de broncode om te zetten in een stroom tokens, opmerkingen, spaties te verwijderen en macro's uit te breiden. Heel vaak stuiten scanners op een dergelijk probleem, of ze nu rekening moeten houden met inspringing, hoofdletters en geneste opmerkingen.

De fouten die tijdens het scannen kunnen optreden, worden lexicaal genoemd. Ze omvatten het volgende:

- ontbrekende tekens in het alfabet;

— overschrijding van het aantal tekens in een regel of woord;

is een niet-gesloten letterlijke tekenreeks of teken;

- einde van bestand in commentaar.

Parsing of parsing wordt gebruikt om een ​​reeks tokens om te zetten in een abstracte syntaxisboom. In dit geval wordt elk knooppunt van de boom opgeslagen als een object met benoemde velden. Velen van hen zijn zelf boomknooppunten. Er zijn geen cycli in dit stadium. Bij het maken van een parser moet men allereerst letten op de mate van complexiteit van de grammatica (LR of LL) en nagaan of er regels zijn voor het ondubbelzinnig maken. Sommige talen vereisen inderdaad semantische analyse. Fouten die in dit stadium optreden, worden syntaxisfouten genoemd.

semantische analyse

Bij het uitvoeren van semantische analyse is het allereerst noodzakelijk om de toelaatbaarheidsregels te controleren en de delen van de syntaxisboom aan elkaar te koppelen om een ​​semantische grafiek te vormen door een bewerking in te voegen voor impliciete typecasting, het oplossen van naamreferenties, enz. Het is duidelijk dat verschillende programmeertalen verschillende ontvankelijkheidsregels hebben. Bij het compileren van Java-achtige talen kunnen compilers de volgende fouten tegenkomen:

- meerdere declaraties van een variabele binnen het bereik van zijn actie;

— schending van toegankelijkheidsregels;

- de aanwezigheid van verwijzingen naar een niet-aangegeven naam;

- te groot of juist onvoldoende aantal argumenten bij het aanroepen van de methode;

- type komt niet overeen.

Generatie

Door de tussencode te genereren, wordt een stroomdiagram geproduceerd dat is samengesteld uit tupels die zijn gegroepeerd in basisblokken. Na het genereren van de code wordt de echte machinecode verkregen. In de eerste stap in traditionele compilers voor RISC-machines, is de eerste stap het creëren van een assembler met een oneindig aantal virtuele registers. Het zal waarschijnlijk niet gebeuren voor CISC-machines.

Stuur uw goede werk in de kennisbank is eenvoudig. Gebruik het onderstaande formulier

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

Gehost op http://www.allbest.ru

Invoering

1.1 Top-down ontleden

1.2 Bottom-up parsing

1.2.1 LR(k) - grammatica

1.2.1.1 LR(0) - grammatica

1.2.2 LALR(1) grammatica's

2. Ontwikkeling van de vertaler

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 Coderen

2.4 Testen

Conclusie

Lijst met gebruikte bronnen

Bijlage A. Lijst van de programmatekst van de vertaler

Bijlage B. Testresultaten

Bijlage C. Schema van het vertaalprogramma

Invoering

De tijd is lang voorbij dat, voordat je een programma schreef, het nodig was om meer dan een dozijn machine-instructies te begrijpen en te onthouden. Een moderne programmeur formuleert zijn taken in programmeertalen op hoog niveau en gebruikt alleen in uitzonderlijke gevallen assembler. Zoals bekend komen algoritmische talen pas beschikbaar voor de programmeur na het maken van vertalers uit deze talen.

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

Programmeertalen zijn hulpmiddelen voor het oplossen van problemen in verschillende vakgebieden, die de specifieke kenmerken van hun organisatie en verschillen in doel bepalen. Voorbeelden zijn Fortran, dat is gericht 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 vervolgd. Elk van de vakgebieden heeft zijn eigen vereisten voor de organisatie van de taal zelf. Daarom kunnen we de verscheidenheid aan vormen van representatie van operators en uitdrukkingen, het verschil in de reeks basisbewerkingen, de afname van de programmeerefficiëntie opmerken bij het oplossen van problemen die geen verband houden met het onderwerpgebied. Taalverschillen komen ook tot uiting in de structuur van vertalers. Lisp en Prolog worden meestal uitgevoerd in de interpretatieve modus omdat ze dynamische gegevenstypegeneratie gebruiken tijdens de berekening. Fortran-compilers worden gekenmerkt door agressieve optimalisatie van de resulterende machinecode, wat mogelijk wordt door de relatief eenvoudige semantiek van de taalconstructies - in het bijzonder door de afwezigheid van alternatieve naamgevingsmechanismen voor variabelen door middel van pointers of referenties. De aanwezigheid van pointers in de C-taal stelt specifieke eisen aan dynamische geheugentoewijzing.

De structuur van de taal kenmerkt de hiërarchische relaties tussen de concepten, die worden beschreven door syntactische regels. Programmeertalen kunnen erg van elkaar verschillen in de organisatie van individuele concepten en in de relatie daartussen. De programmeertaal PL/1 maakt willekeurige nesting van procedures en functies mogelijk, terwijl in C alle functies zich op het buitenste nesting-niveau moeten bevinden. De C++-taal staat de declaratie van variabelen toe op elk punt in het programma vóór het eerste gebruik, terwijl in Pascal variabelen in een speciaal declaratiegebied moeten worden gedefinieerd. PL/1 gaat nog verder in deze kwestie, waardoor een variabele kan worden gedeclareerd nadat deze is gebruikt. Of u kunt de beschrijving helemaal weglaten en de standaardregels volgen. 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 over een zeer breed bereik. Ze verschillen niet alleen in de details van de implementatie van individuele operaties, maar ook in programmeerparadigma's die de fundamentele verschillen bepalen in de methoden voor het ontwikkelen van programma's. De bijzonderheden van de uitvoering van bewerkingen kunnen zowel betrekking hebben op de structuur van de verwerkte gegevens als op de regels voor het verwerken van dezelfde gegevenstypes. Talen zoals PL/1 en APL ondersteunen matrix- en vectorbewerkingen. De meeste talen werken voornamelijk met scalars en bieden procedures en functies die door programmeurs zijn geschreven om arrays te verwerken. 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, zijn er paradigma's zoals functioneel programmeren, logisch programmeren en objectgeoriënteerd programmeren. De structuur van concepten en objecten van talen hangt sterk af van het gekozen paradigma, wat ook van invloed is op de implementatie van de vertaler.

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

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

Programmeertalen zijn ontworpen om het programmeren gemakkelijker te maken. Daarom zijn hun operators en datastructuren krachtiger dan 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 hun perceptie door een persoon.

Voor elke taal is gedefinieerd:

- een set symbolen die kunnen worden gebruikt om de juiste programma's te schrijven (alfabet), basiselementen,

- set van juiste programma's (syntaxis),

- "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 ondubbelzinnige afbeelding 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 is elk correct programma X een reeks symbolen van een alfabet A, die wordt omgezet in de overeenkomstige reeks Y, samengesteld uit symbolen van het alfabet B.

Een programmeertaal, zoals elk complex systeem, wordt gedefinieerd door een hiërarchie van concepten die de relatie tussen zijn elementen definieert. Deze concepten zijn aan elkaar gerelateerd volgens syntactische regels. Elk van de programma's die volgens deze regels zijn gebouwd, heeft een overeenkomstige hiërarchische structuur.

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

Een ander kenmerk van alle talen is hun semantiek. Het bepaalt de betekenis van de taalbewerkingen, de correctheid van de operanden. Ketens die dezelfde syntactische structuur hebben in verschillende programmeertalen kunnen verschillen in semantiek (wat bijvoorbeeld wordt waargenomen in C++, Pascal, Basic). Kennis van de semantiek van de taal maakt het mogelijk om het te scheiden van de syntaxis en het te gebruiken om naar een andere taal te converteren (om code te genereren).

Het doel van deze cursus is om een ​​opleidingsvertaler te ontwikkelen vanuit een bepaalde vereenvoudigde teksttaal op hoog niveau.

1. Parseermethoden

Overweeg de basismethoden van grammaticale analyse.

1.1 Top-down ontleden

Bij het ontleden van boven naar beneden bewegen tussenconclusies zich langs de boom in de richting van de wortel naar de bladeren. In dit geval zullen bij het bekijken van de keten van links naar rechts natuurlijk linkse conclusies worden verkregen. Bij deterministische ontleding zou het probleem zijn welke regel moet worden toegepast om de meest linkse niet-terminal uit te breiden.

1.1.1 LL(k) - talen en grammatica's

Beschouw de outputboom bij het verkrijgen van de linkeroutput van de keten. De tussenliggende keten in het uitvoerproces bestaat uit een keten van terminals w, de meest linkse niet-terminal A, het ondergedrukte deel van x:

-S--

/ \

/ -A-x-\

/ | \

-w---u----

Figuur 1

Om door te gaan met ontleden, is het nodig om de niet-terminale A te vervangen volgens een van de regels van het formulier A:y. Als parsing deterministisch moet zijn (geen backtracking), moet deze regel op een speciale manier worden gekozen. Men zegt dat een grammatica de eigenschap LL(k) heeft als het, om een ​​regel te kiezen, voldoende is om alleen wAx en de eerste k karakters van de niet-doorzochte string u te beschouwen. De eerste letter L (Links, links) verwijst naar het bekijken van de invoerreeks van links naar rechts, de tweede - naar links gebruikte uitvoer.

We definiëren twee reeksen ketens:

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

b) FOLLOW(A) - een set van terminal strings afgekort tot k, die onmiddellijk kan volgen op A in de output strings.

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

S::wAx:wzx::wu

S::wAx:wtx::wv

de voorwaarde FIRST(u)=FIRST(v) impliceert z=t.

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

- kies regel A:x als a in FIRST(x) staat,

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

LL(k)-eigenschap legt vrij sterke beperkingen op aan de grammatica. Bijvoorbeeld, LL(2) grammatica S: aS | a heeft de eigenschap LL(1) niet, omdat EERSTE(aS)=EERSTE(a)=a. In dit geval kunt u de waarde van k verminderen met behulp van "factorisatie" (tussen haakjes):

S:aA

A: S | e

Elke LL(k)-grammatica is uniek. Een links-recursieve grammatica behoort voor geen enkele k tot LL(k). Soms is het mogelijk om een ​​niet-LL(1) grammatica om te zetten naar zijn equivalente LL(1) grammatica door linksrecursie 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, wanneer het gebruik van recursieve procedures is toegestaan.

Het basisidee van recursieve afdaling is dat elke niet-terminal van de grammatica wordt geassocieerd met een procedure die elke tekenreeks herkent die door deze niet-terminal wordt gegenereerd. Deze procedures bellen elkaar wanneer nodig.

Recursieve afdaling kan worden gebruikt voor elke LL(1)-grammatica. elke niet-terminal van de grammatica komt overeen met een procedure die begint met een overgang naar een berekend label en bevat een code die overeenkomt met elke regel voor deze niet-terminal. Voor die invoersymbolen die behoren tot de keuzeset van de gegeven regel, draagt ​​de berekende overgang de controle over aan de code die overeenkomt met deze regel. Voor de rest van de ingevoerde karakters gaat de besturing over naar de foutafhandelingsroutine.

De code van een regel bevat bewerkingen voor elk teken aan de rechterkant van de regel. De bewerkingen worden weergegeven in de volgorde waarin de symbolen in de regel voorkomen. Na de laatste bewerking bevat de code een terugkeer uit de procedure.

Het gebruik van recursieve afdaling in een taal op hoog niveau maakt het gemakkelijker om te programmeren en te debuggen.

1.2 Bottom-up parsing

Laten we een bottom-up parsing beschouwen, waarbij de tussenconclusies langs de boom naar de wortel bewegen. Als je de karakters van de string van links naar rechts leest, dan ziet de ontledingsboom er als volgt uit:

-S--

/ \

/-x-\

/ | \

--w--b--u-

Figuur 2

De tussenuitvoer heeft de vorm xbu, waarbij x een keten van terminals en niet-terminals is waaruit het gescande deel van de terminalketen w wordt uitgevoerd, bu het niet-gescande deel van de terminalketen is, b het volgende teken is. Om verder te gaan met ontleden, kunt u ofwel het teken b toevoegen aan het gescande deel van de keten (voer de zogenaamde "shift" uit), of aan het einde van x zo'n keten z (x=yz) selecteren die een van de grammaticale regels B:z kunnen op z worden toegepast en x worden vervangen door de 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 de convolutie alleen wordt toegepast op de laatste tekens van x, krijgen we de juiste conclusies van de keten. Dit ontleden 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 ploegen- en contractbewerkingen is essentieel. Daarom vereist deterministische ontleding dat je op elk moment moet kiezen tussen verschuiving en samentrekking (en verschillende convolutieregels).

1.2.1 LR(k) - grammatica

Als tijdens LR-parsing een deterministische verschuiving/contractiebeslissing kan worden genomen door alleen de string x en de eerste k karakters van het niet-gescande deel van de invoerstring u te beschouwen (deze k karakters worden de prestring genoemd), zegt de grammatica dat hebben de LR(k)-eigenschap.

-S--

/ \

/-x-\

--w----u--

Figuur 5

Verschil tussen LL(k)- en LR(k)-grammatica in termen van afleidingsboom:

-S-

/ | \

/EEN\

/ / \ \

-w---v---u-

Figuur 6

In het geval van LL(k)-grammatica's kan men de regel die op A wordt toegepast eenduidig ​​bepalen door w en de eerste k symbolen van vu, en in het geval van LR(k)-grammatica's door w,v en de eerste k symbolen van u. Dit losse argument laat zien dat LL(k)-talen< LR(k)-языки (при k > 0).

1.2.1.1 LR(0) - grammatica

Beschouw eerst de eenvoudigste grammatica's van deze klasse - LR(0). Bij het ontleden van een string in een LR(0)-taal, hoef je de leading chain helemaal niet te gebruiken - de keuze tussen shift en contraction wordt gemaakt op basis van string x. Omdat het tijdens het ontleden alleen van rechts verandert, wordt het een stapel genoemd. We nemen aan dat er geen nutteloze tekens in de grammatica staan ​​en dat het beginteken niet in de juiste delen van de regels voorkomt - dan geeft de convolutie naar het beginteken de succesvolle voltooiing van de parsering 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 juiste gevolgtrekkingen uit de grammatica).

We definiëren de volgende sets:

L(A:v) - de linkercontext van de regel A:v - de verzameling stapeltoestanden, onmiddellijk voor de ineenstorting van v in A tijdens alle succesvolle LR-parsing. Het is duidelijk dat elke string in L(A:v) eindigt op v. Als de staart v van al dergelijke kettingen wordt afgesneden, krijgen we de reeks kettingen die links van A voorkomen in het proces van alle succesvolle rechtse gevolgtrekkingen. Geef deze verzameling aan L(A) - de linkercontext van de niet-terminale A.

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

en voeg de regels toe 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 een speciale vorm (dergelijke grammatica's worden links-lineair genoemd), daarom zijn de sets linkercontexten

- zijn regelmatig. Hieruit volgt dat het lidmaatschap van een string in de linkercontext van een niet-terminal inductief kan worden berekend met behulp van een eindige automaat, waarbij de string van links naar rechts wordt gescand. Laten we dit proces constructief beschrijven.

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

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

- ketens consistent 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 bevat, dan hoort de situatie A:bc_d bij V(uc). (c - terminal of niet-terminal; b, d - reeksen (mag leeg zijn) van terminals en niet-terminals). Er zijn geen andere situaties zoals A:b_d, met niet-lege b in V(uc). Het blijft om situaties van de vorm C:_... toe te voegen aan V(uc) voor elke niet-terminale C waarvan de linkercontext uc bevat. Als de situatie A:..._C... (C-niet-terminaal) 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 de situaties S:_... (S-beginteken), evenals de situaties A:_... als de niet-terminal A onmiddellijk na _ optreedt in situaties die al in V(e) zijn opgenomen .

Ten slotte zijn we klaar om een ​​LR(0)-grammatica te definiëren. Laat u de inhoud van de stapel zijn tijdens het ontleden van LR, en laat V(u) de verzameling LR(0)-situaties zijn die consistent zijn met u. Als V(u) een situatie bevat van de vorm A:x_ (x-reeks van terminals en niet-terminals), dan hoort u bij L(A:x) en kan x worden gevouwen tot A. Als V(u) een situatie bevat A:..._a... (a-terminal), dan is een shift toegestaan. Men spreekt van een shift-reduceer-conflict als zowel een shift als een contractie zijn toegestaan ​​voor dezelfde string u. Men spreekt van een vouw-vouw-conflict als vouwen volgens andere regels is toegestaan.

Een grammatica wordt LR(0) genoemd als er geen shift-fold of roll-down-conflicten zijn voor alle stapeltoestanden in het LR-inferentieproces.

1.2.1.2 LR(k) - grammatica

Alleen de status van de stapel wordt gebruikt bij het ontleden van LR(0) om te kiezen tussen verschuiven of samentrekken. LR(k)-parsing houdt ook rekening met de k-eerste tekens van het onzichtbare deel van de invoerstring (de zogenaamde pre-string). Om de methode te rechtvaardigen, moet men zorgvuldig de argumenten van de vorige sectie herhalen en wijzigingen aanbrengen in de definities.

We zullen ook een voorschakelketen opnemen in de linkercontext van de regel. Als de juiste afleiding de afleiding wAu: wvu gebruikt, dan hoort het paar wv,FIRSTk(u) bij Lk(A:v), en het paar w,FIRSTk(u) bij Lk(A). De verzameling 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 voorwaartse keten van maximaal k. We zullen de regel scheiden 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-uitgang is: x_yz = ab_yz:: abc_z:: aA_z:: S_, en FIRSTk(z)=t. De regels voor de inductieve berekening van de toestandsverzameling Vk zijn als volgt:

Vk(e) bevat S:_a|e situaties voor alle S:a regels, waarbij S het initiële symbool is. Voor elke situatie A:_Ba|u uit Vk(e), elke regel B:b, en de keten x die hoort bij FIRSTk(au), moet de situatie B:_b|x worden opgeteld bij Vk(e).

Als de situatie A:b_cd|u Vк(w) invoert, dan zal de situatie A:bc_d|u behoren tot Vk(wc). Voor elke situatie A:b_Cd|u uit Vk(wc), elke regel C:f, en de keten x die hoort bij FIRSTk(du), moeten we de situatie C:_f|x optellen bij 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 voorwaartse keten. Het is duidelijk dat de A:b-convolutie kan worden uitgevoerd als Vk(u) de situatie A:b_|x bevat. Om te beslissen of een dienst toelaatbaar is, is nauwkeurigheid vereist als de grammatica e-regels bevat. In de situatie A:b_c|t (c is niet leeg), is de verschuiving mogelijk als c begint vanaf een terminal en x behoort tot FIRSTk(ct). Informeel gesproken kun je het meest linkse teken van de rechterkant van de regel op de stapel duwen, om de volgende convolutie voor te bereiden. Als c begint vanaf een niet-terminal (de situatie ziet eruit als A:b_Cd|t), dan is het alleen mogelijk om een ​​symbool op de stapel te duwen en een vouw in C voor te bereiden als C geen lege string genereert. Bijvoorbeeld in de toestand V(e)= S:_A|e; A:_AaAb|e,a, A:_|e,a bij het afleiden van terminalketens van A, is het in een bepaalde stap 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 een set EFFk(x) definiëren die bestaat uit alle elementen van de set FIRSTk(x) waarvan de afleiding de niet-terminal aan het linkeruiteinde van x (indien aanwezig) niet vervangt door een lege string. In deze termen is een verschuiving toelaatbaar als de verzameling Vk(u) de situatie А:b_c|t bevat, c niet leeg is en x bij EFFk(ct) hoort.

Een grammatica wordt een LR(k)-grammatica genoemd als geen LR(k)-toestand twee situaties A:b_|u en B:c_d|v bevat zodat u bij EFFk(dv) hoort. Zo'n paar komt overeen met een fold-fold 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: een zeer groot aantal LR(k)-toestanden. Ten tweede bestaat er voor elke taal gedefinieerd door een LR(k)-grammatica een LR(1)-grammatica; bovendien is er een LR(1)-grammatica voor elke deterministische CF-taal.

Het aantal LR(1)-toestanden voor praktisch interessante grammatica's is ook vrij 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 en LALR(1).

1.2.2 LALR(1) grammatica's

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

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 equivalent beschouwen als ze alleen verschillen in voorafgaande ketens. De situaties A:Aa_Ab|e en A:Aa_Ab|a zijn bijvoorbeeld equivalent. Laten we een canonieke verzameling LR(1)-toestanden construeren en de toestanden verenigen die uit een verzameling equivalente situaties bestaan.

Als de resulterende set toestanden geen LR(1)-conflicten bevat, en ons daarom in staat stelt een LR(1)-parser te construeren, dan zou de grammatica de eigenschap LALR(1) hebben.

2. Ontwikkeling van de vertaler

2.1 Analyse van eisen

In deze cursus is het noodzakelijk om een ​​opleidingsvertaler te ontwikkelen in de vorm van een tolk uit een taal die wordt gedefinieerd door de bijbehorende formele grammatica. Er zijn vier hoofdfasen in de ontwikkeling van een tolk:

Het ontwerpen van een lexicale analysator;

Het ontwerpen van een tijdschriftenautomaat;

Software-implementatie van de parser;

Ontwikkeling van de tolkmodule.

De ontwikkeling zal worden uitgevoerd met het besturingssysteem Windows XP op een IBM-pc met een Intel Pentium IV-processor.

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

2.2 Ontwerp

2.1.1 Een lexicale analysator ontwerpen

Lexicale analyse omvat het scannen van het vertaalde (bron)programma en herkenning van lexemen die de zinnen van de brontekst vormen. Tokens omvatten met name trefwoorden, bedieningstekens, identifiers, constanten, speciale tekens, enz.

Het resultaat van het werk van de lexicale analysator (scanner) is een reeks tokens, en elk token wordt meestal weergegeven door een code van een vaste lengte (bijvoorbeeld een geheel getal), evenals de uitgifte van berichten over syntactische (lexicale ) eventuele fouten. Als het lexeme bijvoorbeeld een trefwoord is, geeft de code alle benodigde informatie. In het geval van bijvoorbeeld een identifier is bovendien de naam van de herkende identifier vereist, die meestal wordt vastgelegd in een tabel met identifiers, die in de regel met behulp van lijsten is georganiseerd. Voor constanten is een vergelijkbare tabel nodig.

Een lexeme kan worden beschreven door twee hoofdkenmerken. Een daarvan is het behoren van een lexeme tot een bepaalde klasse (variabelen, constanten, operaties, enz.) Het tweede attribuut definieert een specifiek element van deze klasse.

Het specifieke soort symbooltabel (gegevensstructuur) is niet relevant voor de lexer of parser. Beide hoeven alleen de mogelijkheid te bieden om een ​​index te verkrijgen die bijvoorbeeld een bepaalde variabele op unieke wijze identificeert en de indexwaarde te retourneren om informatie over de gegeven variabelenaam in de symbooltabel aan te vullen.

Het bekijken van de identificatietabel heeft twee hoofdfuncties:

a) het schrijven van een nieuwe naam aan de tabel bij het verwerken van de declaratie van variabelen;

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

Dit maakt het mogelijk om foutieve situaties zoals een meervoudige beschrijving van een variabele en de aanwezigheid van een niet-aangegeven variabele te detecteren.

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

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

Het schema van het werkprogramma van de lexicale analysator wordt gegeven in bijlage B in figuur B.1.

2.2.2 Ontwerp van het automatische magazijn

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, 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 presenteren in tabel 1.

Tabel 1 - Grammaticaregels

regel nummer	Linkerkant van de regel	Rechts van de regel
		f ID = EX t EX d LE n;
Vervolg van tabel 1.
regel nummer	Linkerkant van de regel	Rechts van de regel

De aanduidingen van lexemen, de vertaling van lexemen in codes en de lijst van grammaticale aanduidingen staan ​​respectievelijk in de tabellen 2, 3, 4.

Tabel 2 - Notatie van lexemen

	Lexeme-notatie
	trefwoord "begin" (het begin van de beschrijving van acties)
	het trefwoord "end" (het einde van de beschrijving van acties)
	trefwoord "var" (declaratie van variabelen)
	trefwoord "lezen" (gegevensinvoerverklaring)
	trefwoord "write" (statement voor gegevensuitvoer)
	"for" trefwoord (lus-instructie)
	trefwoord "naar"
	trefwoord "doen"
	trefwoord "end_case" (einde van de lus-instructie)
	variabele type "integer"
	optelbewerking
	aftrekken operatie
	vermenigvuldiging operatie
	scheidingsteken ":"
	scheidingsteken ";"
	scheidingsteken "("
	scheidingsteken ")"
	scheidingsteken ","
	Lexeme-notatie
	scheidingsteken "="

Tabel 3 - Vertaling van lexemen in codes

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

Tabel 4 - Lijst met grammaticasymbolen

Aanwijzing	Uitleg
	Programma
	Beschrijving van berekeningen
	Beschrijving van variabelen
	Lijst met variabelen
	Operator
	Opdracht
	Uitdrukking
	subuitdrukking
	Binaire bewerkingen
	Unaire operaties
	Opdrachtenlijst
	ID
	Constante

Laten we een deterministische oplopende herkenner construeren.

Overweeg de volgende relaties om een ​​deterministische bottom-up resolver op te bouwen:

a) Als er een groepssymbool B is zodat de tekenreeks AB is opgenomen in een grammaticaregel en het symbool xPERV "(B) bestaat, dan nemen we aan dat de relaties x NA A zijn gedefinieerd tussen de symbolen x en A

b) Als er in een bepaalde grammatica een regel B-\u003e bAb A, BV a is, dan wordt tussen A en x de relatie A CONVERT x bepaald.

Al onze grammatica blijft hetzelfde, namelijk:

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

en de grammaticaregels D worden gegeven in Tabel 5.

Tabel 5 - Grammaticaregels

regel nummer	Linkerkant van de regel	Rechts van de regel
		f ID = EX t EX d LE n;?
Vervolg van tabel 5.
regel nummer	Linkerkant van de regel	Rechts van de regel

Waar? - een markering voor het einde van de ketting.

Laten we enkele gevallen definiëren:

a) De ID bestaat uit een reeks 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)

Om ervoor te zorgen dat onze grammatica een strategie met gemengde prioriteit is, moet aan de volgende voorwaarden worden voldaan:

a) Afwezigheid van e-regels

b) Zijn er regels waaronder x NA A? EEN CONVERTEREN x = ?

c) A -> bYg

en het is noodzakelijk dat IN NA x? IN CONVERTEREN x = ?

d.w.z. in de grammatica worden ze uitgevoerd IN NA x of A NA x, waarbij x het symboolpredikaat is van de keten b.

a) PERV "(PG) \u003d (PG?)

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

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

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

PERV" (LV) = PERV (ID, LV) = (LV, ID)

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

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

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

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

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

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

PERV" (UO) = (UO,-)

PERV" (ID)= PERV" (u) = (u)

PERV" (CO) = PERV" (k) = (k)PERV" (e) =( e)

PERV" (b) =( b)

PERV" (e) =( e)

PERV" (v) =( v)

PERV" (w) =( w)

PERV" (r) =( r)

PERV" (i) =( ik)

PERV" (f) =( f)

PERV" (d) = (d)

PERV" (n) =( n)

PERV" (c) =( c)

PERV" (+) =( +)

PERV" (*) =( *)

PERV" (-) =(-)

PERV" (,) =(,)

PERV" (;) =(;)

PERV" (:) =(:)

PERV" (=) = ( = )

PERV" (() =( ()

PERV" ()) =() )

PERV" (u) =(u)

PERV" (k) = (k)

b) VOLGENDE `(AL) = (?)?NEXT"(PG)=(?,b,e)

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

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

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

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

VOLGENDE ` (EX) = (?)?PRIM"(t)?PRIM"(d)?PRIM"(;)?PRIM"())=(?, t,d,;,))

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

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

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

VOLGENDE ` (LE) = (?) ?PRIM"(e) ?PRIM"(n) = (?, e, n)

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

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

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

VOLGENDE ` (e) =(?)?NEXT"(AL)= (?, b)

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

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

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

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

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

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

VOLGENDE ` (n) =(?)?PRIM"(i) = (?, ik )

VOLGENDE ` (+) =(?)?NEXT"(IN) = (?, +,*,-)

VOLGENDE ` (-) =(?)?NEXT"(IN) = (?, +,*,-)

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

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

VOLGENDE ` (:) =(?)?PRIM"(i)= (?, ik )

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

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

VOLGENDE ` ()) =(?)? PERV"(;) = (?,; )

VOLGENDE ` (,) =(?)? PERV"(LV) = (?, u)

VOLGENDE `(u)=(?)? PERV" (ID)= ( u, ?)

VOLGENDE `(k)=(?)? PERV (CO)= (?, k)

c) PG -> DE AL

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

e NA LE = ((e 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: = ( (i:) )

: 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))

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 ROLL PG = AL ROLL NEXT" (PG) = ((AL ?))

e ROLL AL = e ROLL NEXT"(AL)= ((eb), (e?))

=; VOLGENDE VOUWEN"(DE) = ((;b), (;?))

LV-STROOM LV = LV-STROOM VOLGENDE" (LV) = ((LV:), (LV?))

ID ROLL LV = ID ROLL VOLGENDE" (LV) = ((ID:), (ID?))

; CONVERT LE=; VOLGENDE VOUWEN" (LE) = ((; e), (;?), (;n))

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

; CONVERT LE=; VOLGENDE VOUWEN" (LE) = ((; e), (;?), (;n))

EQ ROLL LE = EQ ROLL NEXT" (LE) = ((EQ e), (EQ?), (EQ n))

EQ -> ID = EX;

; CONVERT EQ=; VOLGENDE VOUWEN" (EQ) = ((; (), (;)), (;;), (;f), (;?), (;=), (;t), (;d), (; n), (;w), (;r))

SB ROLL EX = SB ROLL NEXT" (EX) = ((SB t), (SB?), (SB d), (SB)), (SB;), (SB(), (SB=), (SBf ), (SBn), (SBw), (SBr) )

) SB ROL = SB VOLGENDE ROL" (SB) = (() t), ()?), () d), ())), ();))

OP ROLL SB = OP ROLL VOLGENDE" (SB) = ((OP t), (OP ?), (OP d), (OP)), (OP;))

SB->SB BO SB

SB ROL SB = SB ROL VOLGENDE" (SB) = ((SB, t), (SBd), (SB;). (SB)), (SB+), (SB-), (SB*), (SB? ) }

ROLL UO = - ROLL VOLGENDE" (UO) = ( (-?), (--))

ROLL BO = + ROLL VOLGENDE" (BO) = ((++), (+?), (+*), (+-))

* ROLL BO = * ROLL VOLGENDE" (BO) = ((*+), (*?), (**), (*-))

ROLL BO = - ROLL VOLGENDE" (BO) = ((-+), (-?), (-*), (--))

ID ROLL OP = ID ROLL NEXT" (OP) = ((ID+), (ID?), (ID*), (ID-))

CO VOUW OP = CO VOUW VOLGENDE" (OP) = ((CO+), (CO?), (CO*), (CO-), (CO;), (COd), (COt), (CO)))

ID ROLL ID = ID ROLL NEXT" (ID) = ((ID)), (ID ?), (ID k), (ID+), (ID-), (ID*), (ID=), (IDt) , (IDd)))

u ROLL ID = l ROLL NEXT" (ID) = ((u)), (u?), (uk), (u+), (u-), (u*), (u=), (ut), (u)))

CO ROLL CO = CO ROLL NEXT" (CO) = (CO+), (CO?), (CO*), (CO-), (CO;), (COd), (COt), (CO)))

k ROLL CO = k ROLL VOLGENDE" (CO) = (k+), (k?), (k*), (k-), (k;), (kd), (kt), (k)))

Eén conflictsituatie gevonden bij vouwregels

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 ROLL ID = ID1 ROLL NEXT" (ID) = ((ID1)), (ID1 ?), (ID1 k), (ID1+), (ID1-), (ID1*), (ID1=), (ID1t) , (ID1d)))

Voor elk paar (x, A)? x NA A bouwen we een overgangsfunctie die de overdrachtsactie bepaalt ?? (S 0, x, A) \u003d (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, bn)

? (S0, b, 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,i,)) = (S0,)i)

? (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, u)

Voor elk paar (x, A)? En CONVULT x bouwt een overgangsfunctie die de actie van de convolutie definieert? * (S 0, x, bA) \u003d (S 0, B), waarbij B-> bA

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

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

? * (S 0 , n, ?) = (S 0 , 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)

? * (S 0 , SB,;) = (S 0 , 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)

? * (S 0 , SB, +) = (S 0 , 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)

? * (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 , *, *) = (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)

? * (S 0 , CO, +) = (S 0 , 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 , ik 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)

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

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

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

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

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

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

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

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

? * (S 0 , k, -) = (S 0 , 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)

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

2.2.3 Software-implementatie van de parser

De parser (parser) leest het bestand met tokens gegenereerd door de lexicale analysator, voert grammaticale analyse uit, geeft berichten weer over eventuele syntaxisfouten en maakt een tussenvorm van het bronprogramma. De basis voor de ontwikkeling van een parser is het ontwerp en de implementatie van een geschikte pushdown-automaat.

Voor bottom-up parsing voor een deterministische bottom-up herkenner is het nodig om, nadat deze in de gewenste vorm is gebracht, een push-down-automaat te ontwerpen met een gedetailleerde beschrijving van alle overgangen binnen de overgangsfunctie met behulp van de AFTER- en FOLD-functies.

Bij het ontwikkelen van een pushdown-automaat hebben we de overgangsfuncties gebouwd die de basis zullen vormen van de parser. Alle overgangsfuncties kunnen worden onderverdeeld in twee typen:

Bedrijfscyclus van een push-pull-machine zonder het invoersymbool te lezen (lege cyclus);

De cyclus van een push-pull automaat met het lezen van het invoersymbool.

Bij het implementeren van de lexicale analysator hebben we het programma opgesplitst in tokens en deze in een lijst geschreven. Deze lijst verwerken we vervolgens in de parser. We sturen ons programma (lijst), het beginsymbool (PG) en de drukknop-ondermarkering (h0) als invoer, waarna de gewenste overgangsfunctie wordt geselecteerd en een recursieve oproep wordt gedaan.

Het schema van het parserwerkprogramma is weergegeven in bijlage B in figuur B.2.

2.2.4 Ontwikkeling van de tolkmodule

Bij het ontwikkelen van een tolkmodule als tussenvorm van het originele programma de meest gebruikte postfix-notatievorm, die 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 vorming en uitvoering van de postfix-vorm van uitdrukkingen.

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

De gelezen operanden worden toegevoegd aan de postfix-notatie, de bewerkingen worden op de stapel geduwd.

Als de bewerking bovenaan de stapel een hogere (of gelijke) prioriteit heeft dan de momenteel gelezen bewerking, wordt de bewerking van de stapel toegevoegd aan de postfix-invoer en wordt de huidige bewerking op de stapel geduwd. Anders (met de laagste prioriteit) wordt alleen de huidige bewerking op de stapel geduwd.

De lees-open beugel wordt op de stapel geschoven.

Na het lezen van het haakje sluiten worden alle bewerkingen tot en met het eerste haakje openen uit de stapel gehaald en toegevoegd aan het postfix record, waarna zowel het openende als het sluiten haakje worden weggegooid, d.w.z. worden niet op het postfix-record of op de stapel geplaatst.

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

Met de postfix-notatie van een uitdrukking kan deze op de volgende manier worden geëvalueerd.

Als het token een operand is, wordt het op de stapel geduwd. Als het token een bewerking is, wordt de gespecificeerde bewerking uitgevoerd op de laatste elementen (laatste element) die op de stapel zijn geduwd, en deze elementen (element) worden vervangen op de stapel met het resultaat van de bewerking.

Als de lexicale en syntactische analyses met succes zijn geslaagd, gaan we over tot interpretatie. Eerst maken we zinnen van woorden, dan vertalen we uitdrukkingen in postfix-notatie en rekenen.

Het bedieningsschema van de tolk wordt gegeven in bijlage B in figuur B.3.

2.3 Coderen

Het programma is geïmplementeerd in C# in de programmeeromgeving Visual Studio 2010. De tekst van het programma staat in bijlage A.

Het programma heeft vijf klassen. De gebruikersinterface is geïmplementeerd met behulp van de MainForn-klasse. Met behulp van de LexAnalysis-klasse wordt een lexicale analysemodule geïmplementeerd, SynAnalysis is een parseermodule, 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 tabellen 6,7,8.

Tabel 6 - Doel van procedures en functies van lexicale analyse

Vergelijkbare documenten

Een vertaler is een programma of een technisch middel dat de vertaling van een programma uitvoert. Overweging van de belangrijkste kenmerken van de constructie van een lexicale analysator. Bekendheid met de fasen van het ontwikkelen van een vertaler uit een beperkte subset van een taal op hoog niveau.

scriptie, toegevoegd 08/06/2013


Ontwerpen van lexicale en syntactische analysers van de onderwijstaal. Regels voor het converteren van logische expressies naar POLIZ. Vorming van triaden, optimalisatie van hun lijst. De logische opbouw van het programma. Testen van vertaler-tolkmodules.

scriptie, toegevoegd 28-05-2013


Algemene kenmerken en evaluatie van de mogelijkheden van de C-sharp programmeertaal, de overeenkomsten en verschillen met C++ en Java. Ontwikkeling met behulp van deze programmeertaal van een lexicale en parser. Samenstellen van rekenbladen.

scriptie, toegevoegd 06/11/2010


Het ontwerpen van een analyseprogramma dat uit twee delen bestaat: een lexicale analyser die de brontekst van het programma opsplitst in tokens en de namentabel invult; een parser die controleert of de tekst overeenkomt met de gegeven grammatica.

scriptie, toegevoegd 14-06-2010


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

scriptie, toegevoegd 23/02/2012


Ontwikkelingstechniek en gedeeltelijke implementatie van een vertaler voor de "C"-taal met behulp van de "C++"-taal, die de initiële reeks karakters opsplitst in minimaal ondeelbare taalconstructies op basis van het taalvocabulaire. Analyse van het programma.

scriptie, toegevoegd 19/03/2012


Structuur, classificatie en vereisten voor de implementatie van de compiler. Ontwerp en implementatie van het analyserende deel van de C++ compiler. Manieren om lexicale analyse te implementeren. Het algoritme van de parser. Principes van software-implementatie.

scriptie, toegevoegd 26/01/2013


Creatie van een vertaler die de programmacode in de Pascal-taal verwerkt en een C-programma genereert met behulp van equivalente operators. Eigenaardigheden van de externe specificatie en werking van de lexicale analysator. De structuur van het programma, de resultaten op het scherm weergeven.

scriptie, toegevoegd 07/02/2011


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

scriptie, toegevoegd 05/12/2013


Software-implementatie van een desktop-applicatie met behulp van de programmeertaal C#. Ontwerp en opbouw van de gebruikersinterface, eisen daaraan en evaluatie van functionaliteit. Ontwikkeling van een gebruikershandleiding en het gebruik ervan.

AFDELING 7. Vertaling, compilatie en vertolking

Een programma is een reeks instructies die zijn ontworpen om door een computer te worden uitgevoerd. Momenteel worden programma's geschreven in de vorm van tekst die naar bestanden wordt geschreven. Deze tekst is het resultaat van de activiteit van de programmeur en blijft, ondanks de bijzonderheden van de formele taal, programma voor de programmeur.

Het proces van het maken van een programma omvat verschillende fasen. De fase van ontwikkeling van het project van het programma wordt gevolgd door de fase van programmering. In deze fase wordt het programma geschreven. Programmeurs nemen deze tekst gemakkelijker waar dan binaire code, omdat verschillende mnemonische afkortingen en namen aanvullende informatie bevatten.

Een programmabronbestand (ook wel een bronmodule genoemd) wordt verwerkt vertaler , dat een programma uit een programmeertaal vertaalt in een machine-begrijpelijke reeks codes.

Vertaler - software of hardware die presteert uitzending van het programma. Een machineprogramma dat vertaalt van de ene taal naar de andere en in het bijzonder van de ene programmeertaal naar de andere. Een verwerkingsprogramma dat is ontworpen om een ​​bronprogramma om te zetten in een objectmodule.

De vertaler voert meestal ook foutdiagnose uit, genereert woordenboeken met identifiers, drukt programmateksten af, enz.

Programma uitzending - transformatie van een programma gepresenteerd in een van de programmeertalen naar een programma in een andere taal en in zekere zin gelijk aan de eerste.

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

Soorten vertalers

Vertalers zijn onderverdeeld in:

· Adres. Een functioneel apparaat dat een virtueel adres omzet virtueel adres) naar een echt adres (eng. geheugen adres).

· Dialoogvenster. Biedt het gebruik van een programmeertaal in timesharing-modus.

· multipass. Genereert een objectmodule over verschillende weergaven van het bronprogramma.

· Rug. Zelfde als relais. Zie ook: decompiler, disassembler.

· enkele pas. Genereert een objectmodule in één sequentiële scan van het bronprogramma.

· Optimaliseren. Voert code-optimalisaties uit in de gegenereerde objectmodule.

· Syntactisch-georiënteerd (syntactisch-gedreven). Het ontvangt als invoer een beschrijving van de syntaxis en semantiek van de taal en de tekst in de beschreven taal, die wordt vertaald in overeenstemming met de opgegeven beschrijving.

· test. Een set assembler-macro's waarmee u verschillende foutopsporingsprocedures kunt instellen in programma's die in assembler zijn geschreven.

Vertalers worden geïmplementeerd in de vorm compilers of tolken . In termen van het doen van werk, zijn een compiler en een interpreter heel verschillend.

Compiler(Engels) compiler- compiler, verzamelaar) - een vertaler die een in de brontaal gecompileerd programma omzet in een objectmodule. Een programma dat de tekst van een taalprogramma op hoog niveau vertaalt naar het equivalente machinetaalprogramma.

· Een programma dat is ontworpen om een ​​taal op hoog niveau te vertalen in absolute code of, soms, in assembler. De invoerinformatie voor de compiler (broncode) is een beschrijving van het algoritme of een programma in een domeinspecifieke taal, en de uitvoer van de compiler is een equivalente beschrijving van het algoritme in een machinegerichte taal (objectcode).

Compilatie- vertaling van een in de brontaal geschreven programma naar een objectmodule. Geïmplementeerd door de compiler.

Compileren - een machineprogramma vertalen van een probleemgerichte taal naar een machinegerichte taal.

De compiler leest het hele programma geheel, vertaalt het en maakt een volledige versie van het programma in machinetaal, die vervolgens wordt uitgevoerd.

Tolk(Engels) tolk- tolk, tolk) vertaalt en voert het programma uit lijn bij lijn. De interpreter haalt de volgende taalinstructie uit de programmatekst, analyseert de structuur en voert deze vervolgens onmiddellijk uit (meestal wordt de instructie na analyse vertaald in een tussenliggende representatie of zelfs machinecode voor een efficiëntere verdere uitvoering). Pas nadat de huidige instructie met succes is uitgevoerd, gaat de interpreter verder met de volgende. Bovendien, als dezelfde instructie vele malen in het programma wordt uitgevoerd, zal de interpreter deze uitvoeren alsof hij deze voor de eerste keer heeft ontmoet. Als gevolg hiervan zullen programma's die veel rekenkracht vereisen, traag werken. Om het programma op een andere computer uit te voeren, moet er bovendien een tolk zijn - zonder deze is de tekst immers slechts een reeks tekens.

Op een andere manier kunnen we zeggen dat de tolk een of andere virtuele computermachine modelleert, waarvoor de basisinstructies geen elementaire processorcommando's zijn, maar programmeertaaloperators.

Verschillen tussen compilatie en interpretatie.

1. Als het programma eenmaal is gecompileerd, zijn noch het bronprogramma, noch de compiler meer nodig. Tegelijkertijd moet het programma dat door de tolk wordt verwerkt opnieuw: overdracht in machinetaal elke keer dat het programma wordt uitgevoerd.

2. Gecompileerde programma's werken sneller, maar geïnterpreteerde programma's zijn gemakkelijker te repareren en te wijzigen.

3. Elke specifieke taal is gericht op compilatie of interpretatie, afhankelijk van het doel waarvoor deze is gemaakt. Bijvoorbeeld, Pascal meestal gebruikt om vrij complexe problemen op te lossen waarbij de snelheid van programma's belangrijk is. Daarom wordt deze taal meestal geïmplementeerd met behulp van compiler.

Aan de andere kant, BASIS is gemaakt als een taal voor beginnende programmeurs, voor wie regel-voor-regel programma-uitvoering onmiskenbare voordelen heeft.

Bijna alle programmeertalen op laag niveau en van de derde generatie, zoals assembler, C of Modula-2, worden gecompileerd, terwijl talen op een hoger niveau, zoals Python of SQL, worden geïnterpreteerd.

Soms is er voor één taal en compiler, en tolk. In dit geval kunt u een interpreter gebruiken om het programma te ontwikkelen en te testen, en vervolgens het foutopsporingsprogramma compileren om de uitvoering ervan te versnellen. Er is een interpenetratie van vertaal- en interpretatieprocessen: tolken kunnen compilers zijn (inclusief die met dynamische compilatie), en vertalers kunnen interpretatie nodig hebben voor metaprogrammeringsconstructies (bijvoorbeeld macro's in assembleertaal, voorwaardelijke compilatie in C of sjablonen in C ++ ).

4. Vertalen en tolken zijn verschillende processen: vertaling houdt zich bezig met het vertalen van programma's van de ene taal naar de andere, en tolken is verantwoordelijk voor de uitvoering van programma's. Aangezien het doel van vertalen echter meestal is om het programma voor te bereiden op vertolking, worden deze processen meestal samen beschouwd.

Conclusie: Het nadeel van een compiler is de bewerkelijkheid van het vertalen van programmeertalen die data-georiënteerde en complexe structuren zijn, vaak van tevoren onbekend of dynamisch veranderend tijdens de werking van het programma. Vervolgens moeten veel extra controles in de machinecode worden ingevoegd, de beschikbaarheid van besturingssysteembronnen analyseren, deze dynamisch vastleggen en vrijgeven, complexe objecten in het computergeheugen vormen en verwerken, wat vrij moeilijk te implementeren is op het niveau van de harde schijf. gecodeerde machine-instructies, en bijna onmogelijk voor de taak.

Met de hulp van een tolk is het daarentegen mogelijk om het programma op elk moment te stoppen, de inhoud van het geheugen te onderzoeken, een dialoog met de gebruiker te organiseren, willekeurig complexe transformaties uit te voeren en tegelijkertijd constant de status van de omringende software- en hardwareomgeving, waardoor een hoge betrouwbaarheid wordt bereikt. Bij het uitvoeren van elke instructie controleert de interpreter vele kenmerken van het besturingssysteem en informeert, indien nodig, de ontwikkelaar zo gedetailleerd mogelijk over de problemen die zich voordoen. Bovendien is de tolk erg handig om te gebruiken als een hulpmiddel voor het leren van programmeren, omdat u hiermee de werkingsprincipes van elke afzonderlijke verklaring in de taal kunt begrijpen.

Het compilatieproces is onderverdeeld in verschillende fasen:

1. Voorverwerker. Het bronprogramma wordt verwerkt door bestaande macro's en headerbestanden te vervangen.

2. Lexicale en syntactische analyse. Het programma wordt omgezet in een reeks tokens en vervolgens in een interne boomweergave.

3. Wereldwijde optimalisatie. De interne representatie van het programma wordt herhaaldelijk getransformeerd om de omvang en uitvoeringstijd van het programma te verminderen.

4. Code generatie. De interne representatie wordt geconverteerd naar processorinstructieblokken, die worden geconverteerd naar assemblertekst of objectcode.

5. Montage. Als assembly-tekst wordt gegenereerd, wordt deze samengesteld om objectcode te verkrijgen.

6. Montage. De assembler combineert meerdere objectbestanden tot een uitvoerbaar bestand of bibliotheek.

op fase lexicale analyse (LA) het invoerprogramma, dat een stroom van karakters is, is verdeeld in lexemen - woorden in overeenstemming met de definities van de taal. Het belangrijkste formalisme dat ten grondslag ligt aan de implementatie van lexicale analysers zijn eindige automaten en reguliere expressies. De lexicale analysator kan in twee hoofdmodi werken: ofwel als een subroutine die door de parser wordt aangeroepen voor het volgende token, ofwel als een volledige doorgang, wat resulteert in een bestand met tokens. Tijdens het extraheren van tokens kan de LA zowel onafhankelijk tabellen met namen en constanten bouwen, als waarden geven voor elk token de volgende keer dat het wordt gebruikt. In dit geval wordt de naamtabel in opeenvolgende fasen opgebouwd (bijvoorbeeld tijdens het parseren).

In de LA-fase worden enkele (eenvoudigste) fouten gedetecteerd (ongeldige tekens, onjuiste registratie van nummers, identifiers, enz.).

Laten we het stadium van lexicale analyse in meer detail bekijken.

De belangrijkste taak van lexicale analyse - splits de invoertekst, bestaande uit een reeks afzonderlijke tekens, in een reeks woorden of lexemen, d.w.z. isoleer deze woorden uit een continue reeks tekens. Vanuit dit oogpunt zijn alle tekens van de invoerreeks verdeeld in tekens die bij sommige lexemen horen en tekens die lexemen scheiden (scheidingstekens). In sommige gevallen zijn er geen scheidingstekens tussen tokens. Aan de andere kant kunnen tokens in sommige talen onbeduidende tekens bevatten (bijvoorbeeld het spatieteken in Fortran). In C kan de scheidingswaarde van scheidingstekens worden geblokkeerd ("\" aan het einde van een regel binnen "...").

Gewoonlijk zijn alle lexemen onderverdeeld in klassen. Voorbeelden van zulke klassen zijn getallen (integer, octaal, hexadecimaal, real, etc.), identifiers, strings. Sleutelwoorden en leestekens (ook wel scheidingstekens genoemd) worden afzonderlijk gemarkeerd. Doorgaans zijn trefwoorden een eindige subset van ID's. In sommige talen (bijvoorbeeld PL/1) kan de betekenis van een lexeme afhangen van de context en is het onmogelijk om een ​​lexicale analyse los van de syntactische analyse uit te voeren.

Vanuit het oogpunt van verdere analysefasen produceert de lexicale analysator twee soorten informatie: voor de syntactische analysator, die werkt na de lexicale, is informatie over de volgorde van klassen van tokens, scheidingstekens en trefwoorden essentieel, en voor de contextanalyse, werken na de syntactische, informatie over de specifieke betekenissen van individuele tokens (identifiers, nummers, enz.).

Het algemene schema van de lexicale analysator is dus als volgt. Eerst wordt een enkel token toegewezen (misschien met behulp van scheidingstekens). Trefwoorden worden herkend ofwel door expliciete selectie rechtstreeks uit de tekst, ofwel wordt eerst een identifier toegekend, waarna wordt gecontroleerd of deze tot een reeks trefwoorden behoort.

Als het geselecteerde lexeme een scheidingsteken is, wordt het (meer precies, enkele van zijn kenmerken) uitgevoerd als resultaat van lexicale analyse. Als het geselecteerde lexeem een ​​trefwoord is, wordt het attribuut van het corresponderende trefwoord geretourneerd. Als het geselecteerde lexeme een identifier is, wordt het attribuut van de identifier geretourneerd en wordt de identifier zelf apart opgeslagen. Ten slotte, als het geselecteerde token tot een van de andere klassen tokens behoort (het token is bijvoorbeeld een getal, een tekenreeks, enz.), Dan wordt het kenmerk van de overeenkomstige klasse geretourneerd en wordt de waarde van het token opgeslagen afzonderlijk.

Een lexicale analysator kan een onafhankelijke vertaalfase zijn of een subroutine die werkt volgens het principe "geef een token". In het eerste geval (Fig. 3.1, a) is de output van de analysator een bestand met tokens, in het tweede (Fig. 3.1, b) wordt het token uitgegeven bij elke oproep naar de analysator (in dit geval, zoals een regel, het attribuut van de tokenklasse wordt geretourneerd als resultaat van de functie "lexicale analysator" en de waarde van het token wordt doorgegeven via een globale variabele). Wat betreft het omgaan met tokenwaarden, kan de parser ofwel eenvoudig de waarde van elk token retourneren, in welk geval het bouwen van objecttabellen (identifiers, strings, getallen, enz.) aan latere fasen wordt overgelaten, of hij kan zelf objecttabellen bouwen. In dit geval wordt een verwijzing naar het item naar de overeenkomstige tabel gegeven als de waarde van het lexeme.

Rijst. 3.1:

Het werk van de lexicale analysator wordt gegeven door een eindige automaat. De directe beschrijving van de staatsmachine is echter vanuit praktisch oogpunt onhandig. Om een ​​lexicale analysator te specificeren, wordt daarom in de regel ofwel een reguliere expressie ofwel een rechts-lineaire grammatica gebruikt. Alle drie de formalismen (eindige automaten, reguliere expressies en rechts-lineaire grammatica's) hebben dezelfde expressieve kracht. In het bijzonder kan men, gegeven een reguliere expressie of een rechts-lineaire grammatica, een eindige automaat construeren die dezelfde taal herkent.

De belangrijkste taak van het ontleden - analyse van de structuur van het programma. In de regel wordt een structuur begrepen als een boom die overeenkomt met het ontleden in een contextvrije grammatica van een taal. Op dit moment worden ofwel LL(1)-analyse (en zijn variant recursieve afdaling) of LR(1)-analyse en zijn varianten (LR(0), SLR(1), LALR(1) en andere) het meest gebruikt. Recursieve afdaling wordt vaker gebruikt bij het handmatig programmeren van een parser, LR(1) - bij het gebruik van automatiseringssystemen voor het bouwen van parsers.

Het resultaat van het ontleden is een syntaxisboom met links naar een tabel met namen. Het parseerproces detecteert ook fouten met betrekking tot de structuur van het programma.

In het stadium van contextuele analyse afhankelijkheden tussen delen van het programma die niet kunnen worden beschreven door contextvrije syntaxis worden onthuld. Dit zijn voornamelijk "beschrijving-gebruik"-relaties, met name analyse van objecttypen, analyse van scopes, parameterovereenkomst, labels en andere. In het proces van contextuele analyse wordt een symbolentabel gebouwd, die kan worden beschouwd als een tabel met namen, aangevuld met informatie over beschrijvingen (eigenschappen) van objecten.

Het belangrijkste formalisme dat in contextuele analyse wordt gebruikt, is: grammatica's toekennen. Het resultaat van de contextanalysefase is een toegekende programmaboom. Informatie over objecten kan worden verspreid in de boom zelf of worden geconcentreerd in afzonderlijke symbooltabellen. Het proces van contextuele analyse kan ook fouten detecteren die verband houden met het misbruik van objecten.

Dan kan het programma omgezet naar interne representatie . Dit wordt gedaan met het oog op optimalisatie en/of gemak bij het genereren van codes. Een ander doel van het converteren van een programma naar een interne representatie is de wens om draagbare compiler. Dan is alleen de laatste fase (codegeneratie) machineafhankelijk. Als interne representatie kunnen een prefix- of postfix-notatie, een gerichte graaf, triples, quadruples en andere worden gebruikt.

Er kunnen verschillende optimalisatiefasen zijn . optimalisaties meestal onderverdeeld in machine-afhankelijk en machine-onafhankelijk, lokaal en globaal. Een deel van de machine-afhankelijke optimalisatie wordt uitgevoerd tijdens de codegeneratiefase. Globale optimalisatie probeert rekening te houden met de structuur van het hele programma, het lokale - slechts kleine fragmenten ervan. Globale optimalisatie is gebaseerd op een globale stroomanalyse die wordt uitgevoerd op een programmagrafiek en is in wezen een transformatie van deze grafiek. In dit geval kan rekening worden gehouden met eigenschappen van het programma zoals interprocedurele analyse, intermodule-analyse, analyse van de levensgebieden van variabelen, enz..

Tenslotte, code generatie- de laatste fase van de vertaling. Het resultaat is ofwel een assembler module of een object (of boot) module. Tijdens het genereren van codes kunnen enkele lokale optimalisaties worden uitgevoerd, zoals registertoewijzing, selectie van lange of korte sprongen, waarbij rekening wordt gehouden met de kosten van instructies bij het kiezen van een specifieke reeks instructies. Er zijn verschillende methoden ontwikkeld voor het genereren van codes, zoals beslissingstabellen, patroonvergelijking met dynamisch programmeren en verschillende syntactische methoden.

Natuurlijk kunnen bepaalde fasen van de vertaler volledig ontbreken of worden gecombineerd. In het eenvoudigste geval van een één-pass vertaler is er geen expliciete fase voor het genereren van een tussenliggende representatie en optimalisatie, de overige fasen worden gecombineerd tot één, en er is ook geen expliciet geconstrueerde syntaxisboom.