LALR(1)

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 23. maaliskuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

LALR (1) (LA englanniksi lookahead - esikatselu) - alhaalta ylös -jäsennysalgoritmi .

Se on SLR(1) -algoritmin laajennus . Joissakin tapauksissa se toimii, kun SLR(1) jäsennystaulukon rakentaminen tietylle kieliopille ei ole mahdollista siirto-vähennys- tai vähennys-vähennys-ristiriitojen vuoksi. Siten LALR(1):n jäsentämä kielioppiluokka on laajempi kuin SLR(1)-kielioppiluokka.

Jäsennysalgoritmi (analysaattorin suoritus tulovirran mukaan) on sama sekä LALR(1) että SLR(1) ja on leveämpi kuin LR(0) . Ainoastaan algoritmit jäsennystaulukon muodostamiseksi kieliopin mukaan analysaattorin luontiprosessissa eroavat toisistaan.

Kuvaus

Olkoon kielioppi, jota ei jäsenne SLR(1)-algoritmia käyttämällä shift-reduce tai fold-reduce ristiriitoja.

Tässä tapauksessa kielioppi muunnetaan seuraavasti:

ei-päätettä, josta konfliktin aiheuttanut konvoluutio sai alkunsa, etsitään. Kutsutaan sitä A.
uudet ei-päätteet A1, A2, …, An otetaan käyttöön, yksi jokaista A:n esiintymistä varten sääntöjen oikealla puolella.
kaikkialla sääntöjen oikeissa osissa A korvataan vastaavalla Akilla.
sääntöjoukko, jossa A on vasemmalla, toistetaan n kertaa jokaiselle Ak:lle.
säännöt, joiden vasemmalla puolella on A, poistetaan, mikä poistaa A:n kielioppista kokonaan.

Muunnetulle kieliopille (se on isomorfinen alkuperäiseen nähden) yritetään rakentaa SLR(1) jäsennystaulukko.

Toiminta perustuu siihen tosiasiaan, että Follow(A) on kaikkien Follow(Ak) liitto. Jokaisessa tietyssä tilassa uudessa kielioppissa ei ole enää A:ta, vaan yksi Ak, eli tämän tilan Seura-joukossa on vähemmän elementtejä kuin alkuperäisen kieliopin A:ssa.

Tämä johtaa harvempiin yrityksiin LALR(1) laittaa "cast" jäsennystaulukon soluun, mikä vähentää ristiriitojen riskiä heittojen kanssa, joskus päästä eroon niistä kokonaan ja tekee kieliopin, jota järjestelmäkamera ei jäsennä. (1) jäsennetty muunnosten jälkeen.

Joukkoa Follow(Ak) kutsutaan säännöissä A:n ja k:nnen kokouksen ennakointijoukoksi, mistä johtuu algoritmin nimi.

LALR(1) ja täysi LR(1)

Vaihto-vähennys- ja taitto-vähennysristiriidat voivat jäädä LALR(1)-kieliopin muunnoksen jälkeen. Tämä tarkoittaa, että tähän kielioppiin tarvitaan täydellinen LR(1)-jäsennin, joka on paljon monimutkaisempi (LR(0)/SLR(1)/LALR(1)-algoritmit eivät säilytä mitään tietoa jo jäsennetystä osasta. syötevirta, vaikka koko LR(1) tekee, ja siksi vaikeampi), mutta voi jäsentää minkä tahansa yhteydettömän yksiselitteisen kieliopin.

Joidenkin tietojen mukaan (täsmennä!), kaikki LL(1) -kieliopit voidaan muuntaa LALR(1) jäsentämäksi lomakkeeksi.

Käytännön sovellus

Käytetään jäsentäjägeneraattorissa yacc ja sen johdannaisissa, kuten GNU bisonissa.

Suurimmalla osalla todella käytetyistä ohjelmointikielistä on LALR(1)-kielioppi, eli tämäntyyppiset jäsentimet riittävät jäsentämään useimmat todella käytetyt kielet.

GNU C -kääntäjä käyttää yaccia jäsentimen rakentamiseen. Ehkä (merkkijonojen grammar.y ja yacc esiintyminen suoritettavan moduulin rungossa) Microsoft tekee samoin rakentaakseen C-kääntäjänsä .