7. kodutöö: AKTK Parser
Selles kodutöös arendame edasi meie AKTK nimelist keelt. Programm koosneb endiselt vaid ühest avaldisest, aga nüüd võivad avaldises esineda ka mitteassotsiatiivsed tehted lahutamine (-) ja jagamine (/). Arvestada tuleb tavapärase tehete järjekorraga. Lisaks võib nüüdsest tehete järjekorra määramiseks kasutada sulge ja me ei piira, kui mitmel tasemel võivad sulupaarid üksteise sees paikneda.
Legaalsed programmid on nüüd näiteks:
2+ x4pulss - vanus * vo2_max123 + 3*PI - (23 - (r*4 - d))((((( ((((((((((((((((((((((((((( x))))))))) )))))))))))))))))))))))
Selle koduülesande püstitus on natuke rohkem struktureeritud kui eelmine kodutöö. Ülesanne lahendamiseks vajalik tugikood on meie BitBucket repos.
Grammatika
Teie lahendus peab toetama järgmise BNF grammatika poolt defineeritud keelt:
avaldis -> avaldis '+' term
| avaldis '-' term
| term
term -> term '*' faktor
| term '/' faktor
| faktor
faktor -> '(' avaldis ')'
| Muutuja
| Konstant
Parseri implementeerimisel võite võtta ka aluseks sama keelt defineeriva EBNF grammatika
avaldis -> term (('+'|'-') term)*
term -> faktor (('*'|'/') faktor)*
faktor -> '(' avaldis ')'
| Muutuja
| Konstant
AST klassid
NB! AST klasside mõistlik disain on kohustuslik. Kui teie vaheesitus ei ole puu kujul, siis saate ülesanne käsitsi hindamisel täpselt 0 punkti!
Ülesande eesmärk on sisendist genereerida abstraktne süntakspuu (AST), mille peal on mõned arvutused üsna mugav teha. AST klassid asuvad paketis week7. Kõigepealt peab implementeerima mõned AST klassi funktsioonid, mis on ülemklassis (ExprNode) deklareeritud:
- Staatilised klassi loomise meetodid. Me oleme seda nüüd päris palju teinud, et ülemklassis on staatilised meetodid, millega saab mugavalt luua alamklassi isendid. Tuleb nüüd siis disainida vastavad alamklassid. Kas kõikide tehete jaoks on vaja eraldi alamklassid või piisaks ühest BinOp klassist? (Pead ise otsustama!)
int eval(Map<String, Integer> env)väärtustab avaldist etteantud keskkonnas. Selle lahendamine on hädavajalik, sest parseri testimisel kasutame põhiliselt eval funktsiooni. Selle jaoks on eraldi testid klassisAstTest, mida võite kodus kasutada, et testida ainult eval funktsiooni.String toPrettyString()tagastab avaldis infix-notatsioonis võimalikult väheste sulgudega. Selle implementeerimine on raskem, kui proovite ise lahendama, aga analoogilised lahendused on meie näidisklassides olemas.
Selle osa saab eraldi testida. Soovitame seda teha esimesel nädalal!
Nende meetodite pikkused meie lahenduses on 1 .. 15 rida. Kui sinul kipuvad need meetodid oluliselt pikemaks minema, siis küsi abi fleepi'is.
Parser
Ülesande põhiosa on AKTK avaldise parseri implementeerimine klassis week7.AKTKParser.
Vihje. Kuigi nõutud meetod on staatiline, ei tähenda see seda, et parseri põhiloogika peaks asuma staatilistes meetodites. Kaalu samasse klassi konstruktori ja isendimeetodite lisamist! Uuri ka eelmise nädala kodutöö näidislahenduse koodi, sest lekserit tuleks kasutada ja tema mõnedest meetoditest võib inspiratsiooni saada.
Meie parseri kood tuli tiba üle 100 rea. Kui sinu lahendus kipub mitu korda pikemaks minema, siis palun küsi abi!
Hindamine
Ülesande eest jagame punkte järgmiselt:
- Kuni 4 punkti saab korrektse recognizeri eest. Me testime ainult, kas tagastate midagi (näiteks null), kui sõne kuulub keelde, või viskate AKTKParseException, kui ta ei kuulu.
- Kuni 3 punkti saab juurde, kui tagastate korrektne AST:
AKTKParser.parse(...).eval(...)annab õige tulemuse. - 2 punkt saab korrektse veatöötluse eest.
- 1 punkt saab korrektse toPrettyString() meetodi eest.
Tingimused
- Esitada tuleb moodle'is. Tähtaeg on 17. aprill.
- Esitama peab oma Lekser, Parser ja ExprNode koos oma alamklassidega. Eelmisest kodutööst Token klassid ja AKTKParseException on juba serveril olemas ja neid ei tohi muuta.
- Kui soovite kasutada mingeid 3. osapoolte teeke, siis andke teada ja räägime läbi.