Prevoditelj je ... Vrste prevoditelja. Pretvaranje i emitiranje programa. Prevoditelj: osnovni pojmovi. LL(k) - jezici i gramatike

Za prevođenje s jednog jezika na drugi programi, kao i ljudi, trebaju prevoditelja ili, znanstveno rečeno, prevoditelja.

Prevoditelj: osnovni pojmovi

Takav program kao prevoditelj je lingvistički prikaz izračuna I ->P ->P (i). Interpretator je program koji kao ulaz uzima program P s nekim ulaznim podacima X. Izvršava P na X: I(P, x)=P(x). Postoji jedan prevoditelj koji može sve moguće programe(koji se može prikazati u formalnom sustavu). Ovo je Turingovo vrlo značajno i duboko otkriće. Procesor je interpreter programa u strojnom jeziku. Napišite tumače za jezike visoka razina obično su preskupi, pa se prevode u oblik koji je lakši za tumačenje. Neke vrste prevoditelja imaju vrlo čudna imena. Program prevodi programe asemblerskog jezika u strojni jezik. Kompajler vam omogućuje prevođenje s jezika visoke razine na jezik niže razine. Prevoditelj je program koji uzima program na nekom jeziku S kao ulaz i nakon obrade proizvodi program na jeziku T. Dakle, oba imaju istu semantiku: P->X->Q. Dakle, za bilo koji xP(x)=Q(x). Ako cijeli program prevedete u nešto interpretirano, onda se to zove kompilacija prije izvršenja ili AOT kompilacija. AOT prevoditelji mogu se koristiti dosljedno. Posljednji od njih je vrlo često asembler. Dakle, razmotrite primjer: Izvorni kod -> Kompilator (prevoditelj) -> Asemblerski kod -> Asembler (prevoditelj) -> Strojni kod -> CPU (interpretator). Dinamička ili mrežna kompilacija događa se kada se dio programa prevodi dok se drugi prethodno kompajlirani dijelovi izvršavaju. JIT prevoditelji pamte što su već učinili kako ne bi morali uvijek iznova ponavljati izvorni kod. Oni su čak sposobni izvoditi adaptivnu kompilaciju i rekompilaciju, koja se temelji na ponašanju okoline programa za izvođenje. Mnogi jezici pružaju mogućnost izvršavanja koda tijekom prijevoda, kao i kompajliranja novog koda tijekom izvršavanja programa.

Prijenos: pozornice

Proces prevođenja sastoji se od faza sinteze i analize. Shematski ovaj proces izgleda ovako: Izvorni kod -> Analizator -> Konceptualni prikaz -> Sintesajzer (generator) -> Ciljni kod. To je zbog sljedećih razloga:

- bilo koja druga metoda jednostavno ne odgovara;

Prijevod jednostavno ne radi.

Možete koristiti sljedeće inženjersko rješenje: ako trebate napisati prevoditelje za M izvornih jezika i N ciljnih jezika, trebate napisati samo M+N jednostavni programi(polu-kompilatori), a ne MxN puni (složeni) prevoditelji. U praksi, međutim, konceptualni prikaz rijetko je izražajan i dovoljno snažan da pokrije sve postojeće ciljne i izvorne jezike. Iako su mu se neki korisnici uspjeli približiti. Pravi prevoditelji prolaze kroz mnogo različitih faza. Kada izradite vlastiti prevodilac, ne morate ponavljati sav težak posao koji su programeri već obavili pri stvaranju generatora i pogleda. Možete prevesti svoj jezik izravno u JavaScript ili C i koristiti postojeće C kompajlere i JavaScript motore za ostalo. Također možete koristiti postojeće srednje preglede i virtualne strojeve.

Snimka prevoditelja

Prevoditelj može biti tehnički alat ili program koji koristi tri jezika: izvorni, ciljni, osnovni. Možete ih napisati u obliku slova T, postavljajući izvor s lijeve strane, cilj s desne, a bazu ispod. Ukupno postoje tri vrste kompilatora.

Prevoditelj je samokompilator ako njegov izvorni jezik odgovara osnovnom.
Kompilator se naziva samostalnim ako je ciljni jezik jednak osnovnom jeziku.
Ako su ciljni i osnovni jezici različiti, tada je prevoditelj unakrsni prevodilac.

Zašto je važno razlikovati ove vrste kompilatora? Čak i ako nikada ne izradite stvarno kvalitetan kompilator, dobro je naučiti o tehnologiji njegovog stvaranja, budući da se svi koncepti koji se koriste u tu svrhu koriste posvuda u jezicima za upite baza podataka, u formatiranju teksta, u naprednim računalne arhitekture ah, grafička sučelja, generalizirani problemi optimizacije, strojno prevođenje, kontroleri i virtualni strojevi. Također, ako trebate napisati predprocesore, učitavače, asemblere, programe za ispravljanje pogrešaka ili profilere, morate proći kroz sve iste korake kao i kod pisanja prevoditelja. Također možete naučiti o najboljem načinu pisanja programa, jer razvoj prevoditelja za programski jezik znači bolje razumijevanje svih njegovih dvosmislenosti i suptilnosti. Učenjem općih načela prevođenja možete postati dobar dizajner Jezik. Ali je li to doista važno? Koliko je jezik cool ako se ne može učinkovito implementirati?

tehnologija mjerila

Tehnologija prevoditelja pokriva širok raspon različitih područja računalne znanosti. Uključuje teoriju formalnog jezika, gramatiku, računalnu arhitekturu, raščlanjivanje, izračunljivost, skupove instrukcija, CISC ili RISC, cjevovod, cikluse takta, jezgre itd., kao i kontrolu slijeda, rekurzije, uvjetno izvršenje, funkcionalnu dekompoziciju, iteraciju, modularnost, sinkronizacija, metaprogramiranje, konstante, opseg, predlošci, vrsta izlaza, komentari, prototipovi, tokovi, poštanski sandučići, monade, zamjenski znakovi, nastavci, transakcijska memorija, regularni izrazi, polimorfizam, nasljeđivanje, načini parametara itd. . Također, da biste kreirali kompajler, morate razumjeti apstraktne programske jezike, algoritme i strukture podataka, regularne izraze, grafičke algoritme, dinamičko programiranje.

Dizajn kompilatora. Mogući problemi koji nastaju pri stvaranju pravog prevoditelja

Koji problemi mogu nastati s izvornim jezikom? Je li lako sastaviti? Postoji li predprocesor za ovo? Kako se postupa s vrstama? Koje se grupiranje prolaza kompilatora koristi - jedno ili više prolaza? Željeni stupanj optimizacije također zaslužuje posebnu pozornost. Brz i netočan prijevod programa s malo ili nimalo optimizacije može biti normalan. Međutim, pretjerana optimizacija može usporiti kompajler tijekom izvođenja najbolji kod možda bi se isplatilo.

Stupanj otkrivanja pogreške. Je li potrebno da prevoditelj stane već na prvoj pogrešci? Kada bi trebao prestati? Treba li kompilatoru vjerovati da će ispraviti pogreške?

Potreban set alata

Ako u vašem slučaju izvorni jezik nije premali, tada su generator analizatora i skener neophodni. Postoje i posebni generatori kodova, ali nisu u širokoj upotrebi.

Što se tiče vrste ciljanog koda za generiranje, potrebno je odabrati između čistog, proširenog ili koda virtualnog stroja. Također možete napisati prednji kraj koji stvara popularne srednje poglede kao što su LLVM, JVM, RTL. Također možete prevoditi iz izvornog u izvorni kod u Java Script ili C. Ako govorimo o formatu ciljnog koda, ovdje možete odabrati prijenosni strojni kod, strojni kod memorijske slike, asemblerski jezik.

ponovno ciljanje

Kod korištenja većeg broja generatora bilo bi lijepo imati zajednički ulazni dio. Također iz tog razloga, bolje je imati jedan generator za više ulaznih dijelova.

Komponente prevoditelja

Navodimo glavne funkcionalne komponente prevoditelj koji generira strojni kod ako je izlazni program C program ili virtualni stroj:

- ulazni program ulazi u leksički analizator, ili na drugi način u skener, koji ga pretvara u tok tokena;

- parser (parser) od njih gradi apstraktno sintaksno stablo;

— semantički analizator razlaže semantičke informacije i provjerava ima li grešaka u čvorovima stabla;

- kao rezultat, izgrađen je semantički graf. Ovaj pojam se shvaća kao apstraktno sintaksno stablo s uspostavljenim vezama i dodatnim svojstvima;

- generator srednjeg koda gradi graf toka (torke su grupirane u glavne blokove);

- Optimizator neovisan o stroju provodi lokalnu i globalnu optimizaciju, ali uglavnom ostaje unutar okvira potprograma, dok pojednostavljuje izračune i smanjuje redundantni kod. Rezultat bi trebao biti modificirani dijagram toka;

— za povezivanje osnovnih blokova u pravolinijski kod s prijenosom kontrole koristi se generator ciljnog koda. Proizvodi objektnu datoteku u asembleru s vizualnim registrima, možda ne baš učinkovito;

- Optimizator-linker ovisan o stroju koristi se za dodjelu memorije između virtualnih registara i izvođenje rasporeda instrukcija. Također pretvara program napisan u asembleru u pravi asembler pomoću cjevovoda.

— koriste se podsustavi za otkrivanje grešaka i upravitelj tablica simbola;

— skeniranje i leksička analiza. Skener se koristi za pretvaranje toka znakova izvornog koda u tok tokena, uklanjanjem komentara, razmaka i proširivanjem makronaredbi. Često se skeneri susreću s takvim problemom, bilo da uzimaju u obzir uvlake, velika i mala slova, ugniježđene komentare.

Pogreške koje se mogu pojaviti tijekom skeniranja nazivaju se leksičkim. Oni uključuju sljedeće:

- nedostajući znakovi u abecedi;

— prekoračenje broja znakova u retku ili riječi;

je nezatvoreni string literal ili znak;

- kraj datoteke u komentaru.

Raščlanjivanje ili raščlanjivanje koristi se za transformaciju niza tokena u apstraktno sintaksno stablo. U ovom slučaju, svaki čvor stabla sprema se kao objekt s imenovanim poljima. Mnogi od njih sami su čvorovi stabla. U ovoj fazi nema ciklusa. Prilikom izrade parsera prije svega treba obratiti pozornost na razinu složenosti gramatike (LR ili LL) i provjeriti postoje li pravila razjašnjenja. Doista, neki jezici zahtijevaju semantičku analizu. Pogreške koje se javljaju u ovoj fazi nazivaju se sintaktičke pogreške.

Semantička analiza

Prilikom provođenja semantičke analize potrebno je, prije svega, provjeriti pravila prihvatljivosti i povezati dijelove stabla sintakse u jednu cjelinu kako bi se formirao semantički graf umetanjem operacije za implicitno pretvaranje tipa, rješavanje referenci imena itd. . Jasno je da različiti programski jezici imaju različit skup pravila prihvatljivosti. Prilikom prevođenja jezika sličnih Javi, prevoditelji mogu naići na sljedeće pogreške:

- višestruke deklaracije varijable unutar opsega njezine akcije;

— kršenje pravila pristupačnosti;

- prisutnost referenci na nedeklarirano ime;

- prevelik ili, obrnuto, nedovoljan broj argumenata pri pozivanju metode;

- neusklađenost tipa.

Generacija

Generiranjem međukoda proizvodi se graf toka koji je sastavljen od torki grupiranih u osnovne blokove. Nakon generiranja koda dobiva se pravi strojni kod. U prvom koraku u tradicionalnim kompajlerima za RISC strojeve, prvi korak je stvaranje asemblera s beskonačnim brojem virtualnih registara. To se vjerojatno neće dogoditi za CISC strojeve.

Programski jezici se mogu podijeliti na kompilirane i interpretirane.

Program u prevedenom jeziku pretvara se (prevodi) u skup uputa za ove vrste procesor (strojni kod) i zatim zapisan u izvršni modul, koji se može pokrenuti za izvođenje kao zaseban program. Drugim riječima, prevodilac prevodi izvorni kod programa iz programskog jezika visoke razine u binarne kodove procesorskih instrukcija.

Ako je program napisan na interpretiranom jeziku, tada interpreter izravno izvršava (interpretira) izvorni tekst bez prethodnog prijevoda. Međutim, program ostaje izvorni jezik i ne može se pokrenuti bez tumača. Možemo reći da je računalni procesor tumač strojnog koda.

Ukratko, kompajler prevodi izvorni kod programa u strojni jezik odjednom iu cijelosti, dok stvara zaseban izvršni program, a interpreter izvršava izvorni kod tijekom izvođenja programa.

Podjela na prevedene i interpretirane jezike donekle je proizvoljna. Dakle, za bilo koji tradicionalno kompilirani jezik, kao što je Pascal, možete napisati tumač. Osim toga, većina modernih "čistih" interpretatora ne izvršava jezične konstrukcije izravno, već ih kompajlira u neku međureprezentaciju visoke razine (na primjer, s dereferencijom varijable i makro ekspanzijom).

Za bilo koji interpretirani jezik, možete stvoriti kompilator - na primjer, jezik Lisp, izvorno interpretiran, može se kompilirati bez ikakvih ograničenja. Kod generiran za vrijeme izvođenja također se može dinamički kompajlirati za vrijeme izvođenja.

U pravilu, prevedeni programi rade brže i ne zahtijevaju dodatne programe za izvršavanje, jer su već prevedeni na strojni jezik. Istodobno, sa svakom promjenom teksta programa potrebno je njegovo ponovno kompajliranje, što stvara poteškoće u razvoju. Osim toga, prevedeni program može se izvoditi samo na istoj vrsti računala i obično pod istim operativnim sustavom za koji je kompajler dizajniran. Stvoriti izvršna datoteka za stroj drugačijeg tipa potrebna je nova kompilacija.

Interpretirani jezici imaju neke specifičnosti dodatne mogućnosti(vidi gore), osim toga, programi na njima mogu se pokrenuti odmah nakon promjene, što olakšava razvoj. Program interpretiranog jezika često se može pokrenuti na mnogo različitih tipova strojeva i operativnih sustava bez dodatnog napora.

Međutim, interpretirani programi rade osjetno sporije od kompiliranih programa i ne mogu se izvoditi bez dodatnog programa interpretera.

Neki jezici, kao što su Java i C#, nalaze se između kompiliranih i interpretiranih. Naime, program se ne prevodi u strojni jezik, već u niskorazinski strojno neovisan kod, bytecode. Bajt kod tada izvršava virtualni stroj. Za izvođenje bajt koda obično se koristi interpretacija, iako se neki njegovi dijelovi mogu prevesti u strojni kod izravno tijekom izvođenja programa korištenjem Just-in-time kompilacije (JIT) za ubrzanje programa. Za Javu, bajt kod izvršava Java Virtual Machine (JVM), za C# - Common Language Runtime.

Ovaj vam pristup, u određenom smislu, omogućuje korištenje prednosti i tumača i prevoditelja. Treba spomenuti i izvorni Forth jezik, koji ima i tumača i kompajlera.

Budući da je tekst napisan u programskom jeziku nerazumljiv računalu, potrebno ga je prevesti u strojni kod. Takvo prevođenje programa iz programskog jezika u jezik strojnog koda naziva se prevođenje, a izvode ga posebni programi – prevoditelji.

Prevoditelj - servisni program A koji pretvara izvorni program dat u ulaznom programskom jeziku u radni program dat u objektnom jeziku.

Trenutno se prevoditelji dijele u tri glavne skupine: asembleri, prevoditelji i interpreteri.

Asembler je sistemski uslužni program koji pretvara simboličke konstrukcije u instrukcije strojnog jezika. Specifičnost asemblera je da jednu simboličku instrukciju doslovno prevode u jednu strojnu instrukciju. Stoga je asemblerski jezik (također nazvan autocode) dizajniran da olakša percepciju računalnog skupa instrukcija i ubrza programiranje u tom skupu instrukcija. Programeru je puno lakše zapamtiti mnemoničku oznaku strojnih instrukcija nego njihov binarni kod.

