Arvutiteaduse instituut
  1. Esileht
  2. Automaadid, keeled ja translaatorid
EN
Logi sisse

Automaadid, keeled ja translaatorid

  • Üldinfo
  • Ajakava
  • Eksami näidised
  • Teemad
    • 1. Soojendus
    • 2. Regulaaravaldised
    • 3. Automaadid
    • 4. Avaldise struktuur
    • 5. Grammatikad ja lekser
    • 6. Käsitsi parsimine
      • Avaldisgrammatikad
      • Implementatsioon
      • Vasakrekursioon
      • Ennustav parsimine*
      • Lausearvutus*
      • Kodutöö
    • 7. ANTLRiga töötamine
    • 8. Interpretaator
    • 9. Kompilaator
    • 10. Edasi!
  • Huviring
  • Bitbucket
  • Moodle
  • Zulip
  • Zoom

Lisatöö: Lausearvutuse valemid

Ülesanne lahendamise video: Teeme ise AST klasse ja käsitsi parsimine. See võib olla kasulik vaatamine kõigile, kes tahaksid näha, kuidas AST klassid ja visitorid nullist ehitada.

Järgnevad lõigud on võetud Rein Pranki raamatust "Sissejuhatus matemaatilisse loogikasse".

[...]

Pane tähele, et toodud definitsioon ei luba näiteks valemeid (¬A), (A) ja (((A&B)))). Meie oleme antud ülesandes sulgude osas paindlikumad ja lisame Pranki definitsioonile juurde, et

Kui F on lausearvutuse valem, siis ka (F) on lausearvutuse valem.

Selgituseks teise lõigu teisele punktile: siin on mõeldud seda, et konjunktsiooni ja disjunktsiooni operaatoreid võib kasutada vasakassotsiatiivselt (st. A&B&C on lubatud ja see tähendab (A&B)&C), aga implikatsiooni ja ekvivalentsi operaatoreid ei või (st. A→B→C ei ole lubatud, selle asemel tuleb tehete järjekord eksplitsiitselt välja kirjutada: (A→B)→C või A→(B→C)).

Selleks, et mitte kulutada liiga palju auru leksilise analüüsi peale, lepime kokku, et lausemuutujad on alati ühetähelised ja tühikuid valemis esineda ei või.

Ülesanne

Ülesande lahendamiseks on avalikus repositooriumis, paketis week6.lausearvutus kaks faili juba ette antud. Vaja on implementeerida klassi FormulaUtils staatilised meetodid parseFormula ja moveNegations, aga selleks tuleb disainida mõistlikud klassi Formula alamaklassid. Täpsem info on antud meetodite kommentaaridena.

NB! Selleks, et näidatud operaatoreid (¬, &, ∨, →, ↔) java koodis kasutada saaks tuleb enda java failide kodeeringuks määrata mõni Unicode'i toetav kodeering nt. UTF-8 (Eclipse'i puhul paremklõps projektil -> Properties -> Resource). Kuna aga testimissüsteem peab antud ülesande puhul kindlalt teadma, millises kodeeringus esitatud java fail on, siis teeme nii, et kodeering peab olema justnimelt UTF-8, mitte mingi muu Unicode'i kodeering.

Võib juhtuda, et sinu editor ei suuda disjunktsiooni sümbolit õigel kujul näidata (näiteks Consolas fondis see sümbol puudub), sel juhul tuleb lihtsalt arvestada, et see imelik krõnks, mida editor selle asemel näitab, tähendab tegelikult disjunktsiooni. Alternatiiv oleks editori font selle ülesande tarvis ära muuta (Windowsis peaks olema font DejaVu Sans Mono, kus antud sümbol on esindatud).

Tingimused

  • Lahendus tuleb laadida Moodle'isse.
  • Esitada tuleb FormulaUtils ja Formula klassid ning vajadusel ka abiklasse sisaldavad failid.
    • Esitamise mugavuse mõttes soovitame kõik abiklassid defineerida FormulaUtils ja Formula-ga samas java failis, aga testimissüsteem on nõus vastu võtma ka rohkem (kuni 11) faili.
  • Arvutiteaduse instituut
  • Loodus- ja täppisteaduste valdkond
  • Tartu Ülikool
Tehniliste probleemide või küsimuste korral kirjuta:

Kursuse sisu ja korralduslike küsimustega pöörduge kursuse korraldajate poole.
Õppematerjalide varalised autoriõigused kuuluvad Tartu Ülikoolile. Õppematerjalide kasutamine on lubatud autoriõiguse seaduses ettenähtud teose vaba kasutamise eesmärkidel ja tingimustel. Õppematerjalide kasutamisel on kasutaja kohustatud viitama õppematerjalide autorile.
Õppematerjalide kasutamine muudel eesmärkidel on lubatud ainult Tartu Ülikooli eelneval kirjalikul nõusolekul.
Tartu Ülikooli arvutiteaduse instituudi kursuste läbiviimist toetavad järgmised programmid:
euroopa sotsiaalfondi logo