SLR(1)

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2014. december 1-jén felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

Az SLR(1) egy alulról felfelé irányuló elemzési algoritmus.

Ez az LR(0) algoritmus kiterjesztése . Bizonyos esetekben működik, amikor egy LR(0) elemző tábla felépítése egy adott nyelvtanhoz nem lehetséges a shift-cast vagy cast-cast ütközések miatt. Így az SLR(1) szerint elemzett nyelvtanok osztálya (kr. "SLR(1)-grammatika") szélesebb, mint az LR(0)-nyelvtanok osztálya.

Maga az elemzési algoritmus (amely az analizátort a bemeneti adatfolyamnak megfelelően hajtja végre) ugyanaz az SLR(1) és LR(0) - és tágabb értelemben az LALR(1) esetében is . Csak azok az algoritmusok különböznek egymástól, amelyek az elemző táblát a nyelvtan alapján állítják össze az analizátor előállítása során.

Leírás

A nyelvtan minden nem A termináljához a First(A) terminálok készlete jön létre, a következőképpen definiálva:

ha a nyelvtannak van egy szabálya, amelynek bal oldalán egy A, a jobb oldalon pedig terminállal kezdődik, akkor ez a terminál az Első(A)-ban van.
ha a nyelvtannak van egy szabálya, amelynek bal oldalán egy A, és jobb oldalon egy nem terminálissal kezdődik (B-vel), akkor az Első(B) szigorúan az Első(A)-ba tartozik.
a First(A) nem tartalmaz más terminálokat

Ugyanezeket a készleteket használjuk az LL(1) analizátor felépítéséhez.

Továbbá az First(A) halmazok alapján létrejönnek a Follow(A) készletek, a következőképpen definiálva

Ha a nyelvtannak van egy szabálya, ahol az A nem az utolsó helyen fordul elő, és egy terminál követi, akkor a terminál szerepel a Follow(A)-ban.
ha a nyelvtannak van egy szabálya, ahol A nem az utolsó helyen fordul elő, és egy nem terminális követi (B-vel jelölve), akkor az First(B) szigorúan benne van a Follow(A)-ban.
ha a nyelvtannak van egy szabálya, ahol A az utolsó pozícióban fordul elő, akkor a Follow(C) szigorúan benne van a Follow(A)-ban, ahol C a szabály bal oldala.
a Follow(A) nem tartalmaz más terminálokat

(lehet általánosítani ezeket a feltételeket a B -> null szabályok megléte esetén)

Ezután az LR(0-hoz hasonlóan) az elemző tábla generálódik, azzal a különbséggel, amikor az öntési műveleteket megadjuk. Az S állapot és a C bemeneti szimbólum leadása csak akkor kerül táblázatba, ha az S-ben van egy karakterlánc, amely megfelel a szabály teljes jobb oldalának, és a szabály bal oldalán lévő nem terminális N teljesíti a "C követésben van" N)".

Ez azt eredményezi, hogy az SLR(1) kevesebb kísérletet tesz arra, hogy "castot" helyezzen az elemzési táblázat cellájába, ami csökkenti a castokkal való ütközés kockázatát, néha teljesen megszabadul tőlük, és olyan nyelvtant készít, amelyet az LR(0) nem értelmez. ) értelmezhető.

Gyakorlati alkalmazás

Szinte nincs benne (kivéve az oktatási célokat), mivel a nyelvtanok szűk osztályát elemzik. Gyakorlati alkalmazás az LALR(1), amely az SLR(1) általánosítása.

Az unáris és bináris operátorokat és zárójeleket tartalmazó aritmetikai kifejezések elemzése SLR(1) segítségével történik.

Lásd még