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.

Osno vno

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 genrisanja 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 dodavanjem build.xml fajla u projektu.
  • 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 pišete u istom redu.
• Nije neophodno koristiti Log4j bibliioteku za ispis ukoliko ne želite.
• Podrazumevano, Log4j biblioteka neće slati svoj izlaz 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.

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 sva pravila iz njega (osim jednog, poput Program ::= PROG;, kako bi generisanje parsera uopšte radilo) i krenete sa dodavanjem pravila redom po specifikaciji. Kad vidite da ste dodali neku manju ali potpunu celinu, testirajte da li to što ste dodali radi.
• 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.
• 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.
• 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

• Pre početka ove faze ne zaboravite da svim terminalima koji sa sobom nose neke smislene vrednosti (identifikatori, konstante...). Ukoliko ovo ne uradite, u neterminalima koji sadrže te terminale neće se izgenerisati polja sa vrednostima ovih terminala.
• 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.

Reference

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