Napišite leksički analizator za pseudo-XHTML dokument koji sadrži samo liste. Cijeli dokument je uokviren samo u <html> element koji se sastoji od zaglavlja <head> i tijela <body>. Zaglavlje smije sadržavati samo običan tekst, a tijelo se sastoji od običnog teksta i listi. Liste mogu biti uređene <ol> i neuređene <ul>. Lista se sastoji od <li> elemenata. U jednom elementu liste smije se nalaziti običan tekst ili nova lista, ali ne i oboje. Dokument može sadržavati proizvoljan broj listi. Poštujte uobičajena pravila za XHTML dokumente.
Napišite sintaksni analizator za pseudo-XHTML dokumente iz prvog zadatka. Provjerite uobičajena XHTML pravila (neka možete provjeriti već u leksičkom analizatoru!): je li cijeli dokument uokviren u elemente, je li odnos XHTML elemenata odgovarajući, je li svaki element zatvoren, jesu li svi elementi napisani malim slovima, jesu li elementi odgovarajuće ugniježđeni, itd. Omogućite i da se u <li> elementu liste, osim običnog teksta, može pojaviti i nova lista (ali ne i oboje). Liste smiju sadržavati samo <li> elemente (ne tekst i ne direktno druge liste).
Napišite i odgovarajući semantički analizator (renderer) za XHTML liste iz prvog zadatka. Za svaki <li> element iz neuređene liste ispišite tabulator, "*", sadržaj <li> elementa ako se radi o tekstu, te znak za prijelom retka. Ako je sadržaj <li> elementa nova lista, onda samo ispišite novu listu. Elemente liste s prve razine treba ispisati s jednim tabulatorom na početku, a za svaku dodatnu razinu treba ispisati i dodatni tabulator (npr. lista unutar liste počinje s dva tabulatora, itd.).
Napišite leksički analizator za pseudo-XHTML dokument koji sadrži samo tablice. Cijeli dokument je uokviren samo u <html> element. Tablica <table> se sastoji od redaka <tr>, redovi od ćelija <td> ili u zaglavlju <th>. U ćelijama može pisati bilo što. Dokument može imati proizvoljan broj tablica, koje se mogu nalaziti i jedna unutar druge.
Napišite sintaksni analizator za pseudo-XHTML dokumente iz prvog zadatka. Provjerite uobičajena XHTML pravila: je li cijeli dokument uokviren u <html> element, je li odnos HTML elemenata odgovarajući, je li svaki element zatvoren, jesu li svi elementi napisani malim slovima, jesu li elementi odgovarajuće ugniježđeni, itd. Omogućite i da se u ćeliji tablice, osim običnog teksta, može pojaviti i nova tablica. Redovi tablice smiju sadržavati samo ćelije, a sama tablica smije sadržavati samo redove (ne i običan tekst). Tablica smije imati najviše jedan redak u kojem se nalaze ćelije zaglavlja (<th>) i taj redak, ako postoji, mora biti prvi redak u tablici. Sami odaberite vrste apstraktnih sintaksnih stabala.
Napišite i odgovarajući semantički analizator (renderer) za XHTML tablice iz prvog zadatka. Za svaku ćeliju samo ispišite "|", njen sadržaj i tabulator; za svaki redak ispišite znak za prijelom retka. Tablicu započnite i završite ispisom horizontalne crte (dovoljno minusa "--------...--"). Ako tablica ima zaglavlje, nakon zaglavlja ispišite istu horizontalnu crtu.
Napišite funkciju koja prima izvod, i ako je validan, vraća lijevi izvod koji izvodi istu riječ iz istih pravila. Ako izvod nije validan, treba dignuti neki izuzetak ili vratiti None. Izvod je lista stringova: u svakom stringu u listi, svako malo slovo predstavlja znak gramatike, a svako veliko slovo varijablu gramatike. Koristite Pythonove metode .islower() i .isupper() za njihovo razlikovanje.
Izvod je validan ako postoji neka beskontekstna gramatika čiji je to izvod. Naravno, "izvedena riječ" je zadnji element izvoda. Početna varijabla je prvi element izvoda. Neke naznake da izvod nije validan (pokušajte ih sve otkriti): prazan je, prvi element izvoda nije jedno veliko slovo, zadnji element izvoda ima neko veliko slovo u sebi, stringovi u izvodu imaju nešto osim slova, mala slova se zamjenjuju drugim slovima, više pravila je primijenjeno odjednom između susjednih elemenata izvoda.
Primjer: lijevi(['S', 'SS', 'SaSb', 'Sab', 'aSbab', 'aaSbbab', 'aabbab']) treba vratiti ['S', 'SS', 'aSbS', 'aaSbbS', 'aabbS', 'aabbaSb', 'aabbab']. (Objašnjenje: gramatika je S->SS|ε|aSb, radi se o jeziku dobro sparenih zagrada -- a je otvorena, b je zatvorena zagrada.)
Algoritam nije trivijalan. Savjetujem da prvo razmislite i sami iskonstruirate nekoliko testnih primjera, te ih riješite ručno, da vidite kako stvar treba funkcionirati. Posebno obratite pažnju na to da gramatika može imati pravila poput S->ST ili S->S. Smijete biti fleksibilni prilikom interpretacije pravila: recimo ako izvod sadrži 'AB' pa onda 'AcB', smijete pretpostaviti da imate pravilo A->Ac ili B->cB, kako vam je lakše. Naravno, ako izvod sadrži 'AB' pa onda 'AcBd', morate imati pravilo 'B->cBd'. Ako sadrži 'AB' pa onda 'eAcBd', nije validan.
Za 4 boda, smijete pretpostaviti da je gramatika Chomskyjeva (ako u nekom trenutku detektirate da je primijenjeno pravilo koje nije Chomskyjevo, dignite Exception). Za 2 boda, napravite samo detekciju je li primljeni izvod validan i je li lijevi (ako nije validan vratite None, ako je validan a nije lijevi vratite False, ako je lijevi vratite True).
Na http://c0.typesafety.net nalazi se specifikacija programskog jezika c0. Ako pregledate informacije na tom siteu, vidjet ćete da postoji interpreter, coin, za njega. Implementirajte što veći dio coin funkcionalnosti. U dokumentaciji ćete naći primjere, beskontekstnu gramatiku, specifikaciju leksera... Naravno, čitav coin je ogroman posao. Za tipičnih 5 bodova trebaju se moći izvršavati programčići poput sieve2.c0 na http://c0.typesafety.net/tutorial/Computing-primes,-in-Python-and-C0.html, i ne morate razmišljati o dosegu varijabli (recimo, varijabla factor može biti deklarirana na vrhu funkcije). Možete dobiti do 10 bonus bodova za implementaciju raznih dodatnih featurea jezika c0.
Naravno, možete implemetirati "pravo" učitavanje iz filea (https://docs.python.org/3/library/pathlib.html#pathlib.Path.read_text) i "pravi" interaktivni rad (for naredba in iter(input, '#quit'):, ili nešto slično), ali ne trebate. Dovoljno je recimo da funkcija coin prima dva argumenta: prvi je tekst programa (recimo, sadržaj filea sieve2.c0), a drugi je interaktivna naredba (recimo, 'isPrime(17);'). Povratna vrijednost može biti Pythonov True, string 'true (bool)', token BOOLKONST'true', ili bilo što iz čega se vidi tip i vrijednost.
Na http://www.cs.tufts.edu/~sguyer/classes/comp181-2006/minijava.html nalazi se specifikacija, gramatika i primjer koda za programski jezik MiniJava. (Pazite: gramatika je samo informativna, nije direktno prikladna za pisanje parsera jer npr. nema kodirane razine prioriteta operatora, niti asociranost, kroz zasebne varijable. Morate napisati svoju BKG prvo.)
Zadaća je implementirati što više MiniJave: za redovnih 5 bodova morate implementirati dovoljno MiniJave da se može parsirati i izvršiti primjer programa naveden na tom linku (računanje i ispis 10!=3628800). Za razne dodatne značajke jezika možete dobiti do 5 bonus bodova. Dodatne značajke ne moraju nužno biti ono što piše na gornjem linku: jeziku nedostaje puno toga da bi bilo udobno programirati u njemu (npr. operatori || i ==, stringovi,...) -- bilo koju od tih stvari također možete implementirati.
Ako odlučite implementirati ikakve dodatne značajke, obavezno sa zadaćom predajte nekakvu dokumentaciju (minimalno README datoteku) u kojoj ćete opisati što ste napravili. Također predajte i neke testove iz kojih se vidi ta funkcionalnost. Ako ste nešto pokušali implemetirati ali ne radi baš najbolje (nedovršeno, ili ima bugove koje ne znate/niste stigli maknuti), navedite i to.