5. lisatöö: Väiksed Parserid
Selles kodutöös harjutame natuke kontekstivabade grammatikate teisendamine käsitsi parseriteks ja parsepuu loomist. Projekti aluseks tuleks võtta "lisa5" paketti klassid. Kõik parserid tuleb ehitada tutorial koodi põhjal, s.t. nad võiksid olla Parser.java alamklassid. Praktikumi materjalid tasub üle vaadata, eriti ASTi genereerimise kohta vasakrekursiooni eemaldamisel.
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.