Tõlkijate ja koostajate mõiste ja liigid. Rekursiivse laskumise põhiidee seisneb selles, et grammatika igal mitteterminalil on vastav protseduur, mis tunneb ära mis tahes selle mitteterminali genereeritud ahela. Need protseduurid kutsuvad üksteist millal

Ühest keelest teise tõlkimiseks vajavad programmid, nagu ka inimesed, tõlkijat või teaduslikult öeldes tõlkijat.

Tõlkija: põhimõisted

Selline programm tõlkijana on arvutuste I ->P ->P (i) keeleline esitus. Tõlk on programm, mille sisendiks on programm P, millel on mingid sisendandmed X. See käivitab X-l P: I(P, x) = P(x) On ainult üks tõlkija, mis on võimeline kõike tegema. võimalikud programmid(mida saab esitada formaalses süsteemis). See on Turingi väga oluline ja sügav avastus. Protsessor on programmide tõlk masinakeel. Kõrgetasemeliste keelte tõlkide kirjutamine on tavaliselt liiga kallis, mistõttu need tõlgitakse lihtsamini tõlgendatavasse vormi. Teatud tüüpi tõlkidel on väga kummalised nimed. Programm tõlgib montaažikeele programmid masinkeelde. Kompilaator võimaldab tõlkida kõrgetasemelisest keelest madalama taseme keelde. Tõlkija on programm, mis võtab sisendiks mõnes keeles S programmi ja pärast töötlemist toodab programmi keeles T. Seega on neil mõlemal sama semantika: P->X->Q. Seega iga xP(x)=Q(x) korral. Terve programmi tõlkimist millekski tõlgendatavaks nimetatakse eelkäivituskompileerimiseks või AOT-kompileerimiseks. AOT-kompilaatoreid saab kasutada järjestikku. Viimane on väga sageli komplekteerija. Niisiis, vaatame näidet: Lähtekood -> Kompilaator (tõlkija) -> Koostekood -> Assembler (tõlkija) -> Masinakood -> CPU (tõlk). Dünaamiline või siduskompileerimine toimub siis, kui osa programmist tõlgitakse, samal ajal kui täidetakse teisi varem kompileeritud osi. JIT-i tõlkijad jätavad meelde, mida nad on juba varem teinud, et mitte seda ikka ja jälle korrata allikas. Nad on isegi võimelised adaptiivseks kompileerimiseks ja uuesti kompileerimiseks, mis põhineb programmi käituskeskkonna käitumisel. Paljud keeled võimaldavad nii edastamise kui ka kompileerimise ajal koodi käivitada uus kood programmi täitmise ajal.

Saade: etapid

Tõlkeprotsess koosneb sünteesi- ja analüüsietappidest. Skemaatiliselt näeb see protsess välja umbes selline: Lähtekood -> Analüsaator -> Kontseptuaalne esitus -> Süntesaator (generaator) -> Sihtkood. See on tingitud järgmistel põhjustel:

- mõni muu meetod lihtsalt ei sobi;

— sõnadega tõlkimine lihtsalt ei tööta.

Võite kasutada järgmist insenerilahendust: kui teil on vaja kirjutada tõlkijaid M lähtekeele ja N sihtkeele jaoks, peate kirjutama ainult M+N lihtsaid programme (poolkompilaatoreid), mitte aga MxN täis (keerulisi) tõlkijaid. . Praktikas on aga üsna haruldane, et kontseptuaalne esitus on piisavalt väljendusrikas ja võimas, et katta kõiki olemasolevaid siht- ja lähtekeeli. Kuigi mõned kasutajad suutsid sellele lähedale jõuda. Päris koostajad läbivad palju erinevaid etappe. Kui loote oma kompilaatori, ei pea te uuesti tegema kogu seda rasket tööd, mida programmeerijad on generaatorite ja vaadete loomisel juba teinud. Saate tõlkida oma keele otse JavaScripti või C-sse ning kasutada ülejäänu tegemiseks olemasolevaid C-keelekompilaatoreid ja JavaScripti mootoreid. Samuti saate kasutada olemasolevaid vahevaateid ja virtuaalmasinaid.

Tõlkija salvestus

Tõlkija võib olla tehnilisi vahendeid või programm, mis kasutab kolme keelt: allikas, sihtmärk, baas. Neid saab kirjutada T-tähe kujul, asetades allika vasakule, sihtmärgi paremale ja aluse alla. Kokku on kolme tüüpi kompilaatoreid.

Tõlkija on isekompilaator, kui tema lähtekeel ühtib põhikeelega.
Kompilaatorit, mille sihtkeel on võrdne selle baaskeelega, nimetatakse iseresidendiks.
Kui siht- ja põhikeel on erinevad, on tõlkija ristkompilaator.

Miks on oluline seda tüüpi kompilaatoritel vahet teha? Isegi kui te ei loo kunagi tõeliselt head kompilaatorit, on hea mõte õppida tundma selle taga olevat tehnoloogiat, sest kõiki selleks kasutatavaid mõisteid kasutatakse kõikjal andmebaasi päringukeeltes, tekstivormingus, täiustatud arvutiarhitektuurides, graafilistes liidestes ja üldistatud ülesannetes. optimeerimine, masintõlked, kontrollerid ja virtuaalmasinad. Samuti, kui teil on vaja kirjutada eelprotsessoreid, laadijaid, monteerijaid, silujaid või profileerijaid, peate läbima kõik samad sammud, mis kompilaatori kirjutamisel. Samuti saate õppida paremaid viise programmide kirjutamiseks, kuna programmeerimiskeele tõlkija arendamine tähendab kõigi selle ebaselguste ja peensuste paremat mõistmist. Õppides selgeks tõlkimise üldpõhimõtted, võib saada heaks keelekujundajaks. Aga kas see on tõesti oluline? Kui lahe on keel, kui seda ei saa tõhusalt rakendada?

Suuremahuline tehnoloogia

Kompilaatoritehnoloogia hõlmab väga erinevaid arvutiteaduse valdkondi. See hõlmab formaalset keeleteooriat, grammatikat, arvutiarhitektuuri, sõelumist, arvutatavust, käsukomplekte, CISC-d või RISC-i, konveierit, kellatsükleid, tuumasid jne, aga ka järjestuse juhtimist, rekursiooni, tingimuslik täitmine, funktsionaalne dekomponeerimine, iteratsioonid, modulaarsus, sünkroonimine, metaprogrammeerimine, konstandid, ulatus, mallid, väljundi tüüp, annotatsioonid, prototüübid, vood, postkastid, monaadid, metamärgid, jätkud, tehingumälu, regulaaravaldised, polümorfism, pärilikkus, parameetrirežiimid ja nii edasi . Samuti peate kompilaatori loomiseks mõistma abstraktseid programmeerimiskeeli, algoritme ja andmestruktuure, regulaaravaldised, graafilised algoritmid, dünaamiline programmeerimine.

Kompilaatori disain. Võimalikud probleemid, mis tekivad tõelise tõlkija loomisel

Millised probleemid võivad tekkida algkeel? Kas seda on lihtne koostada? Kas selle jaoks on eelprotsessor? Kuidas tüüpe töödeldakse? Millist kompilaatoripääsmete rühmitust kasutatakse - ühe- või mitmekäigulisi? Erilist tähelepanu väärib ka soovitud optimeerimisaste. Programmi kiire ja räpane edastus vähese optimeerimisega või ilma optimeerimiseta võib olla normaalne. Liigne optimeerimine võib aga kompilaatorit käitusajal aeglustada parim kood võib olla seda väärt.

Vigade tuvastamise määr. Kas tõlkija peab esimese vea juures peatuma? Millal ta peaks lõpetama? Kas peaksite usaldama vigade parandamise kompilaatorile?

Vajalik tööriistade komplekt

Kui teie puhul pole lähtekeel liiga väike, siis analüsaatori generaatori ja skanneri olemasolu on kohustuslik. On olemas ka spetsiaalsed koodigeneraatorid, kuid need pole eriti levinud.

Genereeritava sihtkoodi tüübi osas peate valima puhta, täiendatud või virtuaalse masinkoodi vahel. Samuti saate kirjutada sisendosa, mis loob populaarseid vahevaateid, nagu LLVM, JVM, RTL. Samuti saate tõlke lähtekoodist lähtekoodi teha Java Scriptis või C-s. Kui me räägime sihtkoodi vormingust, siis siin saate valida portable masina kood, mälupildi masinkood, montaažikeel.

Resihtimine

Kasutades suur kogus Oleks tore, kui generaatoritel oleks ühine sisendosa. Ka sel põhjusel on paljude sisendosade jaoks parem kasutada ühte generaatorit.

Kompilaatori komponendid

Loetleme tõlkija peamised funktsionaalsed komponendid, mis genereerib masinkoodi, kui väljundprogrammiks on C-keeles kirjutatud programm või virtuaalmasin:

— sisendprogramm siseneb leksikaalanalüsaatorisse ehk teisisõnu skannerisse, mis muudab selle žetoonide vooks;

— süntaksianalüsaator (parser) koostab neist abstraktse süntaksipuu;

— semantiline analüsaator dekomponeerib semantilise teabe ja kontrollib puu sõlmedes vigu;

— selle tulemusena konstrueeritakse semantiline graaf. See termin viitab abstraktsele süntaksipuule koos loodud linkide ja lisaomadustega;

— vahekoodigeneraator koostab voograafiku (korteežid rühmitatakse põhiplokkideks);

— masinast sõltumatu optimeerija teostab kohalikku ja globaalset optimeerimist, kuid jääb põhiliselt alamprogrammide raamidesse, lihtsustades samas arvutusi ja vähendades üleliigset koodi. Tulemuseks peaks olema muudetud voograafik;

— põhiplokkide ühendamiseks sirgjooneliseks koodiks koos juhtimise üleandmisega kasutatakse sihtkoodi generaatorit. See loob visuaalsete registritega objektifaili assembleris, mis ei pruugi olla kuigi tõhus;

— mälu jaotamiseks virtuaalsete registrite vahel ja käskude ajastamiseks kasutatakse masinast sõltuvat optimeerija-linkerit. Samuti teisendab see konveieri abil montaažikeeles kirjutatud programmi tõeliseks assembleriks.

— kasutatakse veatuvastuse alamsüsteeme ja sümbolitabelihaldurit;

— skaneerimine ja leksikaalne analüüs. Skannerit kasutatakse lähtekoodi märkide voo teisendamiseks žetoonide vooks, eemaldades kommentaarid, tühikud ja laiendades makrosid. Üsna sageli puutuvad skannerid kokku järgmise probleemiga: kas võtta arvesse taandusi, suurtähti või pesastatud kommentaare.

Neid vigu, mis võivad skaneerimisel tekkida, nimetatakse leksikaalseteks. Nende hulka kuuluvad järgmised:

— tähestikust puuduvad sümbolid;

— märkide arvu ületamine reas või sõnas;

- mittesuletud stringi literaal või märk;

- faili lõpp kommentaaris.

Parsimist või sõelumist kasutatakse märkide jada teisendamiseks abstraktseks süntaksipuuks. Sel juhul salvestatakse iga puusõlm nimeliste väljadega objektina. Paljud neist on ise puusõlmed. Selles etapis pole tsükleid. Parseri loomisel tuleb esmalt pöörata tähelepanu grammatika keerukuse tasemele (LR või LL) ja uurida, kas seal on mingeid täpsustusreegleid. Tõepoolest, mõned keeled nõuavad semantilist analüüsi. Selles etapis esinevaid vigu nimetatakse süntaktilisteks vigadeks.

Semantiline analüüs

Semantilise analüüsi tegemisel on vaja ennekõike kontrollida kehtivusreegleid ja siduda omavahel süntaksipuu osad semantilise graafi moodustamiseks, sisestades toimingu implitsiitse tüübi valamise, nimeviite lahutamise jms jaoks. On selge, et erinevatel programmeerimiskeeltel on erinevad kehtivusreeglite komplektid. Java-sarnaste keelte koostamisel võivad tõlkijad ilmneda järgmised vead:

— selle ulatuse piires oleva muutuja mitu deklaratsiooni;

— juurdepääsetavuse reeglite rikkumine;

— viidete olemasolu deklareerimata nimele;

— liiga suur või vastupidi, ebapiisav argumentide arv meetodi kutsumisel;

- tüübi mittevastavus.

Põlvkond

Vahekoodi genereerimisega koostatakse voograafik, mis koosneb põhiplokkideks rühmitatud korteežidest. Pärast koodi genereerimist saadakse tegelik masinkood. RISC-masinate traditsiooniliste kompilaatorite esimene samm on luua lõputu arvu virtuaalregistritega komplekteerija. CISC-masinate puhul seda tõenäoliselt ei juhtu.

Distsipliini eesmärgid ja eesmärgid. Põhimõisted ja määratlused. Üldised omadused programmeerimiskeeled ja tõlkijad. Tõlkija üldistatud struktuur. Tõlkijaplokkide interaktsiooni võimalused.

Distsipliini eesmärgid ja eesmärgid

Praegu tehiskeeled, mis kasutavad ainevaldkonna kirjeldamiseks tekstilist esitust, on laialdaselt kasutusel mitte ainult programmeerimises, vaid ka muudes valdkondades. Nende abiga igasuguste dokumentide struktuur, kolmemõõtmeline virtuaalsed maailmad, graafilised kasutajaliidesed ja paljud teised mudelites ja reaalses maailmas kasutatavad objektid. Nende tekstikirjelduste õigeks koostamiseks ning seejärel õigesti äratundmiseks ja tõlgendamiseks kasutatakse nende analüüsimiseks ja teisendamiseks spetsiaalseid meetodeid. Meetodid põhinevad keelte ja formaalsete grammatikateoorial, aga ka automaatide teoorial. Tarkvarasüsteemid, mis on mõeldud tekstide analüüsimiseks ja tõlgendamiseks, nimetatakse tõlkijateks.

Hoolimata asjaolust, et tänaseks on välja töötatud tuhandeid erinevaid keeli ja nende tõlkijaid, ei peatu selles valdkonnas uute rakenduste loomise protsess. See on tingitud nii arvutisüsteemide tootmistehnoloogia arengust kui ka vajadusest lahendada järjest keerukamaid rakendusprobleeme. Lisaks on keelte ja formaalsete grammatikateooria elemendid rakendatavad ka muudes erinevates valdkondades, näiteks andmestruktuuride, failide, piltide kirjeldamisel, mis on esitatud mitte tekstis, vaid kahendvormingus. Need meetodid on kasulikud ka oma tõlkijate väljatöötamisel, isegi kui vastavad analoogid on juba olemas. Sellise arengu põhjuseks võivad olla erinevad põhjused, eelkõige funktsionaalsed piirangud, lokaliseerimise puudumine ja madal efektiivsus. Näiteks Microsofti üks viimaseid arendusi on C# programmeerimiskeel, mille loomise üheks põhjuseks on soov Java programmeerimiskeele populaarsust vähendada. On palju muid näiteid, kus oma tõlkija väljatöötamine võib olla asjakohane. Seetõttu on keeleteooria põhitõed ja formaalsed grammatikad, samuti praktilisi meetodeid Tõlkijate areng on arvutiteaduse ja arvutiteaduse insenerihariduse aluseks.