Istodobno, asemblerski jezik, uz analogne strojne instrukcije, sadrži mnoge dodatne direktive koje olakšavaju, posebice, upravljanje računalnim resursima, pisanje fragmenata koji se ponavljaju i izgradnju višemodulnih programa. Stoga je izražajnost jezika mnogo bogatija od samog jezika simboličkog kodiranja, što uvelike povećava učinkovitost programiranja.

Kompajler je pomoćni program koji prevodi u strojni jezik program napisan u izvornom programskom jeziku. Kao asembler, prevodilac pretvara program iz jednog jezika u drugi (najčešće u jezik određenog računala). Međutim, naredbe izvornog jezika značajno se razlikuju po organizaciji i snazi od naredbi strojnog jezika. Postoje jezici u kojima se jedna instrukcija izvornog jezika prevodi u 7-10 strojnih instrukcija. Međutim, postoje i jezici u kojima svaka instrukcija može odgovarati 100 ili više strojnih instrukcija (na primjer, Prolog). Osim toga, u izvornim jezicima često se koristi striktno tipiziranje podataka koje se provodi njihovim preliminarnim opisom. Programiranje se ne mora oslanjati na kodiranje algoritma, već na pažljivo razmišljanje o strukturama podataka ili klasama. Proces prevođenja s takvih jezika obično se naziva kompilacija, a izvorni jezici obično se nazivaju programski jezici visoke razine (ili jezici visoke razine). Apstrakcija programskog jezika iz sustava naredbi računala dovela je do neovisnog stvaranja širokog spektra jezika orijentiranih na rješenja. specifične zadatke. Pojavili su se jezici za znanstvene izračune, ekonomske izračune, pristup bazama podataka i drugo.

Interpretator je program ili uređaj koji izvodi prevođenje od operatora do operatora i izvršavanje izvornog programa. Za razliku od prevoditelja, tumač ne proizvodi program na strojnom jeziku kao izlaz. Nakon što prepozna naredbu izvornog jezika, odmah je izvršava. I prevoditelji i tumači koriste iste metode raščlanjivanja izvornog teksta programa. Ali tumač vam omogućuje da počnete s obradom podataka nakon što napišete čak i jednu naredbu. To čini proces razvoja i otklanjanja pogrešaka programa fleksibilnijim. Osim toga, odsutnost izlaznog strojnog koda omogućuje da se vanjski uređaji ne "zasipaju" dodatnim datotekama, a sam tumač može se vrlo lako prilagoditi bilo kojoj strojnoj arhitekturi, nakon što ga je razvio samo jednom u široko korištenom programskom jeziku. Stoga su interpretirani jezici kao što su Java Script, VB Script postali široko rasprostranjeni. Nedostatak interpretera je mala brzina izvođenja programa. Tipično, interpretirani programi rade 50 do 100 puta sporije od programa napisanih u strojnom kodu.

Emulator je program ili softverski i hardverski alat koji omogućuje izvođenje programa na danom računalu bez reprogramiranja, korištenjem kodova ili metoda za izvođenje operacija koje se razlikuju od ovog računala. Emulator je sličan tumaču po tome što izravno izvršava program napisan na nekom jeziku. Međutim, najčešće je to strojni jezik ili međukod. Oba predstavljaju upute u binarnom kodu koje se mogu odmah izvršiti nakon prepoznavanja operacijskog koda. Za razliku od tekstualnih programa, nije potrebno prepoznati strukturu programa, odabrati operande.

Emulatori se često koriste u različite svrhe. Na primjer, kada se razvijaju novi računalni sustavi, prvo se kreira emulator koji pokreće programe koji se razvijaju za računala koja još ne postoje. To omogućuje procjenu skupa instrukcija i razvoj osnovnog softvera prije izrade odgovarajućeg hardvera.

Transkoder - program odn uređaj za programiranje, prevođenje programa napisanih na strojnom jeziku jednog računala u programe napisanih na strojnom jeziku drugog računala. Ako je emulator manje inteligentan analog interpretera, tada transkoder djeluje u istom svojstvu u odnosu na kompajler. Slično, izvorni (i obično binarni) strojni kod ili intermedijarna reprezentacija pretvaraju se u drugi sličan kod u jednoj instrukciji i bez ikakve opće analize strukture izvornog programa. Transkoderi su korisni pri prijenosu programa s jedne računalne arhitekture na drugu. Također se mogu koristiti za rekonstrukciju teksta jezičnog programa visoke razine iz dostupnog binarnog koda.

Makroprocesor je program koji zamjenjuje jedan niz znakova drugim. To je neka vrsta kompilatora. Generira izlazni tekst obradom posebni umeci nalazi se u izvornom tekstu. Ovi umetci su napravljeni na poseban način i pripadaju jezičnim konstruktima, koji se nazivaju makro jezik. Makroprocesori se često koriste kao dodaci programskim jezicima, povećavajući funkcionalnost programskih sustava. Gotovo svaki asembler sadrži makroprocesor, što povećava učinkovitost razvoja strojnih programa. Takvi programski sustavi obično se nazivaju makro asembleri.

Sintaksa - skup pravila određenog jezika koji određuju oblikovanje njegovih elemenata. Drugim riječima, to je skup pravila za formiranje semantički smislenih nizova znakova u određenom jeziku. Sintaksa je određena pomoću pravila koja opisuju koncepte određenog jezika. Primjeri koncepata su: varijabla, izraz, operator, procedura. Redoslijed pojmova i njihova dopuštena uporaba u pravilima određuje sintaktički ispravne strukture koje tvore programe. Kroz sintaksu je definirana hijerarhija objekata, a ne način na koji oni međusobno djeluju. Na primjer, operator se može pojaviti samo u proceduri, dok se izraz u operatoru, varijabla može sastojati od imena i izbornih indeksa, i tako dalje. Sintaksa nije povezana s takvim pojavama u programu kao što su "skakanje na nepostojeću oznaku" ili "varijabla s danim imenom nije definirana". To je ono što semantika radi.

Semantika - pravila i uvjeti koji određuju odnos između elemenata jezika i njihovih semantičkih značenja, kao i tumačenje smislenog značenja sintaktičkih konstrukcija jezika. Objekti programskog jezika ne samo da su smješteni u tekstu u skladu s određenom hijerarhijom, već su i dodatno međusobno povezani kroz druge koncepte koji tvore različite asocijacije. Na primjer, varijabla čija sintaksa definira valjanu lokaciju samo u deklaracijama i nekim izjavama ima određena vrsta, može se koristiti s ograničenim skupom operacija, ima adresu, veličinu i mora se deklarirati prije korištenja u programu.

Parser je komponenta prevoditelja koja provjerava usklađenost izvornih izjava s pravilima sintakse i semantikom određenog programskog jezika. Unatoč nazivu, analizator provjerava i sintaksu i semantiku. Sastoji se od nekoliko blokova, od kojih svaki rješava svoje probleme. Razmotrit će se detaljnije pri opisu strukture prevoditelja. translator kompilator jezik programiranje

Svaki prevoditelj obavlja sljedeće glavne zadatke:

– analizira emitirani program, posebice utvrđuje sadrži li sintaktičke pogreške;
- generira izlazni program (često se naziva i objektni program) u jeziku strojnih instrukcija;
- dodjeljuje memoriju za objektni program.1.1 Interpreteri

Jedna od često citiranih prednosti implementacije tumača je da dopušta "trenutni način". Trenutačni način rada omogućuje vam da računalu postavite zadatak kao što je PRINT 3.14159*3/2.1 i vraća vam odgovor čim pritisnete ENTER (ovo vam omogućuje da koristite računalo od 3000 USD kao kalkulator od 10 USD). Osim toga, tumači imaju posebne atribute koji olakšavaju otklanjanje pogrešaka. Možete, na primjer, prekinuti obradu programa tumača, prikazati sadržaj određenih varijabli, preletjeti kroz program i zatim nastaviti s izvođenjem.

Ono što se programerima najviše sviđa kod tumača je mogućnost dobivanja brzog odgovora. Ovdje nema potrebe za kompilacijom, budući da je tumač uvijek spreman intervenirati u vaš program. Unesite RUN i rezultat je vaš Posljednja promjena se pojavi na ekranu.

Međutim, jezici tumača imaju nedostatke. Potrebno je, na primjer, imati kopiju interpretera u memoriji u svakom trenutku, dok mnoge značajke interpretera, a time i njegove značajke, možda neće biti potrebne za izvođenje određenog programa.

Suptilni nedostatak tumača je taj što oni obeshrabruju dobar stil programiranja. Budući da komentari i drugi formalizirajući detalji zauzimaju puno programske memorije, ljudi ih obično ne koriste. Vrag je manje bijesan od programera BASIC tumača koji pokušava staviti 120K programa u 60K memoriju. ali što je najgore, prevoditelji su spori.

Troše previše vremena smišljajući što učiniti umjesto da rade stvarnu stvar. Na izvršenju programski operateri, prevoditelj prvo mora skenirati svaku izjavu kako bi pročitao njen sadržaj (što ta osoba traži od mene?) i zatim izvršiti traženu operaciju. Naredbe u petljama se previše skeniraju.

Razmotrite program: na tumaču BASIC 10 FOR N=1 TO 1000 20 PRINT N,SQR(N) 30 NEXT N pri prvom prijelazu kroz ovaj program, BASIC Interpreter mora shvatiti što linija 20 znači:

1. pretvoriti numeričku varijablu N u niz
2. poslati niz na ekran
3. prijeđite na sljedeće područje ispisa
4. izračunati Korijen od N
5. pretvoriti rezultat u niz
6. poslati niz na ekran

U drugom prolazu petlje, sve se ovo pogađanje ponovno ponavlja, budući da su svi rezultati proučavanja ovog niza prije nekoliko milisekundi potpuno zaboravljeni. I tako u svih sljedećih 998 prolaza. Očito, kad biste nekako mogli odvojiti fazu skeniranja/razumijevanja od faze izvršenja, imali biste brži program. A kompajleri upravo tome i služe.

Ciljevi i zadaci discipline. Osnovni pojmovi i definicije. Osnovne značajke programski jezici i prevoditelji. Generalizirana struktura prevoditelja. Varijante interakcije blokova prevoditelja.

Ciljevi i zadaci discipline

Trenutačno se umjetni jezici koji koriste prikaz teksta za opisivanje predmetnog područja široko koriste ne samo u programiranju, već iu drugim područjima. Uz njihovu pomoć opisuje se struktura svih vrsta dokumenata, trodimenzionalnih virtualnih svjetova, grafičkih korisničkih sučelja i mnogih drugih objekata koji se koriste u modelima iu stvarnom svijetu. Kako bi se ovi tekstualni opisi ispravno sastavili, a zatim ispravno prepoznali i protumačili, koriste se posebne metode njihove analize i transformacije. Metode se temelje na teoriji jezika i formalnih gramatika, kao i na teoriji automata. Softverski sustavi dizajnirani za analizu i tumačenje tekstova nazivaju se prevoditelji.

Unatoč činjenici da su do danas razvijene tisuće različitih jezika i njihovih prevoditelja, proces stvaranja novih aplikacija u ovom području ne prestaje. To je povezano kako s razvojem tehnologije za proizvodnju računalnih sustava, tako i s potrebom rješavanja sve složenijih primijenjenih problema. Osim toga, elementi teorije jezika i formalne gramatike primjenjivi su u raznim drugim područjima, na primjer, kada se opisuju strukture podataka, datoteke, slike, predstavljene ne u tekstu, već u binarnom formatu. Ove su metode također korisne pri razvoju vaših prevoditelja, čak i tamo gdje već postoje odgovarajući analozi. Takav razvoj može biti posljedica raznih razloga, posebice funkcionalnih ograničenja, nedostatka lokalizacije, niske učinkovitosti. Na primjer, jedan od najnovijih događaja Microsoft je programski jezik C#, a jedan od razloga nastanka je želja da se smanji popularnost programskog jezika Java. Postoje mnogi drugi primjeri u kojima razvijanje vlastitog prevoditelja može biti relevantno. Dakle, temelji teorije jezika i formalne gramatike, kao i praktične metode za razvoj prevoditelja, leže u temeljima inženjerskog obrazovanja u informatici i računalnim tehnologijama.

Predloženi materijal dotiče osnove metoda razvoja prevoditelja i sadrži informacije potrebne za proučavanje logike njihovog funkcioniranja, korištenog matematičkog aparata (teorija formalnih jezika i formalne gramatike, metajezici). Koristi se kao dio semestralnih predavanja za različite specijalnosti na Fakultetu informatike i računalnog inženjerstva Krasnojarskog državnog tehničkog sveučilišta. U tijeku laboratorijske nastave provodi se neposredno upoznavanje s pojedinim metodama izrade translatora.

Svrha discipline: pružiti znanja o osnovama teorije jezika i formalne gramatike, teorije automata, metoda za razvoj prevoditelja.

Za postizanje ovog cilja u nastavi discipline rješavaju se sljedeći zadaci:

Tijekom predavanja, generalni principi organizacija procesa prevođenja i struktura prevoditelja. Proučavaju se osnove teorije konstruiranja prevoditelja.
U laboratorijskim sastancima i tijekom samostalan rad provodi se praktična konsolidacija primljenog teorijskog znanja: razvija se prevoditelj za jednostavan programski jezik.

Osnovni pojmovi i definicije

Većina razmatranih definicija posuđena je iz [ARNFTS Englesko-rusko-njemačko-francuski rječnik računarstva i obrade podataka, 4132 pojma. Pod, ispod. izd. A.A. Dorodnjicin. M.: 1978. 416 str.) ].

Prevoditelj - pomoćni program koji pretvara izvorni program koji se nalazi u ulaznom programskom jeziku u radni program koji se nalazi u objektnom jeziku.

Gornja definicija odnosi se na sve vrste emitiranih programa. Međutim, svaki od ovih programa može imati svoje osobitosti u organizaciji procesa prevođenja. Trenutno se prevoditelji dijele u tri glavne skupine: asembleri, prevoditelji i interpreteri.

asembler - uslužni program sustava koji pretvara simboličke konstrukcije u instrukcije strojnog jezika. Specifičnost asemblera je da jednu simboličku instrukciju doslovno prevode u jednu strojnu instrukciju. Stoga je asemblerski jezik (također nazvan autocode) dizajniran da olakša percepciju računalnog skupa instrukcija i ubrza programiranje u tom skupu instrukcija. Programeru je puno lakše zapamtiti mnemoničku oznaku strojnih instrukcija nego njihov binarni kod. Stoga se glavni dobitak ne postiže povećanjem snage pojedinih naredbi, već povećanjem učinkovitosti njihove percepcije.

kompajler - je pomoćni program koji prevodi u strojni jezik program napisan u izvornom programskom jeziku. Kao asembler, prevodilac pretvara program iz jednog jezika u drugi (najčešće u jezik određenog računala). Međutim, naredbe izvornog jezika značajno se razlikuju po organizaciji i snazi od naredbi strojnog jezika. Postoje jezici u kojima se jedna instrukcija izvornog jezika prevodi u 7-10 strojnih instrukcija. Međutim, postoje i jezici u kojima svaka instrukcija može odgovarati 100 ili više strojnih instrukcija (na primjer, Prolog). Osim toga, u izvornim jezicima često se koristi striktno tipiziranje podataka koje se provodi njihovim preliminarnim opisom. Programiranje se ne mora oslanjati na kodiranje algoritma, već na pažljivo razmišljanje o strukturama podataka ili klasama. Proces prevođenja s takvih jezika obično se naziva kompilacija, a izvorni jezici obično se nazivaju programski jezici visoke razine (ili jezici visoke razine). Apstrakcija programskog jezika iz sustava naredbi računala dovela je do neovisnog stvaranja širokog spektra jezika usmjerenih na rješavanje specifičnih problema. Pojavili su se jezici za znanstvene izračune, ekonomske izračune, pristup bazama podataka i drugo.

