• Adresse... En funksjonell enhet som konverterer en virtuell adresse til en ekte adresse.
• Dialog... Gir bruk av et tidsdelingsprogrammeringsspråk.
• Multipass... Danner en objektmodul etter flere visninger av kildeprogrammet.
• Tilbake... Det samme som avoversetteren. Se også: decompiler, disassembler.
• Enkelt pass... Danner en objektmodul i en sekvensiell skanning av kildeprogrammet.
• Optimalisering... Optimaliserer koden i den genererte objektmodulen.
• Syntaksorientert (syntaksdrevet). Mottar som input en beskrivelse av språkets syntaks og semantikk og en tekst på det beskrevne språket, som er oversatt i samsvar med den angitte beskrivelsen.
• Test... Et sett med assemblerspråkmakroer som lar deg angi ulike feilsøkingsprosedyrer i programmer skrevet på assemblerspråk.

Formål med kringkasting- konvertere tekst fra ett språk til et annet, noe som er forståelig for mottakeren av teksten. Når det gjelder oversetterprogrammer, er adressaten en teknisk enhet (prosessor) eller et tolkeprogram.

Prosessorspråk (maskinkode) er vanligvis lavt nivå. Det er plattformer som bruker maskinspråk på høyt nivå (for eksempel iAPX-432), men de er unntaket fra regelen på grunn av deres kompleksitet og høye kostnader. En oversetter som konverterer programmer til maskinspråk akseptert og utført direkte av prosessoren kalles kompilator.

Kompileringsprosessen består vanligvis av flere stadier: leksikalsk, syntaktisk og semantisk analyse, generering av mellomkode, optimalisering og generering av den resulterende maskinkoden. I tillegg avhenger programmet vanligvis av tjenestene som tilbys av operativsystemet og tredjepartsbiblioteker (for eksempel fil I / O eller grafisk grensesnitt), og maskinkoden til programmet må være knyttet til disse tjenestene. Kobling med statiske biblioteker gjøres av en linker eller linker (som kan være et eget program eller være en del av kompilatoren), og med operativsystemet og dynamiske biblioteker gjøres koblingen når programmet begynner å kjøre av lasteren.

Kompilatorfordel: programmet kompileres én gang og det kreves ingen ekstra konverteringer for hver kjøring. Følgelig kreves det ingen kompilator på målmaskinen som programmet kompileres for. Ulempe: et separat kompileringstrinn senker skriving og feilsøking og gjør det vanskelig å kjøre små, enkle eller engangsprogrammer.

En annen implementeringsmetode er når programmet kjøres med tolk ingen sending i det hele tatt. Tolken simulerer programmatisk en maskin hvis hente-utførelsessyklus fungerer med instruksjoner på høynivåspråk, og ikke med maskininstruksjoner. Denne programvaresimuleringen skaper en virtuell maskin som implementerer språket. Denne tilnærmingen kalles ren tolkning. Ren tolkning brukes vanligvis for språk med en enkel struktur (for eksempel APL eller Lisp). Kommandolinjetolkere behandler kommandoer i skript på UNIX eller i batchfiler (.bat) på MS-DOS, også vanligvis i ren tolkningsmodus.

Fordelen med en ren tolk: fraværet av mellomhandlinger for oversettelse forenkler implementeringen av tolken og gjør den mer praktisk å bruke, inkludert i interaktiv modus. Ulempen er at tolken må være tilgjengelig på målmaskinen hvor programmet skal kjøres.

Det er avveininger mellom kompilering og rene tolkningsalternativer for å implementere programmeringsspråk, når tolken, før han kjører programmet, oversetter det til et mellomspråk (for eksempel bytekode eller p-kode), mer praktisk for tolkning (det vil si at vi er snakker om en tolk med en innebygd oversetter) ... Dette kalles en blandet implementering. Et eksempel på en blandet språkimplementering er Perl. Denne tilnærmingen kombinerer både fordelene med en kompilator og en tolk (høy utførelseshastighet og brukervennlighet) og ulemper (ytterligere ressurser kreves for å oversette og lagre et program på et mellomspråk; en tolk må stilles til rådighet for å kjøre programmet på målmaskin). Som med kompilatoren, krever den blandede implementeringen at kildekoden er fri for leksikalske, syntaktiske og semantiske feil før kjøring.

Kringkaste og tolkning- ulike prosesser: oversettelse omhandler oversettelse av programmer fra ett språk til et annet, og tolking er ansvarlig for gjennomføringen av programmer. Men siden hensikten med oversettelse vanligvis er å forberede et program for tolkning, vurderes disse prosessene vanligvis sammen. For eksempel karakteriseres programmeringsspråk ofte som "kompilert" eller "tolket", avhengig av om kompilering eller tolkning dominerer i språket som brukes. Dessuten er nesten alle lavnivå- og tredjegenerasjons programmeringsspråk, som assembler, C eller Modula-2, kompilert, og høyere nivåspråk, som Python eller SQL, tolkes.

På den annen side er det en interpenetrasjon av oversettelses- og tolkningsprosesser: tolker kan kompilere (inkludert dynamisk kompilering), og tolker kan kreve tolkning for (for eksempel for makroer i assemblerspråk, betinget kompilering i C, eller for maler i C ++).

Dessuten kan ett og samme programmeringsspråk oversettes og tolkes, og i begge tilfeller må det være generelle stadier av analyse og gjenkjennelse av konstruksjoner og direktiver for kildespråket. Dette gjelder både programvare- og maskinvareimplementeringer - for eksempel, prosessorer av x86-familien, før de utfører maskinspråkinstruksjoner, utfører dekodingen, fremhever feltene til operander (registre, minneadresser, umiddelbare verdier), bitbredde osv. i opcodes, og i prosessorene Pentium med NetBurst-arkitektur er maskinkode generelt oversatt til en sekvens av mikrooperasjoner før den lagres i den interne cachen.

Hver datamaskin har sitt eget programmeringsspråk - kommandospråk eller maskinspråk - og kan kjøre programmer som kun er skrevet på det språket. I prinsippet kan enhver algoritme beskrives ved hjelp av et maskinspråk, men programmeringskostnadene vil være ekstremt høye. Dette skyldes det faktum at maskinspråk lar deg beskrive og behandle kun primitive datastrukturer - bit, byte, ord. Programmering i maskinkoder krever overdreven detaljering av programmet og er kun tilgjengelig for programmerere som er godt klar over strukturen og driften av datamaskiner. Språk på høyt nivå (Fortran, PL / 1, Pascal, C, Ada, etc.) med utviklede datastrukturer og midler for deres behandling som ikke er avhengig av språket til en bestemt datamaskin tillatt å overvinne denne vanskeligheten.

Algoritmiske språk på høyt nivå gjør det mulig for programmereren å beskrive algoritmer for å løse mange anvendte problemer på en ganske enkel og praktisk måte. Denne beskrivelsen kalles det originale programmet og språket på høyt nivå er inndataspråk.

Språkprosessor refererer til et maskinspråkprogram som gjør det mulig for en datamaskin å forstå og kjøre programmer på et inndataspråk. Det er to hovedtyper språkbehandlere: tolker og oversettere.

Tolk Er et program som aksepterer et program på inndataspråket som input, og ettersom konstruksjonene til inputspråket gjenkjennes, implementerer det dem, og sender ut resultatene av beregninger foreskrevet av det originale programmet.

Oversetter Er et program som aksepterer det originale programmet ved inngangen og ved utgangen genererer et program som funksjonelt tilsvarer originalen, kalt gjenstand... Et objektprogram er skrevet på et objektspråk. I et spesielt tilfelle kan et maskinspråk tjene som et objektspråk, og i dette tilfellet kan programmet som er oppnådd ved utgangen av oversetteren, kjøres umiddelbart på en datamaskin (tolkes). I dette tilfellet er datamaskinen en tolk av objektprogrammet i maskinkoder. Generelt trenger ikke et objektspråk å være maskinspråk eller noe i nærheten av det (autokode). Som et objektspråk, noen mellomspråk- språket som ligger mellom inndata- og maskinspråket.