Kavandatav materjal puudutab tõlkijate arendamise meetodite põhitõdesid ja sisaldab teavet, mis on vajalik nende toimimise loogika ja kasutatava matemaatilise aparatuuri uurimiseks (formaalsete keelte ja formaalsete grammatikate teooria, metakeeled). Seda kasutatakse Krasnojarski Riikliku Tehnikaülikooli informaatika ja arvutiteaduse teaduskonnas erinevatele erialadele peetavate semestriliste loengukursuste osana. ajal laboritööd Otsene tutvumine tõlkijate loomise individuaalsete meetoditega.

Distsipliini eesmärk: anda teadmisi keelte teooria ja formaalse grammatika alustest, automaatide teooriast, tõlkijate arendamise meetoditest.

Selle eesmärgi saavutamiseks lahendatakse distsipliini õpetamisel järgmised ülesanded:

Loengukursusel vaadeldakse tõlkeprotsessi korraldamise üldpõhimõtteid ja tõlkijate struktuuri. Õpitakse tõlkijate konstrueerimise teooria aluseid.
Peal laboriklassid ja ajal iseseisev töö teostatakse omandatud teoreetiliste teadmiste praktiline kinnistamine: töötatakse välja lihtsa programmeerimiskeele tõlkija.

Põhimõisted ja määratlused

Enamik käsitletud määratlusi on laenatud [ARNFTS-ist Inglise-vene-saksa-prantsuse seletav sõnaraamat arvutitehnoloogiast ja andmetöötlusest, 4132 terminit. Under. toim. A.A. Dorodnitsõna. M.: 1978. 416 lk.) ].

Tõlkija - teenindusprogramm, mis muudab sisendprogrammeerimiskeeles pakutava lähteprogrammi objektkeeles pakutavaks tööprogrammiks.

Ülaltoodud määratlus kehtib igat tüüpi ringhäälinguprogrammide kohta. Igal neist programmidest võib aga leviprotsessi korraldamisel olla oma eripära. Praegu jagunevad tõlkijad kolme põhirühma: komplekteerijad, koostajad ja tõlgid.

Kokkupanija - süsteemi utiliit, mis teisendab sümboolsed konstruktsioonid masinkeelseteks käskudeks. Assemblerite eripäraks on see, et nad tõlgivad ühe sümboolse käsu sõna-sõnalt üheks masinkäsuks. Seega on montaažikeel (nimetatakse ka autokoodiks) mõeldud arvutikäsusüsteemi tajumise hõlbustamiseks ja programmeerimise kiirendamiseks selles käsusüsteemis. Programmeerijal on palju lihtsam meeles pidada masinakäskude mnemoloogilist tähistust kui nende kahendkoodi. Seetõttu saavutatakse peamine kasu mitte üksikute käskude võimsuse suurendamise, vaid nende tajumise tõhususe suurendamise kaudu.

Samal ajal sisaldab montaažikeel lisaks masinakäskude analoogidele palju täiendavaid direktiive, mis hõlbustavad eelkõige arvutiressursside haldamist, korduvate fragmentide kirjutamist ja mitmemooduliliste programmide koostamist. Seetõttu on keele väljendusvõime palju rikkalikum kui lihtsalt sümboolne kodeerimiskeel, mis parandab oluliselt programmeerimise efektiivsust.

Kompilaator - on teenindusprogramm, mis tõlgib programmeerimise lähtekeeles kirjutatud programmi masinkeelde. Nii nagu assembler, teisendab ka kompilaator programmi ühest keelest teise (enamasti konkreetse arvuti keelde). Samas erinevad lähtekeelekäsud korralduselt ja võimsuselt oluliselt masinkeele käskudest. On keeli, milles üks lähtekeele käsk tõlgitakse 7-10 masinakäsuks. Siiski on ka keeli, milles igal käsul võib olla 100 või enam masinakäsku (näiteks Prolog). Lisaks kasutavad lähtekeeled üsna sageli ranget andmete sisestamist, mis viiakse läbi nende esialgse kirjelduse kaudu. Programmeerimine ei pruugi tugineda algoritmi kodeerimisele, vaid andmestruktuuride või klasside hoolikale mõtlemisele. Sellistest keeltest tõlkimise protsessi nimetatakse tavaliselt kompileerimiseks ja lähtekeeled liigitatakse tavaliselt kõrgetasemelisteks programmeerimiskeelteks (või kõrgetasemelisteks keelteks). Programmeerimiskeele abstraheerimine arvutikäsusüsteemist tõi kaasa paljude erinevate keelte iseseisva loomise, mis keskendus konkreetsete probleemide lahendamisele. Keeled on ilmunud teaduslike arvutuste, majandusarvutuste, andmebaasidele juurdepääsu ja muu jaoks.

Tõlk - programm või seade, mis teostab operaatorite kaupa tõlkimist ja täitmist originaalprogramm . Erinevalt kompilaatorist ei tooda tõlk väljundina masinkeelset programmi. Olles lähtekeeles käsu ära tundnud, täidab see selle kohe. Nii kompilaatorid kui ka interpretaatorid kasutavad programmi lähtekoodi analüüsimisel samu meetodeid. Kuid tõlk võimaldab teil alustada andmete töötlemist pärast kasvõi ühe käsu kirjutamist. See muudab programmide arendamise ja silumise protsessi paindlikumaks. Lisaks võimaldab väljundmasinkoodi puudumine väliseid seadmeid lisafailidega mitte “üles kuhjata” ja tõlgi ennast saab üsna hõlpsalt kohandada mis tahes masinaarhitektuuriga, olles seda vaid ühe korra laialdaselt kasutatavas programmeerimiskeeles välja töötanud. Seetõttu on laialt levinud tõlgendatavad keeled, nagu Java Script ja VB Script. Tõlkide miinuseks on programmide täitmise väike kiirus. Tavaliselt tõlgendatavad programmid käivituvad 50–100 korda aeglasemad programmid masinkoodiga kirjutatud.

Emulaator - programm või tarkvara ja riistvara tööriist, mis annab võimaluse ilma ümberprogrammeerimiseta käivitada antud arvutis programmi, mis kasutab antud arvutist erinevaid koode või toimingute sooritamise meetodeid. Emulaator sarnaneb tõlgiga selle poolest, et see käivitab otse teatud keeles kirjutatud programmi. Enamasti on see aga masinkeel või vahepealne kood. Mõlemad esindavad meeskondi binaarne kood, mida saab käivitada kohe pärast operatsioonikoodi tuvastamist. Erinevalt tekstiprogrammid, pole vaja programmi struktuuri ära tunda ega operande eraldada.

Emulaatoreid kasutatakse üsna sageli erinevatel eesmärkidel. Näiteks uute arvutussüsteemide väljatöötamisel luuakse esmalt emulaator, mis käivitab programmid, mis on välja töötatud arvutitele, mida veel ei eksisteeri. See võimaldab hinnata käsusüsteemi ja arendada baastarkvara juba enne vastava riistvara loomist.

Väga sageli kasutatakse emulaatorit vanade programmide käivitamiseks uutel. arvutid Oh. Tavaliselt on uuemad arvutid kiiremad ja paremate välisseadmetega. See võimaldab teil vanemaid programme tõhusamalt emuleerida kui vanemates arvutites. Selle lähenemisviisi näide on emulaatorite väljatöötamine koduarvuti ZX Spectrum Z80 mikroprotsessoriga. Endiselt on inimesi, kellele meeldib mängida vananenud, kuid siiski oma endist atraktiivsust mitte kaotavate mänguprogrammidega emulaatoril. Emulaatorit saab kasutada ka rohkema odav analoog kaasaegne arvutisüsteemid, pakkudes samas vastuvõetavat jõudlust, mis on samaväärne teatud arhitektuuriperekonna madalate mudelitega. Näiteks IBM PC emulaatorid ühilduvad arvutid, rakendatud rohkem kui võimsad arvutid Apple'i ettevõte. Mitmed IBM PC jaoks kirjutatud emulaatorid asendavad edukalt erinevaid mängukonsoole.

Vaheesitusemulaatorit ja ka interpretaatorit saab hõlpsasti ühest arvutiarhitektuurist teise üle kanda, võimaldades luua mobiilset tarkvara. Just see omadus määras Java programmeerimiskeele edu, millest programm tõlgitakse vahekoodiks. Selle koodi täitmine virtuaalne java masin pole midagi muud kui emulaator, mis töötab mis tahes kaasaegse operatsioonisüsteemiga.

Transkooder – programm või tarkvara seade, ühe arvuti masinkeeles kirjutatud programmide tõlkimine teise arvuti masinkeeles programmideks. Kui emulaator on tõlgi vähem intelligentne analoog, siis transkooder toimib kompilaatoriga võrreldes samas võimsuses. Samamoodi teisendatakse lähtekoodi (ja tavaliselt binaarne) masinkood või vahepealne esitus teiseks sarnaseks koodiks ühe käsuga ja ilma lähteprogrammi struktuuri üldise analüüsita. Transkooderid on kasulikud programmide ülekandmisel ühest arvutiarhitektuurist teise. Neid saab kasutada ka kõrgetasemelise keeleprogrammi teksti rekonstrueerimiseks olemasolevast kahendkoodist.

Makroprotsessor - programm, mis asendab ühe märgijada teisega[Pruun]. See on teatud tüüpi kompilaator. See genereerib väljundteksti, töödeldes lähtetekstis asuvaid spetsiaalseid sisestusi. Need lisad on kujundatud erilisel viisil ja kuuluvad makrokeeleks kutsutava keele konstruktsioonidesse. Makroprotsessoreid kasutatakse sageli programmeerimiskeelte lisandmoodulitena, suurendades funktsionaalsust programmeerimissüsteemid. Peaaegu iga komplekteerija sisaldab makroprotsessorit, mis suurendab masinaprogrammide arendamise efektiivsust. Selliseid programmeerimissüsteeme nimetatakse tavaliselt makrokoostajateks.

Makroprotsessoreid kasutatakse ka kõrgetasemeliste keelte puhul. Need suurendavad selliste keelte funktsionaalsust nagu PL/1, C, C++. Makroprotsessoreid kasutatakse eriti laialdaselt C ja C++ puhul, mis teeb programmide kirjutamise lihtsamaks. Makroprotsessorite laialdase kasutamise näide on Microsoft Foundation Classes (MFC) klassiteek. See rakendab sõnumikaarte ja muid programmiobjekte makrolisade kaudu. Samal ajal suurendavad makroprotsessorid programmeerimise efektiivsust ilma keele süntaksit ja semantikat muutmata.

Süntaks – teatud keele reeglite kogum, mis määrab selle elementide kujunemise. Teisisõnu, see reeglistik antud keeles semantiliselt oluliste märgijadade moodustamiseks. Süntaks määratakse reeglite abil, mis kirjeldavad keele mõisteid. Mõisted on näiteks: muutuja, avaldis, operaator, protseduur. Mõistete jada ja nende aktsepteeritav kasutamine reeglites määratakse süntaktiliselt õiged struktuurid, moodustades programme. Süntaksi kaudu määratletakse objektide hierarhia, mitte see, kuidas nad üksteisega suhtlevad. Näiteks lause saab esineda ainult protseduuris, avaldis lauses, muutuja võib koosneda nimest ja valikulistest indeksitest jne. Süntaksit ei seostata programmis selliste nähtustega nagu "olematule sildile hüppamine" või "eesnimega muutuja pole määratletud". Seda teeb semantika.

Semantika - reeglid ja tingimused, mis määravad keeleelementide ja nende semantiliste tähenduste vahelise suhte, samuti keele süntaktiliste konstruktsioonide tähendusliku tähenduse tõlgendamise. Programmeerimiskeele objektid ei ole mitte ainult paigutatud teksti vastavalt teatud hierarhiale, vaid on täiendavalt seotud ka muude mõistete kaudu, mis moodustavad erinevaid seoseid. Näiteks muutujal, mille jaoks süntaks määrab kehtiva asukoha ainult deklaratsioonides ja mõnes lauses, on teatud tüüp, seda saab kasutada piiratud arvu toimingutega, sellel on aadress, suurus ja see tuleb enne deklareerimist deklareerida. programmis kasutada.

Süntaktiline analüsaator - kompilaatori komponent, mis kontrollib lähtelausete vastavust süntaktiliste reeglite ja semantikaga sellest keelest programmeerimine. Vaatamata oma nimele kontrollib analüsaator nii süntaksit kui ka semantikat. See koosneb mitmest plokist, millest igaüks lahendab oma probleemid. Täpsemalt tuleb sellest juttu tõlkija struktuuri kirjeldamisel.

Programmeerimiskeelte ja tõlkijate üldised omadused

Programmeerimiskeeled erinevad üksteisest üsna eesmärgi, struktuuri, semantilise keerukuse ja rakendusmeetodite poolest. See paneb konkreetsete tõlkijate arendamisele oma eripärad.

Programmeerimiskeeled on vahendid erinevate ainevaldkondade probleemide lahendamiseks, mis määrab nende korralduse eripära ja eesmärgierinevused. Näideteks on sellised keeled nagu Fortran, mis on orienteeritud teaduslikele arvutustele, C, mis on mõeldud süsteemide programmeerimiseks, Prolog, mis kirjeldab tõhusalt järeldusprobleeme ja Lisp, mida kasutatakse loendite rekursiivseks töötlemiseks. Neid näiteid võib jätkata. Iga ainevaldkond seab keelekorraldusele omad nõuded. Seetõttu võime ainevaldkonnaga mitteseotud ülesannete lahendamisel märkida operaatorite ja avaldiste esitusvormide mitmekesisust, põhitehte hulga erinevust ja programmeerimise efektiivsuse vähenemist. Keelelised erinevused kajastuvad ka tõlkijate struktuuris. Lisp ja Prolog käivitatakse kõige sagedamini tõlgendusrežiimis, kuna nad kasutavad arvutuste ajal andmetüüpide dünaamilist genereerimist. Fortrani tõlkijaid iseloomustab saadud masinkoodi agressiivne optimeerimine, mis saab võimalikuks tänu keelekonstruktsioonide suhteliselt lihtsale semantikale – eelkõige seetõttu, et puuduvad mehhanismid muutujate alternatiivseks nimetamiseks osutite või viidete kaudu. Osutajate olemasolu C-keeles esitab konkreetsed nõuded To dünaamiline jaotus mälu.

