LR-jäsennin ( eng. LR parser ) on jollain ohjelmointikielellä kirjoitettujen ohjelmien lähdekoodien jäsentäjä , joka lukee syötevirran vasemmalta (vasemmalta ) oikealle ja tuottaa yhteydettömän kieliopin oikeanpuoleisimman ( oikeimman ) tuotannon. . Käytetään myös termiä LR( k )-analyzer , jossa k ilmaisee syötevirran lukemattomien esikatselumerkkien määrää , joiden perusteella analyysin aikana tehdään päätöksiä. Yleensä k on 1 ja se jätetään usein pois.
Monien ohjelmointikielten syntaksi voidaan määrittää LR(1):n tai sitä lähellä olevan kieliopin avulla, ja tästä syystä kääntäjät käyttävät usein LR-jäsentimiä lähdekoodin jäsentämiseen.
Tyypillisesti jäsentäjään viitataan sen kielen nimeen, jonka lähdekoodia se jäsentää, esimerkiksi "C++-jäsennys" jäsentää C++- lähdekoodia .
LR-jäsennin voidaan generoida yhteydettömästä kieliopin avulla ohjelmalla, jota kutsutaan jäsentäjägeneraattoriksi , tai ohjelmoija voi kirjoittaa sen käsin. Kontekstiton kielioppi luokitellaan LR( k ):ksi, jos sille on olemassa jäsentäjägeneraattorin määrittämä LR( k )-jäsennin.
LR-jäsentimen sanotaan olevan alhaalta ylöspäin -jäsennystä, koska se yrittää päätellä kieliopin huipputason tuotosta rakentamalla sen lehdistä .
Deterministinen yhteydetön kieli on kieli, jolle on olemassa jonkinlainen LR( k ) -kielioppi. Jokainen LR( k )-kielioppi voidaan automaattisesti muuntaa LR( 1 )-kieliopiksi samalle kielelle, kun taas joidenkin kielten LR( 0 )-kielioppeja ei välttämättä ole olemassa. LR( 0 )-kielet ovat oma determinististen kielten osajoukkonsa.
LR-jäsennin perustuu algoritmiin, jota ohjaa jäsennystaulukko , tietorakenne, joka sisältää jäsennetyn kielen syntaksin. Joten termi LR-jäsennys viittaa itse asiassa jäsentimien luokkaan, joka voi jäsentää melkein minkä tahansa ohjelmointikielen, jolle on olemassa jäsennystaulukko. Jäsennystaulukon luo jäsentäjägeneraattori.
LR-jäsennys voidaan yleistää mielivaltaiseksi yhteydettömän kielen jäsennykseksi ilman suorituskyvyn heikkenemistä, jopa LR(k)-kieliopissa. Tämä johtuu siitä, että useimmat ohjelmointikielet voidaan ilmaista LR( k )-kieliopilla, jossa k on pieni vakio (yleensä 1). Huomaa, että muiden kuin LR(k) kielioppien jäsentäminen on suuruusluokkaa hitaampaa (syötevirran koon mukaan kuutiota neliöllisen sijaan).
LR-jäsennystä voidaan soveltaa useammille kielille kuin LL-jäsennys , ja se on myös parempi virheraportoinnissa, mikä tarkoittaa, että se havaitsee syntaksivirheet, joissa syöte ei vastaa kielioppia mahdollisimman aikaisessa vaiheessa. Sitä vastoin LL(k) (tai pahempaa, jopa LL(*))-jäsentimet voivat viivyttää virheen havaitsemista toiselle kieliopin haaralle palautuksen vuoksi, mikä usein vaikeuttaa virheen paikantamista tavallisten pitkien etuliitteiden paikoista.
LR - jäsentimiä on vaikea luoda käsin , ja ne luodaan yleensä jäsennysgeneraattorilla tai kääntäjällä . Jäsennystaulukon luontitavasta riippuen näitä jäsentimiä voidaan kutsua yksinkertaisiksi LR-jäsentimiksi (SLR), ennakko-LR-jäsentimiksi (LALR) tai kanoniseksi LR-jäsentimiksi . LALR-jäsentimillä on huomattavasti suurempi tunnistusteho kuin SLR-jäsentimillä . Samaan aikaan SLR-analyysin taulukot ovat samankokoisia kuin LALR-analyysissä, joten SLR-analyysiä ei enää käytetä. Kanonisilla LR-jäsentimillä on hieman enemmän tunnistustehoa kuin LALR-jäsentimillä, mutta ne vaativat paljon enemmän taulukkomuistia, joten niitä käytetään harvoin. .
| Muodolliset kielet ja viralliset kieliopit | |
|---|---|
| Yleiset käsitteet | |
| Tyyppi 0 | |
| Tyyppi 1 |
|
| Tyyppi 2 | |
| Tyyppi 3 |
|
| jäsentäminen | |