Compiler-designConceptBeginner · 3 min read

SLR Parser: Definition, How It Works, and Usage

An SLR parser (Simple LR parser) is a type of bottom-up parser used in compilers to analyze the syntax of programming languages. It uses a parsing table built from a grammar's LR(0) items and follow sets to decide shifts and reductions, making it efficient for many programming languages.

⚙️

How It Works

An SLR parser reads the input from left to right and tries to build the correct structure (parse tree) by shifting symbols onto a stack or reducing them based on grammar rules. It uses a table that tells it when to shift (read more input) or reduce (apply a grammar rule) depending on the current state and next input symbol.

Think of it like sorting puzzle pieces: the parser keeps adding pieces (symbols) until it recognizes a pattern that matches a grammar rule, then it replaces those pieces with a single piece representing that rule. This process continues until the entire input is parsed or an error is found.

The SLR parser creates its decision table using simple LR(0) items combined with the follow sets of grammar symbols, which helps it decide the correct action without backtracking.

💻

Example

This example shows a simple SLR parsing table for a grammar and how the parser decides actions based on input and stack state.

python

grammar = {
    'S': ['CC'],
    'C': ['cC', 'd']
}

# Simplified SLR parsing table for this grammar
parsing_table = {
    0: {'c': 's3', 'd': 's4', 'C': 2},
    1: {'$': 'accept'},
    2: {'c': 's3', 'd': 's4', 'C': 5},
    3: {'c': 's3', 'd': 's4', 'C': 6},
    4: {'c': 'r2', 'd': 'r2', '$': 'r2'},
    5: {'c': 'r1', 'd': 'r1', '$': 'r1'},
    6: {'c': 'r3', 'd': 'r3', '$': 'r3'}
}

input_string = list('ccdd$')
stack = [0]

print('Stack\tInput\tAction')
while True:
    state = stack[-1]
    lookahead = input_string[0]
    action = parsing_table[state].get(lookahead, 'error')
    print(f'{stack}\t{input_string}\t{action}')

    if action == 'accept':
        print('Input accepted.')
        break
    elif action.startswith('s'):
        stack.append(lookahead)
        stack.append(int(action[1:]))
        input_string.pop(0)
    elif action.startswith('r'):
        rule_num = int(action[1:])
        if rule_num == 1:  # C -> cC
            pop_len = 4
        elif rule_num == 2:  # C -> d
            pop_len = 2
        elif rule_num == 3:  # S -> CC
            pop_len = 4
        else:
            print('Unknown rule')
            break
        for _ in range(pop_len):
            stack.pop()
        state = stack[-1]
        lhs = 'C' if rule_num in [1,2] else 'S'
        stack.append(lhs)
        stack.append(parsing_table[state][lhs])
    else:
        print('Parsing error.')
        break

Output

Stack Input Action [0] ['c', 'c', 'd', 'd', '$'] s3 [0, 'c', 3] ['c', 'd', 'd', '$'] s3 [0, 'c', 3, 'c', 3] ['d', 'd', '$'] s4 [0, 'c', 3, 'c', 3, 'd', 4] ['d', '$'] r2 [0, 'c', 3, 'c', 3] ['d', '$'] s4 [0, 'c', 3, 'c', 3, 'd', 4] ['$'] r2 [0, 'c', 3, 'c', 3] ['$'] r1 [0, 'c', 3, 'C', 6] ['$'] r3 [0, 'S', 1] ['$'] accept Input accepted.

🎯

When to Use

Use an SLR parser when you need a simple and efficient bottom-up parser for programming languages with grammars that are not too complex. It works well for many common languages and is easier to implement than more powerful LR parsers.

SLR parsers are suitable for educational purposes, simple compilers, and tools where grammar conflicts are minimal. However, for more complex grammars, more advanced parsers like LALR or Canonical LR are preferred.

✅

Key Points

SLR parser is a bottom-up parser using LR(0) items and follow sets.
It builds a parsing table to decide shift and reduce actions.
Efficient for many programming language grammars but limited for complex ones.
Good for simple compiler implementations and learning parsing concepts.

✅

Key Takeaways

SLR parser uses a table-driven approach to parse input bottom-up efficiently.

It combines LR(0) items with follow sets to decide parsing actions.

Best suited for grammars with minimal conflicts and simpler language syntax.

Easier to implement than more powerful LR parsers but less powerful.

Commonly used in teaching and simple compiler projects.