Keele struktuur iseloomustab tema mõistete vahelisi hierarhilisi suhteid, mida kirjeldavad süntaktilised reeglid. Programmeerimiskeeled võivad üksikute mõistete korralduse ja nendevaheliste suhete poolest üksteisest oluliselt erineda. Programmeerimiskeel PL/1 võimaldab protseduuride ja funktsioonide suvalist pesastamist, samas kui C-s peavad kõik funktsioonid olema välimisel pesastustasemel. C++ keel võimaldab muutujaid deklareerida mis tahes punktis programmis enne selle esmakordset kasutamist, samas kui Pascalis tuleb muutujad määratleda spetsiaalses deklaratsioonialas. Seda veelgi kaugemale võttes on PL/1, mis võimaldab muutuja deklareerida pärast selle kasutamist. Või võite kirjelduse üldse ära jätta ja kasutada vaikereegleid. Olenevalt tehtud otsusest saab tõlkija programmi analüüsida ühe või mitme käiguga, mis mõjutab tõlkimise kiirust.

Programmeerimiskeelte semantika on väga erinev. Need erinevad mitte ainult üksikute operatsioonide rakendusomaduste poolest, vaid ka programmeerimisparadigmade poolest, mis määravad programmi arendusmeetodite põhimõttelised erinevused. Toimingute teostamise spetsiifika võib puudutada nii töödeldavate andmete struktuuri kui ka sama liiki andmete töötlemise reegleid. Sellised keeled nagu PL/1 ja APL toetavad maatriksi- ja vektoroperatsioone. Enamik keeli töötab peamiselt skalaaridega, pakkudes programmeerijate kirjutatud protseduure ja funktsioone massiivide töötlemiseks. Kuid isegi kahe täisarvu lisamise toimingu tegemisel võivad sellised keeled nagu C ja Pascal käituda erinevalt.

Traditsioonilise protseduurilise programmeerimise kõrval, mida nimetatakse ka imperatiivseks, eksisteerivad sellised paradigmad nagu funktsionaalne programmeerimine, loogiline programmeerimine ja objektorienteeritud programmeerimine. Loodan, et minu pakutud protseduurilis-parameetrilise programmeerimise paradigma võtab selles seerias oma koha [Legalov2000]. Keelte mõistete ja objektide struktuur sõltub suuresti valitud paradigmast, mis mõjutab ka tõlkija rakendamist.

Isegi sama keelt saab rakendada mitmel viisil. See on tingitud asjaolust, et formaalsete grammatikate teooria võimaldab samade lausete parsimiseks kasutada erinevaid meetodeid. Vastavalt sellele saavad tõlkijad algsest lähtetekstist erineval viisil saada sama tulemuse (objektprogrammi).

Samal ajal on kõigil programmeerimiskeeltel mitmeid ühiseid omadusi ja parameetreid. See ühisosa määrab ka tõlkijate korraldamise põhimõtted, mis on kõigi keelte jaoks sarnased.

Programmeerimiskeeled on loodud programmeerimise hõlbustamiseks. Seetõttu on nende operaatorid ja andmestruktuurid võimsamad kui masinkeelte omad.
Programmide selguse suurendamiseks numbrikoodide asemel sümboolne või graafilised esitused inimese taju jaoks mugavamad keelestruktuurid.
Iga keele jaoks on see määratletud:

Palju sümboleid, millega saab kirjutada õigeid programme (tähestik), põhielemente.
Palju õigeid programme (süntaks).
Iga õige programmi "tähendus" (semantika).

Sõltumata keele spetsiifikast võib iga tõlkijat pidada funktsionaalseks muunduriks F, mis pakub ainulaadset vastendust X-st Y-le, kus X on lähtekeeles programm, Y on programm väljundkeeles. Seetõttu saab tõlkeprotsessi ennast formaalselt esitada üsna lihtsalt ja selgelt:

Formaalselt on iga õige programm X mingi tähestiku A sümbolite ahel, mis on teisendatud sellele vastavaks ahelaks Y, mis koosneb tähestiku B sümbolitest.

Programmeerimiskeel, nagu iga keeruline süsteem, on määratletud mõistete hierarhia kaudu, mis määratleb selle elementide vahelised seosed. Need mõisted on omavahel seotud süntaktiliste reeglite kohaselt. Igal nende reeglite järgi ehitatud programmil on vastav hierarhiline struktuur.

Sellega seoses saab kõigi keelte ja nende programmide puhul lisaks eristada järgmist: ühiseid jooni: iga keel peab sisaldama reegleid sellele keelele vastavate programmide genereerimiseks või kirjalike programmide ja antud keele vahelise vastavuse tuvastamiseks.

Programmi struktuuri ja programmeerimiskeele vahelist seost nimetatakse süntaktiline kaardistamine.

Vaatleme näiteks suhet hierarhilise struktuuri ja sümbolite jada vahel, mis määratleb järgmise aritmeetilise avaldise:

Enamikus programmeerimiskeeltes määrab see avaldis programmiobjektide hierarhia, mida saab kuvada puuna (joonis 1.1.):

Ringid tähistavad elementaarstruktuuridena kasutatavaid sümboleid ja ristkülikud tähistavad liitkontseptsioone, millel on hierarhiline ja võib-olla ka rekursiivne struktuur. See hierarhia on määratletud süntaktiliste reeglite abil, mis on kirjutatud spetsiaalses keeles, mida nimetatakse metakeeleks (metakeeltest räägitakse üksikasjalikumalt formaalsete grammatikate uurimisel):

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

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

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

<буква>

Märge. Märk "::=" loetakse kui "see on". Toru "|" loeb nagu "või".

Kui reeglid on kirjutatud teisiti, siis hierarhiline struktuur. Näitena saame reeglite kirjutamiseks tuua järgmise viisi:

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

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

<буква>::= a | b | c | d | ma | f | g | h | ma | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z

Tulemusena sõelumine sama aritmeetiline avaldis ehitatakse hierarhiline struktuur, mis on näidatud joonisel fig. 1.2.

Tuleb märkida, et hierarhiline struktuur üldjuhul ei pruugi kuidagi olla seotud väljendi semantikaga. Mõlemal juhul saab tehte prioriteedi realiseerida vastavalt üldtunnustatud reeglitele, kui liitmisele eelneb korrutamine (või vastupidi, kõikidel tehtetel võib mis tahes reeglistiku korral olla sama prioriteet). Esimene struktuur toetab aga selgelt üldtunnustatud prioriteedi edasist rakendamist, teine aga sobib paremini sama prioriteediga toimingute teostamiseks ja nende sooritamiseks paremalt vasakule.

Antud programmi süntaktilise struktuuri leidmise protsessi nimetatakse sõelumine.

Ühes keeles õige süntaktiline struktuur võib teises keeles olla vale. Näiteks Forthi keeles antud väljendit ei tuvastata. Selle keele puhul on aga õige postfix avaldis:

Selle süntaktilist struktuuri kirjeldavad reeglid:

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

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

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

<буква>::= a | b | c | d | ma | f | g | h | ma | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z

Hierarhiline puu määratlemine süntaktiline struktuur, näidatud joonisel fig. 1.3.

Teine kõigi keelte iseloomulik tunnus on nende semantika. See määrab keeletehte tähenduse ja operandide õigsuse. Erinevates programmeerimiskeeltes sama süntaktilise struktuuriga ahelad võivad semantika poolest erineda (mida näiteks C++, Pascal, Basic puhul täheldatakse ülaltoodud aritmeetilise avaldise fragmendi puhul).

Keele semantika tundmine võimaldab teil selle süntaksist eraldada ja kasutada teise keelde teisendamiseks (koodi genereerimiseks).

Semantika kirjeldamine ja selle õigsuse tuvastamine on tavaliselt tõlkija töömahukam ja mahukam osa, kuna on vaja loetleda ja analüüsida paljusid toimingute ja operandide kehtivate kombinatsioonide võimalusi.

Üldistatud tõlkija struktuur

Ühised omadused ja mustrid on omased nii erinevatele programmeerimiskeeltele kui ka nende keelte tõlkijatele. Nad läbivad sarnased protsessid lähteteksti teisendamiseks. Vaatamata asjaolule, et nende protsesside koostoimet saab korraldada erineval viisil, on võimalik tuvastada funktsioone, mille rakendamine viib samade tulemusteni. Nimetagem selliseid funktsioone tõlkeprotsessi faasideks.

Arvestades kompilaatori ja tõlgi sarnasust, vaatame kompilaatoris esinevaid faase. See tõstab esile:

Leksikaalse analüüsi faas.
Parsimise faas, mis koosneb:

süntaktilise struktuuri äratundmine;
semantiline parsimine, mille käigus tehakse tööd tabelitega, genereerides keele vahepealse semantilise esituse või objektmudeli.

Koodi genereerimise faas, mis:

keele vahepealse esituse või objektmudeli komponentide semantiline analüüs;
vahepealse esituse või objektimudeli tõlkimine objektkoodiks.

Koos tõlkeprotsessi põhifaasidega on võimalikud ka täiendavad etapid:

2a. Esituse uurimise ja optimeerimise vahepealne etapp, mis koosneb: 2a.1. vahepealse esituse õigsuse analüüsimine;
2a.2. vahepealse esituse optimeerimine.

3a. Objekti koodi optimeerimise etapp.

Tõlk erineb selle poolest, et koodi genereerimise faas asendatakse tavaliselt keele vahepealse esituse või objektmudeli elementide emuleerimise faasiga. Lisaks ei optimeeri tõlk tavaliselt vahepealset esitust, vaid emuleerib seda kohe.

Lisaks on võimalik eristada programmi töödeldud lähtetekstis leiduvate vigade analüüsi ja parandamise protsessi, mis on kõikides faasides ühtne.

Kompilaatori üldistatud struktuur, võttes arvesse selles olemasolevaid faase, on esitatud joonisel fig. 1.4.

See koosneb leksikaalanalüsaatorist, parserist, koodigeneraatorist ja veaanalüsaatorist. Koodigeneraatori asemel kasutab tõlk emulaatorit (joonis 1.5), millesse kantakse lisaks vaheesitluse elementidele ka lähteandmed. Emulaatori väljund on arvutuste tulemus.

Leksikaalne analüsaator (tuntud ka kui skanner) loeb märkide sisendstringi ja rühmitab need elementaarstruktuurideks, mida nimetatakse lekseemideks. Igal märgil on klass ja tähendus. Tavaliselt kandideerivad lekseemide rolli elementaarsed keelekonstruktsioonid, näiteks identifikaator, reaalarv, kommentaar. Saadud märgid edastatakse parserile. Skänner ei ole tõlkija kohustuslik osa. Küll aga võimaldab see tõsta tõlkeprotsessi tõhusust. Leksikaalsest analüüsist on pikemalt juttu teemas “Leksikaalse analüüsi korraldus”.

Parser parsib lähteprogrammi sissetulevate lekseemide abil, konstrueerib programmi süntaktilise struktuuri ja semantilise analüüsi koos keele objektmudeli moodustamisega. Objektimudel esindab süntaktilist struktuuri, mida täiendavad semantilised seosed olemasolevate mõistete vahel. Need ühendused võivad olla:

nimetabelitesse paigutatud viited muutujatele, andmetüüpidele ja protseduuride nimetustele;
ühendused, mis määravad käsu täitmise järjekorra;
seoseid, mis määravad keeleobjekti mudeli elementide pesastumise ja muud.

Nii et parser on üsna keeruline plokk tõlkija. Seetõttu võib selle jagada järgmisteks komponentideks:

äratundja;
semantilise analüüsi plokk;
objektimudel ehk vaheesitus, mis koosneb nimede tabelist ja süntaktilisest struktuurist.

Parseri üldistatud struktuur on näidatud joonisel fig. 1.6.

Äratundja saab lekseemide ahela ja selle põhjal teostab parsimise vastavalt kasutatavatele reeglitele. Reeglite edukal sõelumisel kantakse märgid üle semantilisse analüsaatorisse, mis koostab nimede tabeli ja salvestab süntaktilise struktuuri fragmente. Lisaks registreeritakse täiendavad semantilised seosed nimetabeli ja süntaktilise struktuuri vahel. Selle tulemusena moodustub programmi objektmudel, mis on vabastatud sidumisest programmeerimiskeele süntaksiga. Üsna sageli luuakse keeleobjektide hierarhiat täielikult kopeeriva süntaktilise struktuuri asemel selle lihtsustatud analoog, mida nimetatakse vahepealseks esituseks.

Veaanalüsaator saab teavet vigade kohta, mis ilmnevad erinevad plokid tõlkija. Kasutades saadud teavet, genereerib see kasutajale sõnumeid. Lisaks võib see plokk proovida viga parandada, et sõelumist jätkata. Samuti vastutab ta programmi korrektse lõpetamisega seotud toimingute eest juhul, kui saate jätkamine on võimatu.

Koodigeneraator koostab objekti masinkoodi objektimudeli analüüsi või vahepealse esituse põhjal. Koodi ehitusega kaasneb täiendav semantiline analüüs, mis on seotud vajadusega teisendada üldistatud käsud konkreetse arvuti koodideks. Sellise analüüsi etapis määratakse lõplikult kindlaks ümberkujundamise võimalus ja valitakse tõhusad võimalused. Koodi genereerimine ise on ühe käsu ümberkodeerimine teiseks.

Tõlkijaplokkide interaktsiooni võimalused

Tõlkeprotsesside korraldamine, mis määrab põhifaaside rakendamise, saab läbi viia erinevatel viisidel. Selle määravad erinevad tõlkijaplokkide interaktsiooni võimalused: leksikaalanalüsaator, parser ja koodigeneraator. Vaatamata samale lõpptulemusele, erinevaid valikuid tõlkijaplokkide interaktsioonid pakuvad erinevaid võimalusi vaheandmete salvestamiseks. Tõlkijaplokkide interaktsiooniks on kaks peamist võimalust:

mitme läbipääsuga organisatsioon, kus iga faas on iseseisev protsess, mis annab juhtimise üle järgmisse faasi alles pärast oma andmete täielikku töötlemist;
ühekäiguline organisatsioon, milles kõik faasid esindavad üht protsessi ja edastavad üksteisele andmeid väikeste fragmentidena.

Kahe põhivaliku alusel saate luua ka nende erinevaid kombinatsioone.

Tõlkijaplokkide interaktsiooni mitmekäiguline korraldamine

See plokkide interaktsiooni versioon, kasutades näitena kompilaatorit, on toodud joonisel 1.7.

