Jäsennin
Jäsennin (engl. parser) on tietokoneohjelma, joka jäsentää sille syötteenä annettu merkkijonon tiettyyn muotoon.
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.
Parsereita on käytetty myös seikkailupeleissä, joissa pelaaja ohjaa peliä kirjoittamalla komentoja. Tällöin parseri pyrkii tunnistamaan annetut käskyt ja niiden kohteet.
Tyypit
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.