Hvis et mellomspråk brukes som objektspråk, er det to alternativer for å konstruere en oversetter.

Det første alternativet - for mellomspråket er det (eller er under utvikling) en annen oversetter fra mellomspråket til maskinspråket, og den brukes som den siste blokken i den utformede oversetteren.

Det andre alternativet for å bygge en oversetter med et mellomspråk er å bygge en kommandotolk for mellomspråk og bruke den som den siste blokken til oversetteren. Fordelen med tolker kommer til uttrykk i feilsøkings- og dialogoversettere, som sikrer brukerens arbeid i en dialogmodus, opp til å gjøre endringer i programmet uten å helt oversette det på nytt.

Tolker brukes også i programemulering - kjøring på en teknologisk maskin av programmer kompilert for en annen (objekt) maskin. Dette alternativet brukes spesielt ved feilsøking av programmer på en universell datamaskin som skal kjøres på en spesialisert datamaskin.

En oversetter som bruker et maskinlignende språk (autokode eller assembler) som inndataspråk kalles tradisjonelt montør... Oversetteren for høynivåspråket kalles kompilator.

Det er gjort betydelige fremskritt innen kompilatorkonstruksjon de siste årene. De første kompilatorene brukte den såkalte metoder for direktesending- Dette er hovedsakelig heuristiske metoder, der det, på grunnlag av en generell idé, for hver språkkonstruksjon, ble utviklet sin egen algoritme for å oversette til en maskinekvivalent. Disse metodene var langsomme og ikke-strukturelle.

Designmetodikken til moderne kompilatorer er basert på komposisjonell syntaks-drevet metode behandlingsspråk... Komposisjonell i den forstand at prosessen med å oversette kildeprogrammet til et objektprogram implementeres av en sammensetning av funksjonelt uavhengige kartlegginger med eksplisitt distingerte input- og outputdatastrukturer. Disse kartleggingene er bygget opp fra å betrakte kildeprogrammet som en sammensetning av hovedaspektene (nivåene) ved beskrivelsen av inngangsspråket: vokabular, syntaks, semantikk og pragmatikk, og identifisere disse aspektene fra kildeprogrammet under kompileringen. La oss vurdere disse aspektene for å få en forenklet kompilatormodell.

Grunnlaget for ethvert naturlig eller kunstig språk er alfabet- et sett med elementære tegn (bokstaver, tall og tjenestetegn) som er tillatt på språket. Skilt kan kombineres til ordene- elementære språkkonstruksjoner, betraktet i teksten (programmet) som udelelige symboler som har en viss betydning.

Et enkelt tegn kan også være et ord. For eksempel, i Pascal-språket, er ord identifikatorer, nøkkelord, konstanter og skilletegn, spesielt tegn på aritmetiske og logiske operasjoner, parenteser, kommaer og andre symboler. Språkets vokabular, sammen med en beskrivelse av måtene de presenteres på, utgjør ordforråd Språk.

Ord i et språk kombineres til mer komplekse strukturer - setninger. I programmeringsspråk er den enkleste setningen operatøren. Setninger er bygget opp av ord og enklere setninger i henhold til syntaksreglene. Syntaks språk er en beskrivelse av riktige setninger. Beskrivelse av betydningen av setninger, dvs. betydningen av ord og deres interne forbindelser, er semantikk Språk. I tillegg merker vi at et spesifikt program har en viss effekt på oversetteren - pragmatisme... Samlet syntaks, semantikk og pragmatisme i språkformen semiotikk Språk.

Oversettelse av et program fra ett språk til et annet, i det generelle tilfellet, består i å endre alfabetet, vokabularet og syntaksen til programspråket samtidig som dets semantikk bevares. Prosessen med å oversette et kildeprogram til et objektprogram er vanligvis delt inn i flere uavhengige underprosesser (oversettelsesfaser), som implementeres av de tilsvarende blokkene til oversetteren. Det er praktisk å vurdere hovedfasene av oversettelsesleksikalsk analyse, parsing, semantisk analyse og

syntese av et objektprogram. Men i mange virkelige kompilatorer er disse fasene delt inn i flere underfaser, og det kan også være andre faser (for eksempel objektkodeoptimalisering). I fig. 1.1 viser en forenklet funksjonell modell av oversetteren.

I samsvar med denne modellen er inputprogrammet for det første utsatt for leksikalsk behandling. Hensikten med leksikalsk analyse er å oversette kildeprogrammet til kompilatorens interne språk, der nøkkelord, identifikatorer, etiketter og konstanter reduseres til samme format og erstattes av betingede koder: numeriske eller symbolske, som kalles deskriptorer. Hver deskriptor består av to deler: en klasse (type) av et token og en peker til en adresse i minnet hvor informasjon om et bestemt token er lagret. Denne informasjonen er vanligvis organisert i tabeller. Samtidig med oversettelsen av det originale programmet til det interne språket på stadiet av leksikalsk analyse, leksikalsk kontroll- påvisning av ugyldige ord i programmet.

Parseren tar utdataene fra den leksikale analysatoren og oversetter sekvensen av symbolske bilder til mellomvare. En mellomvare er i hovedsak en syntakstrepresentasjon av et program. Sistnevnte gjenspeiler strukturen til det opprinnelige programmet, dvs. orden og kommunikasjon mellom operatørene. Under konstruksjonen av syntakstreet, syntaktisk kontroll- identifikasjon av syntaksfeil i programmet.

Den faktiske utgangen av parsingen kan være sekvensen av kommandoer som trengs for å bygge mellomvaren, få tilgang til oppslagstabellene og utstede en diagnostisk melding når det er nødvendig.

Ris. 1.1. Forenklet funksjonell oversettermodell

Syntesen av et objektprogram begynner som regel med allokering og allokering av minne for hovedprogramobjektene. Deretter undersøkes hver setning i kildeprogrammet og semantisk ekvivalente setninger av objektspråket genereres. Syntakstreet til programmet og utdatatabellene til den leksikale analysatoren - tabellen med identifikatorer, tabellen med konstanter og andre - brukes som inputinformasjon. Analysen av treet lar deg identifisere sekvensen av genererte kommandoer til objektprogrammet, og tabellen med identifikatorer bestemmer hvilke typer kommandoer som er tillatt for verdiene til operandene i de genererte kommandoene (for eksempel hvilke instruksjoner må genereres: med fast eller flytende punkt, etc.).

Genereringen av selve objektprogrammet innledes ofte med semantisk analyse som inkluderer ulike typer semantisk prosessering. En av typene er å sjekke de semantiske konvensjonene i programmet. Eksempler på slike konvensjoner: den unike beskrivelsen av hver identifikator i programmet, definisjonen av en variabel lages før den brukes osv. Semantisk analyse kan utføres på senere stadier av oversettelsen, for eksempel på stadiet av programoptimalisering, som også kan inkluderes i oversetteren. Målet med optimalisering er å redusere tiden eller minneressursene som kreves for å utføre et objektprogram.

Dette er hovedaspektene ved oversettelsesprosessen fra språk på høyt nivå. Organiseringen av de ulike fasene av oversettelsen og de tilhørende praktiske måtene å beskrive dem matematisk på er diskutert mer detaljert nedenfor.

Send det gode arbeidet ditt i kunnskapsbasen er enkelt. Bruk skjemaet nedenfor

Studenter, hovedfagsstudenter, unge forskere som bruker kunnskapsbasen i studiene og arbeidet vil være veldig takknemlige for deg.

Skrevet på http://www.allbest.ru

Introduksjon

1.1 Top-down parsing

1.2 Bottom-up parsing

1.2.1 LR (k) - grammatikk

1.2.1.1 LR (0) - grammatikk

1.2.2 LALR (1) - grammatikk

2. Utvikling av oversetteren

2.1 Kravanalyse

2.2 Design

2.2.1 Designe en leksikalsk analysator

2.2.4 Programvareimplementering av parseren

2.3 Koding

2.4 Testing

Konklusjon

Liste over kilder som er brukt

Vedlegg A. Liste over programteksten til oversetteren

Vedlegg B. Testresultater

Vedlegg B. Opplegg for oversetterprogrammet

Introduksjon

For lengst er tiden borte da det, før du skrev et program, var nødvendig å forstå og huske mer enn et dusin maskininstruksjoner. En moderne programmerer formulerer oppgavene sine i programmeringsspråk på høyt nivå og bruker assemblerspråk kun i unntakstilfeller. Som du vet, blir algoritmiske språk tilgjengelige for programmereren først etter opprettelsen av oversettere fra disse språkene.

Programmeringsspråk er ganske forskjellige fra hverandre i formål, struktur, semantisk kompleksitet, implementeringsmetoder. Dette påtvinger sine egne spesifikke trekk ved utviklingen av spesifikke oversettere.

Programmeringsspråk er verktøy for å løse problemer i forskjellige fagområder, som bestemmer spesifikke organisasjoner og forskjeller i formål. Eksempler inkluderer språk som Fortran, som er fokusert på vitenskapelig databehandling, C, som er ment for systemprogrammering, Prolog, som effektivt beskriver inferensproblemer, Lisp, som brukes til rekursiv listebehandling. Disse eksemplene kan fortsettes. Hvert av fagområdene har sine egne krav til organiseringen av selve språket. Derfor kan vi merke oss en rekke former for representasjon av operatører og uttrykk, en forskjell i settet med grunnleggende operasjoner, en reduksjon i programmeringseffektivitet når du løser problemer som ikke er relatert til fagområdet. Språkforskjeller gjenspeiles i strukturen til oversetterne. Lisp og Prolog utføres oftest i tolkningsmodus på grunn av at de bruker dynamisk dannelse av datatyper under beregninger. Fortran-oversettere er preget av aggressiv optimalisering av den resulterende maskinkoden, noe som blir mulig på grunn av den relativt enkle semantikken til språkkonstruksjonene – spesielt på grunn av fraværet av mekanismer for alternativ navngivning av variabler gjennom pekere eller referanser. Tilstedeværelsen av pekere i C-språket stiller spesifikke krav til dynamisk minneallokering.

Strukturen til et språk karakteriserer det hierarkiske forholdet mellom dets konsepter, som er beskrevet av syntaktiske regler. Programmeringsspråk kan være svært forskjellige fra hverandre i organiseringen av individuelle konsepter og i forholdet mellom dem. Programmeringsspråket PL / 1 tillater vilkårlig nesting av prosedyrer og funksjoner, mens i C må alle funksjoner være på det ytre nesting-nivået. C ++-språket tillater deklarasjon av variabler på ethvert punkt i programmet før det brukes første gang, og i Pascal må variabler defineres i et spesielt beskrivelsesområde. Lenger ned på linjen er PL / 1, som gjør at en variabel kan deklareres etter at den er brukt. Eller beskrivelsen kan utelates helt og styres av standardreglene. Avhengig av beslutningen som er tatt, kan oversetteren analysere programmet i en eller flere omganger, noe som påvirker sendehastigheten.

Semantikken til programmeringsspråk varierer mye. De skiller seg ikke bare i særegenhetene ved implementeringen av individuelle operasjoner, men også i programmeringsparadigmene som bestemmer grunnleggende forskjeller i metodene for programutvikling. Spesifikasjonene for gjennomføringen av operasjoner kan relatere seg til både strukturen til de behandlede dataene og reglene for behandling av de samme datatypene. Språk som PL / 1 og APL støtter matrise- og vektoroperasjoner. De fleste språk fungerer hovedsakelig med skalarer, og gir prosedyrer og funksjoner skrevet av programmerere for å behandle arrays. Men selv når du legger til to heltall, kan språk som C og Pascal oppføre seg annerledes.

Sammen med tradisjonell prosedyreprogrammering, også kalt imperativ programmering, er det slike paradigmer som funksjonell programmering, logisk programmering og objektorientert programmering. Strukturen til konsepter og objekter av språk avhenger sterkt av det valgte paradigmet, som også påvirker implementeringen av oversetteren.

Selv samme språk kan implementeres på flere måter. Dette skyldes det faktum at teorien om formell grammatikk åpner for ulike metoder for å analysere de samme setningene. Følgelig kan oversettere på forskjellige måter få samme resultat (objektprogram) fra den originale kildekoden.

Imidlertid har alle programmeringsspråk en rekke felles egenskaper og parametere. Dette fellesskapet bestemmer også prinsippene for organisering av oversettere som er like for alle språk.

Programmeringsspråk er designet for å gjøre programmering enklere. Derfor er deres operatører og datastrukturer kraftigere enn maskinspråk.

For å øke synligheten til programmer, i stedet for numeriske koder, brukes symbolske eller grafiske representasjoner av språkkonstruksjoner, som er mer praktisk for menneskelig oppfatning.

For ethvert språk er det bestemt:

- mange symboler som kan brukes til å skrive de riktige programmene (alfabet), grunnleggende elementer,

- mange riktige programmer (syntaks),

- "meningen" av hvert riktig program (semantikk).

Uavhengig av spesifikasjonene til språket, kan enhver oversetter betraktes som en funksjonell omformer F som gir en entydig kartlegging av X til Y, der X er et program på kildespråket, Y er et program i utgangsspråket. Derfor kan selve oversettelsesprosessen formelt presenteres ganske enkelt og tydelig: Y = F (X).

Formelt sett er hvert riktige program X en tegnstreng fra et eller annet alfabet A, som er transformert til den tilsvarende strengen Y, sammensatt av tegn fra alfabetet B.

Et programmeringsspråk, som ethvert komplekst system, er definert gjennom et hierarki av konsepter som definerer relasjonene mellom dets elementer. Disse begrepene er relatert til hverandre i samsvar med syntaktiske regler. Hvert av programmene bygget i henhold til disse reglene har en tilsvarende hierarkisk struktur.

I denne forbindelse, for alle språk og deres programmer, kan følgende generelle funksjoner skilles i tillegg: hvert språk må inneholde regler som tillater generering av programmer som tilsvarer dette språket eller gjenkjenner samsvaret mellom skriftlige programmer og et gitt språk.

Et annet karakteristisk trekk ved alle språk er deres semantikk. Det bestemmer betydningen av operasjonene til språket, riktigheten av operandene. Kjeder som har samme syntaktiske struktur i forskjellige programmeringsspråk kan variere i semantikk (som for eksempel observeres i C ++, Pascal, Basic). Kunnskap om språkets semantikk lar deg skille det fra syntaksen og bruke det til konvertering til et annet språk (for å generere kode).

Formålet med dette kursarbeidet er å utvikle en pedagogisk oversetter fra et gitt forenklet tekstspråk på høyt nivå.

1. Metoder for analyse

La oss se på de grunnleggende metodene for parsing.

1.1 Top-down parsing

Ved parsing fra topp til bunn beveger de mellomliggende ledningene seg langs treet i retning fra roten til bladene. I dette tilfellet, når du ser på kjeden fra venstre til høyre, vil venstre konklusjoner naturlig bli oppnådd. Med deterministisk parsing vil problemet være hvilken regel som skal brukes for å utvide den ikke-terminalen lengst til venstre.

1.1.1 LL (k) - språk og grammatikk

Vurder utdatatreet mens du henter venstre utgang av kjeden. Den mellomliggende kjeden i produksjonsprosessen består av kjeden av terminaler w, den ikke-terminale A lengst til venstre, den ikke-leverte delen av x:

-S--

/ \

/ -A-x- \

/ | \

-w --- u ----

Bilde 1

For å fortsette å analysere, er det nødvendig å erstatte ikke-terminal A i henhold til en av reglene for formen A: y. Hvis du vil at parsingen skal være deterministisk (ingen tilbakesporing), må du velge denne regelen på en spesiell måte. En grammatikk sies å ha LL (k)-egenskapen hvis det, for å velge en regel, er tilstrekkelig å vurdere bare wAx og de første k tegnene i den usynlige strengen u. Den første L (venstre) refererer til venstre-til-høyre-gjennomgang av inngangstrinn, den andre til venstre pinnen i bruk.

La oss definere to sett med kjeder:

a) FØRSTE (x) - settet med terminalstrenger avledet fra x, forkortet til k tegn.

b) FØLG (A) - et sett med terminalstrenger forkortet til k tegn, som umiddelbart kan følge A i utgangsstrengene.

En grammatikk har egenskapen LL (k) hvis fra eksistensen av to kjeder av venstrehåndsslutninger:

S :: voks: wzx :: wu

S :: voks: wtx :: wv

betingelsen FØRSTE (u) = FØRSTE (v) innebærer z = t.

I tilfellet k = 1, for å velge en regel for A, er det nok å vite bare den ikke-terminale A og a - det første tegnet i kjeden u:

- du bør velge regelen A: x, hvis a er inkludert i FØRST (x),

- du bør velge regel A: e hvis a er inkludert i FØLG (A).

LL (k)-egenskapen legger ganske sterke begrensninger på grammatikk. For eksempel, LL (2) grammatikk S: aS | a har ikke egenskapen LL (1), siden FØRSTE (aS) = FØRSTE (a) = a. I dette tilfellet kan du senke verdien av k ved å bruke "faktorisering" (ta faktoren ut av parentesen):

S: aA

A: S | e

Enhver LL (k) -grammatikk er entydig. En venstre rekursiv grammatikk tilhører ikke klasse LL (k) for noen k. Noen ganger er det mulig å transformere en ikke-LL (1) grammatikk til en ekvivalent LL (1) grammatikk ved å eliminere venstre rekursjon og faktorisering. Problemet med eksistensen av en ekvivalent LL (k) -grammatikk for en vilkårlig ikke-LL (k) -grammatikk er imidlertid uavgjørelig.

1.1.2 Rekursiv nedstigningsmetode

Den rekursive nedstigningsmetoden er fokusert på de tilfellene der kompilatoren er programmert på et av høynivåspråkene der rekursive prosedyrer er tillatt.

Den grunnleggende ideen med rekursiv nedstigning er at hver ikke-terminal i grammatikken har en tilsvarende prosedyre som gjenkjenner enhver streng generert av den ikke-terminalen. Disse rutinene ringer hverandre ved behov.

Rekursiv nedstigning kan brukes for enhver LL (1) grammatikk. Hver ikke-terminal i grammatikken har en tilsvarende prosedyre som begynner med en overgang til en beregnet etikett og inneholder koden som tilsvarer hver regel for den gitte ikke-terminalen. For de inndatategnene som tilhører utvalgssettet til denne regelen, overfører den beregnede grenen kontrollen til koden som samsvarer med denne regelen. For resten av inndatategnene overføres kontrollen til feilhåndteringsrutinen.

Koden til en hvilken som helst regel inneholder operasjoner for hvert tegn som er inkludert på høyre side av regelen. Operasjonene er ordnet i den rekkefølgen tegnene er plassert i regelen. Etter den siste operasjonen inneholder koden returen fra prosedyren.

Å bruke rekursiv nedstigning i et språk på høyt nivå gjør programmering og feilsøking enklere.

1.2 Bottom-up parsing

Vurder nedenfra og opp-parsing, der pinnene beveger seg gjennom treet mot roten. Hvis du leser tegnene i strengen fra venstre til høyre, vil parsetreet se slik ut:

-S--

/ \

/ -x- \

/ | \

--w - b - u-

Bilde 2

Den mellomliggende utgangen er av formen xbu, der x er kjeden av terminaler og ikke-terminaler som den viste delen av terminalkjeden w er utgang fra, bu er den uviste delen av terminalkjeden, b er det neste tegnet. For å fortsette å analysere, kan du enten legge til tegnet b til den viste delen av kjeden (utfør den såkalte "shiften"), eller velge på slutten av x en slik kjede z (x = yz) som en av reglene av grammatikk B: z kan brukes på z og erstattes x til kjeden yB (utfør den såkalte "convolution"):

-S-- -S--

/ \ / \

/ -x-b- \ / yB- \

/ | \ / | \

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

Figur 3 - Etter skift Figur 4 - Etter konvolusjon

Hvis konvolusjonen bare brukes på de siste tegnene i x, vil vi få de riktige pinnene i kjeden. Denne analysen kalles LR, der tegnet L (venstre, venstre) refererer til å se trinnet fra venstre til høyre, og R (høyre, høyre) refererer til de resulterende pinnene.

Sekvensen av skift- og foldoperasjoner er avgjørende. Derfor, for deterministisk parsing, kreves det i hvert øyeblikk å velge mellom skift og konvolusjon (og forskjellige konvolusjonsregler).

1.2.1 LR (k) - grammatikk

Hvis det, i prosessen med LR-parsing, er mulig å ta en deterministisk avgjørelse om skiftet / konvolusjonen, med tanke på bare strengen x og de første k tegnene i den uleste delen av inndatastrengen u (disse k tegnene kalles pre-chain), så sies grammatikken å ha LR (k) -egenskapen.

-S--

/ \

/ -x- \

--w ---- u--

Figur 5

Forskjellen mellom LL (k) - og LR (k) -grammatikk når det gjelder et slutningstre:

-S-

/ | \

/ A \

/ / \ \

-w --- v --- u-

Figur 6

Når det gjelder LL (k) -grammatikker, kan regelen som brukes på A bestemmes unikt av w og de første k-symbolene vu, og i tilfellet med LR (k) -grammatikker, av w, v og den første k symboler u. Dette løse resonnementet viser at LL (k) -språk< LR(k)-языки (при k > 0).

1.2.1.1 LR (0) - grammatikk

La oss først vurdere de enkleste grammatikkene i denne klassen - LR (0). Når du analyserer en LR (0) -språkstreng, trenger du ikke bruke pre-strengen i det hele tatt - valget mellom shift og convolution gjøres basert på strengen x. Siden den endres bare fra høyre ende under parsing, kalles den en stack. Vi vil anta at det ikke er noen ubrukelige symboler i grammatikken, og det første tegnet vises ikke på høyresiden av reglene - da signaliserer konvolusjonen til det innledende tegnet vellykket fullføring av parsing. La oss prøve å beskrive settet med kjeder fra terminaler og ikke-terminaler som vises på stabelen i løpet av all LR-parsing (med andre ord, alle riktige deduksjoner fra grammatikken).

Vi definerer følgende sett:

L (A:v) er venstre kontekst til regel A: v er settet med stabeltilstander, like før kollapsen av v til A under all vellykket LR-parsing. Det er klart at hver kjede fra L (A:v) ender på v. Hvis vi kutter av halen v på alle slike kjeder, får vi et sett med kjeder som oppstår til venstre for A i prosessen med alle vellykkede høyre slutninger. La oss betegne dette settet med L (A) - den venstre konteksten til den ikke-terminale A.

La oss konstruere en grammatikk for mengden L (A). Terminalene til den nye grammatikken vil være terminalene og ikke-terminalene til den opprinnelige grammatikken, ikke-terminalene til den nye grammatikken vil bli betegnet med , ... - verdiene deres er de venstre ikke-terminale kontekstene til den originale grammatikken. Hvis S er starttegnet til den opprinnelige grammatikken, vil grammatikken til venstre kontekster inneholde regelen : e - venstre kontekst S inneholder en tom streng For hver regel i den opprinnelige grammatikken, for eksempel A: B C d E

og legg reglene til den nye grammatikken:

: - L (B) inkluderer L (A)

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

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

Den resulterende grammatikken har en spesiell form (slike grammatikker kalles venstre-lineære), derfor settet med venstrekontekster

- er regelmessige. Det følger av dette at tilhørigheten til en kjede til venstre kontekst til en eller annen ikke-terminal kan beregnes induktivt ved å bruke en begrenset automat, som ser gjennom kjeden fra venstre til høyre. La oss beskrive denne prosessen konstruktivt.

La oss kalle en LR (0) -situasjon en grammatikkregel med én markert posisjon mellom symbolene på høyre side av regelen. For eksempel, for grammatikk S: A; A: aAA; A: b følgende LR (0) -situasjoner eksisterer: S: _A; S: A_; A: _aAA; A: a_AA; A: aA_A; A: aAA_; A: _b; A: b_. (posisjonen er angitt med understrekingstegnet).

Vi sier at kjeden x er kompatibel med situasjonen A: b_c hvis x = ab og a tilhører L (A). (Med andre ord, LR-utgang kan fortsettes x _... = ab _... :: abc _... :: aA _... :: S_.) I disse termene, L (A: b) er et sett med strenger matchet med situasjon A: b_, L (A)

- kjeder i samsvar med situasjon A: _b, for enhver regel A: b.

La V (u) være settet av situasjoner i samsvar med u. La oss vise at funksjonen V er induktiv.

Hvis settet V (u) inkluderer en situasjon A: b_cd, så tilhører situasjon A: bc_d V (uc). (c - terminal eller ikke-terminal; b, d - sekvenser (kan være tomme) av terminaler og ikke-terminaler). Det er ingen andre situasjoner som A: b_d med ikke-tom b i V (uc). Det gjenstår å legge til situasjoner av formen C: _... til V (uc), for hver ikke-terminal C hvis venstre kontekst inneholder uc. Hvis situasjon A: ..._ C ... (C-ikke-terminal) tilhører mengden V (uc), så tilhører uc L (C) og V (uc) inkluderer situasjoner av formen C: _... for alle C-grammatikkregler.

V (e) inneholder situasjoner S: _... (S-starttegn), samt situasjoner A: _... hvis ikke-terminal A oppstår umiddelbart etter _ i situasjoner som allerede er inkludert i V (e).

Til slutt er vi klare til å definere en LR (0) grammatikk. La u være innholdet i stabelen i prosessen med LR-parsing, V (u) settet med LR (0) situasjoner i samsvar med u. Hvis V (u) inneholder en situasjon av formen А: x_ (en x-sekvens av terminaler og ikke-terminaler), så tilhører u L (A: x) og konvolusjonen av x i A er tillatt. Hvis V (u) inneholder en situasjon A: ..._ a. .. (a-terminal), så tillates et skift. Man snakker om en skift-konvolusjon-konflikt hvis både skift og konvolusjon er tillatt for én kjede u. Snakk om en konvolusjon-konvolusjon-konflikt hvis konvolusjoner etter forskjellige regler er tillatt.

En grammatikk kalles LR (0) hvis det ikke er noen skift-fold- eller fold-fold-konflikter for alle stabeltilstander i LR-utdataprosessen.

1.2.1.2 LR (k) - grammatikk

LR (0)-parsing bruker bare stabeltilstanden til å velge mellom shift eller fold. LR (k)-parsing tar også hensyn til de første k tegnene i den usynlige delen av inngangsstrengen (den såkalte avanchang). For å underbygge metoden bør man nøye gjenta resonnementet i forrige avsnitt, og gjøre endringer i definisjonene.

Vi vil også inkludere auchain i venstre kontekst av regelen. Hvis den høyre utgangen bruker utgangen wAu: wvu, så tilhører paret wv, FIRSTk (u) Lk (A: v), og paret w, FIRSTk (u) tilhører Lk (A). Settet med venstre kontekster, som i tilfellet med LR (0), kan beregnes ved induksjon på venstre kjede. La oss kalle en LR (k) -situasjon et par: en grammatikkregel med en markert posisjon og en avanchain med lengde på det meste k. Vi vil skille regelen fra pre-kjeden med en vertikal linje.

Vi sier at kjeden x stemmer overens med situasjon A: b_c | t hvis det er en LR-utgang: x_yz = ab_yz :: abc_z :: aA_z :: S_, og FIRSTk (z) = t. Reglene for induktiv beregning av settet med tilstander Vk er som følger:

Vk (e) inneholder situasjoner S: _a | e for alle regler S: a, hvor S er starttegnet. For hver situasjon A: _Ba | u fra Vk (e), hver regel B: b, og en kjede x som tilhører FIRSTk (au), er det nødvendig å legge til situasjon B: _b | x til Vk (e).

Hvis situasjon A: b_cd | u går inn i Vk (w), vil situasjon A: bc_d | u tilhøre Vk (wc). For hver situasjon A: b_Cd | u fra Vk (wc), hver regel C: f og en kjede x som tilhører FIRSTk (du), legg til situasjonen C: _f | x til Vk (wc).

Vi bruker de konstruerte settene med LR (k) -tilstander for å løse skift-konvolusjon-problemet. La u være innholdet i stabelen og x være avanchain. Det er åpenbart at konvolusjonen i henhold til regelen A: b kan utføres hvis Vk (u) inneholder situasjonen A: b_ | x. Å avgjøre om et skifte er tillatt krever nøye oppmerksomhet hvis grammatikken inneholder e-regler. I situasjon A: b_c | t (c er ikke tom), er et skift mulig hvis c starter med en terminal og x tilhører FIRSTk (ct). Uformelt sett kan du skyve tegnet lengst til venstre på høyre side av regelen inn på stabelen, og forberede den påfølgende folden. Hvis c starter med en ikke-terminal (situasjonen ser ut som A: b_Cd | t), er det kun mulig å skyve et tegn på stabelen, forberede en fold i C hvis C ikke genererer en tom kjede. For eksempel, i tilstanden V(e) = S: _A | e; A: _AaAb | e, a, A: _ | e, a det er ingen gyldige skift, fordi når du sender ut terminalkjeder fra A på et eller annet trinn, er det nødvendig å bruke regelen A: e på ikke-terminalen A som er plassert i venstre ende av kjeden.

La oss definere settet EFFk (x), som består av alle elementene i settet FIRSTk (x), i hvis utgang ikke-terminalen i venstre ende av x (hvis noen) ikke erstattes med en tom streng. I disse termene er et skift tillatt hvis settet Vk (u) inneholder en situasjon A: b_c | t, c er ikke tom og x tilhører EFFk (ct).

En grammatikk kalles en LR (k) -grammatikk hvis ingen LR (k) tilstand inneholder to situasjoner A: b_ | u og B: c_d | v slik at u tilhører EFFk (dv). Et slikt par tilsvarer en konvolusjon-konvolusjon-konflikt hvis d er tom, og en skift-konvolusjon-konflikt hvis d ikke er tom.

I praksis brukes ikke LR (k) -grammatikker for k> 1. Det er to grunner til dette. For det første: et veldig stort antall stater LR (k). For det andre: for ethvert språk definert av en LR (k) -grammatikk, er det en LR (1) -grammatikk; dessuten, for ethvert deterministisk CF-språk er det en LR (1) -grammatikk.

Antallet LR (1) -tilstander for praktisk interessante grammatikk er også ganske stort. Slike grammatikker har sjelden egenskapen LR (0). I praksis brukes ofte mellommetoden mellom LR (0) og LR (1), kjent som LALR (1).

1.2.2 LALR (1) - grammatikk

Disse to metodene er basert på samme idé. La oss konstruere et sett med kanoniske LR (0) -tilstander i grammatikken. Hvis dette settet ikke inneholder konflikter, kan en LR (0) -parser brukes. Ellers vil vi forsøke å løse konfliktene som har oppstått ved å vurdere forkjeden med enkelttegn. Med andre ord, la oss prøve å bygge en LR (1) parser med mange LR (0) tilstander.

LALR (1) -metode (Look Ahead - Looking Ahead) er som følger. La oss introdusere en ekvivalensrelasjon på settet av LR (1) -situasjoner: vi vil vurdere to situasjoner som ekvivalente hvis de bare skiller seg med deres autokjeder. For eksempel er situasjoner A: Aa_Ab | e og A: Aa_Ab | a ekvivalente. La oss konstruere et kanonisk sett med LR (1) -tilstander og kombinere tilstandene som består av et sett med ekvivalente situasjoner.

Hvis det resulterende settet med tilstander ikke inneholder LR (1) konflikter, og derfor tillater å konstruere en LR (1) -parser, så sies grammatikken å ha LALR (1) egenskapen.

2. Utvikling av oversetteren

2.1 Kravanalyse

I dette kursarbeidet er det nødvendig å utvikle en pedagogisk oversetter i form av en tolk fra språket definert av den tilsvarende formelle grammatikken. Det er fire hovedstadier i utviklingen av en tolk:

Designe en leksikalsk analysator;

Design av en magasinmaskin;

Programvareimplementering av parseren;

Utvikling av tolkemodulen.

Utviklingen vil bli utført ved hjelp av operativsystemet Windows XP på en IBM PC med en Intel Pentium IV-prosessor.

Basert på trendene innen programvareutvikling, ble programmeringsspråket C # i Visual Studio 2010-miljøet valgt for implementering av den pedagogiske oversetteren.

2.2 Design

2.1.1 Designe en leksikalsk analysator

Leksikalsk analysen inkluderer skanning av det oversatte (kilde)programmet og gjenkjennelse av leksemene som utgjør setningene i kildeteksten. Tokens inkluderer spesielt nøkkelord, operasjonstegn, identifikatorer, konstanter, spesialtegn osv.

Resultatet av den leksikale analysatoren (skanneren) er en sekvens av tokens, og hvert token er vanligvis representert av en kode med en fast lengde (for eksempel et heltall), samt utsendelse av meldinger om syntaktiske (leksikalske) feil, hvis noen. Hvis et token for eksempel er et nøkkelord, gir koden all nødvendig informasjon. Når det for eksempel gjelder en identifikator, kreves det i tillegg navnet på den gjenkjente identifikatoren, som vanligvis registreres i en identifikatortabell, vanligvis organisert ved hjelp av lister. En lignende tabell er nødvendig for konstanter.

Et leksem kan beskrives med to hovedtrekk. En av dem er tilhørigheten av et leksem til en bestemt klasse (variabler, konstanter, operasjoner osv.) Den andre egenskapen definerer et spesifikt element i denne klassen.

Det nøyaktige utseendet til symboltabellen (datastrukturen) er irrelevant for leksikalen eller parseren. Begge trenger bare å gi muligheten til å få en indeks som unikt identifiserer for eksempel en gitt variabel og returnere indeksverdien for å fylle på informasjon om et gitt variabelnavn i symboltabellen.

ID-tabelloppslaget har to hovedfunksjoner:

a) skrive et nytt navn til tabellen når du behandler beskrivelsen av variabler;

b) søk etter et navn som tidligere er registrert i tabellen.

Dette lar deg oppdage feil som flere beskrivelser av en variabel og tilstedeværelsen av en ubeskrevet variabel.

Utviklingen av en leksikalsk analysator består delvis i å modellere ulike automater for gjenkjennelse av identifikatorer, konstanter, reserverte ord osv. Hvis ulike typer tokens starter med samme symbol eller samme tegnsekvens, kan det være nødvendig å kombinere gjenkjenningen.

Ved å starte den leksikale analysatoren deler vi programmet vårt i tokens, hvoretter hvert token sjekkes for lengde (et token kan ikke være mer enn 11 tegn). Etter å ha bestått dette stadiet, kontrollerer vi riktigheten av plasseringen av tokens (søkeord var, begynne, slutt, for, å, gjøre, slutt_for). Deretter analyserer vi leksemene til variablene - de skal ikke inneholde tall i beskrivelsen og gjentas. På det siste stadiet kontrollerer vi stavemåten til tokens (søkeord, ukjente identifikatorer). Hvis minst én av sjekkene gir en feil, viser den leksikalske analysatoren en feil.

Et skjematisk diagram av det leksikalske analysatorprogrammet er vist i vedlegg B i figur B.1.

2.2.2 Designe en magasindispenser

La oss sette følgende grammatikk:

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

der Vt er settet med terminalsymboler, Va er settet med ikke-terminale symboler, I er begynnelsestilstanden til grammatikken, R er settet med grammatikkregler.

For en gitt grammatikk definerer vi sett med terminale og ikke-terminale symboler:

La oss komponere reglene for grammatikken vår Г og liste dem opp i tabell 1.

Tabell 1 - Grammatikkregler

Regel nr.	Venstre side av regelen	Høyre side av regelen
		f ID = EX t EX d LE n;
Fortsettelse av tabell 1.
Regel nr.	Venstre side av regelen	Høyre side av regelen

Betegnelsene på tokens, oversettelsen av tokens til koder og listen over grammatikkbetegnelser er gitt i henholdsvis Tabell 2, 3, 4.

Tabell 2 - Symboler for tokens

	Leksembetegnelse
	nøkkelordet "begynn" (begynnelsen av beskrivelsen av handlinger)
	søkeordet "slutt" (slutten på beskrivelsen av handlinger)
	søkeord "var" (variabelbeskrivelse)
	nøkkelordet "les" (dataregistreringsoperatør)
	nøkkelordet "skriv" (datautdataoperatør)
	nøkkelord "for" (løkkeoperator)
	nøkkelord "til"
	søkeord "gjør"
	søkeord "end_case" (end of loop-setning)
	variabeltype "heltall"
	operasjon tillegg
	subtraksjonsoperasjon
	multiplikasjonsoperasjon
	skilletegn ":"
	skilletegn ";"
	skilletegn "("
	skilletegn ")"
	skilletegn ","
	Leksembetegnelse
	skilletegn "="

Tabell 3 - Oversettelse av leksemer til koder

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

Tabell 4 - Liste over grammatikkbetegnelser

Betegnelse	Forklaring
	Program
	Beskrivelse av beregninger
	Beskrivelse av variabler
	Variabel liste
	Operatør
	Oppdrag
	Uttrykk
	Underuttrykk
	Binære operasjoner
	Unære operasjoner
	Oppgaveliste
	Identifikator
	Konstant

La oss bygge en deterministisk oppstrøms resolver.

Vurder følgende relasjoner for å bygge en deterministisk oppstrømsløser:

a) Hvis det er et symbol for gruppe B slik at en grammatikkregel inkluderer kjeden AB og det er et symbol xPERB "(B), så vil vi anta at relasjonene x ETTER A er bestemt mellom symbolene x og A

b) Hvis det i en gitt grammatikk er en regel B-> bAb A, BV a, b, så mellom A og x, bestemmes forholdet A SVERT x.

All grammatikken vår forblir den samme, det vil si:

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

og reglene for grammatikk D er gitt i tabell 5.

Tabell 5 - Grammatikkregler

Regel nr.	Venstre side av regelen	Høyre side av regelen
		f ID = EX t EX d LE n ;?
Fortsettelse av tabell 5.
Regel nr.	Venstre side av regelen	Høyre side av regelen

Hvor? - markør for enden av kjeden.

La oss definere noen tilfeller:

a) Identifikator-ID-en består av et sett med bokstaver i det latinske alfabetet, det vil si at vi antar at 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) CO-konstanten består av tall, det vil si at vi vil anta at k = (0,1,2,3,4,5,6,7,8,9)

For at grammatikken vår skal være en blandet prioriteringsstrategi, må følgende betingelser være oppfylt:

a) Mangel på e-regler

b) Det er regler under hvilke, x ETTER A? A SVERT x =?

c) A -> byYg

og det er nødvendig at IN ETTER x? VERTED x =?

det vil si at i grammatikken vil de bli utført IN ETTER x eller A ETTER x, der x er predikatsymbolet til strengen b.

a) FØRST "(PG) = (PG?)

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

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

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

FIRST "(LV) = FIRST (ID, LV) = (LV, ID)

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

FØRST "(EQ) = FØRST (ID = EX;) = (EQ, = ,;)

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

FØRSTE "(BO) = (B0, +, *, -)

FØRSTE "(SB) = FØRSTE ((EX) SB)? FØRSTE (OP)? FØRSTE (IN) = (SB, (,), OP, BO);

FØRST "(LE) = FØRST (EQ) = (LE, (,), =,;, f, t, d, n, w, r)

FØRST "(UO) = (UO, -)

FIRST "(ID) = FIRST" (u) = (u)

FØRST "(CO) = FØRST" (k) = (k) FØRST "(e) = (e)

FØRSTE "(b) = (b)

FØRSTE "(e) = (e)

FØRSTE "(v) = (v)

FØRSTE "(w) = (w)

FØRSTE "(r) = (r)

FØRSTE "(i) = (i)

FØRSTE "(f) = (f)

FØRSTE "(d) = (d)

FØRSTE "(n) = (n)

FØRSTE "(c) = (c)

FØRSTE "(+) = (+)

FØRSTE "(*) = (*)

FØRSTE "(-) = (-)

FØRSTE "(,) = (,)

FØRSTE "(;) = (;)

FØRSTE "(:) = (:)

FØRSTE "(=) = (=)

FØRSTE "(() = (()

FØRSTE "()) = ())

FØRSTE "(u) = (u)

FØRSTE "(k) = (k)

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

NESTE `(DE) = (?)? FØRST" (AL) = (?, B, e)

NESTE `(LV) = (?)? FØRST" (:) = (?, :)

NESTE `(OP) = (?)? FØRST" (SB) = (?,;,), D, t, +, -, *)

NESTE `(EQ) = (?)? FØRST" (LE) = (?, (,),;, f, =, t, d, n, w, r)

NESTE `(EX) = (?)? FØRST" (t)? FØRST "(d)? FØRST" (;)? FØRST "()) = (?, t, d,;,))

NESTE `(BO) = (?)? FØRST" (SB) = (?, (,), OP, BO)

NESTE `(UO) = (?)? FØRST" (SB) = (?, (,), OP, BO)

NESTE `(SB) = (?)? NESTE" (EX) = (?, T, d,;,), +, *, -)

NESTE `(LE) = (?)? FØRST" (e)? FØRST "(n) = (?, E, n)

NESTE `(ID) = (?)? NESTE "(OP)? FØRST" (=) = (?,;,), D, t, +, -, *, =)

NESTE `(CO) = (?)? NESTE "(OP) = (?,;,), D, t, +, -, *, =)

NESTE `(b) = (?)? FØRST" (LE) = (?, U, = ,;)

NESTE `(e) = (?)? NESTE" (AL) = (?, B)

NESTE `(v) = (?)? FØRST" (LV) = (?, U)

NESTE `(w) = (?)? FØRST" (() = (?, ()

NESTE `(r) = (?)? FØRST" (() = (?, ()

NESTE `(i) = (?)? FØRST" (;) = (?,;)

NESTE `(f) = (?)? FØRST" (ID) = (?, U)

NESTE `(d) = (?)? FØRST" (LE) = (?, U, = ,;)

NESTE `(n) = (?)? FØRST" (i) = (?, I)

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

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

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

NESTE `(;) = (?)? NESTE" (DE)? NESTE `(LE1)? NESTE" (EQ) = (?, B, e, l, u)

NESTE `(:) = (?)? FØRST" (i) = (?, I)

NESTE `(=) = (?)? FØRST" (EX) = (? (,), U, k, +, -, *)

NESTE `(() = (?)? FØRST" (DE) = (?, V,:, i ,;)

NESTE `()) = (?)? FØRSTE "(;) = (?,;)

NESTE `(,) = (?)? FØRSTE "(LV) = (?, U)

NESTE `(u) = (?)? FØRST "(ID) = (u,?)