Leksikaalne analüsaator töötleb täielikult lähteteksti, moodustades väljundahela, mis koosneb kõigist vastuvõetud lekseemidest. Alles pärast seda antakse juhtimine üle parserile. Parser võtab vastu genereeritud lekseemide ahela ja moodustab selle põhjal vahepealse esituse ehk objektmudeli. Pärast kogu objektimudeli vastuvõtmist annab see juhtimise üle koodigeneraatorile. Koodigeneraator koostab keeleobjekti mudeli põhjal vajaliku masinkoodi

Selle lähenemisviisi eelised hõlmavad järgmist:

Üksikute faaside eraldamine, mis võimaldab neid iseseisvalt rakendada ja kasutada.
Võimalus salvestada iga faasi töö tulemusena saadud andmeid välistele salvestusseadmetele ja kasutada neid vastavalt vajadusele.
Mahu vähendamise võimalus muutmälu, mis on faaside järjestikuse kutsumise tõttu vajalik tõlkija tööks.

Puuduste hulka kuuluvad:

Suure hulga vaheteabe olemasolu, millest Sel hetkel Vajalik on vaid väike osa ajast.
Edastuskiiruse aeglustumine faaside järjestikuse täitmise ja väliste salvestusseadmete kasutamise tõttu RAM-i säästmiseks.

See lähenemisviis võib olla mugav tõlkijate koostamisel keeruka süntaktilise ja semantilise struktuuriga programmeerimiskeeltest (näiteks PL/I). Sellistes olukordades on tõlkimist raske ühe käiguga teostada, mistõttu on lihtsam esitada eelmiste läbimiste tulemusi täiendavate vaheandmetena. Tuleb märkida, et keele keerulised semantilised ja süntaktilised struktuurid võivad põhjustada täiendavaid läbipääsu, mis on vajalik vajalike sõltuvuste tuvastamiseks. Läbimiste koguarv võib olla üle kümne. Läbimiste arvu võib mõjutada ka see, kui programm kasutab konkreetseid keelefunktsioone, nagu muutujate ja protseduuride deklareerimine pärast nende kasutamist, deklaratsiooni vaikereeglite rakendamine jne.

Tõlkijaplokkide vahelise suhtluse ühekäiguline korraldamine

Üks võimalustest kompilaatoriplokkide interaktsiooniks ühekäigulise organisatsiooniga on esitatud joonisel fig. 1.8.

Sel juhul toimub tõlkeprotsess järgmiselt. Leksikaalne analüsaator loeb ühe lekseemi saamiseks vajaliku fragmendi lähtetekstist. Pärast märgi moodustamist kutsub see parseri ja edastab sellele parameetrina loodud märgi. Kui parser suudab konstrueerida vahepealse esituse järgmise elemendi, siis ta teeb seda ja edastab konstrueeritud fragmendi koodigeneraatorile. Vastasel juhul tagastab parser kontrolli skannerile, tehes seeläbi selgeks, et järgmine luba on töödeldud ja vaja on uusi andmeid.

Koodigeneraator toimib sarnaselt. Vastuvõetud vaheesituse fragmendi põhjal loob see vastava objektikoodi fragmendi. Pärast seda naaseb juhtimine parserisse.

Pärast lähteteksti valmimist ja kõigi vaheandmete töötlemise lõpetamist iga ploki poolt algatab leksikaalne analüsaator programmi lõpetamise protsessi.

Kõige sagedamini kasutavad ühekäigulised tõlkijad teistsugust juhtimisskeemi, milles parser täidab põhiploki rolli (joonis 1.9).

Leksikaalne analüsaator ja koodigeneraator toimivad alamprogrammidena, mida ta kutsub. Niipea, kui parser vajab teist tunnust, kutsub ta skanneri. Vaheesitluse fragmendi vastuvõtmisel helistatakse koodigeneraatorile. Tõlkeprotsess lõpetatakse pärast viimase märgi vastuvõtmist ja töötlemist ning selle algatab parser.

Ühekäigulise skeemi eelised hõlmavad suurte vaheandmete puudumist, suurt töötlemiskiirust, mis on tingitud faaside kombinatsioonist ühes protsessis, ja juurdepääsu puudumist välistele salvestusseadmetele.

Puuduste hulka kuuluvad: sellise tõlkeskeemi rakendamise võimatus keeruka struktuuriga keelte jaoks ja vaheandmete puudumine, mida saaks kasutada keerukaks analüüsiks ja optimeerimiseks.

Seda skeemi kasutatakse sageli programmeerimiskeelte jaoks, mis on semantilistes ja süntaktilistes struktuurides lihtsad, nii kompilaatorites kui ka tõlkides. Selliste keelte näited on Basic ja Pascal. Klassikaline tõlk ehitatakse tavaliselt ühekäigulise skeemi abil, kuna otsene täitmine toimub vahepealse esituse üksikute fragmentide tasemel. Sellise tõlgi plokkide vahelise interaktsiooni korraldus on näidatud joonisel fig. 1.10.

Tõlkijaplokkide kombineeritud interaktsioonid

Mitme- ja ühekäiguliste tõlkeskeemide kombinatsioonid toovad kaasa mitmesuguseid kombineeritud valikuid, millest paljusid kasutatakse edukalt. Näitena võime vaadelda mõnda neist.

Joonisel fig. Joonisel 1.11 on kujutatud translaatoriplokkide interaktsiooni skeem, mis jagab kogu protsessi kaheks käiguks. Esimene läbimine genereerib programmi täieliku vahepealse esituse ja teine koodi. Sellise skeemi kasutamine võimaldab hõlpsasti tõlkija ühest arvutisüsteemist teise üle kanda, kirjutades koodigeneraatori ümber.

Lisaks on koodigeneraatori asemel lihtne ühendada vahepealne esitusemulaator, mis võimaldab üsna lihtsalt välja töötada kindlas keeles programmeerimissüsteemi, mis on orienteeritud erinevatele täitmiskeskkondadele. Sellise tõlkijaplokkide vahelise interaktsiooni korralduse näide on näidatud joonisel fig. 1.12.

Lisaks skeemidele, mis hõlmavad koodigeneraatori asendamist emulaatoriga, on ka tõlkijaid, mis võimaldavad nende ühist kasutamist. Üks sellistest skeemidest on näidatud joonisel fig. 1.13.

Tõlkeprotsessi, sealhulgas koodi genereerimist, saab lõpule viia suvalise arvu käikudega (näites kasutatakse varem esitatud ühekäigulist tõlget). Loodud objektikoodi aga vastaval ei käivitata arvutussüsteem, kuid seda emuleeritakse erineva arhitektuuriga arvutis. Seda skeemi kasutatakse keele ümber ehitatud keskkonnas Java programmeerimine. Tõlkija ise genereerib Java virtuaalmasina koodi, mida emuleeritakse erivahenditega nii iseseisvalt kui ka Interneti-brauseri keskkonnas.

Esitatud skeemil võib olla ka laiem tõlgendus seoses mis tahes kompilaatoriga, mis genereerib masinkoodi. Asi on selles, et enamik kaasaegseid arvuteid on rakendatud mikroprogrammide juhtimise abil. Mikroprogrammi juhtimisseadet võib käsitleda kui masinkoodi emuleerivat programmi. See võimaldab meil rääkida uusima esitatud skeemi laialdasest kasutamisest.

Testi küsimused ja ülesanded

Nimetage erinevused:

tõlk koostajast;
koostaja assemblerist;
tõlkija transkooder;
emulaator tõlgilt;
süntaks semantikast.

Rääkige meile teadaolevatest programmeerimiskeelte viimastest arengutest. Esitage nende keelte peamised omadused.
Tooge konkreetseid näiteid tõlkemeetodite kasutamisest valdkondades, mis pole seotud programmeerimiskeeltega.
Tooge konkreetseid näiteid kompileeritud programmeerimiskeelte kohta.
Tooge konkreetseid näiteid tõlgendatud programmeerimiskeelte kohta.
Tooge konkreetseid näiteid programmeerimiskeeltest, mille jaoks on saadaval nii kompilaatorid kui ka tõlgid.
Kompilaatorite peamised eelised ja puudused.
Tõlkide peamised eelised ja puudused.
Kirjeldage peamisi erinevusi kahe teile tuttava programmeerimiskeele süntaksis.
Kirjeldage peamisi erinevusi kahe teile tuttava programmeerimiskeele semantikas.
Nimeta tõlkeprotsessi põhifaasid ja nende eesmärk.
Nimeta ühekäigulise tõlke eripärad.
Nimeta mitmekäigulise tõlke eripärad.
Tooge näiteid ühe- ja mitmekäigulise tõlke võimalike kombinatsioonide kohta. Rääkige meile nende skeemide praktilisest kasutamisest.

Tõlkija tegeleb enamasti ka vigade diagnoosimisega, identifikaatorisõnastiku koostamisega, printimiseks programmitekstide tootmise jms.

Saate ülekanne- ühes programmeerimiskeeles esitatud programmi muutmine programmiks teises keeles ja teatud mõttes samaväärseks esimesega.

Nimetatakse keel, milles sisendprogrammi esitatakse algkeel ja programm ise - lähtekood. Väljundkeelt nimetatakse sihtkeel või objekti kood.

Tõlke mõiste ei kehti mitte ainult programmeerimiskeelte, vaid ka teiste arvutikeelte kohta, nagu HTML-ile sarnased märgistuskeeled ja loomulikud keeled, nagu inglise või vene keel. See artikkel räägib aga ainult programmeerimiskeeltest, umbes loomulikud keeled Vaata tõlget.

Tõlkijate tüübid

Aadress. Funktsionaalne seade, mis teisendab virtuaalse aadressi reaalseks mäluaadressiks.
Dialoog. Võimaldab kasutada programmeerimiskeelt ajajagamise režiimis.
Mitmikpass. Moodustab objektmooduli mitme lähteprogrammi vaate kaudu.
tagasi. Sama mis detõlkija. Vaata ka: dekompilaator, disassembler.
Üksikpääs. Vormid objekti moodul algprogrammi üheks järjestikuseks vaatamiseks.
Optimeerimine. Teostab loodud objektimoodulis koodi optimeerimise.
Süntaktiline (süntaktiline). Saab sisendiks keele ja teksti süntaksi ja semantika kirjelduse kirjeldatud keeles, mis tõlgitakse vastavalt antud kirjeldusele.
Test. Assamblee keele makrode komplekt, mis võimaldab seadistada erinevaid silumisprotseduure montaažikeeles kirjutatud programmides.

Rakendused

Tõlke eesmärk on teisendada tekst ühest keelest teise, mis on teksti vastuvõtjale arusaadav. Tõlkeprogrammide puhul on adressaadiks tehniline seade (protsessor) või tõlkeprogramm.

On veel hulk näiteid, kus väljatöötatud arvutiseeria arhitektuur põhines või sõltus tugevalt mõnest programmistruktuuri mudelist. Seega põhines GE/Honeywell Multicsi seeria semantilisel mudelil PL/1 keeles kirjutatud programmide täitmiseks. Mall:Tõlgimata B5500, B6700 ... B7800 põhines käitusprogrammi mudelil, mis oli kirjutatud laiendatud ALGOL-keeles. ...

i432 protsessor, nagu ka need varasemad arhitektuurid, põhineb samuti programmi struktuuri semantilisel mudelil. Erinevalt eelkäijatest ei põhine i432 aga kindlal programmeerimiskeele mudelil. Selle asemel oli arendajate peamine eesmärk pakkuda mõlemale otsest käitusaegset tuge abstraktsed andmed(st abstraktsete andmetüüpidega programmeerimine) ja jaoks domeenispetsiifilised operatsioonisüsteemid. …

Kompilaatori eelis: programm kompileeritakse üks kord ja iga käivitamise korral pole vaja täiendavaid teisendusi. Seetõttu pole sihtmasinas, mille jaoks programm kompileeritud, kompilaatorit vaja. Puudus: eraldi kompileerimise etapp aeglustab kirjutamist ja silumist ning raskendab väikeste, lihtsate või ühekordsete programmide käitamist.

Kui lähtekeeleks on assemblerkeel ( madalal tasemel keel, masinakeele lähedane), siis kutsutakse sellise keele kompilaator komplekteerija.

Vastupidine rakendamisviis on siis, kui programmi käivitatakse kasutades tõlkülekannet pole üldse. Tõlgitarkvara modelleerib masinat, mille tõmbamis-käitmise tsükkel töötab kõrgetasemelistes keeltes olevate käskude, mitte masina käskude alusel. See tarkvarasimulatsioon loob virtuaalse masina, mis rakendab keelt. Seda lähenemist nimetatakse puhas tõlgendus. Puhast tõlget kasutatakse tavaliselt lihtsa struktuuriga keelte puhul (näiteks APL või Lisp). Käsurea tõlgid töötlevad käske UNIX-is skriptides või MS-DOS-is pakkfailides (.bat), tavaliselt ka puhta tõlgenduse režiimis.

Puhta tõlgi eelis: tõlkimisel vahetoimingute puudumine lihtsustab tõlgi rakendamist ja muudab selle kasutamise mugavamaks, sealhulgas dialoogirežiimis. Puuduseks on see, et sihtmasinas, kus programmi käivitatakse, peab olema tõlk. Ja puhta interpreteerija omadust, et tõlgendatavas programmis avastatakse vead alles siis, kui üritatakse veaga käsku (või rida) täita, võib pidada nii puuduseks kui eeliseks.

Programmeerimiskeelte rakendamisel on kompileerimise ja puhta tõlgendamise vahel kompromissid, kui tõlk tõlgib enne programmi käivitamist selle vahekeelde (näiteks baitkoodi või p-koodi), mis on tõlgendamiseks mugavam (st räägime tõlgist, millel on sisseehitatud tõlkija) . Seda meetodit nimetatakse segarakendus. Segakeele rakendamise näide on Perl. See lähenemine ühendab endas nii kompilaatori ja tõlgi eelised (suurem täitmiskiirus ja kasutusmugavus) kui ka puudused (programmi tõlkimiseks ja salvestamiseks vahepealsesse keelde on vaja lisaressursse; programmi käivitamiseks sihtmärgil peab olema tõlk masin). Samuti, nagu kompilaatori puhul, nõuab segarakendus, et lähtekood oleks enne käivitamist vigadeta (leksikaalsed, süntaktilised ja semantilised).

Seoses arvutiressursside suurenemisega ja heterogeensete võrkude (sh Internet), mis ühendavad erinevat tüüpi ja erineva arhitektuuriga arvuteid, laienemisega, uut tüüpi tõlgendus, mille puhul lähte- (või vahe-) kood kompileeritakse masinkoodiks otse käitusajal, “käigul”. Juba kompileeritud koodilõigud salvestatakse vahemällu, nii et kui neile uuesti juurde pääsete, saavad need kohe kontrolli, ilma uuesti kompileerimata. Seda lähenemist nimetatakse dünaamiline koostamine.

