Jäsennin
Jäsennin (engl. parser) on tietokoneohjelma, jolla tarkastetaan onko jokin sille syötteenä annettu merkkijono rakenteeltaan tietyn ohjelmointikielen kelvollinen ilmaisu ja luo ilmaisusta sitä vastaavan tietorakenteen.
Esimerkiksi C-kielen jäsennin tarkistaa, onko syöte C-ohjelmointikielen syntaksin mukainen ilmaisu ja XML-jäsennin tarkastaa, onko syöte XML-kielinen ilmaisu.
Validoiva XML-jäsennin tarkistaa lisäksi, onko syöte XML-kielen yleisten sääntöjen mukainen ja onko se annetun dokumenttityyppimäärittelyn mukainen.
Tyypit[muokkaa | muokkaa wikitekstiä]
Jäsentimet voidaan jakaa kahteen tyyppiin sen mukaan, missä järjestyksessä ne käyvät lävitse kielioppia. Tyypit ovat
- Osittava (top-down) LL-jäsennin. Sen etuna on yksinkertainen toteutus - syötettä luetaan vasemmalta oikealle, ja kunkin symbolin merkitys puretaan vasemmalta oikealle edettäessä. Ongelmana on ns. vasen rekursio, jonka kohdatessaan LL-jäsennin joutuu ikuiseen silmukkaan. Esimerkiksi lausekielissä tyypillinen osa termin määrittelyä BNF-notaatiolla ilmaistuna voisi olla jotain seuraavanlaista:
<TERMI> ::= <TERMI> ('*'|'/') <KERROIN>
LL-jäsennin kutsuisi ensin alirutiinia, joka laajentaa <TERMI>:n, ja kutsuisi heti sen jälkeen alirutiinia, joka laajentaa <TERMI>:n joutuen näin ikuiseen rekursiosilmukkaan.
- Kokoava (bottom-up) LR-jäsennin, joka poistaa vasemman rekursion ongelman. Toisaalta sen toteuttaminen ei ole yhtä suoraviivaista kuin LL-jäsentimen. LR-jäsennin toimii päinvastaisella periaatteella kuin LL-jäsennin: se kerää luettuja symboleita (
::=-merkin oikealla puolella olevat symbolit) ja koettaa sovittaa niitä vasemmalla puolella oleviin symboleihin.