Tumač - program ili uređaj koji izvodi operator-po-operator prijevod i izvršavanje izvornog programa. Za razliku od prevoditelja, tumač ne proizvodi program na strojnom jeziku kao izlaz. Nakon što prepozna naredbu izvornog jezika, odmah je izvršava. I prevoditelji i tumači koriste iste metode raščlanjivanja izvornog teksta programa. Ali tumač vam omogućuje da počnete s obradom podataka nakon što napišete čak i jednu naredbu. To čini proces razvoja i otklanjanja pogrešaka programa fleksibilnijim. Osim toga, odsutnost izlaznog strojnog koda omogućuje da se vanjski uređaji ne "zasipaju" dodatnim datotekama, a sam tumač može se vrlo lako prilagoditi bilo kojoj strojnoj arhitekturi, nakon što ga je razvio samo jednom u široko korištenom programskom jeziku. Stoga su interpretirani jezici kao što su Java Script, VB Script postali široko rasprostranjeni. Nedostatak interpretera je mala brzina izvođenja programa. Tipično, interpretirani programi rade 50 do 100 puta sporije od programa napisanih u strojnom kodu.

Emulator - program ili softverski i hardverski alat koji omogućuje, bez reprogramiranja, izvršavanje na danom računalu programa koji koristi kodove ili metode za izvođenje operacije koja se razlikuje od ovog računala. Emulator je sličan tumaču po tome što izravno izvršava program napisan na nekom jeziku. Međutim, najčešće je to strojni jezik ili međukod. Oba predstavljaju upute u binarnom kodu koje se mogu odmah izvršiti nakon prepoznavanja operacijskog koda. Za razliku od tekstualnih programa, nije potrebno prepoznati strukturu programa, odabrati operande.

Vrlo često se emulator koristi za pokretanje starih programa na novim računalima. Obično su novija računala brža i imaju bolje periferne uređaje. To vam omogućuje da emulirate starije programe učinkovitije nego da ih pokrećete na starijim računalima. Primjer ovakvog pristupa je razvoj emulatora kućnog računala ZX Spectrum s mikroprocesorom Z80. Do sada postoje ljubitelji igranja na emulatoru u zastarjelim programima za igre, ali još uvijek nisu izgubili svoju bivšu privlačnost. Emulator se također može koristiti kao više jeftin analog suvremeni računalni sustavi, dok pruža prihvatljive performanse ekvivalentne nižim modelima neke obitelji arhitektura. Primjer su IBM PC emulatori. kompatibilna računala implementiran na snažnijim Apple računalima. Brojni emulatori napisani za IBM PC uspješno zamjenjuju razne igraće konzole.

Srednji emulator reprezentacije, poput tumača, može se lako prenijeti s jedne računalne arhitekture na drugu, omogućujući stvaranje mobilnog softvera. To je svojstvo koje je unaprijed odredilo uspjeh programskog jezika Java, iz kojeg se program prevodi u međukod. Izvršavanje ovog koda virtualna java stroj nije ništa više od emulatora koji pokreće bilo koji moderni operacijski sustav.

Transkoder - program ili softverski uređaj koji prevodi programe napisane na strojnom jeziku jednog računala u programe napisane na strojnom jeziku drugog računala. Ako je emulator manje inteligentan analog interpretera, tada transkoder djeluje u istom svojstvu u odnosu na kompajler. Slično, izvorni (i obično binarni) strojni kod ili intermedijarna reprezentacija pretvaraju se u drugi sličan kod u jednoj instrukciji i bez ikakve opće analize strukture izvornog programa. Transkoderi su korisni pri prijenosu programa s jedne računalne arhitekture na drugu. Također se mogu koristiti za rekonstrukciju teksta jezičnog programa visoke razine iz dostupnog binarnog koda.

Makroprocesor - program koji zamjenjuje jedan niz znakova drugim[Smeđa]. To je neka vrsta kompilatora. Generira izlazni tekst obradom posebnih umetaka koji se nalaze u izvornom tekstu. Ovi umetci su napravljeni na poseban način i pripadaju jezičnim konstruktima, koji se nazivaju makro jezik. Makroprocesori se često koriste kao dodaci programskim jezicima, povećavajući funkcionalnost programskih sustava. Gotovo svaki asembler sadrži makroprocesor, što povećava učinkovitost razvoja strojnih programa. Takvi programski sustavi obično se nazivaju makro asembleri.

Makroprocesori se također koriste s jezicima visoke razine. Povećavaju funkcionalnost jezika kao što su PL/1, C, C++. Makroprocesori se posebno široko koriste u C i C++, što olakšava pisanje programa. Primjer raširene upotrebe makro procesora je biblioteka klasa Microsoft Foundation Classes (MFC). Kroz makroumetke implementira mape poruka i druge programske objekte. U isto vrijeme, makroprocesori povećavaju učinkovitost programiranja bez promjene sintakse i semantike jezika.

Sintaksa - skup pravila određenog jezika koji određuju oblikovanje njegovih elemenata. Drugim riječima, ovo skup pravila za formiranje semantički smislenih nizova znakova u određenom jeziku. Sintaksa je određena pomoću pravila koja opisuju koncepte određenog jezika. Primjeri koncepata su: varijabla, izraz, operator, procedura. Redoslijed pojmova i njihova dopuštena uporaba u pravilima određuje sintaktički ispravne strukture koje tvore programe. Kroz sintaksu je definirana hijerarhija objekata, a ne način na koji oni međusobno djeluju. Na primjer, operator se može pojaviti samo u proceduri, dok se izraz u operatoru, varijabla može sastojati od imena i izbornih indeksa, i tako dalje. Sintaksa nije povezana s takvim pojavama u programu kao što su "skakanje na nepostojeću oznaku" ili "varijabla s danim imenom nije definirana". To je ono što semantika radi.

Semantika - pravila i uvjeti koji određuju odnos između elemenata jezika i njihovih semantičkih značenja, kao i tumačenje značenjskog značenja sintaktičkih konstrukcija jezika. Objekti programskog jezika ne samo da su smješteni u tekstu u skladu s određenom hijerarhijom, već su i dodatno međusobno povezani kroz druge koncepte koji tvore različite asocijacije. Na primjer, varijabla za koju sintaksa definira valjanu lokaciju samo u deklaracijama i nekim izjavama, ima specifičan tip, može se koristiti s ograničenim skupom operacija, ima adresu, veličinu i mora se deklarirati prije upotrebe u program.

Sintaktički analizator - komponenta prevoditelja koja provjerava usklađenost izvornih naredbi s pravilima sintakse i semantikom zadanog programskog jezika. Unatoč nazivu, analizator provjerava i sintaksu i semantiku. Sastoji se od nekoliko blokova, od kojih svaki rješava svoje probleme. Razmotrit će se detaljnije pri opisu strukture prevoditelja.

Opće značajke programskih jezika i prevoditelja

Programski jezici se prilično razlikuju jedni od drugih u svrhu, strukturi, semantičkoj složenosti, metodama implementacije. To nameće svoje specifičnosti razvoju pojedinih prevoditelja.

Programski jezici su alati za rješavanje problema u različitim predmetnim područjima, što određuje specifičnosti njihove organizacije i razlike u namjeni. Primjeri uključuju Fortran za znanstveno računanje, C za sistemsko programiranje, Prolog za učinkovito opisivanje problema zaključivanja i Lisp za rekurzivnu obradu popisa. Ovi primjeri se mogu nastaviti. Svako od predmetnih područja ima svoje zahtjeve za organizaciju samog jezika. Stoga možemo primijetiti raznolikost oblika reprezentacije operatora i izraza, razliku u skupu osnovne operacije, smanjenje učinkovitosti programiranja pri rješavanju problema koji nisu povezani s predmetno područje. Jezične razlike odražavaju se i na strukturu prevoditelja. Lisp i Prolog se najčešće izvode u interpretativnom načinu jer koriste dinamičko generiranje tipa podataka tijekom izračuna. Fortranove prevoditelje karakterizira agresivna optimizacija rezultirajućeg strojnog koda, što postaje moguće zahvaljujući relativno jednostavnoj semantici jezičnih konstrukcija - posebice zbog nepostojanja alternativnih mehanizama imenovanja varijabli putem pokazivača ili referenci. Prisutnost pokazivača u jeziku C čini specifične zahtjeve Do dinamička distribucija memorija.

Struktura jezika karakterizira hijerarhijske odnose između njegovih koncepata, koji su opisani sintaktičkim pravilima. Programski jezici mogu se međusobno jako razlikovati u organizaciji pojedinačnih koncepata i u odnosu među njima. Programski jezik PL/1 dopušta proizvoljno ugniježđivanje procedura i funkcija, dok u C-u sve funkcije moraju biti na vanjskoj razini ugniježđivanja. Jezik C++ dopušta deklaraciju varijabli u bilo kojoj točki programa prije njegove prve uporabe, dok u Pascalu varijable moraju biti definirane u posebno područje opisi. PL/1 ide još dalje po ovom pitanju, što dopušta da se varijabla deklarira nakon što je korištena. Ili možete potpuno izostaviti opis i slijediti zadana pravila. Ovisno o odluka, prevoditelj može analizirati program u jednom ili više prolaza, što utječe na brzinu prijevoda.

Semantika programskih jezika varira u vrlo širokom rasponu. Razlikuju se ne samo u specifičnostima implementacije pojedinih operacija, već iu programskim paradigmama koje određuju temeljne razlike u metodama razvoja programa. Specifičnosti provedbe operacija mogu se odnositi i na strukturu obrađenih podataka i na pravila obrade istih vrsta podataka. Jezici kao što su PL/1 i APL podržavaju matrične i vektorske operacije. Većina jezika prvenstveno radi sa skalarima, pružajući procedure i funkcije koje su napisali programeri za rukovanje nizovima. Ali čak i kada se izvodi operacija zbrajanja dva cijela broja, jezici poput C i Pascala mogu se ponašati drugačije.

Uz tradicionalno proceduralno programiranje, koje se također naziva imperativnim, postoje paradigme kao što su funkcionalno programiranje, logičko programiranje i objektno orijentirano programiranje. Nadam se da će proceduralno-parametarska paradigma programiranja koju sam predložio [Legalov2000] također zauzeti svoje mjesto u ovoj seriji. Struktura koncepata i objekata jezika snažno ovisi o odabranoj paradigmi, što također utječe na implementaciju prevoditelja.

Čak se isti jezik može implementirati na nekoliko načina. To je zbog činjenice da teorija formalnih gramatika dopušta različite metode raščlanjivanja istih rečenica. Sukladno tome, prevoditelji različiti putevi može dobiti isti rezultat (program objekta) iz izvornog izvornog koda.

Međutim, svi programski jezici imaju niz zajedničkih karakteristika i parametara. To zajedništvo također određuje principe organiziranja prevoditelja koji su slični za sve jezike.

Programski jezici osmišljeni su kako bi olakšali programiranje. Stoga su njihovi operatori i podatkovne strukture moćniji nego u strojnim jezicima.
Da bi se povećala vidljivost programa, umjesto numeričkih kodova koriste se simbolički ili grafički prikazi jezičnih konstrukata koji su prikladniji za njihovu percepciju od strane osobe.
Za bilo koji jezik definirano je:

Skup simbola pomoću kojih se mogu napisati ispravni programi (abeceda), osnovni elementi.
Skup ispravnih programa (sintaksa).
"Značenje" svakog ispravnog programa (semantika).

Bez obzira na specifičnosti jezika, bilo koji prevoditelj može se smatrati funkcionalnim pretvaračem F koji omogućuje nedvosmisleno preslikavanje X u Y, gdje je X program u izvornom jeziku, Y je program u izlaznom jeziku. Stoga se sam proces prevođenja može formalno prikazati vrlo jednostavno i jasno:

Formalno, svaki ispravan program X je niz znakova iz neke abecede A, pretvoren u odgovarajući niz Y, sastavljen od znakova iz abecede B.

programski jezik kao i svaki drugi složen sustav, definiran je kroz hijerarhiju koncepata koja definira odnos između njegovih elemenata. Ovi pojmovi su međusobno povezani u skladu sa sintaktičkim pravilima. Svaki od programa izgrađenih prema ovim pravilima ima odgovarajuću hijerarhijsku strukturu.

U tom smislu, za sve jezike i njihove programe mogu se dodatno razlikovati sljedeće zajedničke značajke: svaki jezik mora sadržavati pravila koja omogućuju generiranje programa koji odgovaraju tom jeziku ili prepoznavanje korespondencije između pisanih programa i danog jezika.

Odnos između programske strukture i programskog jezika naziva se sintaktičko preslikavanje.

Kao primjer, razmotrite odnos između hijerarhijske strukture i niza znakova koji definira sljedeći aritmetički izraz:

U većini programskih jezika dati izraz definira hijerarhiju programskih objekata koji se mogu prikazati kao stablo (slika 1.1.):

Krugovi predstavljaju simbole koji se koriste kao elementarne konstrukcije, a pravokutnici predstavljaju složene koncepte koji imaju hijerarhijsku i, moguće, rekurzivnu strukturu. Ova hijerarhija je definirana uz pomoć sintaktičkih pravila napisanih na posebnom jeziku koji se naziva metajezik (metajezici će biti detaljnije obrađeni prilikom proučavanja formalnih gramatika):

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

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

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

<буква>

Bilješka. Znak "::=" se čita kao "jest". Okomita crta "|" čitati kao "ili".

Ako su pravila drugačije napisana, promijenit će se i hijerarhijska struktura. Primjer je sljedeći način unosi pravila:

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

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

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

Kao rezultat raščlanjivanje isti aritmetički izraz, izgradit će se hijerarhijska struktura, prikazana na sl. 1.2.

Treba napomenuti da hijerarhijska struktura u općem slučaju ne mora biti ni na koji način povezana sa semantikom izraza. U oba slučaja, prioritet izvođenja operacija može se implementirati u skladu s općeprihvaćenim pravilima, kada množenje prethodi zbrajanju (ili obrnuto, sve operacije mogu imati isti prioritet pod bilo kojim skupom pravila). Međutim, prva struktura eksplicitno podržava daljnju implementaciju zajedničkog prvenstva, dok je druga prikladnija za implementaciju operacija s istim prioritetom i njihovo izvršavanje s desna na lijevo.

Proces pronalaženja sintaktičke strukture zadani program nazvao raščlanjivanje.

Sintaktička struktura koja je ispravna u jednom jeziku može biti pogrešna u drugom. Na primjer, u Forthu, gornji izraz neće biti prepoznat. Međutim, za ovaj jezik, postfiks izraz će biti točan:

Njegova sintaktička struktura opisana je pravilima:

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

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

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

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

Hijerarhijsko stablo koje definira sintaktičku strukturu prikazano je na sl. 1.3.

Još jedna karakteristična značajka svih jezika je njihova semantika. Određuje značenje jezičnih operacija, ispravnost operanda. Lanci koji imaju istu sintaktičku strukturu u različitim programskim jezicima mogu se razlikovati u semantici (što se, na primjer, opaža u C ++, Pascal, Basic za gornji fragment aritmetičkog izraza).

Poznavanje semantike jezika omogućuje njegovo odvajanje od njegove sintakse i korištenje za pretvaranje u drugi jezik (za generiranje koda).

Opis semantike i prepoznavanje njezine ispravnosti obično je najdugotrajniji i najobimniji dio prevoditelja, budući da je potrebno nabrojati i analizirati skup mogućih kombinacija operacija i operanda.

Generalizirana struktura prevoditelja

Opća svojstva i obrasci svojstveni su različitim programskim jezicima i prevoditeljima s tih jezika. Imaju slične procese pretvaranja izvornog teksta. Unatoč činjenici da se interakcija ovih procesa može organizirati na različite načine, moguće je izdvojiti funkcije čije izvršavanje dovodi do istih rezultata. Takve funkcije nazivamo fazama procesa prevođenja.

S obzirom na sličnost prevoditelja i interpretera, razmotrimo faze koje postoje u prevoditelju. Ističe:

Faza leksičke analize.
Faza parsiranja, koja se sastoji od:

prepoznavanje sintaktičke strukture;
semantičko parsiranje, tijekom kojeg se provodi rad s tablicama, generiranje srednje semantičke reprezentacije ili objektnog modela jezika.

Faza generiranja koda, koja izvodi:

semantička analiza komponenata međureprezentacije ili objektnog modela jezika;
prevođenje posredne reprezentacije ili objektnog modela u objektni kod.

Uz glavne faze procesa prevođenja moguće su i dodatne faze:

2a. Faza istraživanja i optimizacije intermedijarne reprezentacije, koja se sastoji od: 2a.1. analiza ispravnosti posrednog prikaza;
2a.2. intermedijarna optimizacija predstavljanja.

3a. Faza optimizacije objektnog koda.

Interpretator se razlikuje po tome što se faza generiranja koda obično zamjenjuje fazom emulacije elemenata međureprezentacije ili objektnog modela jezika. Osim toga, tumač obično ne optimizira posredni prikaz, već ga odmah emulira.

Osim toga, moguće je izdvojiti jedan proces za sve faze analize i ispravljanja grešaka koje postoje u obrađenom izvornom kodu programa.

Generalizirana struktura prevoditelja, uzimajući u obzir faze koje postoje u njemu, prikazana je na sl. 1.4.

Sastoji se od leksičkog analizatora, parsera, generatora koda, analizatora grešaka. U interpreteru se umjesto generatora koda koristi emulator (sl. 1.5), u koji se, osim elemenata međureprezentacije, prenose i izvorni podaci. Izlaz emulatora je rezultat izračuna.

Leksički analizator (poznat i kao skener) čita ulazni niz znakova i grupira ih u elementarne konstrukte koji se nazivaju tokeni. Svaki token ima klasu i vrijednost. Obično elementarne konstrukcije jezika, na primjer, identifikator, pravi broj, komentar, djeluju kao kandidati za ulogu leksema. Rezultirajući tokeni prosljeđuju se parseru. Skener nije obavezni dio prevoditelja. Međutim, omogućuje povećanje učinkovitosti procesa prevođenja. Leksička analiza se detaljnije razmatra u temi: "Organizacija leksičke analize".

Parser analizira izvorni program koristeći dolazne tokene, gradi sintaktičku strukturu programa i provodi semantičku analizu s formiranjem objektnog modela jezika. Objektni model predstavlja sintaktičku strukturu dopunjenu semantičkim vezama između postojećih pojmova. Ove veze mogu biti:

reference varijabli, tipovi podataka i nazivi procedura smješteni u tablice naziva;
veze koje određuju redoslijed izvršavanja naredbi;
poveznice koje određuju ugniježđenje elemenata objektnog modela jezika i druge.

Dakle, parser je prilično složen prevoditeljski blok. Stoga se može podijeliti na sljedeće komponente:

prepoznavač;
blok semantičke analize;
objektni model ili intermedijarni prikaz koji se sastoji od tablice imena i sintaktičke strukture.

Generalizirana struktura parsera prikazana je na sl. 1.6.

Prepoznavač prima lanac tokena i na temelju njega ga analizira u skladu s korištenim pravilima. Tokeni se, nakon uspješnog analiziranja pravila, prosljeđuju semantičkom analizatoru, koji gradi tablicu imena i popravlja fragmente sintaktičke strukture. Osim toga, dodatne semantičke veze su fiksirane između tablice naziva i sintaktičke strukture. Kao rezultat, formira se objektni model programa, oslobođen vezivanja za sintaksu programskog jezika. Često se umjesto sintaktičke strukture koja u potpunosti kopira hijerarhiju jezičnih objekata, stvara njezin pojednostavljeni analog, koji se naziva intermedijarni prikaz.

Analizator pogrešaka prima informacije o pogreškama koje se javljaju u različitim blokovima prevoditelja. Koristeći primljene informacije, generira poruke korisniku. Osim toga, ovaj blok može pokušati ispraviti pogrešku kako bi se nastavilo dalje analiziranje. Također je odgovoran za točan završetak programa u slučaju da se daljnji prijenos ne može nastaviti.

Generator koda gradi objektni strojni kod na temelju analize objektnog modela ili posredne reprezentacije. Konstrukciju koda prati dodatna semantička analiza povezana s potrebom pretvaranja generaliziranih naredbi u kodove za određeno računalo. U fazi takve analize konačno se utvrđuje mogućnost transformacije i učinkovite opcije. Samo generiranje koda je kodiranje jednih naredbi u druge.

Mogućnosti interakcije za blokove prevoditelja

Organizacija procesa prevođenja, koja određuje provedbu glavnih faza, može se provesti na različite načine. To je određeno različitim opcijama za interakciju blokova prevoditelja: leksički analizator, parser i generator koda. Unatoč istom krajnjem rezultatu, razne opcije Interakcije blokova prevoditelja pružaju različite opcije za pohranjivanje posrednih podataka. Postoje dvije glavne opcije za interakciju blokova prevoditelja:

višeprolazna organizacija, u kojoj je svaka od faza neovisan proces koji kontrolu prenosi na sljedeću fazu tek nakon završetka potpune obrade svojih podataka;
organizacija s jednim prolazom, u kojoj sve faze predstavljaju jedan proces i prenose podatke jedna drugoj u malim fragmentima.

Na temelju dvije glavne opcije, također možete stvoriti različite kombinacije od njih.

Višeprolazna organizacija interakcije blokova prevoditelja

Ova varijanta interakcije blokova, koristeći kompilator kao primjer, prikazana je na slici 1.7.

Leksički analizator u potpunosti obrađuje izvorni tekst, tvoreći lanac koji se sastoji od svih primljenih leksema na izlazu. Tek nakon toga kontrola se prenosi na parser. Parser prima formirani lanac tokena i na temelju njega formira međureprezentaciju ili objektni model. Nakon što primi cijeli objektni model, predaje kontrolu generatoru koda. Generator koda, na temelju objektnog modela jezika, gradi potrebni strojni kod

Prednosti ovog pristupa uključuju:

Izolacija pojedinih faza, što omogućuje njihovu neovisnu implementaciju i korištenje.
Mogućnost pohranjivanja podataka dobivenih kao rezultat rada svake od faza na vanjske uređaje za pohranu i njihovo korištenje po potrebi.
Mogućnost smanjenja volumena RAM memorija, potreban za rad prevoditelja, zbog sekvencijalnog pozivanja faza.

Treba uzeti u obzir nedostatke.

Dostupnost velike količine posredne informacije, iz kojih ovaj trenutak potrebno je samo malo vremena.
Usporavanje brzine prijevoda zbog sekvencijalnog izvođenja faza i upotrebe vanjskih uređaja za pohranu radi uštede RAM-a.

Ovaj pristup može biti prikladan pri izradi prevoditelja iz programskih jezika sa složenom sintaktičkom i semantičkom strukturom (na primjer, PL/I). U takvim je situacijama teško prevesti u jednom prolazu, pa je lakše prikazati rezultate prethodnih prolaza kao dodatne međupodatke. Treba napomenuti da složene semantičke i sintaktičke strukture jezika mogu rezultirati dodatnim prolazima potrebnim za uspostavljanje potrebnih ovisnosti. Ukupan broj prolaza može biti veći od deset. Na broj prolaza također može utjecati programsko korištenje specifičnih jezičnih značajki, kao što je deklariranje varijabli i procedura nakon njihove upotrebe, primjena zadanih pravila deklaracije i tako dalje.

Jednoprolazna organizacija interakcije blokova prevoditelja

Jedna od opcija za interakciju blokova prevoditelja s organizacijom s jednim prolazom prikazana je na slici. 1.8.

U ovom slučaju, proces prevođenja odvija se na sljedeći način. Leksički analizator čita fragment izvornog teksta koji je potreban za dobivanje jednog tokena. Nakon formiranja leksema poziva parser i prosljeđuje mu kreirani leksem kao parametar. Ako parser može konstruirati sljedeći element posredne reprezentacije, on to čini i prosljeđuje konstruirani fragment generatoru koda. U suprotnom, parser vraća kontrolu skeneru, čime daje do znanja da je sljedeći token obrađen i da su potrebni novi podaci.

Generator koda funkcionira na sličan način. Na temelju primljenog fragmenta međureprezentacije kreira odgovarajući fragment objektnog koda. Nakon toga kontrola se vraća parseru.

Po završetku obrade izvornog teksta i završetka obrade svih međupodataka po svakom od blokova, leksički analizator pokreće proces završetka programa.

Najčešće, jednoprolazni prevoditelji koriste drugu kontrolnu shemu, u kojoj parser igra ulogu glavnog bloka (slika 1.9).

Leksički analizator i generator koda djeluju kao potprogrami koje pozivaju. Čim parser treba još jedan token, poziva skener. Kada se primi fragment međureprezentacije, upućuje se poziv generatoru koda. Završetak procesa prevođenja događa se nakon primanja i obrade posljednjeg tokena, a pokreće ga parser.

Prednosti sheme s jednim prolazom uključuju odsutnost velikih količina posrednih podataka, veliku brzinu obrade zbog kombinacije faza u jednom procesu i odsutnost pristupa vanjskim uređajima za pohranu.

Nedostaci uključuju: nemogućnost implementacije takve sheme prevođenja za jezike sa složenim strukturama i nedostatak posrednih podataka koji se mogu koristiti za složenu analizu i optimizaciju.

Takva se shema često koristi za programske jezike koji su jednostavni u semantičkim i sintaktičkim strukturama, kako u kompajlerima tako iu interpreterima. Basic i Pascal su primjeri takvih jezika. Klasični tumač obično se gradi prema shemi s jednim prolazom, budući da se izravno izvođenje provodi na razini pojedinačnih fragmenata međureprezentacije. Organizacija interakcije blokova takvog tumača prikazana je na sl. 1.10.

Kombinirane interakcije blokova prevoditelja

Kombinacije višeprolaznih i jednoprolaznih shema prevođenja dovode do niza kombiniranih opcija, od kojih se mnoge uspješno koriste. Pogledajmo neke od njih kao primjer.

Na sl. 1.11 prikazuje dijagram interakcije blokova prevoditelja, koji cijeli proces dijeli u dva prolaza. U prvom prolazu generira se potpuna međureprezentacija programa, a u drugom prolazu se vrši generiranje koda. Korištenje takve sheme olakšava prijenos prevoditelja s jednog računalnog sustava na drugi prepisivanjem generatora koda.

Osim toga, umjesto generatora koda, lako je spojiti posredni emulator reprezentacije, koji vrlo jednostavno omogućuje razvoj programskog sustava na određenom jeziku koji je orijentiran na različita izvršna okruženja. Primjer takve organizacije interakcije blokova prevoditelja prikazan je na sl. 1.12.

Uz sheme koje uključuju zamjenu generatora koda emulatorom, postoje prevoditelji koji to dopuštaju dijeljenje. Jedna od tih shema prikazana je na sl. 1.13.

Proces prevođenja, uključujući generiranje koda, može se dovršiti u bilo kojem broju prolaza (primjer koristi prijevod s jednim prolazom predstavljen ranije u ). Međutim, generirani objektni kod se ne izvršava na odgovarajućem računalni sustav, ali se emulira na računalu s drugačijom arhitekturom. Takva se shema koristi u okruženju izgrađenom oko programskog jezika Java. Sam prevoditelj generira kod Java virtualnog stroja koji se emulira posebnim sredstvima kako samostalno tako iu okruženju internetskog preglednika.

Prikazana shema može imati širu interpretaciju u odnosu na bilo koji kompilator koji generira strojni kod. Stvar je u tome što je većina modernih računala implementirana pomoću mikroprogramske kontrole. Mikroprogramski upravljački uređaj može se smatrati programom koji emulira strojni kod. To nam omogućuje da govorimo o širokoj upotrebi posljednje predstavljene sheme.

Kontrolna pitanja i zadaci

Navedi razlike:

prevodilac prevoditelj;
kompajler iz asemblera;
transkoder iz prevoditelja;
emulator iz tumača;
sintaksa iz semantike.

Recite nam o najnovijim dostignućima u programskim jezicima koje poznajete. Navedite glavne karakteristike ovih jezika.
Navedite konkretne primjere korištenja metoda prevođenja u područjima koja nisu povezana s programskim jezicima.
Navedite konkretne primjere kompiliranih programskih jezika.
Navedite konkretne primjere interpretiranih programskih jezika.
Navedite konkretne primjere programskih jezika za koje su dostupni i kompajleri i interpreteri.
Glavne prednosti i nedostaci kompilatora.
Glavne prednosti i nedostaci tumača.
Opišite glavne razlike u sintaksi dva programska jezika koja poznajete.
Opišite glavne razlike u semantici dva programska jezika koja poznajete.
Navedite glavne faze procesa prevođenja i njihovu svrhu.
Navedite specifičnosti jednoprolaznog prevođenja.
Navedite specifičnosti višeprolaznog prevođenja.
Navedite primjere mogućih kombinacija jednoprolaznog i višeprolaznog prevođenja. Recite nam nešto o praktičnoj upotrebi ovih shema.

Pošaljite svoj dobar rad u bazu znanja jednostavno je. Koristite obrazac u nastavku

Studenti, diplomanti, mladi znanstvenici koji koriste bazu znanja u svom studiju i radu bit će vam vrlo zahvalni.

Domaćin na http://www.allbest.ru

Uvod

1.1 Raščlanjivanje odozgo prema dolje

1.2 Raščlanjivanje odozdo prema gore

1.2.1 LR(k) - gramatike

1.2.1.1 LR(0) - gramatike

1.2.2 LALR(1) gramatike

2. Razvoj prevoditelja

2.1 Analiza zahtjeva

2.2 Dizajn

2.2.1 Dizajniranje leksičkog analizatora

2.2.4 Softverska implementacija parsera

2.3 Kodiranje

2.4 Ispitivanje

Zaključak

Popis korištenih izvora

Dodatak A. Popis programskog teksta prevoditelja

Dodatak B. Rezultati ispitivanja

Dodatak C. Shema programa prevoditelja

Uvod

Davno su prošli dani kada je prije pisanja programa bilo potrebno razumjeti i zapamtiti više od desetak strojnih instrukcija. Moderni programer formulira svoje zadatke u programskim jezicima visoke razine i koristi asemblerski jezik samo u iznimnim slučajevima. Kao što je poznato, algoritamski jezici postaju dostupni programeru tek nakon stvaranja prevoditelja s tih jezika.

Programski jezici se prilično razlikuju jedni od drugih u svrhu, strukturi, semantičkoj složenosti, metodama implementacije. To nameće svoje specifičnosti razvoju pojedinih prevoditelja.

Programski jezici su alati za rješavanje problema u različitim predmetnim područjima, što određuje specifičnosti njihove organizacije i razlike u namjeni. Primjeri uključuju Fortran za znanstveno računanje, C za sistemsko programiranje, Prolog za učinkovito opisivanje problema zaključivanja i Lisp za rekurzivnu obradu popisa. Ovi primjeri se mogu nastaviti. Svako od predmetnih područja ima svoje zahtjeve za organizaciju samog jezika. Stoga možemo primijetiti raznolikost oblika predstavljanja operatora i izraza, razliku u skupu osnovnih operacija, smanjenje učinkovitosti programiranja pri rješavanju problema koji nisu povezani s predmetnim područjem. Jezične razlike odražavaju se i na strukturu prevoditelja. Lisp i Prolog se najčešće izvode u interpretativnom načinu jer koriste dinamičko generiranje tipa podataka tijekom izračuna. Fortranove prevoditelje karakterizira agresivna optimizacija rezultirajućeg strojnog koda, što postaje moguće zahvaljujući relativno jednostavnoj semantici jezičnih konstrukcija - posebice zbog nepostojanja alternativnih mehanizama imenovanja varijabli putem pokazivača ili referenci. Prisutnost pokazivača u jeziku C nameće posebne zahtjeve na dinamičku dodjelu memorije.

Struktura jezika karakterizira hijerarhijske odnose između njegovih koncepata, koji su opisani sintaktičkim pravilima. Programski jezici mogu se međusobno jako razlikovati u organizaciji pojedinačnih koncepata i u odnosu među njima. Programski jezik PL/1 dopušta proizvoljno ugniježđivanje procedura i funkcija, dok u C-u sve funkcije moraju biti na vanjskoj razini ugniježđivanja. Jezik C++ dopušta deklaraciju varijabli u bilo kojem trenutku programa prije njegove prve uporabe, dok u Pascalu varijable moraju biti definirane u posebnom deklaracijskom području. PL/1 ide još dalje po ovom pitanju, što dopušta da se varijabla deklarira nakon što je korištena. Ili možete potpuno izostaviti opis i slijediti zadana pravila. Ovisno o donesenoj odluci, prevoditelj može analizirati program u jednom ili više prolaza, što utječe na brzinu prijevoda.

Uz tradicionalno proceduralno programiranje, koje se također naziva imperativnim, postoje paradigme kao što su funkcionalno programiranje, logičko programiranje i objektno orijentirano programiranje. Struktura koncepata i objekata jezika snažno ovisi o odabranoj paradigmi, što također utječe na implementaciju prevoditelja.

Čak se isti jezik može implementirati na nekoliko načina. To je zbog činjenice da teorija formalnih gramatika dopušta različite metode raščlanjivanja istih rečenica. Sukladno tome, prevoditelji na različite načine mogu dobiti isti rezultat (objektni program) iz izvornog izvornog teksta.

Međutim, svi programski jezici imaju niz zajedničkih karakteristika i parametara. To zajedništvo također određuje principe organiziranja prevoditelja koji su slični za sve jezike.

Programski jezici osmišljeni su kako bi olakšali programiranje. Stoga su njihovi operatori i podatkovne strukture moćniji nego u strojnim jezicima.

Da bi se povećala vidljivost programa, umjesto numeričkih kodova koriste se simbolički ili grafički prikazi jezičnih konstrukata koji su prikladniji za njihovu percepciju od strane osobe.

Za bilo koji jezik definirano je:

- skup simbola pomoću kojih se mogu napisati ispravni programi (abeceda), osnovni elementi,

- set ispravnih programa (sintaksa),

- "značenje" svakog ispravnog programa (semantika).

Bez obzira na specifičnosti jezika, bilo koji prevoditelj može se smatrati funkcionalnim pretvaračem F koji omogućuje nedvosmisleno preslikavanje X u Y, gdje je X program u izvornom jeziku, Y je program u izlaznom jeziku. Stoga se sam proces prevođenja može formalno prikazati sasvim jednostavno i jasno: Y = F(X).

Formalno, svaki točan program X je niz simbola neke abecede A, koji se transformira u odgovarajući niz Y, sastavljen od simbola abecede B.

Programski jezik, kao i svaki složeni sustav, definiran je kroz hijerarhiju koncepata koja definira odnos između njegovih elemenata. Ovi pojmovi su međusobno povezani u skladu sa sintaktičkim pravilima. Svaki od programa izgrađenih prema ovim pravilima ima odgovarajuću hijerarhijsku strukturu.

U tom smislu, za sve jezike i njihove programe mogu se dodatno razlikovati sljedeće zajedničke značajke: svaki jezik mora sadržavati pravila koja omogućuju generiranje programa koji odgovaraju tom jeziku ili prepoznavanje korespondencije između pisanih programa i danog jezika.

Još jedna karakteristična značajka svih jezika je njihova semantika. Određuje značenje jezičnih operacija, ispravnost operanda. Lanci koji imaju istu sintaktičku strukturu u različitim programskim jezicima mogu se razlikovati u semantici (što se, na primjer, opaža u C++, Pascal, Basic). Poznavanje semantike jezika omogućuje njegovo odvajanje od njegove sintakse i korištenje za pretvaranje u drugi jezik (za generiranje koda).

Svrha ovog kolegija je razviti prevoditelja za obuku sa zadanim pojednostavljenim jezik teksta visoka razina.

1. Metode raščlanjivanja

Razmotrite osnovne metode gramatičke analize.

1.1 Raščlanjivanje odozgo prema dolje

Prilikom raščlanjivanja od vrha prema dolje, međuzaključci se kreću duž stabla u smjeru od korijena prema lišću. U ovom slučaju, kada se lanac gleda slijeva na desno, prirodno će se dobiti lijevi zaključci. U determinističkom parsiranju, problem bi bio koje pravilo primijeniti za proširenje krajnjeg lijevog neterminala.

1.1.1 LL(k) - jezici i gramatike

Razmotrite izlazno stablo u procesu dobivanja lijevog izlaza lanca. Međulanac u procesu izlaza sastoji se od lanca terminala w, krajnjeg lijevog ne-terminala A, ispod tiskanog dijela x:

-S--

/ \

/ -A-x-\

/ | \

-w---u----

Slika 1

Za nastavak parsiranja potrebno je zamijeniti neterminal A prema jednom od pravila oblika A:y. Ako je potrebno da raščlanjivanje bude determinističko (bez praćenja unatrag), ovo pravilo mora biti odabrano na poseban način. Kaže se da gramatika ima svojstvo LL(k) ako je, da bi se odabralo pravilo, dovoljno uzeti u obzir samo wAx i prvih k znakova nepretraženog niza u. Prvo slovo L (lijevo, lijevo) odnosi se na gledanje ulaznog niza slijeva na desno, drugo - na korišteni lijevi izlaz.

Definiramo dva skupa lanaca:

a) FIRST(x) - skup terminalnih nizova izvedenih iz x, skraćenih na k znakova.

b) FOLLOW(A) - skup terminalnih nizova skraćenih na k, koji mogu odmah slijediti A u izlaznim nizovima.

Gramatika ima svojstvo LL(k) ako iz postojanja dvaju lanaca lijevih zaključaka:

S::wAx:wzx::wu

S::wAx:wtx::wv

uvjet FIRST(u)=FIRST(v) implicira z=t.

U slučaju k=1, za odabir pravila za A dovoljno je znati samo ne-terminal A i a - prvi znak niza u:

- odaberite pravilo A:x ako je a u FIRST(x),

- pravilo A:e treba odabrati ako je a uključeno u FOLLOW(A).

LL(k)-svojstvo nameće prilično jaka ograničenja na gramatiku. Na primjer, LL(2) gramatika S: aS | a nema svojstvo LL(1), jer PRVI(aS)=PRVI(a)=a. U ovaj slučaj možete smanjiti vrijednost k koristeći "faktorizaciju" (stavljanje faktora u zagrade):

S:aA

O: S | e

Svaka LL(k)-gramatika je jedinstvena. Lijevo-rekurzivna gramatika ne pripada LL(k) ni za jedno k. Ponekad je moguće pretvoriti ne-LL(1) gramatiku u njenu ekvivalentnu LL(1) gramatiku eliminacijom lijeve rekurzije i faktorizacije. Međutim, problem postojanja ekvivalentne LL(k)-gramatike za proizvoljnu ne-LL(k)-gramatiku je neriješiv.

1.1.2 Metoda rekurzivnog spuštanja

Metoda rekurzivnog spuštanja usmjerena je na one slučajeve kada je prevodilac programiran na jednom od jezika visoke razine, kada je dopuštena uporaba rekurzivnih procedura.

Osnovna ideja rekurzivnog spuštanja je da je svaki neterminal gramatike povezan s procedurom koja prepoznaje bilo koji niz koji generira ovaj neterminal. Ove procedure pozivaju jedna drugu kada je potrebno.

Rekurzivno spuštanje može se koristiti za bilo koju LL(1) gramatiku. svaki ne-terminal gramatike odgovara proceduri koja počinje prijelazom na izračunatu oznaku i sadrži kod koji odgovara svakom pravilu za ovaj ne-terminal. Za one ulazne simbole koji pripadaju skupu izbora danog pravila, izračunati prijelaz prenosi kontrolu na kod koji odgovara ovom pravilu. Za ostale znakove unosa kontrola prelazi na rutinu za obradu grešaka.

Kod bilo kojeg pravila sadrži operacije za svaki znak uključen u desnu stranu pravila. Operacije su navedene redoslijedom kojim se simboli pojavljuju u pravilu. Nakon posljednje operacije kod sadrži povrat iz procedure.

Korištenje rekurzivnog spuštanja u jeziku visoke razine olakšava programiranje i otklanjanje pogrešaka.

1.2 Raščlanjivanje odozdo prema gore

Razmotrimo raščlanjivanje odozdo prema gore, u kojem se srednji zaključci kreću duž stabla prema korijenu. Ako čitate znakove niza slijeva nadesno, stablo će izgledati ovako:

-S--

/ \

/-x-\

/ | \

--w--b--u-

Slika 2

Međuizlaz ima oblik xbu, gdje je x lanac terminala i ne-terminala iz kojeg izlazi skenirani dio lanca terminala w, bu je neskenirani dio lanca terminala, b je sljedeći znak. Za nastavak parsiranja možete ili dodati znak b skeniranom dijelu lanca (izvršiti tzv. "pomak"), ili odabrati na kraju x takav lanac z (x=yz) da jedna od gramatika pravila B:z mogu se primijeniti na z i zamijeniti x na lanac yB (izvesti takozvanu "konvoluciju"):

-S-- -S--

/ \ / \

/-x-b- \ /yB- \

/ | \ / | \

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

Slika 3 - Nakon pomaka Slika 4 - Nakon konvolucije

Ako se konvolucija primijeni samo na zadnje znakove od x, tada ćemo dobiti ispravne zaključke lanca. Ova analiza se naziva LR, gdje se simbol L (lijevo, lijevo) odnosi na gledanje lanca slijeva na desno, a R (desno, desno) se odnosi na rezultirajući izlaz.

Redoslijed smjena i ugovornih operacija je bitan. Stoga determinističko parsiranje zahtijeva da birate između pomaka i kontrakcije (i različitih pravila konvolucije) u svakom trenutku.

1.2.1 LR(k) - gramatike

Ako je, tijekom LR parsiranja, moguće donijeti determinističku odluku o pomaku/sažimanju uzimajući u obzir samo niz x i prvih k znakova neskeniranog dijela ulaznog niza u (ovih k znakova naziva se prethodni niz), gramatika kaže se da ima LR(k)-svojstvo.

-S--

/ \

/-x-\

--w----u--

Slika 5

Razlika između LL(k)- i LR(k)-gramatika u smislu derivacijskog stabla:

-S-

/ | \

/A\

/ / \ \

-w---v---u-

Slika 6

U slučaju LL(k)-gramatika, jednoznačno se može odrediti pravilo primijenjeno na A pomoću w i prvih k simbola od vu, a u slučaju LR(k)-gramatika, pomoću w,v i prvih k simboli u. Ovaj labavi argument pokazuje da LL(k)-jezici< LR(k)-языки (при k > 0).

1.2.1.1 LR(0) - gramatike

Razmotrimo prvo najjednostavnije gramatike ove klase - LR(0). Prilikom raščlanjivanja niza u LR(0)-jeziku, uopće ne morate koristiti vodeći lanac - izbor između pomaka i kontrakcije se vrši na temelju niza x. Budući da se mijenja samo s desnog kraja tijekom parsiranja, naziva se stog. Pretpostavit ćemo da u gramatici nema beskorisnih znakova i da se početni znak ne pojavljuje u pravim dijelovima pravila - tada konvolucija do početnog znaka signalizira uspješan završetak raščlanjivanja. Pokušajmo opisati skup lanaca terminala i ne-terminala koji se pojavljuju na stogu tijekom svih LR parsiranja (drugim riječima, svi ispravni zaključci iz gramatike).

Definiramo sljedeće skupove:

L(A:v) - lijevi kontekst pravila A:v - skup stanja stoga, neposredno prije kolapsa v u A tijekom svih uspješnih LR parsiranja. Očito, svaki niz u L(A:v) završava na v. Ako se odsječe rep v svih takvih lanaca, tada dobivamo skup lanaca koji se pojavljuju lijevo od A u procesu svih uspješnih desnih zaključaka. Označimo ovaj skup L(A) - lijevi kontekst neterminala A.

Konstruirajmo gramatiku za skup L(A). Terminali i ne-terminali izvorne gramatike bit će terminali nove gramatike; ne-terminali nove gramatike bit će označeni ,... - njihove vrijednosti će biti lijevi konteksti ne-terminala izvorne gramatike. Ako je S početni simbol izvorne gramatike, tada će gramatika lijevog konteksta sadržavati pravilo : e - lijevi kontekst od S sadrži prazan niz Za svako pravilo izvorne gramatike, npr. A: B C d E

i dodajte pravila novoj gramatici:

: - L(B) uključuje L(A)

: B - L(C) uključuje L(A) B

: B C d - L(E) uključuje L(A) B C d

Dobivena gramatika ima posebna vrsta(takve se gramatike nazivaju lijevo-linearnim), otuda i skupovi lijevih konteksta

- su redoviti. Iz ovoga slijedi da se članstvo niza u lijevom kontekstu nekog neterminala može izračunati induktivno pomoću konačnog automata, skeniranjem niza slijeva na desno. Opišimo ovaj proces konstruktivno.

Nazovimo LR(0)-situaciju gramatičko pravilo s jednom označenom pozicijom između simbola desne strane pravila. Na primjer, za gramatiku S:A; A: aAA; A:b postoje sljedeće LR(0)-situacije: S:_A; S:A_; A:_aAA; A:a_AA; A:aA_A; A:aAA_; A:_b; A:b_. (pozicija je označena podvlakom).

Reći ćemo da je lanac x konzistentan sa situacijom A:b_c ako je x=ab i a pripada L(A). (Drugim riječima, LR zaključivanje može se nastaviti x_... = ab_...:: abc_...:: aA_...:: S_.) U ovim terminima, L(A:b) je skup nizovi koji odgovaraju situaciji A:b_, L(A)

- lanci konzistentni sa situacijom A:_b za bilo koje pravilo A:b.

Neka je V(u) skup situacija u skladu s u. Pokažimo da je funkcija V induktivna.

Ako skup V(u) uključuje situaciju A:b_cd, tada situacija A:bc_d pripada V(uc). (c - terminal ili neterminal; b, d - nizovi (mogu biti prazni) terminala i neterminala). Ne postoje druge situacije poput A:b_d, s nepraznim b u V(uc). Ostaje dodati situacije oblika C:_... u V(uc) za svaki neterminal C čiji lijevi kontekst sadrži uc. Ako situacija A:..._C... (C-neterminal) pripada skupu V(uc), tada uc pripada L(C) i V(uc) uključuje situacije oblika C:_... za sva C- gramatička pravila.

V(e) sadrži situacije S:_... (S-početni znak), kao i situacije A:_... ako se ne-terminal A pojavljuje neposredno nakon _ u situacijama koje su već uključene u V(e) .

Konačno, spremni smo za definiranje LR(0) gramatike. Neka u bude sadržaj stoga tijekom LR parsiranja, i neka V(u) bude skup LR(0) situacija koje su u skladu s u. Ako V(u) sadrži situaciju oblika A:x_ (x-slijed terminala i neterminala), tada u pripada L(A:x) i x se može saviti u A. Ako V(u) sadrži situaciju A:..._a... (a-terminal), tada je dozvoljen pomak. Govori se o sukobu shift-reduce ako su i pomak i kontrakcija dopušteni za isti niz u. Govori se o sukobu odustajanja i odustajanja ako su odustajanja dopuštena prema različitim pravilima.

Gramatika se naziva LR(0) ako nema sukoba shift-fold ili roll-down za sva stanja stoga u procesu zaključivanja LR.

1.2.1.2 LR(k) - gramatike