Dünaamilise kompileerimise eeliseks on see, et programmi tõlgendamise kiirus muutub võrreldavaks tavapärastes kompileeritud keeltes programmi täitmise kiirusega, samas kui programm ise salvestatakse ja levitatakse ühel kujul, sõltumata sihtplatvormidest. Puuduseks on suurem juurutamise keerukus ja suurem ressursinõue kui lihtsate kompilaatorite või puhaste tõlkide puhul.

See meetod sobib hästi

Saada oma head tööd teadmistebaasi on lihtne. Kasutage allolevat vormi

Üliõpilased, magistrandid, noored teadlased, kes kasutavad teadmistebaasi oma õpingutes ja töös, on teile väga tänulikud.

Postitatud aadressil http://www.allbest.ru

Sissejuhatus

1.1 Ülalt-alla analüüs

1.2 Alt-üles analüüs

1.2.1 LR(k) - grammatika

1.2.1.1 LR(0) - grammatika

1.2.2 LALR(1) - grammatika

2. Tõlkija arendamine

2.1 Nõuete analüüs

2.2 Disain

2.2.1 Leksikaalanalüsaatori projekteerimine

2.2.4 Parseri tarkvara juurutamine

2.3 Kodeerimine

2.4 Testimine

Järeldus

Kasutatud allikate loetelu

Lisa A. Tõlkeprogrammi teksti loetlemine

Lisa B. Katsetulemused

Lisa B. Tõlkija programmi skeem

Sissejuhatus

Ammu on möödas ajad, mil enne programmi kirjutamist pidi mõistma ja meeles pidama kümneid masinajuhiseid. Kaasaegne programmeerija sõnastab oma ülesanded kõrgetasemelistes programmeerimiskeeltes ja kasutab assemblerkeelt ainult erandjuhtudel. Nagu teada, muutuvad algoritmilised keeled programmeerijale kättesaadavaks alles pärast nendest keeltest tõlkijate loomist.

Programmeerimiskeeled erinevad üksteisest üsna eesmärgi, struktuuri, semantilise keerukuse ja rakendusmeetodite poolest. See paneb konkreetsete tõlkijate arendamisele oma eripärad.

Programmeerimiskeeled on vahendid erinevate ainevaldkondade probleemide lahendamiseks, mis määrab nende korralduse eripära ja eesmärgierinevused. Näideteks on sellised keeled nagu Fortran, mis on orienteeritud teaduslikele arvutustele, C, mis on mõeldud süsteemide programmeerimiseks, Prolog, mis kirjeldab tõhusalt järeldusprobleeme ja Lisp, mida kasutatakse loendite rekursiivseks töötlemiseks. Neid näiteid võib jätkata. Iga ainevaldkond seab keelekorraldusele omad nõuded. Seetõttu võime ainevaldkonnaga mitteseotud ülesannete lahendamisel märkida operaatorite ja avaldiste esitusvormide mitmekesisust, põhitehte hulga erinevust ja programmeerimise efektiivsuse vähenemist. Keelelised erinevused kajastuvad ka tõlkijate struktuuris. Lisp ja Prolog käivitatakse kõige sagedamini tõlgendusrežiimis, kuna nad kasutavad arvutuste ajal andmetüüpide dünaamilist genereerimist. Fortrani tõlkijaid iseloomustab saadud masinkoodi agressiivne optimeerimine, mis saab võimalikuks tänu keelekonstruktsioonide suhteliselt lihtsale semantikale – eelkõige seetõttu, et puuduvad mehhanismid muutujate alternatiivseks nimetamiseks osutite või viidete kaudu. Osutite olemasolu C-keeles seab dünaamilisele mälu jaotamisele erinõuded.

Traditsioonilise protseduurilise programmeerimise kõrval, mida nimetatakse ka imperatiivseks, eksisteerivad sellised paradigmad nagu funktsionaalne programmeerimine, loogiline programmeerimine ja objektorienteeritud programmeerimine. Keelte mõistete ja objektide struktuur sõltub suuresti valitud paradigmast, mis mõjutab ka tõlkija rakendamist.

Isegi sama keelt saab rakendada mitmel viisil. See on tingitud asjaolust, et formaalsete grammatikate teooria võimaldab samade lausete parsimiseks kasutada erinevaid meetodeid. Vastavalt sellele saavad tõlkijad algsest lähtetekstist erineval viisil saada sama tulemuse (objektprogrammi).

Samal ajal on kõigil programmeerimiskeeltel mitmeid ühiseid omadusi ja parameetreid. See ühisosa määrab ka tõlkijate korraldamise põhimõtted, mis on kõigi keelte jaoks sarnased.

Programmeerimiskeeled on loodud programmeerimise hõlbustamiseks. Seetõttu on nende operaatorid ja andmestruktuurid võimsamad kui masinkeelte omad.

Programmide nähtavuse suurendamiseks kasutatakse numbrikoodide asemel keelekonstruktsioonide sümboolseid või graafilisi esitusi, mis on inimese taju jaoks mugavamad.

Iga keele jaoks on see määratletud:

- palju sümboleid, millega saab kirjutada õigeid programme (tähestik), põhielemente,

- palju õigeid programme (süntaks),

- iga õige programmi "tähendus" (semantika).

Sõltumata keele spetsiifikast võib iga tõlkijat pidada funktsionaalseks muunduriks F, mis pakub ainulaadset vastendust X-st Y-le, kus X on lähtekeeles programm, Y on programm väljundkeeles. Seetõttu saab tõlkeprotsessi ennast formaalselt esitada üsna lihtsalt ja selgelt: Y = F(X).

Formaalselt on iga õige programm X mingi tähestiku A sümbolite ahel, mis on teisendatud sellele vastavaks ahelaks Y, mis koosneb tähestiku B sümbolitest.

Programmeerimiskeel, nagu iga keeruline süsteem, on määratletud mõistete hierarhia kaudu, mis määratleb selle elementide vahelised seosed. Need mõisted on omavahel seotud süntaktiliste reeglite kohaselt. Igal nende reeglite järgi ehitatud programmil on vastav hierarhiline struktuur.

Sellega seoses saab kõigi keelte ja nende programmide puhul lisaks eristada järgmisi ühiseid jooni: iga keel peab sisaldama reegleid, mis võimaldavad genereerida sellele keelele vastavaid programme või tuvastada kirjalike programmide ja antud keele vastavust.

Teine kõigi keelte iseloomulik tunnus on nende semantika. See määrab keeletehte tähenduse ja operandide õigsuse. Erinevates programmeerimiskeeltes sama süntaktilise struktuuriga ahelad võivad semantika poolest erineda (mida näiteks täheldatakse C++, Pascal, Basic puhul). Keele semantika tundmine võimaldab teil selle süntaksist eraldada ja kasutada teise keelde teisendamiseks (koodi genereerimiseks).

Selle kursusetöö eesmärgiks on etteantud lihtsustatud tõlgi väljatöötamine teksti keel kõrge tase.

1. Grammatikaanalüüsi meetodid

Vaatame grammatilise parsimise põhimeetodeid.

1.1 Ülalt-alla analüüs

Ülevalt alla sõelumisel liiguvad vahepealsed juhtmed piki puud juurest lehtedeni. Sel juhul tehakse ahelat vasakult paremale vaadates loomulikult vasakukäelised järeldused. Deterministliku parsimise puhul on probleem selles, millist reeglit rakendada vasakpoolseima mitteterminali lahendamiseks.

1.1.1 LL(k) - keeled ja grammatika

Kaaluge järelduspuud ahela vasakpoolse väljundi saamise protsessis. Järeldusprotsessi vaheahel koosneb klemmide ahelast w, kõige vasakpoolsemast mitte-otsast A, alajäreldatavast osast x:

-S--

/ \

/ -A-x-\

/ | \

-w---u----

Joonis 1

Parsimise jätkamiseks on vaja asendada mitteterminaal A vastavalt ühele vormi A:y reeglitest. Kui soovite, et sõelumine oleks deterministlik (tagastamata), tuleb see reegel valida erilisel viisil. Väidetakse, et grammatika omab omadust LL(k), kui reegli valimiseks piisab, kui võtta arvesse ainult wax ja uurimata stringi u esimest k märki. Esimene täht L (vasak) viitab sisendahela vaatamisele vasakult paremale, teine aga vasakpoolse väljundi kasutamisele.

Määratleme kaks ahelate komplekti:

a) FIRST(x) on x-ist tuletatud terminali stringide kogum, mis on lühendatud k märgini.

b) FOLLOW(A) - k-märgini lühendatud terminalahelate komplekt, mis võib väljundahelates kohe järgneda A-le.

Grammatikal on omadus LL(k), kui kahe vasakpoolsete järelduste ahela olemasolust:

S:: vaha: wzx:: wu

S:: vaha: wtx:: wv

tingimusest FIRST(u)=FIRST(v) järgneb z=t.

Juhul k=1, piisab A jaoks reegli valimiseks ainult mitteterminali A ja a – ahela u esimese tähe teadmisest:

- reegel A:x tuleks valida, kui a sisaldub jaotises FIRST(x),

- reegel A:e tuleks valida, kui a sisaldub järgus FOLLOW(A).

Omadus LL(k) seab grammatikale üsna tugevad piirangud. Näiteks LL(2) grammatika S: aS | a ei oma LL(1) omadust, sest FIRST(aS)=FIRST(a)=a. Sel juhul saate k väärtust vähendada "faktoriseerimise" abil (võte teguri sulgudest välja):

S: aA

A: S | e

Iga LL(k)-grammatika on üheselt mõistetav. Vasakpoolne rekursiivne grammatika ei kuulu ühegi k puhul klassi LL(k). Mõnikord on võimalik mitte-LL(1) grammatika teisendada samaväärseks LL(1) grammatikaks, välistades vasakpoolse rekursiooni ja faktoriseerimise. Siiski on lahendamatu probleem samaväärse LL(k)-grammatika olemasolust suvalise mitte-LL(k)-grammatika jaoks.

1.1.2 Rekursiivne laskumise meetod

Rekursiivne laskumismeetod on suunatud nendele juhtudele, kui kompilaator on programmeeritud mõnes kõrgetasemelises keeles, kui rekursiivsete protseduuride kasutamine on lubatud.

Rekursiivse laskumise põhiidee seisneb selles, et grammatika igal mitteterminalil on vastav protseduur, mis tunneb ära mis tahes selle mitteterminali genereeritud ahela. Need protseduurid helistavad vajadusel üksteisele.

Rekursiivset laskumist saab kasutada mis tahes LL(1) grammatika puhul. Igal grammatika mitteterminalil on vastav protseduur, mis algab üleminekuga arvutatud sildile ja sisaldab selle mitteterminali igale reeglile vastavat koodi. Nendele sisestussümbolitele, mis kuuluvad valikukomplekti sellest reeglist, annab arvutatud üleminek juhtimise üle sellele reeglile vastavale koodile. Ülejäänud sisendsümbolite puhul viiakse juhtimine üle veakäsitluse protseduurile.

Mis tahes reegli kood sisaldab toiminguid iga selles sisalduva märgi jaoks parem pool reeglid. Toimingud on paigutatud selles järjekorras, milles sümbolid reeglis esinevad. Pärast viimast toimingut sisaldab kood protseduuri naasmist.

Rekursiivse laskumise kasutamine kõrgetasemelises keeles muudab programmeerimise ja silumise lihtsamaks.

1.2 Alt-üles analüüs

Vaatleme alt-üles parsimist, mille käigus liigutatakse vahepealseid tihvte mööda puud juure poole. Kui loete stringis olevaid märke vasakult paremale, näeb parsipuu välja järgmine:

-S--

/ \

/-x-\

/ | \

--w--b--u-

Joonis 2

Vaheväljund on kujul xbu, kus x on klemmide ja mitteterminalide ahel, millest väljastatakse klemmiahela w vaadatud osa, bu on klemmahela vaatamata osa, b on järgmine sümbol. Analüüsi jätkamiseks võid lisada vaadeldavale ahela osale märgi b (sooritada nn “nihutust”) või valida x lõpus sellise ahela z (x=yz), et üks grammatika reegleid B:z saab rakendada z-le ja asendada x ahelaga yB (sooritada nn konvolutsiooni):

-S-- -S--

/ \ / \

/-x-b-\ /yB-\

/ | \ / | \

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

Joonis 3 – Pärast vahetust Joonis 4 – Pärast keerdumist

Kui konvolutsiooni rakendada ainult x viimastele märkidele, saame ahela õiged väljundid. Seda sõelumist nimetatakse LR-ks, kus sümbol L (vasak, vasak) viitab ahela vaatamisele vasakult paremale ja R (parem, parem) viitab saadud väljunditele.

Nihutamise ja voltimise toimingute järjestus on oluline. Seetõttu nõuab deterministlik parsimine igal hetkel valikut nihke ja konvolutsiooni (ja erinevate konvolutsioonireeglite) vahel.

1.2.1 LR(k) - grammatika

Kui LR-i parsimise käigus on võimalik teha deterministlik otsus nihke/vähendamise kohta, võttes arvesse ainult stringi x ja sisendstringi u nähtamatu osa esimest k märki (neid k märki nimetatakse eelstringiks ), väidetakse, et grammatika omab LR(k) omadust.

-S--

/ \

/-x-\

--w----u--

Joonis 5

Erinevus LL(k) ja LR(k) grammatika vahel järelduspuu poolest:

-S-

/ | \

/A\

/ / \ \

-w---v---u-

Joonis 6

LL(k)-grammatika puhul saab A-le rakendatavat reeglit üheselt määrata w ja vu esimese k tähemärgiga ning LR(k)-grammatika puhul w,v ja esimese k-ga. tegelased u. See mitterange arutluskäik näitab, et LL(k)-keeled< LR(k)-языки (при k > 0).

1.2.1.1 LR(0) - grammatika

Vaatleme kõigepealt selle klassi lihtsamaid grammatikaid - LR(0). Stringi sõelumisel LR(0) keeles ei pea te edenemisahelat üldse kasutama – valik nihutamise ja voltimise vahel tehakse ahela x põhjal. Kuna parsimise käigus muutub see ainult paremast otsast, siis nimetatakse seda virnaks. Eeldame, et grammatikas puudub kasutud tegelased ja algusmärki ei esine reeglite paremal pool – siis konvolutsioon algusmärgiks annab signaali parsimise edukast lõpetamisest. Proovime kirjeldada terminalide ja mitteterminalide ahelate kogumit, mis ilmuvad virnale kogu LR-i parsimise ajal (teisisõnu kõiki grammatika parempoolseid järeldusi).

Määratleme järgmised komplektid:

