Programski prevodioci 1/Projekat

Projekat na predmetu važi za jednu od najtežih aktivnosti na njemu zbog toga što zahteva praktičnu primenu znanja stečenih u trećem bloku (i ponekih iz prvog i drugog bloka). Njegova izrada može zahtevati oko nedelju dana konstantnog rada (u zavisnosti od nivoa za koji radite) ali se takođe veliki deo toga može iskoristiti iz postojećih materijala sa vežbi i zvaničnih video vodiča za projekat, na koje će se ovaj vodič nadalje oslanjati.

Osnovno

Ideja projekta jeste konstrukcija prevodioca za Mikrojavu — pojednostavljenu, školsku varijantu jezika Java čija se specifikacija pomalo menja iz godine u godinu (ali neke suštinske stvari ostaju iste). Prevodilac iz jednog fajla sa izvornim kodom čita Mikrojava kod po specifikaciji datoj uz tekst projekta (a odvojenoj od same postavke), prolazi kroz četiri faze prevođenja (leksičku analizu, sintaksnu analizu, semantičku analizu i generisanje koda) i njegov krajnji rezultat jeste objektna datoteka sa Mikrojava bajtkodom. Taj objektni fajl se zatim može izvršavati preko Mikrojava virtuelne mašine (čija je implementacija već data i ne može se menjati) i na osnovu nekog unosa proizvesti neki izlaz.

Za projekat je potrebno gledati vežbe trećeg bloka iz tabele simbola i Mikrojava virtuelne mašine, i eventualno vežbe prvog i drugog bloka iz JFlex i CUP. Takođe su dostupni video vodiči za projekat sa stranice predmeta, koje je korisno pogledati kao uvod u alate i neka generalna očekivanja. Ti vodiči su enkodovani nekim jako zastarelim kodekom, a reenkodovani snimci se mogu naći ovde.

Pre nego što pređete na dalje odeljke, preporučuje se da pročitate postavku projekta. Mikrojava specifikaciju ne morate čitati, jer će vam ona najviše značiti prilikom samog razvijanja projekta.

Postavka

Sada kada ste pročitali postavku, o njoj je potrebno reći par reči.

• Struktura projekta uopšte ne mora da bude onakva kakva piše u postavci. To znači:
  • Paket ne mora da se zove rs.ac.bg.etf.pp1.
  • Ne postoji konkretan direktorijum u koji morate da smestite specifikacije leksera i parsera.
  • Nije obavezno korišćenje JDK 1.8 (mada je preporučeno)
  • Klase ne moraju da se zovu Compiler, SemanticAnalyzer i CodeGenerator.
• Na odbrani se manje-više gleda samo izlaz prevedenog Mikrojava programa za modifikaciju i za javni test odgovarajućeg nivoa za koji radite. Ovo u praksi znači:
  • Niko neće proveravati format greške leksera.
  • Niko neće proveravati da li se uspešno radi oporavak od greške.
    • Ipak, preporučuje se da probate ovaj deo da odradite, ali ako na nekom mestu ne radi to nije veliki problem.
  • Niko neće proveravati da li niste koristili precedence (ali niko neće ni objasniti kako se koristi).
  • Niko neće proveravati kako su imenovani neterminali niti klase koje odgovaraju granama tih neterminala.
  • Niko neće proveravati da li ste dodali akcije u specifikaciju parsera.
    • Svakako se preporučuje da potrebne akcije obavljate kroz odgovarajuće posetioce stabla, jer u specifikaciji parsera nije dostupan IntelliSense.
  • Nije mnogo verovatno da će predmetni saradnici pogledati da li koristite njihovu tabelu simbola, da li ste je raspakovali i preveli ponovo ili koristite neku potpuno drugu implementaciju.
    • Ipak, korišćenje njihove tabele simbola nosi sa sobom pogodnost da ćete uvežbati rad sa njom pa nećete mnogo morati da obnavljate za takve zadatke na ispitu.
  • Niko neće proveravati da li ste implementirali metodu tsdump().
  • Niko neće proveravati da li ispisujete simbole pri njihovoj detekciji.
  • Slabo će se proveravati da li se prijavljuju semantičke greške.
    • Ipak, pošto tokom semantičke obrade svakako mora da se popuni tabela simbola, vredi dodati ove provere, u krajnjem slučaju zato što će vama značiti ukoliko budete pisali svoje test primere i napišete nešto semantički neispravno.
    • Može da se desi da neke stvari iz javnih testova ili testova za modifikacije koje su zakomentarisane moraju da prijave semantičke greške, i da ih predmetni saradnici otkomentarišu prilikom odbrane.
  • Niko neće proveravati da li se putanje do ulaznih i izlaznih fajlova prosleđuju kroz argumente komandne linije.
