Väiksed parserid
Siin on mõned näited eelmiste aastate eksamitest/kontrolltöödest. Avalikus repos on nendele vastavad testid. Me enam seda ülesannet eksamil ei küsi, aga see on ikkagi väga väärt harjutus, et rekursioonist paremini aru saada. 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 tagastada vastav süntakspuu ja õiged expected hulgad. 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 (näidislahendustega)
| MiniParser | ||
|---|---|---|
| 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 MiniParser grammatika lahendusi (parsers.mini.levels), mida võib eeskujuks võtta. Seal on näitena toodud lisaks rekursiivsele lahendusele ka erinevad lahendused vastavalt raskusastmetele. Kui oled seda näidet uurinud, siis võid proovida lahendada järgmised ülesanded eelmistest aastatest:
Nende lahendused ilmuvad ka sols kataloogi.
Lisatöö: Väiksed parserid
Selles ülesandes harjutame natuke kontekstivabade grammatikate käsitsi teisendamist parseriteks ja parsepuu loomist. Projekti aluseks tuleks võtta week7.parsers.xtra 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 kümme testi, kusjuures kaks neist on iga ülesanne juures ainult keele äratundmise kohta, aga 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. Grammatikat 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 lihtsalt parsida. See vajab vasakrekursiooni elimineerimist. Lisaks tahame aga ka luua abstraktse süntakspuu, mis kirjeldab tüüpide 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 ilusalt ei õnnestugi seda ära teha.