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.

Noam Chomsky julkaisi kontekstittomien kielioppien kuvauksen 1957. Niiden hyödyllisyyden tajuaminen johti siihen että Algol 60 -raportista julkaistiin uusi painos, jossa kielioppi kuvattiin BNF-notaatiolla. Donald Knuth oli keksinyt LR-parserin 1965.^[1] Franklin DeRemer esitteli käyttökelpoisen LALR-parserin väitöskirjassaan vuonna 1969.^[2]

Jäsentimet ovat tärkeitä etenkin ohjelmointikielten ja vastaavien kehityksessä. Stephen Johnson ja Alfred Aho määrittelivät 1971 Bell Labsilla B-kielen syntaksin formaalisti ja Johnsonin kehittämää Yaccia käytettiin sen kehittämiseen. Myöhemmin Yaccilla kehitettiin Portable C Compiler, Pascal-, Ratfor-, APL-kääntäjät ja muita ohjelmointikieliä kuten awk. Sillä oli myös muuta käyttöä kuten taitto-ohjelman kuvauskielen jäsennys ja laskimet.^[3]

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.

• Jäsentäminen