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 tarkistaa, 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. Jäsentimiä on käytetty myös seikkailupeleissä, joissa pelaaja ohjaa peliä kirjoittamalla komentoja. Tällöin jäsennin 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-jäsentimen 1965.Isoaho, LR-jäsennyksen toiminta ja käyttökohteet § 3.1 LR-jäsennyksen historiasta, Jyväskylän yliopisto s. 9 Franklin DeRemer esitteli käyttökelpoisen LALR-jäsentimen väitöskirjassaan vuonna 1969.Franklin Lewis DeRemer, Practical translators for LR (k) languages. MIT Libraries 

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.Unix programmer’s manual, 7th ed., Vol. 2B, January, 1979 

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.

 Katso myös 
 Jäsentäminen

 Lähteet 

Luokka:Ohjelmointi