L(A:v) - reegli A:v vasak kontekst - pinu olekute kogum vahetult enne v voldimist A-ks kõigi edukate LR-i parsimiste ajal. Ilmselgelt lõpeb iga ahel L(A:v)-ga v. Kui kõigi selliste ahelate saba v on ära lõigatud, saame kõigi edukate parempoolsete järelduste ajal A-st vasakul esinevate ahelate hulga. Tähistame seda hulka kui L(A) - mitteterminaalse A vasakpoolset konteksti.

Koostame hulga L(A) jaoks grammatika. Uue grammatika terminalid on algse grammatika terminalid ja mitteterminalid, uue grammatika mitteterminalid tähistatakse ,... - nende väärtused on algse grammatika mitteterminali vasakpoolsed kontekstid. Kui S on algse grammatika algusmärk, sisaldab reeglit vasakpoolsete kontekstide grammatika : e - vasakpoolne kontekst S sisaldab tühja ahelat Iga algse grammatika reegli jaoks, näiteks A: B C d E

ja lisage uuele grammatikale reeglid:

: - L(B) sisaldab L(A)

: B – L(C) sisaldab L(A) B-d

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

Saadud grammatika on eritüüp(sellisi grammatikaid nimetatakse vasakpoolseteks lineaarseteks), seega vasakpoolsete kontekstide kogumid

- tavaline. Sellest järeldub, et seda, kas string kuulub mitteterminali vasakpoolsesse konteksti, saab arvutada induktiivselt lõpliku oleku masina abil, skaneerides stringi vasakult paremale. Kirjeldame seda protsessi konstruktiivselt.

Nimetagem LR(0)-situatsiooniks grammatikareeglit, mille reegli parempoolse külje sümbolite vahel on üks märgitud asukoht. Näiteks grammatika S:A jaoks; A:aAA; A:b on olemas järgmised LR(0)-olukorrad: S:_A; S:A_; A:_aAA; A:a_AA; A:aA_A; A:aAA_; A:_b; A:b_. (positsiooni tähistab allkriips).

Me ütleme, et ahel x on kooskõlas olukorraga A:b_c, kui x=ab ja a kuulub L(A). (Teisisõnu, LR väljundit saab jätkata x_... = ab_...:: abc_...:: aA_...:: S_.) Nendes tingimustes on L(A:b) hulk stringidest, mis on kooskõlas olukorraga A:b_, L(A)

- ahelad, mis vastavad olukorrale A:_b, mis tahes reegli A:b jaoks.

Olgu V(u) u-ga kooskõlas olevate olukordade hulk. Näitame, et funktsioon V on induktiivne.

Kui hulk V(u) sisaldab olukorda A:b_cd, siis olukord A:bc_d kuulub V(uc) hulka. (c - terminaalne või mitteterminaalne; b, d - terminalide ja mitteterminalide järjestused (võivad olla tühjad). Muid olukordi kujul A:b_d, kus V(uc) on mittetühi b, pole. Jääb üle V(uc) lisada olukorrad kujul C:_... iga mitteterminaalse C jaoks, mille vasakpoolne kontekst sisaldab uc. Kui olukord A:..._C... (C-mitteterminaalne) kuulub hulka V(uc), siis uc kuulub hulka L(C) ja V(uc) sisaldab olukordi kujul C:_... kõik C-grammatikareeglid.

V(e) sisaldab olukordi S:_... (S-algusmärk), aga ka olukordi A:_..., kui mitteterminaalne A esineb kohe pärast _ V(e-s juba sisalduvates olukordades).

Lõpuks oleme valmis defineerima LR(0) grammatika. Olgu u virna sisu LR-i sõelumise ajal ja V(u) LR(0) olukordade hulk, mis on kooskõlas u-ga. Kui V(u) sisaldab olukorda kujul A:x_ (terminalide ja mitteterminalide x-jada), siis u kuulub L(A:x) ja x konvolutsioon A-ks on lubatud Kui V(u ) sisaldab olukorda A:..._a... (a-terminal), siis on nihe lubatud. Väidetavalt eksisteerib nihke-konvolutsiooni konflikt, kui sama stringi u jaoks on lubatud nii nihe kui ka konvolutsioon. Konvolutsiooni ja redutseerimise konflikt on väidetavalt olemas, kui on lubatud konvolutsioonid erinevate reeglite järgi.

Grammatikat nimetatakse LR(0)-ks, kui LR-i järeldamisel ei esine nihke-vähendamise või voltimise-vähendamise konflikte kõigi pinu olekute puhul.

1.2.1.2 LR(k) - grammatika

LR(0) parsimisel nihutamise ja voltimise vahel otsustamiseks kasutatakse ainult virna olekut. LR(k) parsimine võtab arvesse ka sisendahela nägemata osa (nn eelahela) esimest k märki. Meetodi põhjendamiseks tuleks hoolikalt korrata eelmise lõigu põhjendusi, tehes määratlustes muudatusi.

Lisame reeglite vasakpoolsesse konteksti ka eelahela. Kui õige väljund kasutab väljundit wAu: wvu, siis paar wv,FIRSTk(u) kuulub Lk(A:v) ja paar w,FIRSTk(u) Lk(A). Vasakpoolsete kontekstide komplekti, nagu LR(0) puhul, saab arvutada vasakpoolse ahela induktsiooni abil. Nimetagem LR(k)-situatsiooni paariks: grammatikareegel, millel on märgitud asukoht ja kuni k pikkuste edenemisahel. Eraldame reegli eelahelast vertikaalse joonega.

Me ütleme, et ahel x on kooskõlas olukorraga A:b_c|t, kui on olemas LR-väljund: x_yz = ab_yz:: abc_z:: aA_z:: S_ ja FIRSTk(z) = t. Olekute hulga Vk induktiivse arvutamise reeglid on järgmised:

Vk(e) sisaldab olukordi S:_a|e kõigi reeglite S:a jaoks, kus S on algusmärk. Iga olukorra A:_Ba|u jaoks Vk(e), iga reegli B:b ja FIRSTk(au-sse kuuluva ahela x) jaoks on vaja Vk(e)-le lisada olukord B:_b|x.

Kui Vк(w) sisaldab olukorda A:b_cd|u, siis olukord A:bc_d|u kuulub Vk(wc) alla. Iga olukorra A:b_Cd|u jaoks Vk(wc), iga reegli C:f ja FIRSTk(du) ahela x jaoks on vaja Vk(wc) lisada olukord C:_f|x.

Nihke-konvolutsiooni probleemi lahendamiseks kasutame konstrueeritud LR(k) olekute komplekte. Olgu u virna sisu ja x ülesahel. Ilmselgelt saab konvolutsiooni reegli A:b järgi teostada, kui Vk(u) sisaldab olukorda A:b_|x. Kui grammatika sisaldab e-reegleid, on vaja hoolt otsustada, kas nihe on lubatud. Olukorras A:b_c|t (c ei ole tühi) on nihe võimalik, kui c algab terminalist ja x kuulub FIRSTk(ct) alla. Mitteametlikult öeldes saate reegli parema poole vasakpoolseima sümboli virnasse lükata, valmistades ette järgneva keerdumise. Kui c algab mitteterminaaliga (olukord näeb välja nagu A:b_Cd|t), on sümboli virnale surumine C-ks konvolutsiooni ettevalmistamiseks võimalik ainult siis, kui C ei genereeri tühja ahelat. Näiteks olekus V(e)= S:_A|e; A:_AaAb|e,a, A:_|e,a pole lubatud nihkeid, kuna Terminaalsete ahelate tuletamisel A-st on mingil etapil vaja rakendada reeglit A:e mitte-terminalile A, mis asub ahela vasakus otsas.

Defineerime hulga FIRSTk(x) kõigist elementidest koosneva hulga EFFk(x), mille tuletamisel x vasakpoolses otsas olevat mitteterminaali (kui see on olemas) ei asendata tühja ahelaga. Nendes tingimustes on nihe lubatud, kui hulgas Vk(u) on olukord A:b_c|t, c ei ole tühi ja x kuulub EFFk(ct) hulka.

Grammatikat nimetatakse LR(k)-grammatikaks, kui ükski LR(k) olek ei sisalda kahte olukorda A:b_|u ja B:c_d|v, nii et u kuulub EFFk(dv) hulka. Selline paar vastab fold-reduce konfliktile, kui d on tühi, ja shift-fold konfliktile, kui d ei ole tühi.

Praktikas LR(k) grammatikaid k>1 puhul ei kasutata. Sellel on kaks põhjust. Esiteks: väga suur hulk LR(k) olekuid. Teiseks: iga LR(k)-grammatikaga määratletud keele jaoks on olemas LR(1)-grammatika; Lisaks on iga deterministliku KS keele jaoks olemas LR(1) grammatika.

LR(1) olekute arv praktiliselt huvitavad grammatikad on ka päris suur. Sellistel grammatikatel on harva LR(0) omadus. Praktikas kasutatakse sagedamini LR(0) ja LR(1) vahepealset meetodit, tuntud kui LALR(1).

1.2.2 LALR(1) - grammatika

Need kaks meetodit põhinevad samal ideel. Koostame grammatika kanooniliste LR(0)-olekute komplekti. Kui see komplekt ei sisalda konflikte, saab kasutada LR(0) parserit. Vastasel juhul püüame tekkinud konflikte lahendada ühetähelise edasiliikumise ahelaga. Teisisõnu, proovime ehitada LR(1) parseri paljude LR(0) olekutega.

LALR(1) meetod (Look Ahead) on järgmine. Tutvustame LR(1)-situatsioonide hulgal ekvivalentsusseost: kahte olukorda loeme samaväärseteks, kui need erinevad ainult oma juhtahelate poolest. Näiteks olukorrad A:Aa_Ab|e ja A:Aa_Ab|a on samaväärsed. Koostame LR(1) olekute kanoonilise hulga ja ühendame samaväärsete olukordade hulgast koosnevad olekud.

Kui saadud olekute kogum ei sisalda LR(1) konflikte ja võimaldab seetõttu ehitada LR(1) parseri, siis öeldakse, et grammatika omab LALR(1) omadust.

2. Tõlkija arendamine

2.1 Nõuete analüüs

Selles kursusetöö on vaja välja töötada tõlgi vormis õppetõlk vastava formaalse grammatikaga määratletud keelest. Tõlgi väljatöötamisel on neli peamist etappi:

Leksikaalanalüsaatori projekteerimine;

Müügiautomaadi disain;

Parseri tarkvara juurutamine;

Tõlkemooduli väljatöötamine.

Arendus toimub Windows XP operatsioonisüsteemi abil personaalarvuti IBM PC protsessoriga Intel Pentium IV.

Tarkvaraarenduse trendidest lähtuvalt valiti õppetõlgi keskkonda juurutamiseks programmeerimiskeel C# Visual Studio 2010.

2.2 Disain

2.1.1 Leksikaalanalüsaatori projekteerimine

Leksikaalne analüüs hõlmab tõlgitud (allika)programmi skaneerimist ja lähteteksti lauseid moodustavate lekseemide äratundmist. Märgid hõlmavad eelkõige märksõnu, operatsioonimärke, identifikaatoreid, konstante, erimärke jne.

Leksikaalse analüsaatori (skanneri) töö tulemuseks on märkide jada, kus iga märk on tavaliselt esindatud mingi kindla pikkusega koodiga (näiteks täisarv), samuti genereeritakse teateid süntaktiliste (leksikaalsete) vigade kohta. , kui mõni. Kui märgiks on näiteks märksõna, siis selle kood annab kogu vajaliku info. Näiteks identifikaatori puhul on lisaks nõutav ka tuvastatud identifikaatori nimetus, mis tavaliselt fikseeritakse identifikaatorite tabelis, mis on korrastatud reeglina loendite abil. Sarnast tabelit on vaja konstantide jaoks.

Lekseemi saab kirjeldada kahe peamise tunnusega. Üks neist on lekseemi kuulumine teatud klassi (muutujad, konstandid, toimingud jne) Teine atribuut määrab konkreetne element sellest klassist.

Sümbolitabeli konkreetne vorm (andmestruktuur) ei oma lekseri ega analüüsija jaoks tähtsust. Mõlemad peavad pakkuma ainult võimalust hankida indeks, mis identifitseerib unikaalselt näiteks antud muutuja, ja tagastama indeksi väärtuse, et täiendada sümbolitabelis oleva muutuja nime kohta teavet.

ID-tabeli vaatamine täidab kahte peamist funktsiooni:

a) muutujate kirjelduste töötlemisel uue nime registreerimine tabelisse;

b) varem tabelisse kantud nime otsimine.

See võimaldab tuvastada ekslikke olukordi, nagu muutuja mitu kirjeldust ja kirjeldamata muutuja olemasolu.

Leksikaalanalüsaatori väljatöötamine seisneb osaliselt erinevate automaatide modelleerimises identifikaatorite, konstantide, reserveeritud sõnad jne Kui märgid erinevad tüübid alustage sama märgi või sama tähemärkide jadaga, võib osutuda vajalikuks nende äratundmine kombineerida.

Leksikaalanalüsaatorit käivitades jagame oma programmi märkideks, misjärel iga märk läbib pikkuse kontrolli (märk ei tohi olla pikem kui 11 tähemärki). Pärast selle etapi edukat läbimist kontrollime märkide õiget asukohta (märksõnad var, begin, end, for, to, do, end_for). Seejärel analüüsime muutujate lekseeme – nende kirjelduses ei tohiks olla numbreid ja neid ei tohiks korrata. Viimases etapis kontrollime lekseemide (märksõnad, tundmatud identifikaatorid) õiget kirjapilti. Kui vähemalt üks kontrollimistest ebaõnnestub, prindib leksikaalanalüsaator veateate.

Leksikaalanalüsaatori programmi diagramm on näidatud B lisas joonisel B.1.

2.2.2 Automaadi projekteerimine

Määratleme järgmise grammatika:

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

kus Vt on lõppsümbolite hulk, Va on mitteterminaalsete sümbolite hulk, I on grammatika algseisund, R on grammatikareeglite kogum.

Selle grammatika jaoks määratleme terminaalsete ja mitteterminaalsete sümbolite komplektid:

Koostame oma grammatika G reeglid ja esitame need tabelis 1.

Tabel 1 – grammatikareeglid

Reegel nr.	Reegli vasak pool	Reegli parem pool








		f ID = EX t EX d LE n;













Tabeli 1 jätk.
Reegel nr.	Reegli vasak pool	Reegli parem pool

Lekseemide tähistused, lekseemide tõlkimine koodidesse ja grammatikatähistuste loetelu on toodud vastavalt tabelites 2, 3, 4.