• Na odbrani se ne traži da se bilo šta pokreće iz komandne linije, niti preusmerava standardni izlaz i izlaz za greške.
• Primeri Mikrojava koda iz postavke i specifikacije mogu često biti sintaksno ili semantički neispravni. Ovo je zbog toga što predmetni saradnici ne napišu prevodilac za specifikaciju Mikrojave koju su zadali, a primer verovatno iskopiraju iz postavke odnosno specifikacije od prethodne godine, pa ne provere da li je ispravan.
• Na odbrani niko ne pogleda izveštaj sa projekta.
• Niko neće tražiti da se pokrenu studentski testovi projekta.
• Suprotno postavci, dorada projekata na odbrani je dozvoljena.
• U odeljku za kontekstne uslove u okviru specifikacije mogu biti opisane stvari koje se ne rade u fazi semantičke analize, već ili opisuju generalno funkcionisanje tog programskog konstrukta, ili opisuju stvari koje se moraju obezbediti u fazi generisanja koda.
• Prilikom specifikacije sintakse koristi se EBNF notacija.
• Podela funkcionalnosti po nivoima može biti jako konfuzna. Specifikacija Mikrojave može posebno napomenuti za samo par stvari da se implementiraju samo na određenim nivoima (ostavljajući utisak da je potrebno prepoznati sintaksu za metode i klase čak i u projektu A nivoa), dok postavka može nepotpuno izlistavati smene koje su potrebne da se implementiraju za određeni nivo. Najbolji način za određivanje šta se implementira za koji nivo jesu odgovarajući javni testovi.

Alati

U ovom odeljku navedene su sve napomene u vezi sa alatima koje ćete koristiti na projektu, od kojih će neke imati smisla tek nakon što pogledate video vodiče.

• Nekoliko stvari iz video vodiča urađeno je na neoptimalan način:
  • Jedna od prvih stvari pomenutih u video vodičima jeste instaliranje Ant. Za ovime nema potrebe, jer je Ant već instaliran u okviru Eclipse. Takođe, Ant pravila se dosta lakše mogu pokretati odlaskom na Window → Show View → Ant, i zatim biranjem build.xml fajla iz projekta.
  • Ukoliko krećete od koda iz video vodiča, moguće je da će vam izbacivati deprecation upozorenja povodom korišćenja new Integer() konstruktora. Ovo možete zameniti sa Integer.parseInt().
  • Brojanje parametara i lokalnih promenljivih korišćenjem VarCounter i FormParamCounter nije zapravo potrebno, već ih možete brojati prilikom obilaska tih čvorova stabla.
  • Na nekoliko mesta se koristi Tab.insert() radi pravljenja Obj čvora koji nema potrebe zapravo ubacivati u tabelu simbola. Umesto ovoga, mogu se koristiti regularni konstruktori za Obj.
• U računarskim laboratorijama bi trebalo da je dostupan i IntelliJ, pa možete u njemu takođe raditi projekat.
• Obavezno preuzeti biblioteke sa stranice predmeta umesto korišćenja onih iz šablona projekta ili video vodiča, jer njihove verzije mogu biti zastarele i prouzrokovati probleme.
• Unos sa standardnog ulaza neće raditi ukoliko se prevedeni Mikrojava program pokreće kroz Ant, pa je potrebno dodati direktivu <redirector input="input.txt" /> kako bi se standardni ulaz čitao iz datoteke input.txt koja se nalazi u korenom direktorijumu projekta.
  • Na ovaj isti način mogu se preusmeriti standardni izlaz i izlaz za greške: <redirector input="input.txt" output="output.txt" error="error.txt" />
  • Ukoliko umesto ovoga program pokrenete kroz komandnu liniju, moguće je da ćete morati da različite podatke za unos (preko read i bread instrukcija) pišete u istom redu (umesto u novim redovima).
