Eksami parseri ülesanne
Siin on mõned näited eelmistest aastate eksam/kontrolltöödest. Avalikus repos on nendele vastavad testid. Selle aasta eksamil tuleb ka samasuguse struktuuriga ülesanne. Me anname grammatika järk-järgult.
- Esimene tase on LL(1) grammatika, mida saab otse transleerida koodiks.
- Teine tase nõuab vasakfaktoriseerimist.
- Kolmanda taseme jaoks on vaja vasakrekursiooni eemaldada.
Täispunktide saamiseks on ka vaja vastav süntakspuu tagastada ja õiged expected hulkasid. See nõuab teatud määral teooria valdamist. Kui miski selle juures jääb segaseks, siis esitage loengus küsimusi. See teema on eelkõige teooria teema, aga viimastes praktikumides võime selle juurde tagasi pöörduda.
Harjutused
| EksamParser | ||
|---|---|---|
| Esimene Tase | Teine Tase | Kolmas Tase |
| S → aAa S → ε A → bB B → b | S → aAa S → ε A → bB A → bSc B → b | S → aAa S → ε A → bB A → bSc B → b B → Bc |
| AbbaParser | ||
|---|---|---|
| Esimene Tase | Teine Tase | Kolmas Tase |
| S → ABAR A → a B → bb R → +S R → ε | S → ABAR A → a A → aAb B → bb R → +S R → ε | S → ABAR A → a A → aAb B → bb B → BbSb R → +S R → ε |
| BoratParser | ||
|---|---|---|
| Esimene Tase | Teine Tase | Kolmas Tase |
| S → AB A → boA A → ε B → rat | S → AB A → boA A → baA A → ε B → rat | S → AB A → boA A → baA A → ε B → rat B → Bbi B → Blo |
| AktParser | ||
|---|---|---|
| Esimene Tase | Teine Tase | Kolmas Tase |
| S → AkT A → aA A → ε T → t | S → AkT A → aA A → ε T → t T → tSp | S → AkT A → aA A → ε T → t T → tSp T → Tt |
Kõigepealt vaadake EksamParser grammatika lahendusi (parsers.eksam.grading), mida võib eeskujuks võtta. Seal on näitena toodud lisaks rekursiivsele lahendusele ka erinevad lahendused vastavalt meie hindamisskaalale. Kui oled selle näide uurinud, siis võid proovida lahendada järgmised ülesanded eelmistest aastatest:
Nende lahendused on ka sols kataloogis.
Lisatöö: Väiksed parserid
Parim viis eksamiks ette valmistada on meie järgmine lisatöö. Selles harjutame natuke kontekstivabade grammatikate teisendamine käsitsi parseriteks ja parsepuu loomist. Projekti aluseks tuleks võtta "xtra5" paketti klassid. Kõik parserid tuleb ehitada parsers paketti koodi põhjal, s.t. nad võiksid olla Parser.java alamklassid.
Esitada saab moodle'is. Kokku on võimalik saada 10 punkti. Kaks punkti saab iga ülesanne juures saama ainult keele ära tundmise eest ja siis on iga ülesanne juures mõned natuke raskemad ülesanded, mis puudutavad puude ehitamist või veatöötlust.
1) SAParser
Esimesena tuleks kirjutada Parser järgmise keele jaoks:
Esimeses reeglis on kaks valikut, aSb ja aA, mis algavad sama tähega. Teine reegel on vasakrekursiivne. Grammatika peab seega teisendama: paneme esimese reegli jaoks uue mitte-terminali nimeks R ja teise reegli jaoks uue mitte-terminali nimeks Q. Paremal on toodud parsepuu näide sisendi abdb korral. (See on muide see puu, mida me kontrolltööl ei taha!)
2) AC/DCParser
Järgmises grammatikas peab samuti vasakrekursiooni elimineerima:
Seekord tuleb aga originaalse grammatika parsepuu tagastada. Näiteks ac/dc parsepuu peaks tulema nagu paremal joonisel.
3) TypeParser
Viimane grammatika on inspireeritud C keele tüübideklaratsioonide grammatikast:
Siin tuleb kõigepealt lithsalt parsida. See vajab vasakrekursiooni elimineerimist. Lisaks tahame aga ka luua abstraktne süntakspuu, mis kirjeldab tüübide päris tähendusi:
int*[]→ TArray(TPtr(TInt)).int(*)[]→ TPtr(TArray(TInt)).
Kahjuks ei ole C keel eriti LL-parsimiseks sõbralik keel ja see ülesanne on oluliselt raskem, kui esialgu võib tunduda. Väga puhtalt või ilusasti ei õnnestugi seda ära teha.