Tabel 2 - Lekseemide tähistused

	Märgi tähistus
	märksõna "algus" (toimingute kirjelduse algus)
	märksõna "lõpp" (tegevuse lõpu kirjeldus)
	märksõna "var" (muutuja kirjeldus)
	märksõna "loe" (andmesisestusoperaator)
	märksõna "kirjutamine" (andmeväljundi operaator)
	märksõna "for" (silmuslause)
	märksõna "kuni"
	märksõna "teha"
	märksõna "end_case" (tsükli lõpu lause)
	muutuja tüüp "täisarv"
	lisamise operatsioon
	lahutamistehte
	korrutamisoperatsioon
	eraldusmärk ":"
	eraldaja ";"
	eraldaja "("
	eraldaja ")"
	eraldusmärk ","
	Märgi tähistus
	eraldaja "="

Tabel 3 – Lekseemide tõlkimine koodidesse












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

Tabel 4 – grammatika sümbolite loend

Määramine	Selgitus
	Programm
	Arvutuste kirjeldus
	Muutujate kirjeldus
	Muutujate loend
	Operaator
	Ülesandmine
	Väljendus
	Alamväljend
	Binaarsed operatsioonid
	Unaarsed operatsioonid
	Ülesannete nimekiri
	Identifikaator
	Püsiv

Ehitame üles deterministliku alt-üles tuvastaja.

Mõelge järgmistele seostele, et konstrueerida deterministlik alt-üles tunnustaja:

a) Kui rühmas B on selline sümbol, et mõni grammatika reegel sisaldab ahelat AB ja on sümbol xFIRST"(B), siis eeldame, et seosed x PÄRAST A on määratud sümbolite x ja A vahel.

b) Kui antud grammatikas on reegel B -> bAb A, BV a, b, siis on A ja x vahel määratud seos A COVER x.

Kogu meie grammatika jääb samaks, see tähendab:

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

ja grammatika G reeglid on toodud tabelis 5.

Tabel 5 – grammatikareeglid

Reegel nr.	Reegli vasak pool	Reegli parem pool








		f ID = EX t EX d LE n;?














Tabeli 5 jätk.
Reegel nr.	Reegli vasak pool	Reegli parem pool

Kuhu? - marker keti otsa jaoks.

Määratleme mõned juhtumid:

a) ID koosneb paljudest tähtedest Ladina tähestik, see tähendab, et 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 konstant koosneb arvudest, st eeldame, et k = (0,1,2,3,4,5,6,7,8,9)

Selleks, et meie grammatika oleks segase prioriteediga strateegia, peavad olema täidetud järgmised tingimused:

a) E-reeglite puudumine

b) Kas on reegleid, mille alusel x PÄRAST A? A VERT x = ?

c) A -> bYg

ja see on vajalik, et PEALE x? B VERT x = ?

see tähendab, et grammatikas täidetakse need IN AFTER x või A AFTER x, kus x on ahela b predikaatsümbol.

a) FIRST"(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)

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

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

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

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

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

FIRST" (UO) = (UO,-)

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

FIRST" (CO) = FIRST" (k) = (k) FIRST" (e) =( e)

ESIMENE" (b) = (b)

FIRST" (e) =( e)

FIRST" (v) =( v)

FIRST" (w) =( w)

FIRST" (r) = (r)

FIRST" (i) =( i)

FIRST" (f) = (f)

FIRST" (d) = (d)

FIRST" (n) =( n)

FIRST" (c) = (c)

FIRST" (+) =( +)

FIRST" (*) =( *)

ESIMENE" (-) =( -)

FIRST" (,) =(,)

ESIMENE" (;) =(;)

ESIMENE" (:) =(:)

ESIMENE" (=) = ( = )

ESIMENE" (() =( ()

ESIMESE" ()) =() )

FIRST" (u) = (u)

FIRST" (k) = (k)

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

JÄRGMINE ` (DE) = (?)? FIRST"(AL)= (?, b, e)

JÄRGMINE ` (LV) = (?)? ESIMESE"(:)= (?,:)

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

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

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

JÄRGMINE ` (BO) = (?)? FIRST"(SB)= (?, (,), OP, BO)

JÄRGMINE ` (UO) = (?)? FIRST"(SB)= (?, (,), OP, BO)

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

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

TRACE `(ID)= (?)? JÄRGMINE" (OP) ? ESIMESE" (=) =(?,;,), d, t, +, -, *, =)

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

JÄRGMINE` (b) =(?)?ESIMESE"(LE)= (?, u, =,;)

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

JÄRGMINE` (v) =(?)?ESIMESE"(LV)= (?, u)

JÄRGMINE` (w) =(?)?ESIMESE"(()= (?, ()

JÄRGMINE` (r) =(?)? ESIMESE"(() = (?, ()

JÄRGMINE` (i) =(?)?ESIMESE"(;)= (?,; )

JÄRGMINE` (f) =(?)?ESIMESE"(ID) = (?, u)

JÄRGMINE` (d) =(?)?ESIMESE"(LE)= (?, u, =,;)

JÄRGMINE` (n) =(?)? ESIMESE"(i) = (?, i )

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

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

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

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

JÄRGMINE` (:) =(?)?ESIMESE"(i)= (?, i )

JÄRGMINE` (=) = (?)? ESIMESE"(EX) = (? (,), u, k, +, -, *)

JÄRGMINE ` (() =(?)? ESIMESE"(DE)= (?, v,:, i,;)

TRACE` ()) =(?)? ESIMESE"(;) = (?,; )

TRACE ` (,) =(?)? FIRST"(LV) = (?, u)

TRACE `(u) =(?)? FIRST" (ID)= ( u, ?)

TRACE `(k) =(?)? ESIMESE (CO)= (?, k)

c) PG ->DE AL

AL PÄRAST DE = (b,e) PÄRAST DE = ((b DE), (e DE) )

e PÄRAST LE = ((e LE))

LE PÄRAST b = ((,), =,;, f, t, d, n, w, r) PÄRAST b = (((b), ()b), (=b), (;b), ( f b), (t b), (d b), (n b), (w b), (r b))

;PÄRAST i = ((; i))

i PÄRAST: = ( (i:) )

: PÄRAST LV = ( (: LV) )

LV PÄRAST v = ( (ID, v) )

LV PÄRAST, = ((ID,))

PÄRAST ID = ((,u))

LE PÄRAST EQ = ((,), =,;, f, t, d, n, w, r ) PÄRAST EQ = (((EQ), () EQ), (= EQ), (; EQ), ( f EQ), (t EQ), (d EQ), (n EQ), (w EQ), (r EQ))

LE -> r (DE);

; PÄRAST) = ((;)))

) PÄRAST DE = (((DE))

DE PÄRAST (= (= ((v)), (:)), (i)), (;)), (e)))

(PÄRAST r = (((r))

LE -> w (DE);

; PÄRAST) = ((;)))

) VIIMANE DE = (((DE))

DE PÄRAST (= ((v)), (:)), (i)), (;)), (e)))