• Nije neophodno koristiti Log4j biblioteku za ispis ukoliko ne želite.
• Podrazumevano, Log4j biblioteka neće ispisivati na izlaz za greške već na standardni izlaz, čak i kad su u pitanje poruke sa greškama. Ovo može da se konfiguriše, ali svakako niko neće obraćati pažnju na to na odbrani.
• Ukoliko dobijete Cannot invoke "java.net.URL.toString()" because "this.val$url" is null grešku, probajte da liniju DOMConfigurator.configure(Log4JUtils.instance().findLoggerConfigFile()); zamenite sa DOMConfigurator.configure("config/log4j.xml");.
• Greška za nepostojeći log4j.dtd se može ignorisati.
• Ne zaboravite da na sve <java> elemente u build.xml dodate fork="true" atribut, jer će se inače te stavke pokretati iz nekog direktorijuma koji nije koreni direktorijum projekta.

Faze izrade

Leksička analiza

• Da biste počeli sa razvojem ove faze ne morate kucati svoj sym.java fajl, već se on može generisati iz CUP specifikacije čim pokrenete parserGen pravilo u Ant, ukoliko ste sve svoje terminale napisali u CUP specifikaciji (terminal).
• Ova faza je najlakša i moguće ju je uraditi za samo par sati, ali je bitno uraditi je kako treba. Greške u lekseru mogu izazvati probleme prilikom parsiranja, samo što lekser u tom trenutku može biti mesto na kojem ćete najmanje posumnjati da se nalazi greška. Postoji nekoliko stvari na koje treba obratiti pažnju:
  • Generalnija pravila idu na dno. Na primer, ukoliko se pravilo za if nalazi ispod pravila za detekciju identifikatora, lekser će if prepoznati kao identifikator i zato će parser izbaciti grešku prilikom parsiranja if naredbe.
  • Na samo dno ubaciti jedno match-all pravilo (kao što je urađeno u video vodiču). Ukoliko to ne uradite, lekser će izbaciti Error: could not match input grešku ukoliko se naiđe na karakter koji nije u specifikaciji Mikrojave, što samo po sebi nije problem, ali vam vaša sopstvena greška može dati više informacija o tome gde je tačno problem.
  • Ukoliko radite na operativnom sistemu Linux ili macOS, potrebno je odvojiti pravilo za \r\n na pravila za \r i \n kako bi ih pravilno ignorisao.
  • U video vodiču se za prepoznavanje identifikatora koristi ([a-z]|[A-Z])[a-z|A-Z|0-9|_]* regularni izraz, gde je karakter | greškom dozvoljen u okviru identifikatora, dok je pravilno [a-zA-Z][a-zA-Z0-9_]*. Ovo je mala greška, ali može napraviti problem prilikom konstrukata poput a||b, koji će biti prepoznati kao jedan identifikator umesto dva identifikatora sa operatorom između njih.

Sintaksna analiza

• Najvažnije pravilo tokom razvoja ove faze jeste da sva pravila pišete korak po korak i sa testiranjem između. Tokom razvoja alati mogu prijaviti greške koje vam ni na koji način ne sugerišu gde je zapravo problem, i takve greške je daleko lakše pronaći ukoliko znate koji deo sintakse je testiran i radi, a koji je novododat. Ovo znači da kada preuzmete projekat iz video vodiča obrišete sve smene iz njega (osim jedne, poput Program ::= PROG;, kako bi generisanje parsera uopšte radilo) i krenete sa dodavanjem smena redom po specifikaciji. Kad vidite da ste dodali neku manju ali potpunu celinu, testirajte da li to što ste dodali radi. Ako ne radi, uklanjanjem i vraćanjem delova koje ste dodali možete locirati gde je tačno izazvana greška. Ovakav način razvoja pomoći će i vama i ljudima koje pitate za pomoć oko eventualnih greški.
• Kada krenete sa razvojom ove faze, najbolje je da uopšte ne postavljate nazive klasa na neterminalima. Ovi nazivi klasa se mnogo lakše postavljaju nakon što ste već razvili celu gramatiku (pre sledeće faze) i imate ceo kontekst, a njihovo dodavanje tokom razvoja gramatike može izazvati neke od čestih greški. Isto tako, nema potrebe dodeljivati tipove terminalima i neterminalima dok ne stignete do sledeće faze, već je dovoljno samo deklarisati ih.
  • Ukoliko ste ovo pokušali da radite i naišli na greške, njihova rešenja će biti objašnjavana u sledećem odeljku.
