Jäsennin

Wikipedia
Loikkaa: valikkoon, hakuun

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.
Tämä tietotekniikkaan liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.