GLR -jäsennys ( englanniksi Yleistetty vasemmalta oikealle Oikeanpuoleisin johdannaisparser - Yleistetty nouseva varaston jäsentäjä ) - tietojenkäsittelytieteessä laajennettu LR-jäsennin algoritmi , joka on suunniteltu jäsentämään epädeterministisiä ja moniselitteisiä kielioppeja . Masaru Tomita kuvasi sen ensimmäisen kerran vuonna 1984 , ja sitä kutsutaan myös "rinnakkaisjäsennyksiksi" .
Koska tämä algoritmi on johdettu LR-jäsentimestä, sen toimintaperiaatteet pysyivät ennallaan: Tomita asetti tavoitteekseen saavuttaa nopean ja tehokkaan luonnollisella kielellä kirjoitetun tekstin tunnistamisen . Normaali LR-jäsentäjä ei pysty ratkaisemaan luonnollisten kielten epämääräisyyttä ja moniselitteisyyttä, kun taas GLR-algoritmi pystyy ratkaisemaan sen.
GLR-algoritmi toimii täsmälleen kuten LR-algoritmi , paitsi että tietyn kieliopin osalta GLR-jäsentäjä käsittelee kaikki mahdolliset syöttösekvenssin tulkinnat käyttämällä leveyshakua . GLR-jäsennysgeneraattorit muuntavat alkuperäisen kieliopin jäsennystaulukoiksi, aivan kuten LR-jäsennysgeneraattorit. Mutta vaikka LR-jäsennystaulukot sallivat vain yhden tilasiirtymän (määritetty jäsentimen alkutilan ja tuloliittimen symbolin perusteella), GLR-jäsennystaulukot sallivat monia tuloksena olevia tiloja. Tämän seurauksena GLR-algoritmi sallii siirtymisen/vähentämisen ja konfliktien vähentämisen/vähentämisen.
Kun ristiriita ilmenee, jäsentimen pino (kutistaa varasto) haarautuu kahteen tai useampaan rinnakkaiseen pinoon, joiden ylimmät tilat vastaavat kutakin mahdollista siirtymää. Seuraavassa seuraavaa syötesymbolia käytetään määrittämään seuraavat siirtymät pinon kunkin haaran ylimmissä tiloissa. Tässä tapauksessa pinon haaroitus voi olla jälleen tarpeen. Jos jollekin ylimmälle tilalle ja tulosymbolille ei ole siirtymää (jäsennystaulukossa), tämä pinon haara katsotaan virheelliseksi ja hylättäväksi.
Optimoinnin perusta on kyky jakaa pinon osia useiden sen haarojen kanssa, mikä vähentää syöttösekvenssin jäsentämiseen tarvittavan muistin kokonaismäärää. Tästä optimoinnista johtuva monimutkainen rakenne saa pinon näyttämään enemmän suunnatulta asykliseltä graafilta kuin puulta.
GLR-algoritmi on pahimmassa tapauksessa yhtä monimutkainen kuin Kok-Younger-Kasami- algoritmi ja Earley-algoritmi -O ( n³ ) . GLR-algoritmilla on kuitenkin kaksi etua:
Käytännössä useimmat ohjelmointikielet ovat deterministisiä tai "melkein deterministisiä". Tämä tarkoittaa, että epädeterminismi voidaan yleensä ratkaista lukemalla pieni (vaikkakin rajoittamaton) määrä syötettyjä merkkejä. Verrattuna muihin algoritmeihin, jotka pystyvät käsittelemään koko luokkaa yhteydettömiä kielioppeja (kuten Early-algoritmi tai Kok-Younger-Kasami- algoritmi), GLR-algoritmi on tehokkaampi tällaisissa "melkein deterministisissa" kieliopeissa, koska vain yksi kielioppihaara pino.