• Kako se u okviru ove faze takođe radi i oporavak od greške, vredno je napomenuti da je svrha tog oporavka da se prijave sve postojeće sintaksne greške u programu (umesto da se prijavi samo jedna i izađe), ali da se pri detekciji bilo kakve greške ne nastavlja na sledeću fazu, čak iako se od svih sintaksnih greški parser uspešno oporavio.
• Ukoliko se umesto reda za mesto sintaksne greške od koje se oporavlja ispisuje kolona, to je bag u alatu i angažovani na predmetu neće to zamerati. Ovo se takođe može desiti u sledećoj fazi.
• Greška java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "X" is null obično znači da je negde zaboravljena tačka-zarez, ali pošto je ovo suštinski greška u implementaciji AST-CUP ona ne daje nikakvih dodatnih informacija o tome gde bi ta greška mogla da bude.
• Greška Syntax error X(Y) označava grešku u sintaksi CUP fajla i može se desiti iz više razloga. Bitno je napomenuti da se broj X odnosi na liniju u autogenerisanoj CUP specifikaciji koja se nalazi u fajlu sa sufiskom _astbuild.cup, a ne u originalnoj CUP specifikaciji, dok se broj Y odnosi na kolonu (karakter) u tom redu gde je prijavljena sintaksna greška (koji nije od velike koristi). Razlozi iz kojih se ova greška dešava mogu biti:
  • zaboravljena tačka-zarez na kraju smene,
  • nedostatak razmaka nakon zareza u deklaraciji terminala ili neterminala,
  • korišćenje := umesto ::=,
  • i tako dalje.
• Ukoliko dobijate konflikte prilikom implementacije if-else, postavka obično pomene koja tačno precedence direktiva sme da se koristi za to (i samo to).
• Greška koja glasi java.lang.NullPointerException: Cannot invoke "java_cup.astext.AstSymInfo.getType()" because "this.lhInfo" is null znači da neki neterminal koji se koristi sa leve strane neke smene nije prethodno deklarisan. Za neterminale koji se koriste sa desne strane a nisu deklarisani se dešava drugačija greška koja jasnije kaže da se radi o tome.
• Od koristi može biti sledeća skripta za generisanje liste neterminala koje je potrebno deklarisati tokom ove faze (koja prestaje da bude korisna u trenutku kada neterminalima treba dodeljivati tipove), koju je potrebno pokrenuti Python interpreterom iz korenog direktorijuma projekta:

  from re import compile
  
  NTERM_REGEX = compile(r'^(\w+)\s*::=')
  
  nterms = []
  
  with open('spec/mjparser.cup') as file:
      for line in file:
          match = NTERM_REGEX.match(line)
          if match:
              nterms.append(match.group(1))
  
  print(f'nonterminal {", ".join(nterms)};')
  

Semantička analiza

Tehničke napomene

• Pre početka ove faze ne zaboravite da svim terminalima koji sa sobom nose neke smislene vrednosti (identifikatori, konstante...) dodelite tip (preko terminal Tip naziv;). Ukoliko ovo ne uradite, u neterminalima koji sadrže te terminale neće se izgenerisati polja sa vrednostima ovih terminala.
• Takođe pre početka ove faze potrebno je svim neterminalima dodeliti nazive klasa (ukoliko ih ne dodelite, nazivi klasa biće autogenerisani pa su kao takvi generalno nepogodni za rad sa njima). Kada dodeljujete ove nazive, bitno je da se vodite sa dva pravila:
  1. Ukoliko neterminal ima samo jednu granu, postavite da njen naziv klase bude isti kao i naziv samog neterminala. Ovo će generisati jednu konkretnu klasu za taj neterminal.
  2. Ukoliko neterminal ima više od jedne grane, nijedna njegova grana ne sme da se zove isto kao i sam neterminal. Naziv neterminala koristi se kao naziv apstraktne klase, a nazivi klasa njegovih grana koriste se za konkretne klase koje su izvedene iz te apstraktne klase. Ukoliko neterminal ima više grana, i jedna grana se zove isto kao neterminal, AST-CUP će se zbuniti i neće znati da li ta klasa treba da bude apstraktna i konkretna i ovo će ispoljiti kao greška sa konstruktorima.
     • Važno je napomenuti da se levoj i desnoj strani ne smeju dodeljivati nazivi klasa sa različitom kapitalizacijom (AssignOp i Assignop), jer se na fajl sistemima koji se obično koriste pod Windows ovi nazivi klasa mapiraju u istu Java datoteku. Ovo je posebno opasno na operativnim sistemima Linux i macOS, gde do greški ovog tipa neće doći (već će se one desiti tek u laboratoriji).
