Automaadid, keeled ja translaatorid - Kursused

6. kodutöö: AKTK käsitsi kirjutatud parser

Käsitsi parserite kirjutamine ei ole meil (enam) eksami teema, aga see on siiski üsna oluline. Rekursiivse laskumisega parseri kirjutamise meetod kuulub arvutiteaduse klassika hulka. See valgustab tõdesid rekursiooni kohta, mistõttu võiks vähemalt põhimõttest üritada aru saada: see on üsna kindel skeem, kuidas grammatika saab parseri koodiks teisendada.

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))))))))) )))))))))))))))))))))))

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. Kõigepealt peab disainima ja implementeerima mõned AST klassid koos meetoditega, mis on ülemklassis (AktkNode) 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 AktkNodeTest, 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. Meie testid tõlgendavad liitmist ja korrutamist assotsiatiivsetena, seega väljastame 5+(6+7) kui 5+6+7, aga lahutamisel peavad sulud jääma, sest 5-(3-1) ei ole sama mis 5-3-1.

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õhiline osa on AKTK avaldise parseri implementeerimine klassis AktkHandwrittenParser.

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 testid kontrollivad järgmisi aspekte antud mahus:

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

Tingimused

Esitada tuleb moodle'is.
Esitama peab AktkHandwrittenLexer, AktkHandwrittenParser ja AktkNode koos oma alamklassidega. Eelmisest kodutööst AktkToken klassid ja AktkParseException on juba serveril olemas ja neid ei tohi muuta.
- Soovi korral võib kasutada meie AKtkHandwrittenLexer-i näidislahendust.

Video juhuks, kui jääd alustamisega hätta: AktkHandwrittenParser-i algus.

Automaadid, keeled ja translaatorid 2020/21 kevad