NESTE `(k) = (?)? FØRST (CO) = (?, K)

c) PG -> DE AL

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

e ETTER LE = ((e LE))

LE ETTER b = ((,), =,;, f, t, d, n, w, r) ETTER b = (((b), () b), (= b), (; b), ( fb), (tb), (db), (nb), (wb), (rb))

; ETTER i = ((; i))

i ETTER: = ((i :))

: ETTER LV = ((: LV))

LV ETTER v = ((ID, v))

LV ETTER, = ((ID,))

ETTER ID = ((, u))

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

LE -> r (DE);

; ETTER) = ((;)))

) ETTER DE = (((DE))

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

(ETTER r = (((r))

LE -> w (DE);

; ETTER) = ((;)))

) SEX DE = (((DE))

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

(ETTER w = (((w))

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

; ETTER n = ((; n))

n ETTER LE = ((n, LE))

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

d ETTER EX = ((d, EX))

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

t ETTER EX = (t EX)

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

ETTER ID = ((= ID))

ID ETTER f = ((ID f))

EQ -> ID = EX;

; ETTER EX = ((; EX)

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

ETTER u = ((= u))

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

) ETTER EX = (() EX))

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

SB-> SB BO SB

SB ETTER BO = ((,), OP, BO) ETTER BO = (((BO), () BO), (OP BO), (BO BO))

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

ID ETTER u = ((u, u))

G) PG -> DE AL

AL SWITCH PG = AL SWITCH FOLLOW "(PG) = ((AL?))

e KONVERTER AL = e KONVERTER NESTE "(AL) = ((eb), (e?))

=; KONVERTER NESTE "(DE) = ((; b), (;?))

LV SVELGE LV = LV SVELGE FØLG "(LV) = ((LV :), (LV?))

ID SWITCH LV = ID SWITCH FOLLOW "(LV) = ((ID :), (ID?))

; KONVERTERING LE =; KONVERTER NESTE "(LE) = ((; e), (;?), (; N))

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

; KONVERTERING LE =; KONVERTER NESTE "(LE) = ((; e), (;?), (; N))

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

EQ -> ID = EX;

; VERSJON EQ =; KONVERTER NESTE "(EQ) = ((; (), (;)), (;;), (; f), (;?), (; =), (; T), (; d), (; n), (; w), (; r))

SB SVELGE EX = SB SVELGE SPOR "(EX) = ((SB t), (SB?), (SB d), (SB)), (SB;), (SB (), (SB =), (SBf) ), (SBn), (SBw), (SBr))

) KONVERTER SB = SB KONVERTER NESTE "(SB) = (() t), ()?), () D), ())), ();))

OP CONVERT SB = OP CONVERT NEXT "(SB) = ((OP t), (OP?), (OP d), (OP)), (OP;))

SB-> SB BO SB

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

KONVERTER UO = - KONVERTER NESTE "(UO) = ((-?), (-))

KONVERTER BO = + KONVERTER NESTE "(BO) = ((++), (+?), (+ *), (+ -))

* KONVERTER BO = * KONVERTER NESTE "(BO) = ((* +), (*?), (**), (* -))

KONVERTER BO = - KONVERTER NESTE "(BO) = ((- +), (-?), (- *), (-))

ID KONTRAKT OP = ID KONTRAKT FØLG "(OP) = ((ID +), (ID?), (ID *), (ID-))

COLLECT OP = COLLECT FOLLOW "(OP) = ((CO +), (CO?), (CO *), (CO-), (CO;), (COd), (COt), (CO)) )

ID KONVERTER ID = ID KONVERTER NESTE "(ID) = ((ID)), (ID?), (ID k), (ID +), (ID-), (ID *), (ID =), (IDt ) , (IDd)))

u KONVERTER ID = l KONVERTER NESTE "(ID) = ((u)), (u?), (uk), (u +), (u-), (u *), (u =), (ut) , (ud)))

COLLECT CO = COLLECT FOLLOW "(CO) = (CO +), (CO?), (CO *), (CO-), (CO;), (COd), (COt), (CO)))

k KONVERTER CO = k KONVERTER SPOR "(CO) = (k +), (k?), (k *), (k-), (k;), (kd), (kt), (k)))

En kollisjon oppdaget ved rullende regler

OP -> ID og ID -> u ID

Vi skriver inn ID1 -> ID, derfor omskriver vi regelen ID1 -> u ID

Derfor vil vi utføre konvolusjonsoperasjonene.

ID1 KONVERTER ID = ID1 KONVERTER NESTE "(ID) = ((ID1)), (ID1?), (ID1 k), (ID1 +), (ID1-), (ID1 *), (ID1 =), (ID1t ) , (ID1d)))

For hvert par (x, A)? x ETTER A konstruerer vi en overgangsfunksjon som bestemmer overføringshandlingen ?? (S 0, x, A) = (S 0, A)

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

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

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

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

? (SO,;, b) = (SO, 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, w, b) = (S0, bw)

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

? (S0,;, i) = (SO, i;)

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

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

? (SO,;, n) = (SO, n;)

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

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

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

? (SO,;, d) = (SO, d;)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

For hvert par (x, A)? En CONVERT X bygger en overgangsfunksjon som bestemmer handlingen til konvolusjonen ?? * (S 0, x, bA) = (S 0, B), hvor 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, I OP)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

? * (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 Programvareimplementering av parseren

Parseren (parseren) leser filen med tokens generert av den leksikale analysatoren, utfører grammatisk analyse, sender ut meldinger om syntaksfeil, hvis noen, og lager en mellomform av kildeprogramposten. Utviklingen av en parser er basert på design og implementering av en tilsvarende maskin som er kjøpt i butikken.

For den stigende parsingen for den deterministiske stigende gjenkjenneren, etter å ha brakt den til ønsket form, er det nødvendig å designe en FSM ved å bruke AFTER- og CONVERT-funksjonene med en detaljert beskrivelse av alle overganger i overgangsfunksjonen.

Når vi utviklet FSM, bygde vi overgangsfunksjonene som skal danne grunnlaget for parseren. Alle overgangsfunksjoner kan deles inn i to typer:

Haken på magasinmaskinen uten å lese inndatategnet (tom hake);

Haken på butikkmaskinen med lesing av inngangssymbolet.

Når vi implementerte den leksikalske analysatoren, delte vi opp programmet i tokens og skrev dem ned i en liste. Vi behandler deretter denne listen i en parser. Ved inngangen sender vi vårt program (liste), startsymbolet (PG) og markøren til bunnen av magasinmaskinen (h0), hvoretter ønsket overgangsfunksjon velges og et rekursivt anrop foretas.

Et skjematisk diagram av parserprogrammet er vist i vedlegg B i figur B.2.

2.2.4 Utvikling av tolkemodulen

Ved utvikling av en tolkningsmodul som en mellomform av det originale programmet den mest brukte er postfix-formen for notasjon, som gjør det enkelt å implementere prosessen med utførelse (tolking) av det oversatte programmet.

La oss vurdere de grunnleggende prinsippene for dannelse og utførelse av postfix-formen for skriveuttrykk.

De grunnleggende reglene for å konvertere et infix-uttrykk til et postfix-uttrykk er som følger.

Leseoperanden legges til postfix-posten, operasjonene skrives på stabelen.

Hvis en operasjon på toppen av stabelen har høyere (eller lik) prioritet enn den for øyeblikket leste operasjonen, blir operasjonen fra stabelen lagt til postfix-posten, og den gjeldende operasjonen skyves inn i stabelen. Ellers (ved laveste prioritet) blir bare den gjeldende operasjonen skjøvet inn på stabelen.

Den lese åpne parentesen skyves på stabelen.

Etter å ha lest den avsluttende parentesen, blir alle operasjoner frem til den første åpningsparentesen poppet fra stabelen og lagt til postfix-posten, hvoretter både åpnings- og lukkeparentesen forkastes, dvs. er ikke satt på postfix-posten eller på stabelen.

Etter å ha lest hele uttrykket, blir de resterende operasjonene på stabelen lagt til postfix-posten.

Postfix-notasjonen til uttrykket lar deg evaluere det som følger.

Hvis tokenet er en operand, skyves det på stabelen. Hvis tokenet er en operasjon, utføres den spesifiserte operasjonen på de siste elementene (siste element) som er skjøvet inn på stabelen, og disse elementene (elementet) erstattes på stabelen av resultatet av operasjonen.

Hvis de leksikale og syntaktiske analysene har bestått, går vi videre til tolkningen. Først lager vi setninger av ord, deretter oversetter vi uttrykkene til en postfix-notasjon og regner.

Oppsettet for tolkeoperasjonen er vist i vedlegg B i figur B.3.

2.3 Koding

Programmet er implementert i C # i programmeringsmiljøet Visual Studio 2010. Teksten til programmet er presentert i vedlegg A.

Det er fem klasser implementert i programmet. Brukergrensesnittet er implementert ved hjelp av MainForn-klassen. Ved å bruke LexAnalysis-klassen implementeres en leksikalsk analysemodul, SynAnalysis er en parsemodul, Interpreter er en tolkningsmodul, ProgramisciJakPolska er en hjelpeklasse for å oversette uttrykk til omvendt polsk notasjon (postfix).

Hensikten med prosedyrene og funksjonene implementert i programmet er beskrevet i tabellene 6,7,8.

Tabell 6 - Formål med prosedyrer og funksjoner for leksikalsk analyse

Lignende dokumenter

En oversetter er et program eller et teknisk middel som oversetter et program. Betraktning av hovedtrekkene i konstruksjonen av den leksikalske analysatoren. Bekjentskap med stadiene i oversetterutvikling fra en begrenset delmengde av et språk på høyt nivå.

semesteroppgave, lagt til 08.06.2013


Utforming av leksikale og syntaktiske analyser av det pedagogiske språket. Regler for konvertering av logiske uttrykk til POLIZ. Dannelse av triader, optimalisering av listen deres. Den logiske strukturen til programmet. Testing av oversetter-tolk-moduler.

semesteroppgave lagt til 28.05.2013


Generelle egenskaper og vurdering av funksjonene til programmeringsspråket C-Sharp, dets likheter og forskjeller fra C ++ og Java. Utvikling av en leksikalsk og syntaktisk analysator ved å bruke dette programmeringsspråket. Tegne opp parsetabeller.

semesteroppgave, lagt til 06.11.2010


Utforme et analysatorprogram som består av to deler: en leksikalsk analysator som deler opp kildekoden til et program i tokens og fyller ut en navnetabell; en parser som sjekker om teksten samsvarer med den gitte grammatikken.

semesteroppgave, lagt til 14.06.2010


Å skrive et program som utfører leksikalsk og analysering av et inndataprogrammeringsspråk, genererer en tabell med tokens med en indikasjon på deres typer og verdier, og bygger også et syntakstre; teksten til inndataspråket skrives inn fra tastaturet.

semesteroppgave lagt til 23.02.2012


Utviklingsmetodikk og delvis implementering av en oversetter for "C"-språket ved bruk av "C ++"-språket, som deler opp den originale tegnstrengen i minimale udelelige språkkonstruksjoner basert på språkvokabularet. Analyse av programmet.

semesteroppgave, lagt til 19.03.2012


Kompilatorstruktur, klassifisering og implementeringskrav. Design og implementering av den analyserende delen av C++ kompilatoren. Måter å implementere leksikalsk analyse. Algoritme for parseren. Prinsipper for programvareimplementering.

semesteroppgave lagt til 26.01.2013


Opprettelse av en oversetter som behandler programkoden i Pascal og, på bekostning av tilsvarende operatører, genererer et C-program. Funksjoner ved den eksterne spesifikasjonen og leksikalsk analysatordrift. Strukturen til programmet, resultatet av resultatene på skjermen.

semesteroppgave, lagt til 07.02.2011


Parsingmetoder. Utvikling av strukturen til den pedagogiske oversetteren i det grunnleggende programmeringsspråket Object Pascal i den objektorienterte visuelle programmeringen Borland DELPHI 6.0 ved bruk av operativsystemet Windows XP.

semesteroppgave, lagt til 05.12.2013


Programvareimplementering av en skrivebordsapplikasjon ved bruk av programmeringsspråket C #. Design og struktur av brukergrensesnittet, krav til det og vurdering av funksjonalitet. Utvikling av brukermanualen og bruken av den.