Parser SLR

Parser SLR (ang. SLR parser, Simple LR parser) jest to parser typu LR, utworzony na podstawie zadanej gramatyki formalnej G, którego tabela parsingu konstruowana jest na podstawie kanonicznej rodziny zbiorów sytuacji LR(0) oraz zbiorów FOLLOW dla gramatyki G. Gramatyka, dla której można skonstruować deterministyczny parser SLR nazywana jest gramatyką SLR. Język posiadający generującą go gramatykę SLR nazywany jest językiem SLR. SLR(k) jest wyznaczane na podstawie sytuacji LR(0) i FOLLOWk. Zazwyczaj przez SLR jest rozumiane SLR(1). Parser SLR zazwyczaj jest tworzony przez generator parserów SLR, który na podstawie zadanej gramatyki bezkontekstowej konstruuje maszynę stanów LR(0) oraz oblicza zbiory następników (FOLLOW) dla symboli nieterminalnych. Następnie na tej podstawie tworzy tabele parsingu dla generowanego parsera. Sam parser od innych parserów typu LR (LALR, kanoniczny LR) różni się właśnie sposobem konstrukcji (i zazwyczaj zawartością) tej tablicy, natomiast sam algorytm analizy jest identyczny. Jeśli w tabeli parsingu istnieje konflikt (dwie różne akcje w jednej komórce tabeli) oznacza to, że powstały parser nie jest deterministyczny i w zasadzie do celów praktycznych się nie nadaje (co przez generatory jest zazwyczaj traktowane jako błąd) i trzeba albo zmodyfikować gramatykę albo zastosować lepszy generator (np. LALR). Jeśli w gramatyce jest produkcja A → ω, to jeśli parser znajdzie się w stanie oznaczającym, że na wierzchołku stosu jest ciąg ω, a następny symbol na wejściu należy do FOLLOW(A), to dokona redukcji ω na A. Problemem parserów SLR jest to, że wyznaczanie zbioru look-ahead jest zbyt uproszczone, ponieważ używa jedynie reguł gramatyki. Dokładniejszą metodą wyznaczania zbiorów look-ahead jest analizowanie symboli nieterminalnych w każdym ich stanie za pomocą maszyny stanów LR(0). Dokładniejsze zbiory look-ahead są nazywane zbiorami parsingu LALR.Główną zaletą SLR w stosunku do LALR jest łatwość konstrukcji, płaci się jednak za to zmniejszeniem ilości rozpoznawalnych gramatyk, gdyż dosyć często interesujące gramatyki nie są SLR, natomiast są już LALR.