Automata, Languages and Compilers 2018/19 spring

7. kodutöö: AKTK Parser

Selles kodutöös arendame edasi meie AKTK nimelist keelt. Programm koosneb 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+ x
• 4
• pulss - vanus * vo2_max
• 123 + 3*PI - (23 - (r*4 - d))
• ((((( ((((((((((((((((((((((((((( x))))))))) )))))))))))))))))))))))

Selle koduülesande püstitus on natuke rohkem struktureeritud kui eelmisel kodutööl. Ü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 ülesande käsitsi hindamisel täpselt 0 punkti!

Ülesande eesmärk on sisendist genereerida abstraktne süntakspuu (AST), mille peal saab mõningaid arvutusi mugavalt 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 klassis AstTest, mida võite kodus kasutada, et testida ainult eval funktsiooni.
• String toPrettyString() tagastab avaldise infix-notatsioonis võimalikult väheste sulgudega. Selle implementeerimine on raskem, kui proovite ise lahendada, aga analoogilised lahendused on meie näidisklassides olemas.

Seda 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 fleep'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 kodutöö näidislahenduse koodi, sest lekserit tuleks kasutada ja tema mõningatest 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 testide põhjal. Nad jagunevad järgmiselt:

• Kuni 40% 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 30% saab juurde, kui tagastate korrektse AST-i: AKTKParser.parse(...).eval(...) annab õige tulemuse.
• 20% saab korrektse veatöötluse eest.
• 10% saab korrektse toPrettyString() meetodi eest.

Tingimused

• Esitada tuleb moodle'is.
• 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.