SLR steht für Simple LR. Der SLR-Parser ist die einfachste Vertreterin der LR-Parser-Familie: Er arbeitet bottom-up mit Shift- und Reduce-Schritten, verwendet aber nur die FOLLOW-Menge eines Nichtterminals, um über Reduktionen zu entscheiden. Entwickelt wurde er 1971 von Frank DeRemer, gemeinsam mit dem mächtigeren LALR-Parser.
So funktioniert ein SLR-Parser
Der SLR-Parser besitzt drei Bausteine:
- LR(0)-Items: Zustände, die beschreiben, an welcher Stelle der rechten Regelseite sich der Parser gerade befindet.
- FOLLOW-Mengen: Für jedes Nichtterminal die Menge der Terminale, die ihm in einer Ableitung folgen können.
- Aktions-Tabellen: Die ACTION-Tabelle entscheidet pro Zustand und Lookahead-Zeichen über Shift oder Reduce.
Eine Reduktion auf ein Nichtterminal A ist nur erlaubt, wenn das aktuelle Eingabezeichen in FOLLOW(A) liegt. Diese globale Lookahead-Information ist der Grund, warum SLR(1) Grammatiken ablehnt, die eigentlich eindeutig sind: Manche Konstrukte brauchen im selben Zustand verschiedene Lookahead-Mengen, je nach Kontext — das kann die eine FOLLOW-Menge nicht leisten.
Grenzen und Einsatz
Klassische Gegenbeispiele für SLR(1) sind Grammatiken mit Zuweisungen, bei denen dasselbe Nichtterminal links und rechts einer Zuweisung vorkommt. Dann entstehen Shift/Reduce-Konflikte, obwohl die Grammatik eindeutig ist. Solche Grammatiken brauchen die feineren Lookaheads des LALR- oder kanonischen LR-Verfahrens. Jede SLR-Grammatik ist automatisch auch LALR(1)-beschreibbar — SLR ist also eine echte Teilmenge.
In der Praxis taucht SLR vor allem in Lehrbüchern und im Compilerbau-Unterricht auf; reale Parser-Generatoren wie Yacc oder Bison erzeugen standardmäßig LALR(1)-Parser. Zum Verständnis der LR-Familie ist SLR aber der ideale Einstieg, weil die Tabellen klein und die Idee klar nachvollziehbar sind.
Einordnung in die Parser-Familie
- LR(0): ganz ohne Lookahead — erkennt nur sehr wenige Grammatiken.
- SLR(1): Lookahead nur als FOLLOW-Menge — kompakt, aber mit Konfliktgrenzen.
- LALR(1): propagierte Lookaheads auf LR(0)-Zuständen — der praktische Standard.
- LR(1): kanonisch, exakte Lookaheads — mächtigste Tabelle, oft riesig.