(PÄRAST w = (((w))

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

; PÄRAST n = ((;n))

n PÄRAST LE = ( (n, LE))

LE PÄRAST d = ( ((,), =,;, f, t, d, n, w, r)) ? PÄRAST d = (((d), ()d), (;d), (f d), (t d), (d d), (n d), (d d), (r d))

d PÄRAST EX = ((d, EX))

EX PÄRAST t = (BO, -) ? PÄRAST t = ((BO t), (- t))

t PÄRAST EX = ( t EX)

EX AFTER = = ((BO, -) ? PÄRAST = = ((BO =), (- =))

PÄRAST ID = ((= ID))

ID PÄRAST f = ((ID f))

EQ -> ID = EX;

; PÄRAST EX = ((; EX )

EX AFTER = = (BO, -) ? PÄRAST = = ((BO =), (- =))

PÄRAST u = ( (=u))

SB PÄRAST UO = ( (,), OP, BO ) PÄRAST UO = (((UO), (OP UO), (BO UO) )

) PÄRAST EX = ( ()EX) )

EX AFTER (= (BO, -) ? PÄRAST (= ((BO (),), (- ()))

SB->SB BO SB

SB PÄRAST BO = ((,), OP, BO) PÄRAST BO = (((BO), ()BO), (OP BO), (BO BO))

BO PÄRAST SB = (+,*,-) PÄRAST SB = ((+SB), (*SB), (-SB))

ID PÄRAST u = ((u, u))

G) PG ->DE AL

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

e KOGU AL = e KOGUJÄlg"(AL)= ((eb), (e?))

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

LV KOGUMINE LV = LV COLLECTION TRAIL" (LV) = ((LV:), (LV?))

ID-KOGU LV = ID-KOGU" (LV) = ((ID:), (ID ?))

; AHENDA LE =; KOGURAJA" (LE) = ((; e), (;?), (; n))

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

; AHENDA LE =; KOGURAJA" (LE) = ((; e), (;?), (; n))

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

EQ -> ID = EX;

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

SB KOGU EX = SB KATTEJÄLG" (EX) = ((SB t), (SB?), (SB d), (SB)), (SB;), (SB(), (SB=), (SBf ), (SBn), (SBw), (SBr) )

) KOGU SB = SB KOGUJÄLG" (SB) = (() t), ()?), () d), ())), ();))

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

SB->SB BO SB

SB KOGU SB = SB KATTEJÄLG" (SB) = ((SB, t), (SBd), (SB;). (SB)), (SB+), (SB-), (SB*), (SB? ) }

KOGU UO = - KOGURAJA" (UO) = ( (-?), (--))

KOGU BO = + KOGURAJA" (BO) = ((++), (+?), (+*), (+-))

* KOGU BO = * KOGURAJA" (BO) = ((*+), (*?), (**), (*-))

KOGU BO = - KOGURAJA" (BO) = ((-+), (-?), (-*), (--))

ID KOGUMINE OP = ID KATTEJÄLG" (OP) = ((ID+), (ID?), (ID*), (ID-))

KAATE OP = KAATTE JÄLG" (OP) = ((CO+), (CO?), (CO*), (CO-), (CO;), (COd), (COt), (CO)))

ID-KOGU ID = ID-KOGU RAJA" (ID) = ((ID)), (ID ?), (ID k), (ID+), (ID-), (ID*), (ID=), (IDt) , (IDd)))

u KOGU ID = l KOGURAJA" (ID) = ((u)), (u?), (uk), (u+), (u-), (u*), (u=), (ut), (ud)))

KAATE CO = KAATTE JÄLG" (CO) = (CO+), (CO?), (CO*), (CO-), (CO;), (COd), (COt), (CO)))

k KOGU CO = k KOGUJÄLG" (CO) = (k+), (k?), (k*), (k-), (k;), (kd), (kt), (k)))

Reeglite kokkuvarisemisel tuvastati üks konfliktsituatsioon

OP ->ID ja ID -> u ID

Sisestame ID1 -> ID, seetõttu kirjutame ümber reegli ID1 -> u ID

Seetõttu teostame konvolutsioonitehteid.

ID1 KOGU ID = ID1 KOGURAJA" (ID) = ((ID1)), (ID1 ?), (ID1 k), (ID1+), (ID1-), (ID1*), (ID1=), (ID1t) , (ID1d)))

Iga paari (x, A) jaoks? x PÄRAST A konstrueerime üleminekufunktsiooni, mis määrab ülekandetoimingu??(S 0 , x, A) = (S 0 , A)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

? (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) = (SO, n;)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Iga paari (x, A) jaoks? Ja CONVERT x loome üleminekufunktsiooni, mis määrab konvolutsiooni toimingu?? * (S 0 , x, bA) = (S 0 , B), kus 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 Parseri tarkvara juurutamine

Süntaktiline analüsaator (parser) loeb leksikaalanalüsaatori loodud lekseemifaili, teostab grammatilist sõelumist ja väljastab selle kohta teateid. süntaksivead võimaluse korral ja loob algsaate salvestamise vahevormi. Parseri väljatöötamise aluseks on vastava ajakirjamasina projekteerimine ja teostus.

Alt-üles sõelumiseks deterministliku alt-üles parseri jaoks pärast selle redutseerimist õiget tüüpi Funktsioonide AFTER ja COVER kasutamine on vajalik kauplusmasina kujundamiseks koos kõigi üleminekufunktsiooni üleminekute üksikasjaliku kirjeldusega.

Automaadi arendamisel ehitasime parseri aluseks olevad üleminekufunktsioonid. Kõik üleminekufunktsioonid võib jagada kahte tüüpi:

Ajakirjamasina töötsükkel ilma sisestussümbolit lugemata (tühitsükkel);

Ajakirjamasina töötakt sisestussümboli lugemisega.

Leksikaalanalüsaatori rakendamisel jagasime programmi lekseemideks ja kirjutasime need nimekirja. Seejärel töötleme seda loendit parseris. Sisendisse saadame oma programmi (nimekirja), algsümboli (PG) ja poe masina alumise markeri (h0), misjärel valitakse soovitud üleminekufunktsioon ja tehakse rekursiivne kõne.

Parser programmi diagramm on näidatud B lisas joonisel B.2.

2.2.4 Tõlkemooduli väljatöötamine

Tõlgendusmooduli kui algprogrammi vahevormi väljatöötamisel Kõige sagedamini kasutatakse tähistusvormi postfix, mis teeb tõlgitud programmi täitmise (tõlgendamise) protsessi rakendamise üsna lihtsaks.

Vaatleme väljendite kirjutamise postfiksi vormi moodustamise ja teostamise põhiprintsiipe.

Põhireeglid infiksi avaldise teisendamiseks postfiksiks on järgmised.

Loetud operandid lisatakse postfixi tähistusele ja toimingud kirjutatakse virna.

Kui virna ülaosas oleval toimingul on kõrgem (või võrdne) prioriteet kui praegu loetaval toimingul, lisatakse virna tehing postfixi kirjesse ja praegune toiming lükatakse virna. Vastasel juhul (madalama prioriteediga) lükatakse virna ainult praegune toiming.

Loetud avasulg lükatakse virnale.

Pärast sulgemisklambri lugemist hüppatakse kõik toimingud kuni esimese avamisklambrini virnast välja ja lisatakse postfixi kirjesse, misjärel visatakse ära nii avamis- kui sulgemisklambrid, s.t. ei paigutata postfix-kirjele ega virnale.

Pärast kogu avaldise lugemist lisatakse ülejäänud virna toimingud postfixi kirjesse.

Avaldise postfiksi tähistus võimaldab seda arvutada järgmiselt.

Kui märk on operand, kirjutatakse see virna. Kui märgiks on tehe, siis sooritatakse määratud toiming viimaste virna kirjutatud elementidega (viimane element) ja need elemendid (element) asendatakse virnas toimingu tulemusega.

Kui leksikaalne ja süntaktiline analüüs on edukalt lõpule viidud, jätkame tõlgendamist. Kõigepealt teeme sõnadest laused, seejärel tõlgime väljendid postfiksi tähistusse ja arvutame.

Tõlgi tööskeem on näidatud B lisas joonisel B.3.

2.3 Kodeerimine

Programm realiseeritakse keskkonnas C# keeles Visuaalne programmeerimine Stuudio 2010. Programmi tekst on toodud lisas A.

Programm sisaldab viit klassi. Kasutajaliides on realiseeritud MainForn klassi abil. Klassi LexAnalysis kasutades realiseeritakse leksikaalse analüüsi moodul, SynAnalysis on süntaktilise analüüsi moodul, Interpreter on tõlgendusmoodul, ProgramisciJakPolska on abiklass väljendite tõlkimiseks poola pöördmärgistusse (postfix).

Programmis rakendatavate protseduuride ja funktsioonide eesmärk on kirjeldatud tabelites 6,7,8.

Tabel 6 – Leksikaalse analüüsi protseduuride eesmärk ja funktsioonid

Sarnased dokumendid

Tõlkija kui programm või tehniline vahend, mis tõlgib programmi. Leksikaalanalüsaatori ehituse põhijoonte käsitlemine. Sissejuhatus kõrgetasemelise keele piiratud alamhulga tõlkija arendamise etappidesse.

kursusetöö, lisatud 06.08.2013

Õppekeele leksikaalsete ja süntaktiliste analüsaatorite kujundamine. Reeglid loogiliste avaldiste teisendamiseks POLYZ-iks. Kolmkõlaliste moodustamine, nende loetelu optimeerimine. Programmi loogiline ülesehitus. Tõlkija-tõlgi moodulite testimine.

kursusetöö, lisatud 28.05.2013

üldised omadused ja C-Sharp programmeerimiskeele võimaluste hindamine, selle sarnasused ja erinevused C++ ja Javaga. Selle programmeerimiskeele abil leksikaalse ja süntaktilise analüsaatori väljatöötamine. Parsimistabelite koostamine.

kursusetöö, lisatud 11.06.2010

Kahest osast koosneva analüsaatoriprogrammi kujundamine: leksikaalanalüsaator, mis jagab programmi lähteteksti lekseemideks ja täidab nimetabeli; parser, mis kontrollib teksti vastavust antud grammatikale.

kursusetöö, lisatud 14.06.2010

Programmi kirjutamine, mis teostab sisendprogrammeerimiskeele leksikaalset ja süntaktilist analüüsi, genereerib lekseemide tabeli, mis näitab nende tüüpe ja väärtusi ning koostab ka süntaksipuu; sisestuskeele tekst sisestatakse klaviatuurilt.

kursusetöö, lisatud 23.02.2012

C++ keelt kasutava C-keele tõlkija arendamise ja osalise juurutamise metoodika, mis jagab algse märgiahela minimaalseteks jagamatuteks keelekonstruktsioonideks, lähtudes keele sõnavarast. Programmi toimimise analüüs.

kursusetöö, lisatud 19.03.2012

Struktuur, klassifikatsioon ja nõuded kompilaatori rakendamisele. C++ keele kompilaatori analüüsiosa kavandamine ja juurutamine. Leksikaalse analüüsi rakendamise meetodid. Parseri töö algoritm. Tarkvara juurutamise põhimõtted.

kursusetöö, lisatud 26.01.2013

Tõlkija loomine, mis töötleb programmi koodi Pascalis ja kasutades samaväärseid operaatoreid, genereerib programmi C keeles. Leksikaalanalüsaatori välise spetsifikatsiooni ja töö omadused. Programmi struktuur, tulemuste kuvamine ekraanil.

kursusetöö, lisatud 07.02.2011

Grammatilise analüüsi meetodid. Haridusliku tõlgi struktuuri väljatöötamine lähtuvalt põhikeel Object Pascal programmeerimine objektorienteeritud visuaalses programmeerimiskeskkonnas Borland DELPHI 6.0, kasutades operatsioonisüsteemi Windows XP.

kursusetöö, lisatud 12.05.2013

Tarkvara juurutamine töölauarakendus kasutades C# programmeerimiskeelt. Kasutajaliidese disain ja struktuur, nõuded sellele ja funktsionaalsuse hindamine. Kasutusjuhendi väljatöötamine ja selle kasutamine.

Tõlkija (inglise tõlkija – tõlkija) on tõlkeprogramm. See teisendab ühes kõrgetasemelises keeles kirjutatud programmi masinakäskudest koosnevaks programmiks. Tõlkija tavaliselt ka diagnoosib vigu, koostab identifikaatorite sõnastikke, toodab printimiseks programmitekste jne. Keelt, milles sisendprogrammi esitatakse, nimetatakse lähtekeeleks ja programmi ennast lähtekoodiks. Väljundkeelt nimetatakse sihtkeeleks või objektikoodiks.

Üldiselt ei kehti tõlke mõiste mitte ainult programmeerimiskeelte, vaid ka muude keelte kohta - nii ametlike arvutikeelte (nagu märgistuskeeled nagu HTML) kui ka loomulike (vene, inglise jne).

Tõlkijate tüübid

Dialoog. Võimaldab ajajagamise režiimis kasutada programmeerimiskeelt.

Süntaktiliselt orienteeritud (süntaktiliselt juhitud). Saab sisendiks keele ja teksti süntaksi ja semantika kirjelduse kirjeldatud keeles, mis tõlgitakse vastavalt antud kirjeldusele.

Üksikpääs. Moodustab objektmooduli lähteprogrammi ühes järjestikuses vaatamises.

Mitmikpass. Moodustab objektmooduli mitme lähteprogrammi vaate kaudu.

Optimeerimine. Teostab loodud objektimoodulis koodi optimeerimise.

Test. Assamblee keele makrokäskude komplekt, mis võimaldab seadistada montaažikeeles kirjutatud programmides erinevaid silumisprotseduure.

Tagasi. Masinkoodis oleva programmi jaoks toodab see samaväärse programmi mis tahes programmeerimiskeeles (vt: disassembler, dekompilaator).

Tõlkijaid rakendatakse koostajate või tõlkijatena. Töö tegemise mõttes on koostaja ja tõlk oluliselt erinevad.

Koostaja (inglise kompilaator – koostaja, koguja) loeb kogu programmi läbi, tõlgib selle ja loob programmist masinkeeles täisversiooni, mis seejärel käivitatakse. Kompilaatori sisendinformatsioon (lähtekood) on algoritmi või programmi kirjeldus probleemipõhises keeles ja kompilaatori väljund on algoritmi samaväärne kirjeldus masinorienteeritud keeles (objektkood).

Kompilaatorite tüübid

Vektoriseerimine. Tõlgib vektorprotsessoriga arvutites lähtekoodi masinkoodiks.

Paindlik. Mõeldud modulaarselt, juhitud tabelite abil ja programmeeritud kõrgetasemelises keeles või rakendatud kompilaatorite kompilaatori abil.

Dialoog. Vaata: dialoogi tõlkija.

Kasvav. Taasedastab programmi fragmente ja selle täiendusi ilma kogu programmi uuesti kompileerimata.

Tõlgendav (samm-sammult). Teostab järjestikku lähteprogrammi iga üksiku avalduse (käsu) sõltumatu kompileerimise.

Koostajate koostaja. Tõlkija, mis aktsepteerib programmeerimiskeele ametlikku kirjeldust ja genereerib selle keele jaoks kompilaatori.

Silumine. Kõrvaldab üksikud liigid süntaksivead.

Resident. Asub pidevalt RAM-is ja on juurdepääsetav taaskasuta palju ülesandeid.

Ise koostav. Kirjutatud samas keeles, millest ülekannet tehakse.

Universaalne. Põhineb sisestuskeele süntaksi ja semantika formaalsel kirjeldusel. Komponendid sellised kompilaatorid on: kernel, süntaktilised ja semantilised laadijad.

Minu saladus

Distsipliini eesmärgid ja eesmärgid

Põhimõisted ja määratlused

Programmeerimiskeelte ja tõlkijate üldised omadused

Üldistatud tõlkija struktuur

Tõlkijaplokkide interaktsiooni võimalused

Tõlkijaplokkide interaktsiooni mitmekäiguline korraldamine

Tõlkijaplokkide vahelise suhtluse ühekäiguline korraldamine

Tõlkijaplokkide kombineeritud interaktsioonid

Testi küsimused ja ülesanded

Tõlkijate tüübid

Rakendused

Saada oma head tööd teadmistebaasi on lihtne. Kasutage allolevat vormi

1.1 Ülalt-alla analüüs

1.2 Alt-üles analüüs

1.2.1 LR(k) - grammatika

1.2.1.1 LR(0) - grammatika

1.2.2 LALR(1) - grammatika

2. Tõlkija arendamine

2.1 Nõuete analüüs

2.2 Disain

2.2.1 Leksikaalanalüsaatori projekteerimine

2.2.4 Parseri tarkvara juurutamine

2.3 Kodeerimine

2.4 Testimine

Järeldus

Kasutatud allikate loetelu

Lisa A. Tõlkeprogrammi teksti loetlemine

Lisa B. Katsetulemused

Lisa B. Tõlkija programmi skeem

Sissejuhatus

Programmeerimiskeeled erinevad üksteisest üsna eesmärgi, struktuuri, semantilise keerukuse ja rakendusmeetodite poolest. See paneb konkreetsete tõlkijate arendamisele oma eripärad.

Isegi sama keelt saab rakendada mitmel viisil. See on tingitud asjaolust, et formaalsete grammatikate teooria võimaldab samade lausete parsimiseks kasutada erinevaid meetodeid. Vastavalt sellele saavad tõlkijad algsest lähtetekstist erineval viisil saada sama tulemuse (objektprogrammi).

Samal ajal on kõigil programmeerimiskeeltel mitmeid ühiseid omadusi ja parameetreid. See ühisosa määrab ka tõlkijate korraldamise põhimõtted, mis on kõigi keelte jaoks sarnased.

Programmeerimiskeeled on loodud programmeerimise hõlbustamiseks. Seetõttu on nende operaatorid ja andmestruktuurid võimsamad kui masinkeelte omad.

Programmide nähtavuse suurendamiseks kasutatakse numbrikoodide asemel keelekonstruktsioonide sümboolseid või graafilisi esitusi, mis on inimese taju jaoks mugavamad.

Iga keele jaoks on see määratletud:

- palju sümboleid, millega saab kirjutada õigeid programme (tähestik), põhielemente,

- palju õigeid programme (süntaks),

- iga õige programmi "tähendus" (semantika).

Sõltumata keele spetsiifikast võib iga tõlkijat pidada funktsionaalseks muunduriks F, mis pakub ainulaadset vastendust X-st Y-le, kus X on lähtekeeles programm, Y on programm väljundkeeles. Seetõttu saab tõlkeprotsessi ennast formaalselt esitada üsna lihtsalt ja selgelt: Y = F(X).

Formaalselt on iga õige programm X mingi tähestiku A sümbolite ahel, mis on teisendatud sellele vastavaks ahelaks Y, mis koosneb tähestiku B sümbolitest.

Programmeerimiskeel, nagu iga keeruline süsteem, on määratletud mõistete hierarhia kaudu, mis määratleb selle elementide vahelised seosed. Need mõisted on omavahel seotud süntaktiliste reeglite kohaselt. Igal nende reeglite järgi ehitatud programmil on vastav hierarhiline struktuur.

Sellega seoses saab kõigi keelte ja nende programmide puhul lisaks eristada järgmisi ühiseid jooni: iga keel peab sisaldama reegleid, mis võimaldavad genereerida sellele keelele vastavaid programme või tuvastada kirjalike programmide ja antud keele vastavust.

Selle kursusetöö eesmärgiks on etteantud lihtsustatud tõlgi väljatöötamine teksti keel kõrge tase.

1. Grammatikaanalüüsi meetodid

Vaatame grammatilise parsimise põhimeetodeid.

1.1 Ülalt-alla analüüs

Ülevalt alla sõelumisel liiguvad vahepealsed juhtmed piki puud juurest lehtedeni. Sel juhul tehakse ahelat vasakult paremale vaadates loomulikult vasakukäelised järeldused. Deterministliku parsimise puhul on probleem selles, millist reeglit rakendada vasakpoolseima mitteterminali lahendamiseks.

1.1.1 LL(k) - keeled ja grammatika

Kaaluge järelduspuud ahela vasakpoolse väljundi saamise protsessis. Järeldusprotsessi vaheahel koosneb klemmide ahelast w, kõige vasakpoolsemast mitte-otsast A, alajäreldatavast osast x:

-S--

/ \

/ -A-x-\

/ | \

-w---u----

Joonis 1

Määratleme kaks ahelate komplekti:

a) FIRST(x) on x-ist tuletatud terminali stringide kogum, mis on lühendatud k märgini.

b) FOLLOW(A) - k-märgini lühendatud terminalahelate komplekt, mis võib väljundahelates kohe järgneda A-le.

Grammatikal on omadus LL(k), kui kahe vasakpoolsete järelduste ahela olemasolust:

S:: vaha: wzx:: wu

S:: vaha: wtx:: wv

tingimusest FIRST(u)=FIRST(v) järgneb z=t.

Juhul k=1, piisab A jaoks reegli valimiseks ainult mitteterminali A ja a – ahela u esimese tähe teadmisest:

- reegel A:x tuleks valida, kui a sisaldub jaotises FIRST(x),

- reegel A:e tuleks valida, kui a sisaldub järgus FOLLOW(A).

Omadus LL(k) seab grammatikale üsna tugevad piirangud. Näiteks LL(2) grammatika S: aS | a ei oma LL(1) omadust, sest FIRST(aS)=FIRST(a)=a. Sel juhul saate k väärtust vähendada "faktoriseerimise" abil (võte teguri sulgudest välja):

S: aA

A: S | e

1.1.2 Rekursiivne laskumise meetod

Rekursiivne laskumismeetod on suunatud nendele juhtudele, kui kompilaator on programmeeritud mõnes kõrgetasemelises keeles, kui rekursiivsete protseduuride kasutamine on lubatud.

Rekursiivse laskumise põhiidee seisneb selles, et grammatika igal mitteterminalil on vastav protseduur, mis tunneb ära mis tahes selle mitteterminali genereeritud ahela. Need protseduurid helistavad vajadusel üksteisele.

Mis tahes reegli kood sisaldab toiminguid iga selles sisalduva märgi jaoks parem pool reeglid. Toimingud on paigutatud selles järjekorras, milles sümbolid reeglis esinevad. Pärast viimast toimingut sisaldab kood protseduuri naasmist.

Rekursiivse laskumise kasutamine kõrgetasemelises keeles muudab programmeerimise ja silumise lihtsamaks.

1.2 Alt-üles analüüs

Vaatleme alt-üles parsimist, mille käigus liigutatakse vahepealseid tihvte mööda puud juure poole. Kui loete stringis olevaid märke vasakult paremale, näeb parsipuu välja järgmine:

-S--

/ \

/-x-\