• Ukoliko ste došli do ovog dela a potrebno vam je da regenerišete parser, ne zaboravite da nakon regenerisanja parsera osvežite projekat desnim klikom na projekat i opcijom Refresh. Ovaj korak je potreban zbog toga što generisanje parsera poziva spoljašnji program koji bez znanja Eclipse menja fajlove unutar projekta, i kako bi Eclipse znao da su se ti fajlovi promenili potrebno je osvežiti ih. Ukoliko ovo ne uradite, IntelliSense može prijavljivati greške koje nemaju smisla i Eclipse može sprečavati pokretanje kompajlera zbog toga.
  • Ovo se u Eclipse-u može zaobići tako što se namesti automatsko osvežavanje nakon pokretanja spoljašnje Ant skripte. To se radi tako što se u Project Explorer-u klikne desni klik na build.xml skriptu, onda Run as -> External Tools Configuration, onda se u iskačućem prozoru izabere tab Refresh i čekira se opcija Refresh resources upon completion i The entire workspace u podmeniju.
• Compiler klasa je zapravo skoro neizmenjena MJParserTest klasa iz video vodiča, tako da možete samo nju da preimenujete/premestite.

Tabela simbola

• Pre rada sa njihovom tabelom simbola, ne zaboravite da u glavnoj klasi pozovete Tab.init(). Ukoliko to ne uradite, greška koju ćete dobiti može sadržati "rs.etf.pp1.symboltable.Tab.currentScope" is null.
• Podrazumevano, Tab.dump() neće ispisivati bool tipove objektnih čvorova, jer to nije implementirano u DumpSymbolTableVisitor (već će to mesto stajati prazno). Pošto svakako niko nije gledao ispis tabele simbola na odbrani projekta, ovo nikome nije ni bilo bitno.
• Takođe, Tab.dump() može praviti problem kada se kao član neke klase ili kao lokalni simbol člana neke klase nađe objekat te klase, jer tada dolazi do beskonačne rekurzije pri ispisu. Jedini slučaj kad neće doći do ove beskonačne rekurzije jeste kad samo simboli sa nazivom this nose tip te klase (u tom slučaju se njihov tip uopšte ne ispisuje). Pošto ovakvih test primera nije bilo, ovo nikome nije pravilo problem.
• Još jedan problem sa beskonačnom rekurzijom u njihovoj tabeli simbola može se desiti ukoliko poredite klasne tipove sa njihovom implementacijom equals. Ako dva klasna tipa imaju isti broj polja i metoda, i barem jednu metodu, equals će preći na poređenje tih metoda i upasti u beskonačnu rekurziju. Kao i prethodno, pošto ovakvih test primera generalno nema ovo nikome ne pravi problem. Sa druge strane, pošto se na ovu grešku najčešće naiđe prilikom provere natklasa, može se specijalno za slučaj kada se radi o dve klase koristiti operator == za poređenje referenci.
• assignableTo metoda u njihovoj tabeli simbola ne proverava da li je jedna klasa podklasa druge, pa je ovu proveru potrebno implementirati (videti takođe napomenu iznad).
• Format ispisa čvora u Tab.dump() jeste <kind> <name>: <type>, <adr>, <level>.
• Prilikom postavljanja type polja objektnim čvorovima koji predstavljaju nizove prave se novi Struct čvorovi, tako da dva objektna čvora sa istim nizovskom tipom neće pokazivati na isti objekat u pozadini. Ovo generalno ne pravi nikakav problem.
• Kada se kroz Tab.insert() ubaci jedan objektni čvor u tabelu simbola, njegov level se automatski postavlja na 0 ukoliko se radi o globalnom dosegu i 1 ukoliko se radi o lokalnom. Ovo je poželjno ponašanje za promenljive, ali za metode, čiji level treba da sadrži broj parametara, je prvo potrebno vratiti level na 0 a zatim ga prilikom obilaska svakog čvora sintaksnog stabla za parametre povećavati za 1.
• Ukoliko je potrebno dodati nešto u universe doseg (a obično jeste), to se može obaviti odmah nakon pozivanja Tab.init(), i kod iz Tab.init() se može iskoristiti za to.