Samo se stanje stoga koristi u LR(0) raščlanjivanju za odabir između pomaka ili skupljanja. LR(k) raščlanjivanje također uzima u obzir k-prvih znakova nevidljivog dijela ulaznog niza (tzv. predniz). Da bi se opravdala metoda, treba pažljivo ponoviti argumente iz prethodnog odjeljka, unoseći izmjene u definicije.

Također ćemo uključiti lanac unaprijed u lijevom kontekstu pravila. Ako desna derivacija koristi derivaciju wAu: wvu, tada par wv,FIRSTk(u) pripada Lk(A:v), a par w,FIRSTk(u) pripada Lk(A). Skup lijevih konteksta, kao u slučaju LR(0), može se izračunati pomoću indukcije na lijevom lancu. Nazovimo LR(k)-situaciju par: gramatičko pravilo s označenom pozicijom i prethodni lanac duljine najviše k. Pravilo ćemo odvojiti od naprednog lanca okomitom crtom.

Reći ćemo da je lanac x konzistentan sa situacijom A:b_c|t ako postoji LR-izlaz: x_yz = ab_yz:: abc_z:: aA_z:: S_, i FIRSTk(z)=t. Pravila za induktivni izračun skupa stanja Vk su sljedeća:

Vk(e) sadrži S:_a|e situacije za sva S:a pravila, gdje je S početni znak. Za svaku situaciju A:_Ba|u iz Vk(e), svako pravilo B:b i lanac x koji pripada FIRSTk(au), situacija B:_b|x mora se dodati u Vk(e).

Ako situacija A:b_cd|u ulazi u Vk(w), tada će situacija A:bc_d|u pripadati Vk(wc). Za svaku situaciju A:b_Cd|u iz Vk(wc), svako pravilo C:f i lanac x koji pripada FIRSTk(du), moramo dodati situaciju C:_f|x u Vk(wc).

Koristimo konstruirane skupove LR(k)-stanja za rješavanje problema pomaka-konvolucije. Neka je u sadržaj steka, a x lanac napredovanja. Očito, A:b konvolucija se može izvesti ako Vk(u) sadrži situaciju A:b_|x. Odlučivanje je li pomak dopušten zahtijeva točnost ako gramatika sadrži e-pravila. U situaciji A:b_c|t (c nije prazno), pomak je moguć ako c počinje s terminala i x pripada FIRSTk(ct). Neslužbeno govoreći, možete gurnuti krajnji lijevi znak desne strane pravila na stog, pripremajući naknadnu konvoluciju. Ako c počinje s ne-terminala (situacija izgleda kao A:b_Cd|t), tada je guranje simbola na stog, pripremajući preklop u C, moguće samo ako C ne generira prazan niz. Na primjer, u stanju V(e)= S:_A|e; A:_AaAb|e,a, A:_|e,a pri izvođenju terminalnih lanaca iz A, u nekom koraku potrebno je primijeniti pravilo A:e na ne-terminal A koji se nalazi na lijevom kraju lanca.

Definirajmo skup EFFk(x) koji se sastoji od svih elemenata skupa FIRSTk(x) čija derivacija ne zamjenjuje neterminal na lijevom kraju od x (ako postoji) s praznim nizom. U ovim terminima, pomak je dopustiv ako skup Vk(u) sadrži situaciju A:b_c|t, c nije prazan, a x pripada EFFk(ct).

Gramatika se naziva LR(k)-gramatika ako nijedno LR(k) stanje ne sadrži dvije situacije A:b_|u i B:c_d|v takve da u pripada EFFk(dv). Takav par odgovara sukobu savijanja i savijanja ako je d prazan, i sukoba pomaka i savijanja ako d nije prazan.

U praksi se LR(k) gramatike ne koriste za k>1. Dva su razloga za to. Prvo: vrlo velik broj LR(k) stanja. Drugo, za svaki jezik definiran LR(k) gramatikom, postoji LR(1) gramatika; štoviše, postoji LR(1)-gramatika za svaki deterministički CF-jezik.

Broj LR(1)-stanja za praktički zanimljive gramatike također vrlo velik. Takve gramatike rijetko imaju svojstvo LR(0). U praksi se češće koristi metoda između LR(0) i LR(1), poznata kao i LALR(1).

1.2.2 LALR(1) gramatike

Ove dvije metode temelje se na istoj ideji. Konstruirajmo skup kanonskih LR(0)-stanja gramatike. Ako ovaj skup ne sadrži sukobe, tada se može koristiti LR(0) parser. U protivnom, pokušat ćemo riješiti sukobe koji su se pojavili razmatranjem predniza od jednog znaka. Drugim riječima, pokušajmo izgraditi LR(1) parser sa skupom LR(0) stanja.

Metoda LALR(1) (Look Ahead) je sljedeća. Uvedimo relaciju ekvivalencije na skupu LR(1)-situacija: smatrat ćemo dvije situacije ekvivalentnima ako se razlikuju samo u prethodnim lancima. Na primjer, situacije A:Aa_Ab|e i A:Aa_Ab|a su ekvivalentne. Konstruirajmo kanonski skup LR(1)-stanja i ujedinimo stanja koja se sastoje od skupa ekvivalentnih situacija.

Ako rezultirajući skup stanja ne sadrži LR(1) sukobe, i stoga nam omogućuje konstruiranje LR(1) parsera, tada se kaže da gramatika ima svojstvo LALR(1).

2. Razvoj prevoditelja

2.1 Analiza zahtjeva

U ovom kolegiju potrebno je razviti trening prevoditelja u obliku tumača s jezika definiranog odgovarajućom formalnom gramatikom. Postoje četiri glavne faze u razvoju tumača:

Dizajniranje leksičkog analizatora;

Projektiranje stroja za časopis;

Implementacija softvera parser;

Razvoj modula tumačenja.

Razvoj će se provoditi pomoću operativnog Windows sustavi XP uključen osobno računalo IBM PC s procesorom Intel Pentium IV.

Na temelju trendova razvoja softver Programski jezik C# u Visual Studio 2010 odabran je za implementaciju prevoditelja za obuku.

2.2 Dizajn

2.1.1 Dizajniranje leksičkog analizatora

Leksička analiza uključuje skeniranje prevedenog (izvornog) programa i prepoznavanje leksema koji čine rečenice izvornog teksta. Tokeni uključuju, posebno, ključne riječi, operacijske znakove, identifikatore, konstante, posebne znakove itd.

Rezultat rada leksičkog analizatora (skenera) je niz tokena, a svaki token obično je predstavljen nekim kodom fiksne duljine (na primjer, cijeli broj), kao i izdavanje poruka o sintaktičkom (leksičkom ) pogreške, ako ih ima. Ako je leksem, na primjer, ključna riječ, tada njegov kod daje cjelinu potrebne informacije. U slučaju, na primjer, identifikatora, dodatno je potreban naziv prepoznatog identifikatora, koji se obično bilježi u tablici identifikatora, organiziranoj, u pravilu, pomoću popisa. Slična tablica je potrebna za konstante.

Leksem se može opisati s dva glavna obilježja. Jedan od njih je pripadnost leksema određenoj klasi (varijable, konstante, operacije itd.) Drugi atribut definira određeni element ove klase.

Posebna vrsta tablice simbola (struktura podataka) je irelevantna za lexer ili parser. Oba trebaju samo pružiti mogućnost dobivanja indeksa koji jedinstveno identificira, na primjer, danu varijablu i vratiti vrijednost indeksa za dopunjavanje informacija o danom nazivu varijable u tablici simbola.

Pregled tablice identifikatora obavlja dvije glavne funkcije:

a) upisivanje novog imena u tablicu prilikom obrade deklaracije varijabli;

b) traženje imena koje je prethodno zabilježeno u tablici.

To omogućuje otkrivanje takvih pogrešnih situacija kao što je višestruki opis varijable i prisutnost nedeklarisane varijable.

Razvoj leksičkog analizatora djelomično se sastoji od modeliranja raznih automata za prepoznavanje identifikatora, konstanti, rezerviranih riječi itd. Ako tokeni drugačiji tip početi s istim znakom ili istim nizom znakova, možda će biti potrebno kombinirati njihovo prepoznavanje.

Pokretanjem leksičkog analizatora razbijamo naš program na tokene, nakon čega svaki token prolazi provjeru duljine (token ne može imati više od 11 znakova). Nakon uspješnog prolaska ove faze, provjeravamo ispravnost lokacije tokena (ključne riječi var, begin, end, for, to, do, end_for). Zatim analiziramo varijabilne žetone - ne smiju sadržavati brojeve u svom opisu i ponavljati se. Na posljednji korak provjeriti pravopis tokena (ključne riječi, nepoznati identifikatori). Ako barem jedna od provjera izbaci pogrešku, leksički analizator ispisuje pogrešku.

Shema programa rada leksičkog analizatora data je u Prilogu B na slici B.1.

2.2.2 Projektiranje automatskog spremnika

Definirajmo sljedeću gramatiku:

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

gdje je Vt skup terminalnih simbola, Va skup neterminalnih simbola, I početno stanje gramatike, R skup gramatičkih pravila.

Za ovu gramatiku definiramo skupove terminalnih i neterminalnih simbola:

Sastavimo pravila za našu gramatiku G i predstavimo ih u tablici 1.

Tablica 1 - Gramatička pravila

broj pravila	Lijeva strana pravila	Desna strana pravila








		f ID = EX t EX d LE n;













Nastavak tablice 1.
broj pravila	Lijeva strana pravila	Desna strana pravila

Oznake leksema, prijevod leksema u kodove i popis gramatičkih oznaka dani su u tablicama 2, 3, 4. redom.

Tablica 2 - Zapis leksema

	Bilježenje leksema
	ključna riječ "početak" (početak opisa radnji)
	ključna riječ "end" (kraj opisa radnji)
	ključna riječ "var" (deklaracija varijabli)
	ključna riječ "čitaj" (izjava za unos podataka)
	ključna riječ "write" (izjava za izlaz podataka)
	ključna riječ "za" (naredba petlje)
	ključna riječ "do"
	ključna riječ "učiniti"
	ključna riječ "end_case" (naredba o kraju petlje)
	tip varijable "cijeli broj"
	operacija zbrajanja
	operacija oduzimanja
	operacija množenja
	znak razdjelnika ":"
	znak razdjelnika ";"
	znak razdjelnika "("
	znak za razdvajanje ")"
	znak razdjelnika ","
	Bilježenje leksema
	znak razdjelnika "="

Tablica 3 - Prijevod leksema u kodove












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

Tablica 4 - Popis gramatičkih simbola

Oznaka	Obrazloženje
	Program
	Opis izračuna
	Opis varijabli
	Popis varijabli
	Operater
	Zadatak
	Izraz
	podizraz
	Binarne operacije
	Unarne operacije
	Popis zadataka
	Identifikator
	Konstantno

Konstruirajmo deterministički uzlazni prepoznavač.

Razmotrite sljedeće odnose kako biste izgradili deterministički rezolver odozdo prema gore:

a) Ako postoji grupni simbol B takav da je niz AB uključen u neko gramatičko pravilo i postoji simbol xPERV "(B), tada ćemo pretpostaviti da su između simbola x i A definirani odnosi x NAKON A

b) Ako u danoj gramatici postoji pravilo B-\u003e bAb A, BV a, tada je između A i x određena relacija A PRETVORI x.

Sva naša gramatika ostaje ista, to jest:

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

a gramatička pravila D data su u tablici 5.

Tablica 5 - Gramatička pravila

broj pravila	Lijeva strana pravila	Desna strana pravila








		f ID = EX t EX d LE n;?














Nastavak tablice 5.
broj pravila	Lijeva strana pravila	Desna strana pravila

Gdje? - marker za kraj lanca.

Definirajmo neke slučajeve:

a) ID se sastoji od skupa slova latinične abecede, odnosno pretpostavit ćemo da je 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 konstanta se sastoji od brojeva, odnosno pretpostavit ćemo da je k = (0,1,2,3,4,5,6,7,8,9)

Da bi naša gramatika bila strategija mješovitog prvenstva, moraju biti ispunjeni sljedeći uvjeti:

a) Nepostojanje e-pravila

b) Postoje li pravila prema kojima x NAKON A? A PRETVORI x = ?

c) A -> bYg

a potrebno je da IN NAKON x? U PRETVORI x = ?

tj. u gramatici će se izvesti IN NAKON x ili A NAKON x, gdje je x znak-predikat lanca b.

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

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

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

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

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

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

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

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

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

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

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

PERV" (UO) = (UO,-)

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

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

PERV" (b) =( b)

PERV" (e) =( e)

PERV" (v) =( v)

PERV" (w) =( w)

PERV" (r) =( r)

PERV" (i) =( i)

PERV" (f) =( f)

PERV" (d) = (d)

PERV" (n) =( n)

PERV" (c) =( c)

PERV" (+) =( +)

PERV" (*) =( *)

PERV" (-) =(-)

PERV" (,) =(,)

PERV" (;) =(;)

PERV" (:) =(:)

PERV" (=) = ( = )

PERV" (() =( ()

PERV" ()) =() )

PERV" (u) =(u)

PERV" (k) = (k)

b) SLJEDEĆI `(AL) = (?)?SLJEDEĆI"(PG)=(?,b,e)

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

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

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

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

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

DALJE ` (BO) = (?)?PRVI"(SB)= (?, (,), OP, BO)

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

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

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

DALJE `(ID)=(?)? SLJEDEĆI" (OP) ? PRVI" (=) =(?,;,), d, t, +, -, *, =)

DALJE `(CO) = (?)? SLJEDEĆI" (OP)= (?,;,), d, t, +, -, *, =)

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

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

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

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

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

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

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

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

DALJE ` (n) =(?)?PRIM"(i) = (?, i )

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

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

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

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

DALJE ` (:) =(?)?PRIM"(i)= (?, i )

DALJE ` (=) = (?)?PRVI"(EX) = (? (,), u, k, +, -, *)

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

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

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

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

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

c) PG -> DE AL

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

e NAKON LE = ((e LE))

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

;NAKON i = ((; i))

i NAKON: = ( (i:) )

: NAKON LV = ( (: LV) )

LV NAKON v = ( (ID, v) )

LV POSLIJE, = ((ID,))

NAKON ID = ((,u))

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

LE -> r (DE);

; POSLIJE) = ((;)))

) NAKON DE = (((DE))

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

(NAKON r = (((r))

LE -> w (DE);

; POSLIJE) = ((;)))

) ZADNJI DE = (((DE))

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

(NAKON w = (((w))

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

; NAKON n = ((;n))

n NAKON LE = ( (n, LE))

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

d NAKON EX = ((d, EX))

EX POSLIJE t = (BO, -) ? NAKON t = ((BO t), (- t))

t NAKON EX = ( t EX)

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

NAKON ID=((=ID))

ID NAKON f = ((ID f))

EQ -> ID = EX;

; NAKON EX = ((; EX )

EX AFTER == (BO, -) ? NAKON == ((BO=), (-=))

NAKON u = ( (=u))

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

) NAKON EX = ( ()EX) )

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

SB->SB BO SB

SB NAKON BO = ((,), OP, BO) NAKON BO = (((BO), ()BO), (OP BO), (BO BO))

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

ID NAKON u = ((u, u))

G) PG ->DE AL

AL ROLL PG = AL ROLL NEXT" (PG) = ((AL ?))

e KOTRI AL = e KORITI SLJEDEĆI"(AL)= ((eb), (e?))

=; FOLD NEXT"(DE) = ((;b), (;?))

LV PROTOK LV = LV PROTOK SLJEDEĆI" (LV) = ((LV:), (LV?))

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

; PRETVORI LE=; FOLD NEXT" (LE) = ((; e), (;?), (;n))

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

; PRETVORI LE=; FOLD NEXT" (LE) = ((; e), (;?), (;n))

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

EQ -> ID = EX;

; PRETVORI EQ=; FOLD NEXT" (EQ) = ((; (), (;)), (;;), (;f), (;?), (;=), (;t), (;d), (; n), (;w), (;r))

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

) SB ROLL = SB SLJEDEĆI ROLL" (SB) = (() t), ()?), () d), ())), ();))

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

SB->SB BO SB

SB ROLL SB = SB ROLL NEXT" (SB) = ((SB, t), (SBd), (SB;). (SB)), (SB+), (SB-), (SB*), (SB? ) }

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

BACI BO = + BACI SLJEDEĆI" (BO) = ((++), (+?), (+*), (+-))

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

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

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

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

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

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

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

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

Jedna konfliktna situacija pronađena prilikom sklapanja pravila

OP ->ID i ID -> u ID

Upisujemo ID1 -> ID, stoga prepisujemo pravilo ID1 -> u ID

Stoga ćemo izvršiti operacije konvolucije.

ID1 ROLL ID = ID1 ROLL NEXT" (ID) = ((ID1)), (ID1 ?), (ID1 k), (ID1+), (ID1-), (ID1*), (ID1=), (ID1t) , (ID1d)))

Za svaki par (x, A)? x NAKON A gradimo prijelaznu funkciju koja određuje akciju prijenosa ?? (S 0, x, A) \u003d (S 0, A)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Za svaki par (x, A)? A CONVULT x gradi prijelaznu funkciju koja definira djelovanje konvolucije?? * (S 0, x, bA) \u003d (S 0, B), gdje je 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 Softverska implementacija parsera

Parser (parser) čita datoteku tokena koju je generirao leksički analizator, provodi gramatičku analizu, prikazuje poruke o sintaktičkim pogreškama, ako postoje, i stvara međuoblik izvornog programa. Osnova za razvoj parsera je dizajn i implementacija odgovarajućeg pushdown automata.

Za raščlanjivanje odozdo prema gore za deterministički razrješivač odozdo prema gore, nakon njegovog pretvaranja u prava vrsta potrebno je pomoću funkcija AFTER i CONVERT dizajnirati push-pull stroj s detaljnim opisom svih prijelaza unutar prijelazne funkcije.

Prilikom razvoja pushdown automata izgradili smo prijelazne funkcije koje će biti osnova parsera. Sve prijelazne funkcije mogu se podijeliti u dvije vrste:

Ciklus rada push-pull stroja bez očitavanja ulaznog simbola (prazan ciklus);

Ciklus push-pull automata s čitanjem ulaznog simbola.

Prilikom implementacije leksičkog analizatora, podijelili smo program na tokene i upisali ih u listu. Zatim obrađujemo ovaj popis u parseru. Kao ulaz šaljemo naš program (listu), početni simbol (PG) i donji marker tipke (h0), nakon čega se odabire željena prijelazna funkcija i vrši se rekurzivni poziv.

Shema radnog programa parsera dana je u Dodatku B na slici B.2.

2.2.4 Razvoj modula tumačenja

Pri razvoju interpretacijskog modula kao posrednog oblika izvornog programa najčešće korišteni postfiksni oblik notacije, koji olakšava provedbu procesa izvršavanja (tumačenja) programa koji se prevodi.

Razmotrimo osnovna načela formiranja i izvođenja postfiksnog oblika izraza.

Osnovna pravila za pretvaranje infiks notacije izraza u postfiks su sljedeća.

Operandi za čitanje dodaju se postfiksnoj notaciji, operacije se guraju na stog.

Ako operacija na vrhu stoga ima viši (ili jednak) prioritet od trenutne operacije čitanja, tada se operacija sa stoga dodaje postfiksnom unosu, a trenutna operacija se gura na stog. U suprotnom (s najnižim prioritetom), samo se trenutna operacija gura na stog.

Čitaj otvorenu zagradu gura se na hrpu.

Nakon čitanja zatvorene zagrade, sve operacije do prve otvarajuće zagrade izvlače se iz stoga i dodaju postfiksnom zapisu, nakon čega se i otvarajuća i zatvarajuća zagrada odbacuju, tj. ne stavljaju se na postfiksni zapis ili na hrpu.

Nakon što je cijeli izraz pročitan, preostale operacije na stogu se dodaju postfiksnom unosu.

Postfiksna notacija izraza omogućuje njegovu procjenu na sljedeći način.

Ako je token operand, tada se gura na stog. Ako je token operacija, tada se navedena operacija izvodi na zadnjim elementima (zadnji element) gurnutim na stog, a ti elementi (element) se zamjenjuju na stogu rezultatom operacije.

Ako su leksičke i sintaktičke analize uspješno prošle, prelazimo na tumačenje. Prvo sastavljamo rečenice od riječi, zatim prevodimo izraze u postfiksalni zapis i računamo.

Shema rada tumača data je u Dodatku B na slici B.3.

2.3 Kodiranje

Program je implementiran u C# okruženju Vizualno programiranje Studio 2010. Tekst programa nalazi se u prilogu A.

Program ima pet razreda. Korisničko sučelje implementirano je pomoću klase MainForn. Uz pomoć klase LexAnalysis implementiran je modul leksičke analize, SynAnalysis je modul za raščlanjivanje, Intepreter je modul za tumačenje, ProgramisciJakPolska je pomoćna klasa za prevođenje izraza u obrnuto Poljska notacija(postfiks).

Svrha postupaka i funkcija implementiranih u program opisana je u tablicama 6,7,8.

Tablica 6 - Svrha postupaka i funkcije leksičke analize

Slični dokumenti

Prevoditelj je program ili tehničko sredstvo koje obavlja prevođenje programa. Razmatranje glavnih značajki konstrukcije leksičkog analizatora. Poznavanje faza razvoja prevoditelja iz ograničenog podskupa jezika visoke razine.

seminarski rad, dodan 06.08.2013

Dizajniranje leksičkih analizatora i analizatora raščlanjivanja nastavni jezik. Pravila pretvorbe Booleovi izrazi u POLIZ. Formiranje trijada, optimizacija njihovog popisa. Logička struktura programa. Testiranje prevoditeljsko-tumačkih modula.

seminarski rad, dodan 28.05.2013

Opće karakteristike i ocjena mogućnosti programskog jezika C-sharp, njegove sličnosti i razlike od C++ i Jave. Razvoj uz pomoć ovog programskog jezika leksičkog i parsera. Sastavljanje proračunskih tablica.

seminarski rad, dodan 11.06.2010

Dizajniranje programa analizatora koji se sastoji od dva dijela: leksički analizator koji rastavlja izvorni tekst programa na tokene i popunjava tablicu imena; parser koji provjerava odgovara li tekst zadanoj gramatici.

seminarski rad, dodan 14.06.2010

Pisanje programa koji provodi leksičku i sintaktičku analizu ulaznog programskog jezika, generira tablicu leksema s naznakom njihovih vrsta i vrijednosti, te također gradi sintaktičko stablo; tekst jezika unosa unosi se s tipkovnice.

seminarski rad, dodan 23.02.2012

Tehnika razvoja i djelomična implementacija prevoditelja za jezik "C" korištenjem jezika "C++", koji početni niz znakova dijeli na minimalne nedjeljive jezične konstrukcije na temelju vokabulara jezika. Analiza programa.

seminarski rad, dodan 19.03.2012

Struktura, klasifikacija i zahtjevi za implementaciju prevoditelja. Dizajn i implementacija analitičkog dijela C++ prevoditelja. Načini provedbe leksičke analize. Algoritam parsera. Principi implementacije softvera.

seminarski rad, dodan 26.01.2013

Izrada prevoditelja koji obrađuje programski kod u jeziku Pascal i generira C program koristeći ekvivalentne operatore. Osobitosti vanjska specifikacija te rad leksičkog analizatora. Struktura programa, prikaz rezultata na ekranu.

seminarski rad, dodan 02.07.2011

Metode gramatičke analize. Razvoj strukture obrazovnog prevoditelja u osnovnom programskom jeziku Object Pascal u okruženju objektno orijentiranog vizualnog programiranja Borland DELPHI 6.0 uz korištenje operacijskog sustava Windows XP.

seminarski rad, dodan 12.05.2013

Programska implementacija desktop aplikacije korištenjem C# programskog jezika. Dizajn i struktura korisničko sučelje, zahtjevi za njega i ocjena funkcionalnosti. Izrada korisničkog priručnika i njegovo korištenje.

ODJELJAK 7. Prijevod, kompilacija i tumačenje

Program je slijed instrukcija dizajniranih da ih računalo izvrši. Trenutno su programi napisani u obliku teksta koji se upisuje u datoteke. Ovaj tekst rezultat je aktivnosti programera i unatoč specifičnostima formalni jezik, ostaje program za programera.

Proces izrade programa uključuje nekoliko faza. Nakon faze razvoja projekta programa slijedi faza programiranja. U ovoj fazi program je napisan. Programeri lakše percipiraju ovaj tekst nego binarni kod, budući da razne mnemoničke kratice i imena sadrže dodatne informacije.

Obrađuje se izvorna datoteka programa (koja se naziva i izvorni modul). prevoditelj , koji prevodi program iz programskog jezika u strojno razumljiv niz kodova.

Prevoditelj - softver ili hardver koji obavlja emitiranje programa. Strojni program koji prevodi s jednog jezika na drugi i, posebno, s jednog programskog jezika na drugi. Program za obradu dizajniran za pretvaranje izvornog programa u objektni modul.

Prevoditelj obično također provodi dijagnostiku grešaka, generira rječnike identifikatora, ispisuje tekstove programa itd.

Emitiranje programa - transformacija programa predstavljenog na jednom od programskih jezika u program na drugom jeziku i, u određenom smislu, ekvivalentan prvom.

Poziva se jezik na kojem je predstavljen ulazni program izvorni jezik, i sam program izvorni kod. Poziva se izlazni jezik ciljani jezik ili objektni kod.

Vrste prevoditelja

Prevoditelji se dijele na:

· Adresa. Funkcionalni uređaj koji pretvara virtualnu adresu virtualna adresa) na pravu adresu (eng. memorijska adresa).

· Dijalog. Omogućuje korištenje programskog jezika u načinu dijeljenja vremena.

· višeprolazni. Generira objektni modul preko nekoliko prikaza izvornog programa.

· leđa. Isto kao relej. Vidi također: decompiler, disassembler.

· jedan prolaz. Generira objektni modul u jednom sekvencijalnom skeniranju izvornog programa.

· Optimiziranje. Izvodi optimizacije koda u generiranom objektnom modulu.

· Sintaktički orijentiran (sintaktički vođen). Kao ulaz prima opis sintakse i semantike jezika te tekst na opisanom jeziku, koji se prevodi u skladu s navedenim opisom.

· test. Skup makronaredbi asemblerskog jezika koji vam omogućuju postavljanje različitih postupaka otklanjanja pogrešaka u programima napisanim asemblerskim jezikom.

Prevoditelji su implementirani u obrazac sastavljači ili tumači . U smislu obavljanja posla, kompilator i interpreter su vrlo različiti.

Sastavljač(Engleski) sastavljač- compiler, collector) - prevoditelj koji pretvara program preveden u izvornom jeziku u objektni modul. Program koji prevodi tekst jezičnog programa visoke razine u svoj ekvivalentni program strojnog jezika.

· Program dizajniran za prevođenje jezika visoke razine u apsolutni kod ili, ponekad, u asemblerski jezik. Ulazna informacija za prevodilac (izvorni kod) je opis algoritma ili programa u jeziku specifičnom za domenu, a izlaz prevoditelja je ekvivalentan opis algoritma u strojno orijentiranom jeziku (objektni kod).

Kompilacija- prijevod programa napisanog na izvornom jeziku u objektni modul. Implementirao kompilator.

Prevedi - emitirati strojni program od domensko-specifičnog jezika do strojno orijentiranog jezika.

Kompajler čita cijeli program u cijelosti, prevodi ga i stvara potpunu verziju programa na strojnom jeziku, koji se zatim izvršava.

Tumač(Engleski) tumač- tumač, tumač) prevodi i izvršava program redak po redak. Interpretator uzima sljedeći jezični operator iz programskog teksta, analizira njegovu strukturu, a zatim ga odmah izvršava (obično se nakon analize operator prevodi u neku međureprezentaciju ili čak strojni kod za učinkovitije daljnje izvođenje). Tek nakon uspješnog izvršenja trenutne naredbe, tumač će prijeći na sljedeću. Štoviše, ako se ista naredba izvrši više puta u programu, interpretator će je izvršiti kao da se s njom susreo prvi put. Kao rezultat toga, programi koji zahtijevaju veliki volumen proračuni će biti spori. Osim toga, da biste pokrenuli program na drugom računalu, ondje također mora postojati tumač - uostalom, bez njega je tekst samo skup znakova.

Na drugi način, možemo reći da tumač modelira neke računalne virtualni stroj, za koji osnovne upute nisu elementarne naredbe procesora, već operatori programskog jezika.

Razlike između kompilacije i interpretacije.

1. Nakon što je program preveden, ni izvorni program ni prevodilac više nisu potrebni. U isto vrijeme, program koji tumač obrađuje mora ponovno prijenos u strojni jezik svaki put kada se program pokrene.

2. Prevedeni programi rade brže, ali interpretirane programe lakše je popraviti i promijeniti.

3. Svaki specifični jezik usmjeren je ili na kompilaciju ili na interpretaciju, ovisno o svrsi za koju je stvoren. Na primjer, Pascal obično se koristi za rješavanje prilično složenih problema u kojima je važna brzina programa. Stoga se ovaj jezik obično implementira korištenjem sastavljač.

Na drugoj strani, OSNOVNI, TEMELJNI je stvoren kao jezik za programere početnike, za koje izvođenje programa red po red ima neosporne prednosti.

Gotovo svi programski jezici niske razine i treće generacije, kao što su asembler, C ili Modula-2, mogu se kompajlirati i više jezici visoke razine, poput Pythona ili SQL-a - interpretabilan.

Ponekad za jedan jezik postoji i sastavljač, i tumač. U ovom slučaju, možete koristiti tumač za razvoj i testiranje programa, a zatim kompajlirati otklonjeni program kako biste ubrzali njegovo izvođenje. Postoji međusobno prožimanje procesa prevođenja i tumačenja: tumači mogu biti prevoditelji (uključujući one s dinamičkom kompilacijom), a prevoditelji mogu zahtijevati tumačenje za konstrukcije metaprogramiranja (na primjer, makronaredbe u asemblerskom jeziku, uvjetna kompilacija u C-u ili predlošci u C++ ).

4. Emitiranje i tumačenje - različite procese: prijevod se bavi prevođenjem programa s jednog jezika na drugi, a tumačenje je zaduženo za izvođenje programa. Međutim, budući da je svrha prevođenja obično pripremiti program za usmeno prevođenje, ti se procesi obično razmatraju zajedno.

Zaključak: Nedostatak prevoditelja je zahtjevnost prevođenja programskih jezika koji su orijentirani na podatke i složene strukture, često nepoznati unaprijed ili se dinamički mijenjaju tijekom rada programa. Zatim morate umetnuti puno dodatnih provjera u strojni kod, analizirati dostupnost resursa operativnog sustava, dinamički ih uhvatiti i otpustiti, formirati i obraditi u memoriji računala. složeni objekti, što je prilično teško implementirati na razini tvrdo kodiranih strojnih instrukcija, i gotovo nemoguće za zadatak.

Uz pomoć tumača, naprotiv, dopušteno je zaustaviti program u bilo kojem trenutku, ispitati sadržaj memorije, organizirati dijalog s korisnikom, izvršiti proizvoljno složene transformacije i istovremeno stalno pratiti stanje okruženje softvera i hardvera, čime se postiže visoka pouzdanost. Prilikom izvršavanja svake naredbe, tumač provjerava mnoge karakteristike operacijskog sustava i, ako je potrebno, informira programera što je moguće detaljnije o problemima koji se pojavljuju. Osim toga, prevoditelj je vrlo prikladan za korištenje kao alat za učenje programiranja, jer vam omogućuje razumijevanje principa rada bilo koje pojedinačne izjave u jeziku.

Proces kompilacije podijeljen je u nekoliko faza:

1. Pretprocesor. Izvorni program obrađuje se zamjenom postojećih makronaredbi i datoteka zaglavlja.

2. Leksička i sintaktička analiza. Program se pretvara u niz tokena, a zatim u interni prikaz stabla.

3. Globalna optimizacija. Unutarnji prikaz programa stalno se transformira kako bi se smanjila veličina i vrijeme izvođenja programa.

4. Generiranje koda. Interni prikaz se pretvara u blokove instrukcija procesora, koji se pretvaraju u asemblerski tekst ili objektni kod.

5. Skupština. Ako se generira asemblerski tekst, asemblera se da bi se dobio objektni kod.

6. Skupština. Asembler kombinira više objektnih datoteka u izvršnu datoteku ili biblioteku.

U fazi leksička analiza (LA) ulazni program, koji je tok znakova, podijeljen je na lekseme - riječi u skladu s definicijama jezika. Glavni formalizam koji leži u osnovi implementacije leksičkih analizatora su konačni automati i regularni izrazi. Leksički analizator može raditi u dva glavna načina: ili kao podrutina koju poziva parser nakon sljedećeg tokena ili kao puni prolaz, što rezultira datotekom tokena. U procesu izdvajanja tokena, LA može neovisno graditi tablice imena i konstanti i dati vrijednosti za svaki token sljedeći put kada mu se pristupi. U ovom slučaju, tablica imena se gradi u sljedećim fazama (na primjer, tijekom parsiranja).

U fazi LA otkrivaju se neke (najjednostavnije) pogreške (nevažeći znakovi, neispravno bilježenje brojeva, identifikatori itd.).

Razmotrimo detaljnije fazu leksičke analize.

Glavni zadatak leksičke analize - razbiti unos teksta, koji se sastoji od niza pojedinačnih znakova, u niz riječi, odnosno leksema, tj. izolirajte ove riječi iz kontinuiranog niza znakova. S ove točke gledišta svi znakovi ulaznog niza dijele se na znakove koji pripadaju nekim leksemima i znakove koji razdvajaju lekseme (separatore). U nekim slučajevima možda neće biti razdjelnika između tokena. S druge strane, u nekim jezicima tokeni mogu sadržavati beznačajne znakove (na primjer, razmak u Fortranu). U C-u, vrijednost razdvajanja znakova za razdvajanje može se blokirati ("\" na kraju retka unutar "...").

Obično su svi leksemi podijeljeni u klase. Primjeri takvih klasa su brojevi (cijeli, oktalni, heksadecimalni, realni, itd.), identifikatori, nizovi. Ključne riječi i interpunkcijski simboli (ponekad zvani simboli za razdvajanje) označeni su zasebno. Tipično, ključne riječi su neki konačni podskup identifikatora. U nekim jezicima (na primjer, PL/1) značenje leksema može ovisiti o njegovom kontekstu i nemoguće je provesti leksičku analizu odvojeno od sintaktičke.

Sa stajališta daljnjih faza analize, leksički analizator proizvodi dvije vrste informacija: za sintaktički analizator, koji radi nakon leksičkog analizatora, bitne su informacije o slijedu klasa tokena, graničnika i ključnih riječi, a za analiza konteksta, radeći nakon sintaktičke, važni su podaci o specifičnim značenjima pojedinih leksema (identifikatori, brojevi itd.).

Tako, opća shema rad leksičkog analizatora je sljedeći. Prvo se dodjeljuje jedan token (možda korištenjem znakova za razdvajanje). Ključne riječi se prepoznaju eksplicitnim odabirom izravno iz teksta ili se prvo dodjeljuje identifikator, a zatim se provjerava pripada li skupu ključnih riječi.

Ako je odabrani leksem graničnik, tada se on (točnije, neka njegova obilježja) ispisuje kao rezultat leksičke analize. Ako je odabrani leksem ključna riječ, tada znak odgovarajuće ključna riječ. Ako je odabrani leksem identifikator, vraća se atribut identifikatora, a sam identifikator pohranjuje se zasebno. Konačno, ako odabrani token pripada bilo kojoj drugoj klasi tokena (na primjer, token je broj, niz itd.), tada se vraća atribut odgovarajuće klase, a vrijednost tokena se pohranjuje odvojeno.

Leksički analizator može biti neovisna faza prijevoda ili potprogram koji radi na principu "daj token". U prvom slučaju (Slika 3.1, a), izlaz analizatora je datoteka tokena, u drugom (Slika 3.1, b), token se izdaje sa svakim pozivom analizatoru (u ovom slučaju, kao pravilo, atribut klase tokena vraća se kao rezultat funkcije "leksičkog analizatora", a vrijednost tokena se prosljeđuje kroz globalnu varijablu). Što se tiče obrade vrijednosti tokena, parser može jednostavno vratiti vrijednost svakog tokena, u kojem slučaju se konstrukcija tablica objekata (identifikatora, nizova, brojeva itd.) odgađa za kasnije faze, ili može sam izgraditi tablice objekata . U tom se slučaju kao vrijednost leksema daje pokazivač na unos u odgovarajuću tablicu.

Riža. 3.1:

Rad leksičkog analizatora zadaje neki konačni automat. Međutim, izravan opis državnog stroja nezgodan je s praktičnog stajališta. Stoga se za određivanje leksičkog analizatora u pravilu koristi ili regularni izraz ili desnolinearna gramatika. Sva tri formalizma (konačni automati, regularni izrazi i desnolinearne gramatike) imaju istu izražajnu snagu. Konkretno, prema regularni izraz ili desno-linearne gramatike, može se konstruirati stroj stanja koji prepoznaje isti jezik.

Glavni zadatak raščlanjivanja - analiza strukture programa. U pravilu se struktura shvaća kao stablo koje odgovara raščlanjivanju u gramatici jezika bez konteksta. Trenutno se najčešće koriste ili LL(1) analiza (i njena varijanta rekurzivnog spuštanja) ili LR(1) analiza i njene varijante (LR(0), SLR(1), LALR(1) i druge). Rekurzivno spuštanje se češće koristi pri ručnom programiranju parsera, LR(1) - kada se koriste sustavi automatizacije za izgradnju parsera.

Rezultat parsiranja je stablo sintakse s vezama na tablicu imena. Proces raščlambe također otkriva pogreške povezane sa strukturom programa.

U fazi kontekstualne analize otkrivaju se ovisnosti između dijelova programa koje se ne mogu opisati sintaksom bez konteksta. To su uglavnom odnosi "opis-uporaba", posebice analiza tipova objekata, analiza opsega, podudaranje parametara, oznake i drugo. U procesu kontekstualne analize gradi se tablica simbola, koja se može smatrati tablicom imena, dopunjena informacijama o opisima (svojstvima) objekata.

Glavni formalizam koji se koristi u kontekstualnoj analizi je gramatike atributa. Rezultat faze analize konteksta je atribuirano programsko stablo. Informacije o objektima mogu biti ili disperzirane u samom stablu ili koncentrirane u zasebnim tablicama simbola. Proces kontekstualne analize također može detektirati pogreške povezane sa zlouporabom objekata.

Tada se program može pretvoren u internu reprezentaciju . To je učinjeno u svrhu optimizacije i/ili pogodnosti generiranja koda. Još jedan cilj pretvaranja programa u interni prikaz je želja da se ima prijenosni prevodilac. Tada samo posljednja faza (generiranje koda) ovisi o stroju. Kao interni prikaz mogu se koristiti prefiksna ili postfiksna notacija, usmjereni graf, trojke, četvorke i drugi.

Može postojati nekoliko faza optimizacije . Optimizacije obično se dijele na strojno ovisne i strojno neovisne, lokalne i globalne. Dio optimizacije ovisne o stroju izvodi se tijekom faze generiranja koda. Globalna optimizacija pokušava uzeti u obzir strukturu cjelokupnog programa, lokalno - samo njegove male fragmente. Globalna optimizacija temelji se na analizi globalnog toka koja se izvodi na programskom grafu i u biti je transformacija tog grafa. U ovom slučaju, takva svojstva programa kao što su interproceduralna analiza, intermodulna analiza, analiza područja života varijabli, itd. mogu se uzeti u obzir.

Konačno, generiranje koda- posljednja faza prijevoda. Njegov rezultat je ili asemblerski modul ili objektni (ili boot) modul. Tijekom generiranja koda, neki lokalne optimizacije, kao što je distribucija registara, izbor dugih ili kratkih skokova, uzimanje u obzir troškova naredbi pri odabiru određenog niza naredbi. Razvijene su različite metode za generiranje koda, kao što su tablice odlučivanja, uključujući podudaranje uzoraka dinamičko programiranje, razne sintaktičke metode.

Naravno, određene faze prevoditelja mogu biti potpuno odsutne ili kombinirane. U najjednostavnijem slučaju prevoditelja s jednim prolazom, ne postoji eksplicitna faza generiranja međureprezentacije i optimizacije, preostale faze se spajaju u jednu i ne postoji eksplicitno konstruirano stablo sintakse.

Moja tajna

Ciljevi i zadaci discipline

Osnovni pojmovi i definicije

Opće značajke programskih jezika i prevoditelja

Generalizirana struktura prevoditelja

Mogućnosti interakcije za blokove prevoditelja

Višeprolazna organizacija interakcije blokova prevoditelja

Jednoprolazna organizacija interakcije blokova prevoditelja

Kombinirane interakcije blokova prevoditelja

Kontrolna pitanja i zadaci

Pošaljite svoj dobar rad u bazu znanja jednostavno je. Koristite obrazac u nastavku

1.1 Raščlanjivanje odozgo prema dolje

1.2 Raščlanjivanje odozdo prema gore

1.2.1 LR(k) - gramatike

1.2.1.1 LR(0) - gramatike

1.2.2 LALR(1) gramatike

2. Razvoj prevoditelja

2.1 Analiza zahtjeva

2.2 Dizajn

2.2.1 Dizajniranje leksičkog analizatora

2.2.4 Softverska implementacija parsera

2.3 Kodiranje

2.4 Ispitivanje

Zaključak

Popis korištenih izvora

Dodatak A. Popis programskog teksta prevoditelja

Dodatak B. Rezultati ispitivanja

Dodatak C. Shema programa prevoditelja

Uvod

Programski jezici se prilično razlikuju jedni od drugih u svrhu, strukturi, semantičkoj složenosti, metodama implementacije. To nameće svoje specifičnosti razvoju pojedinih prevoditelja.

Čak se isti jezik može implementirati na nekoliko načina. To je zbog činjenice da teorija formalnih gramatika dopušta različite metode raščlanjivanja istih rečenica. Sukladno tome, prevoditelji na različite načine mogu dobiti isti rezultat (objektni program) iz izvornog izvornog teksta.

Međutim, svi programski jezici imaju niz zajedničkih karakteristika i parametara. To zajedništvo također određuje principe organiziranja prevoditelja koji su slični za sve jezike.

Programski jezici osmišljeni su kako bi olakšali programiranje. Stoga su njihovi operatori i podatkovne strukture moćniji nego u strojnim jezicima.

Da bi se povećala vidljivost programa, umjesto numeričkih kodova koriste se simbolički ili grafički prikazi jezičnih konstrukata koji su prikladniji za njihovu percepciju od strane osobe.

Za bilo koji jezik definirano je:

- skup simbola pomoću kojih se mogu napisati ispravni programi (abeceda), osnovni elementi,

- set ispravnih programa (sintaksa),

- "značenje" svakog ispravnog programa (semantika).

Formalno, svaki točan program X je niz simbola neke abecede A, koji se transformira u odgovarajući niz Y, sastavljen od simbola abecede B.

U tom smislu, za sve jezike i njihove programe mogu se dodatno razlikovati sljedeće zajedničke značajke: svaki jezik mora sadržavati pravila koja omogućuju generiranje programa koji odgovaraju tom jeziku ili prepoznavanje korespondencije između pisanih programa i danog jezika.

Svrha ovog kolegija je razviti prevoditelja za obuku sa zadanim pojednostavljenim jezik teksta visoka razina.

1. Metode raščlanjivanja

Razmotrite osnovne metode gramatičke analize.

1.1 Raščlanjivanje odozgo prema dolje

1.1.1 LL(k) - jezici i gramatike

Razmotrite izlazno stablo u procesu dobivanja lijevog izlaza lanca. Međulanac u procesu izlaza sastoji se od lanca terminala w, krajnjeg lijevog ne-terminala A, ispod tiskanog dijela x:

-S--

/ \

/ -A-x-\

/ | \

-w---u----

Slika 1

Definiramo dva skupa lanaca:

a) FIRST(x) - skup terminalnih nizova izvedenih iz x, skraćenih na k znakova.

b) FOLLOW(A) - skup terminalnih nizova skraćenih na k, koji mogu odmah slijediti A u izlaznim nizovima.

Gramatika ima svojstvo LL(k) ako iz postojanja dvaju lanaca lijevih zaključaka:

S::wAx:wzx::wu

S::wAx:wtx::wv

uvjet FIRST(u)=FIRST(v) implicira z=t.

U slučaju k=1, za odabir pravila za A dovoljno je znati samo ne-terminal A i a - prvi znak niza u:

- odaberite pravilo A:x ako je a u FIRST(x),

- pravilo A:e treba odabrati ako je a uključeno u FOLLOW(A).

LL(k)-svojstvo nameće prilično jaka ograničenja na gramatiku. Na primjer, LL(2) gramatika S: aS | a nema svojstvo LL(1), jer PRVI(aS)=PRVI(a)=a. U ovaj slučaj možete smanjiti vrijednost k koristeći "faktorizaciju" (stavljanje faktora u zagrade):

S:aA

O: S | e

1.1.2 Metoda rekurzivnog spuštanja

Metoda rekurzivnog spuštanja usmjerena je na one slučajeve kada je prevodilac programiran na jednom od jezika visoke razine, kada je dopuštena uporaba rekurzivnih procedura.

Osnovna ideja rekurzivnog spuštanja je da je svaki neterminal gramatike povezan s procedurom koja prepoznaje bilo koji niz koji generira ovaj neterminal. Ove procedure pozivaju jedna drugu kada je potrebno.

Kod bilo kojeg pravila sadrži operacije za svaki znak uključen u desnu stranu pravila. Operacije su navedene redoslijedom kojim se simboli pojavljuju u pravilu. Nakon posljednje operacije kod sadrži povrat iz procedure.

Korištenje rekurzivnog spuštanja u jeziku visoke razine olakšava programiranje i otklanjanje pogrešaka.

1.2 Raščlanjivanje odozdo prema gore

Razmotrimo raščlanjivanje odozdo prema gore, u kojem se srednji zaključci kreću duž stabla prema korijenu. Ako čitate znakove niza slijeva nadesno, stablo će izgledati ovako:

-S--

/ \

/-x-\

/ | \

--w--b--u-

Slika 2

-S-- -S--

/ \ / \

Reći ćemo da je lanac x konzistentan sa situacijom A:b_c ako je x=ab i a pripada L(A). (Drugim riječima, LR zaključivanje može se nastaviti x_... = ab_...:: abc_...:: aA_...:: S_.) U ovim terminima, L(A:b) je skup nizovi koji odgovaraju situaciji A:b_, L(A)

Reći ćemo da je lanac x konzistentan sa situacijom A:b_c|t ako postoji LR-izlaz: x_yz = ab_yz:: abc_z:: aA_z:: S_, i FIRSTk(z)=t. Pravila za induktivni izračun skupa stanja Vk su sljedeća:

Vk(e) sadrži S:_a|e situacije za sva S:a pravila, gdje je S početni znak. Za svaku situaciju A:_Ba|u iz Vk(e), svako pravilo B:b i lanac x koji pripada FIRSTk(au), situacija B:_b|x mora se dodati u Vk(e).

Ako situacija A:b_cd|u ulazi u Vk(w), tada će situacija A:bc_d|u pripadati Vk(wc). Za svaku situaciju A:b_Cd|u iz Vk(wc), svako pravilo C:f i lanac x koji pripada FIRSTk(du), moramo dodati situaciju C:_f|x u Vk(wc).