SLR Parser Simulator

About This Simulation

This SLR parser simulator builds every part of an SLR(1) parser from a grammar you type: the augmented grammar, the LR(0) automaton (canonical collection of LR(0) items), FIRST and FOLLOW sets and the ACTION/GOTO parsing table. It then parses an input string and shows the stack, symbols, remaining input and action on every line.

Features

• Grammar input with -> or →, ε rules and | alternatives
• Automatic augmentation with rule 0 (S′ → S) and numbered productions
• Draggable LR(0) automaton with kernel and closure items
• FIRST and FOLLOW table with an explanation for each row
• ACTION and GOTO table with Sᵢ, Rᵢ and Acc entries, synced with the automaton
• Shift/reduce and reduce/reduce conflict detection
• Step-by-step parse trace: Stack, Symbols, Input and Action

Topics covered

• SLR(1) Parsing
• LR(0) Items
• Closure and GOTO
• FIRST and FOLLOW
• ACTION and GOTO Table
• Shift-Reduce Parsing
• Bottom-Up Parsing

Explanation

SLR (Simple LR) parsing is a bottom-up parsing method. The parser reads the input left to right and builds a rightmost derivation in reverse: it shifts tokens onto a stack and reduces them by grammar rules when the top of the stack matches a rule's right side. An SLR parser decides when to reduce using the LR(0) automaton and the FOLLOW sets of the grammar.

How it works

1. Augment the grammar with a new start rule S′ → S, numbered 0.
2. Build the LR(0) items. An item such as E → E • + T shows how much of a rule has been seen: the part before the dot has been read.
3. Start from CLOSURE({S′ → • S}). For each symbol X after a dot, GOTO(I, X) moves the dot over X and takes the closure; each new set of items is a new state.
4. Compute FIRST for every non-terminal, then FOLLOW, starting with $ in FOLLOW(S′).
5. Fill the table: a transition on a terminal a gives ACTION[i, a] = Sⱼ; a transition on a non-terminal A gives GOTO[i, A] = j; a complete item A → α • gives Rₖ under every terminal in FOLLOW(A); S′ → S • gives Acc under $.
6. Parse: look up ACTION[top state, next token]. Shift pushes the next state; reduce by A → α pops |α| states and pushes GOTO[new top, A]; Acc means the input is accepted, and a blank cell is an error.

Why it matters

LR parsers are used by parser generators such as Yacc and Bison, and building an SLR table by hand is one of the most common compiler design exam questions. Practising the item sets, FOLLOW sets and table entries on your own grammars is the fastest way to learn bottom-up parsing.

Frequently Asked Questions

Related Simulations