SLR(1)

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 1. joulukuuta 2014 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

SLR(1) on alhaalta ylös -jäsennysalgoritmi.

Se on LR(0) -algoritmin laajennus . Joissakin tapauksissa se toimii, kun LR(0)-jäsennystaulukon rakentaminen tietylle kieliopille ei ole mahdollista shift-cast- tai cast-cast-ristiriitojen vuoksi. Siten SLR(1):n mukaan jäsennelty kielioppiluokka (vrt. "SLR(1)-kielioppi") on laajempi kuin LR(0)-kielioppien luokka.

Itse jäsennysalgoritmi (analysaattorin suorittaminen tulovirran mukaan) on sama sekä SLR(1) että LR(0) - ja laajemmin LALR(1) :lle . Ainoastaan algoritmit jäsennystaulukon muodostamiseksi kieliopin mukaan analysaattorin luontiprosessissa eroavat toisistaan.

Kuvaus

Jokaiselle kieliopin ei-päätteelle A luodaan joukko päätteitä First(A), joka määritellään seuraavasti:

jos kieliopin sääntö on A vasemmalla ja oikealla, joka alkaa terminaalilla, niin kyseinen pääte on kohdassa First(A)
jos kieliopin sääntö on A vasemmalla ja oikealla puolella, joka alkaa ei-päätteellä (merkitty B), niin First(B) sisältyy tiukasti kohtaan First(A)
First(A) ei sisällä muita päätteitä

Samoja sarjoja käytetään LL(1)-analysaattorin rakentamiseen.

Lisäksi First(A)-joukkojen perusteella luodaan Follow(A)-joukot, jotka määritellään seuraavasti

jos kieliopissa on sääntö, jossa A ei ole viimeisessä paikassa ja sitä seuraa pääte, niin pääte sisältyy Follow(A) -ryhmään.
jos kieliopissa on sääntö, jossa A ei ole viimeisessä paikassa, ja sen jälkeen on ei-pääte (merkitty B:llä), ensimmäinen(B) sisältyy tiukasti seuraamaan(A)
jos kielioppi sisältää säännön, jossa A esiintyy viimeisessä paikassa, Follow(C) sisältyy tiukasti seuraamiseen(A), jossa C on säännön vasen puoli.
Seuraa(A) ei sisälly muita päätteitä

(näitä ehtoja on mahdollista yleistää sääntöjen B -> tyhjälle olemassaololle)

Seuraavaksi luodaan jäsennystaulukko, kuten LR(0), erolla, kun cast-toiminnot syötetään. Tilan S ja syöttösymbolin C heitto on taulukoitu vain, jos S:ssä on merkkijono, joka vastaa säännön koko oikeaa puolta, ja säännön vasemman puolen ei-pääte N täyttää ehdon "C is in Follow( N)".

Tämä johtaa siihen, että SLR(1) yrittää harvemmin laittaa "cast" jäsennystaulukon soluun, mikä vähentää ristiriitojen riskiä heittojen kanssa, joskus päästä eroon niistä kokonaan ja tekee kieliopin, jota LR(0 ei jäsennä ) jäsenneltävä.

Käytännön sovellus

Siinä ei melkein ole (lukuun ottamatta opetuskäyttöä), koska jäsennetään kapea kielioppiluokka. Käytännön sovellus on LALR(1), joka on SLR(1) yleistys.

Aritmeettiset lausekkeet, joissa on yksi- ja binäärioperaattoreita ja sulkeita, jäsennetään SLR:llä(1)

Katso myös