Generisanje koda

• Ukoliko se neke varijante dup instrukcije ispisuju kao ??? prilikom disasembliranja, to je normalno ponašanje.
• Ukoliko je negde potrebno obilaziti niz ili iz nekog drugog razloga dohvatiti dužinu niza, to nije moguće uraditi tokom prevođenja, već je potrebno generisati kod koji poziva arraylength instrukciju, koja sa steka skine niz a postavi dužinu tog niza, i zatim iskoristiti tu vrednost sa steka u ostatku generisanog koda.
• Ako su u postavci zadatka date neke globalne funkcije, kod za njih je potrebno generisati na nekom mestu (najbolje na početku) a zatim tim funkcijama postaviti adresu na ta mesta gde je izgenerisan kod za njih.
• Ukoliko želite da nakon generisanja koda taj kod pokrenete tako da se prikazuje tok izvršenja programa i stanje steka, možete dodati novo pravilo poput:

  <target name="debug" depends="disasm">
      <java classname="rs.etf.pp1.mj.runtime.Run">
          <arg value="test/program.obj" />
          <arg value="-debug" />
          <redirector input="input.txt" />
          <classpath>
              <pathelement location="lib/mj-runtime.jar" />
          </classpath>
      </java>
  </target>
  

  • Ovo vam, doduše, neće prikazati sadržaj memorije Mikrojava virtuelne mašine nakon izvršenih instrukcija. Ukoliko vas to zanima, možete prekopirati Run klasu iz JAR fajla sa izvršnim okruženjem u svoj projekat, promeniti mu paket, postaviti argumente i breakpoint-ove na odgovarajuća mesta (najverovatnije u interpret metodi) i pokrenuti u debag režimu.

Odbrana

• Na odbrani, projekat se podešava tako što se Eclipse projekat otvori pomoću opcije File → Open Projects from File System i zatim pokrene bilo kroz Ant prozor bilo na način pokazan na video vodiču.
• U postavci projekta je izričito rečeno da su studenti dužni da osiguraju da njihovo rešenje radi na laboratorijskim računarima. Ovo generalno nije toliko neophodno, jer su rešenja generalno prenosiva, ali ukoliko želite da se uverite laboratorija P26 je otvorena za studentski rad radnim danima do 20 časova, kada se ne održavaju ostale laboratorijske vežbe.
• Odbrana projekta izgleda tako što angažovani na predmetu prvo daju modifikaciju i od tada studenti imaju tri sata da urade modifikaciju i odbrane projekat. Test primeri za modifikacije su generalno dati na deljenim diskovima (ali mogu biti pogrešni, jer nisu bili testirani na pravom projektu). Kada student uradi modifikaciju, pozove asistenta ili demonstratora i oni pokrenu projekat na testu za modifikaciju (eventualno više puta sa promenjenim parametrima, otkomentarisanim linijama koje su zakomentarisane), ispitaju studenta kako je uradio modifikaciju, pokrenu javni test i opciono pitaju neko pitanje o samom projektu. Ukoliko nešto ne radi, student može da ispravlja projekat dok ne istekne vreme.
• Dozvoljeno je deljenje testova između studenata, tako da pre odbrane možete podeliti sa ostalima svoje testove kako bi svi zajedno više bagova uhvatili u svojim projektima.

Reference

• Vodič za projekat 2021/2022. na kojem su delovi ovog vodiča zasnovani.