LR Parsing — Bottom-Up Parsing with Shift-Reduce

def closure(items, grammar):
    closure_set = set(items)
    changed = True
    while changed:
        changed = False
        for item in list(closure_set):
            dot_pos = item.index('.')
            if dot_pos < len(item) - 1:
                next_symbol = item[dot_pos + 1]
                if next_symbol in grammar:
                    for production in grammar[next_symbol]:
                        new_item = (next_symbol,) + ('.',) + tuple(production)
                        if new_item not in closure_set:
                            closure_set.add(new_item)
                            changed = True
    return closure_set

def goto(items, symbol, grammar):
    moved = set()
    for item in items:
        dot_pos = list(item).index('.')
        if dot_pos < len(item) - 1 and list(item)[dot_pos + 1] == symbol:
            new_list = list(item)
            new_list[dot_pos] = new_list[dot_pos + 1]
            new_list[dot_pos + 1] = '.'
            moved.add(tuple(new_list))
    return closure(moved, grammar)

grammar_lr = {
    "E'": [['E']],
    'E': [['E', '+', 'T'], ['T']],
    'T': [['T', '*', 'F'], ['F']],
    'F': [['(', 'E', ')'], ['id']]
}

start = closure({("E'", '.', 'E')}, grammar_lr)
print("Initial closure set:")
for item in sorted(start):
    print(' '.join(str(s) for s in item))

def build_lr0_table(grammar, terminals):
    items = closure({("E'", '.', next(iter(grammar.keys())))}, grammar)
    states = [items]
    state_map = {tuple(sorted(items)): 0}
    action = {}
    goto_table = {}
    queue = [0]

    while queue:
        current = queue.pop(0)
        items = states[current]
        symbols_seen = set()

        for item in items:
            dot_pos = list(item).index('.')
            if dot_pos < len(item) - 1:
                symbols_seen.add(list(item)[dot_pos + 1])

        for symbol in symbols_seen:
            new_items = goto(items, symbol, grammar)
            key = tuple(sorted(new_items))
            if key not in state_map:
                state_map[key] = len(states)
                states.append(new_items)
                queue.append(len(states) - 1)

            for item in items:
                dot_pos = list(item).index('.')
                if dot_pos < len(item) - 1 and list(item)[dot_pos + 1] == symbol:
                    if symbol in terminals or symbol == '$':
                        action[(current, symbol)] = ('S', state_map[key])
                    else:
                        goto_table[(current, symbol)] = state_map[key]

        for item in items:
            dot_pos = list(item).index('.')
            if dot_pos == len(item) - 1:
                lhs = item[0]
                if lhs == "E'":
                    action[(current, '$')] = ('ACC',)
                else:
                    prod_len = len(item) - 2
                    for t in terminals + ('$',):
                        action[(current, t)] = ('R', lhs, list(item[1:-1]))

    return action, goto_table, states

terminals = ['id', '+', '*', '(', ')']
action, goto_table, states = build_lr0_table(grammar_lr, terminals)

print("Number of states:", len(states))
for key, val in sorted(action.items()):
    state, sym = key
    print(f"ACTION[{state}, {sym}] = {val}")

def lr_parse(tokens, action, goto_table, grammar):
    stack = [0]
    pos = 0
    tokens = list(tokens) + [('$', '$')]

    while True:
        state = stack[-1]
        token_type = tokens[pos][0]

        act = action.get((state, token_type))
        if act is None:
            print(f"Syntax error at token {tokens[pos]}")
            return False

        if act[0] == 'S':
            stack.append(token_type)
            stack.append(act[1])
            pos += 1
            print(f"Shift {token_type} -> state {act[1]}")

        elif act[0] == 'R':
            lhs, production = act[1], act[2]
            pop_count = len(production) * 2
            stack = stack[:-pop_count] if pop_count > 0 else stack
            state = stack[-1]
            stack.append(lhs)
            stack.append(goto_table.get((state, lhs), 0))
            print(f"Reduce by {lhs} -> {' '.join(production)}")

        elif act[0] == 'ACC':
            print("Parse successful!")
            return True

tokens = [('id', 'x'), ('+', '+'), ('id', 'y'), ('*', '*'), ('id', 'z')]
lr_parse(tokens, action, goto_table, grammar_lr)