LR(0) — Alhaalta ylös -algoritmi yhteydettömien kielioppien jäsentämiseen , yksi LR -tyypeistä .
LR(0) on harvoin käytössä käytännössä johtuen kapeasta jäsenneltyjen kielioppien joukosta, mutta se on perusta tehokkaammille algoritmeille SLR(1) ja LALR(1) , joista jälkimmäisellä on runsaasti käytännön sovelluksia.
Kaikilla kolmella mainitulla algoritmilla on sama suoritusvaihe syöttövirralle, eroten vain kieliopin jäsennystaulukon muodostamisvaiheessa.
Tämä suoritusvaihe on erittäin nopea (lineaarinen aika), joka pystyy jäsentämään kaikki LALR(1)-kielet, eli lähes kaikki käytössä olevat ohjelmointikielet. Lisäksi se pystyy generoimaan ymmärrettäviä syntaksivirheitä, jotka ovat muotoa "jäsentämätön merkki sellaisessa ja sellaisessa paikassa" ja jos jäsennystaulukon koko rivillä on vain 1 vaihtotoiminto, muotoa " sellaista ja sellaista hahmoa odotettiin”.
Koska jäsennystaulukon rakentaminen LR(0), SLR(1) ja LALR(1) -algoritmeille on erittäin monimutkainen, tähän käytetään yleensä jäsentimien generaattoria, kuten yacc , jos haluat kirjoittaa jäsentimen nopeasti manuaalisesti, käytä rekursiivista laskeutumismenetelmää tai LL(1 )
Esittelemme "ketjun" käsitteen. Tämä on tietyn kieliopin säännön oikea puoli ja sijainti siinä, 0:sta N:ään (oikean puolen pituus), paikka N tarkoittaa - säännön oikean puolen lopun takana. Merkitään ketjua R(K, L), jossa K on säännön numero ja L on oikealla puolella oleva paikka.
Ketjua, jossa L = säännön K oikean puolen pituus, kutsutaan täydelliseksi.
Otetaan käyttöön käsite "symboli R(K, L)", eli merkkijonon osoittama symboli. Tämä on L:s merkki K-säännön oikealta puolelta. Valmis merkkijono ei osoita mihinkään merkkiin.
Otetaan käyttöön käsite "alkuperäisten ketjujen joukko ei-terminaalille". Ei-päätteelle A alkuketjujen joukko sisältää:
Otetaan käyttöön käsite "valtio" ketjujen joukkona.
Otetaan käyttöön käsite "alkutila" symbolin E alkuketjujen sarjana, kieliopin alun.
Otetaan käyttöön "siirtymän" käsite siirtymänä tilasta tilaan symbolin (ei-päätelaitteen tai terminaalin) vaikutuksesta. Uusi tila rakennetaan vanhasta tilasta siirryttäessä symbolia A pitkin seuraavasti:
Siirron sanotaan olevan mahdotonta, jos tuloksena on tyhjä joukko.
Kielioppia varten muodostetaan alkutila.
Lisäksi kaikille terminaaleille ja ei-päätteille konstruoidaan kaikki mahdolliset tilat (ketjujoukot), jotka saadaan siirtymällä aiemmin tunnetuista tiloista. Tämä poistaa päällekkäiset tilat.
Seuraavaksi rakennetaan jäsennystaulukko, pystysuunnassa - tilanumerot (0 - alkutila), vaakasuunnassa - symbolit (päätteet, ei-päätteet ja "virran loppu" -symboli).
Siirrot syötetään taulukkoon seuraavasti: jos siirto on mahdollinen symbolille C ja tilalle S, niin soluun syötetään arvo "siirtymä S-iskutilaan" (saatu siirron tuloksena). S, C).
Seuraavaksi korvataan kieliopin alku S → E ja uuden alun S kohdalla syötetään soluun (S, virran loppu) arvo "jäsennys on suoritettu loppuun".
Lisäksi vähennystoiminnot (reduce) syötetään taulukkoon, vain päätteille, seuraavasti: jos tilassa S on valmis ketju, niin arvo "pienennys säännön R mukaan, N:n pituuden oikea puoli merkkiä" syötetään kaikkiin soluihin (S, pääte), saamme säännön vasemmalta puolelta ei-terminaalisen C:n."
Yritystä lisätä heitto jo varattuun taulukon soluun (esimerkiksi, jos tilassa on kaksi täydellistä ketjua) kutsutaan shift-cast-konfliktiksi tai cast-cast-konfliktiksi. Tässä tapauksessa LR(0)-jäsentimen rakentaminen ei ole mahdollista, mutta se voi olla mahdollista rakentaa käyttämällä hieman monimutkaisempaa SLR(1)- tai LALR(1)-algoritmia, jotka eroavat vain tavasta, jolla castit syötetään pöytä.
Käytetään analysaattoripinoa, jossa sijaitsevat tilanumerot, tulo (päätteet ja virran loppu) ja lähtö (sääntönumerot) virrat.
0 työnnetään pinoon ensin.
Lisäksi, kunnes syntaksivirhe tai jäsennys on suoritettu onnistuneesti: