Untitled

class Grammar:
    def __init__(self):
        self.rules = []
        self.terminals = set()
        self.non_terminals = set()
        self.start_symbol = None
        self.symbols = set()

    def add_rule(self, left, right):
        self.rules.append((left, right))
        self.non_terminals.add(left)
        self.symbols.add(left)
        for symbol in right:
            if symbol.isupper():  # Non-terminal symbols
                self.non_terminals.add(symbol)
            else:  # Terminal symbols
                self.terminals.add(symbol)
                self.symbols.add(symbol)

    def set_start_symbol(self, start):
        self.start_symbol = start

    def get_start_symbol(self):
        return self.start_symbol

class LR1Item:
    def __init__(self, left, right, dot_position, lookahead):
        self.left = left
        self.right = right
        self.dot_position = dot_position
        self.lookahead = lookahead
    
    def __str__(self):
        return f"{self.left} -> {''.join(self.right[:self.dot_position])}.{''.join(self.right[self.dot_position:])}, {self.lookahead}"

    def __eq__(self, other):
        return (self.left == other.left and 
                self.right == other.right and 
                self.dot_position == other.dot_position and 
                self.lookahead == other.lookahead)

    def __hash__(self):
        return hash((self.left, tuple(self.right), self.dot_position, self.lookahead))

def construct_lr1_items(grammar):
    items = set()
    # Augmented start symbol rule
    items.add(LR1Item(grammar.start_symbol, ['.'], 0, '$'))
    for left, right in grammar.rules:
        for i in range(len(right) + 1):  # Including position after the last symbol
            lookahead = '$'  # Placeholder for simplicity; real lookahead computation needed
            items.add(LR1Item(left, right, i, lookahead))
    return items

def display_lr1_items(lr1_items):
    print("LR(1) Items:")
    for item in lr1_items:
        print(item)

def merge_lr1_items(lr1_items):
    merged_items = set()
    for item in lr1_items:
        core = (item.left, item.right, item.dot_position)
        matching_items = {i for i in merged_items if (i.left, i.right, i.dot_position) == core}
        if matching_items:
            # Merge lookaheads from matching items
            lookaheads = {item.lookahead for item in matching_items} | {item.lookahead}
            for match in matching_items:
                merged_items.remove(match)
            for new_item in matching_items:
                merged_items.add(LR1Item(new_item.left, new_item.right, new_item.dot_position, list(lookaheads)))
        else:
            merged_items.add(item)
    return merged_items

# Construct LALR parsing table (simplified)
def construct_lalr_table(grammar, merged_items):
    action_table = {}
    goto_table = {}
    states = list(merged_items)  # Each item represents a state for simplicity

    for item in states:
        if item.dot_position == len(item.right):  # If dot is at the end of the rule
            if item.left == grammar.start_symbol:
                action_table[(item.left, item.lookahead)] = 'accept'  # Accepting the input
            else:
                action_table[(item.left, item.lookahead)] = 'reduce'  # Reduce operation
        else:
            next_symbol = item.right[item.dot_position]
            if next_symbol.isupper():  # Non-terminal, goto operation
                goto_table[(item.left, next_symbol)] = 'goto'
            else:  # Terminal, shift operation
                action_table[(item.left, item.lookahead)] = 'shift'

    return action_table, goto_table

def display_parse_table(action_table, goto_table):
    print("\nParse Table:")
    print("\nAction Table:")
    for (state, lookahead), action in action_table.items():
        print(f"State {state}, Lookahead {lookahead}: {action}")
    
    print("\nGoto Table:")
    for (state, non_terminal), action in goto_table.items():
        print(f"State {state}, Non-terminal {non_terminal}: {action}")

# Perform LALR parsing (simplified)
def lalr_parse(input_string, start_symbol, action_table, goto_table):
    stack = [start_symbol]
    input_tokens = list(input_string) + ['$']  # Add end-of-input symbol
    index = 0

    while stack:
        current_symbol = input_tokens[index]
        current_state = stack[-1]

        # Check the action table
        action = action_table.get((current_state, current_symbol), None)

        if action == 'shift':
            stack.append(current_symbol)
            index += 1
        elif action == 'reduce':
            # Example: Reduction based on a rule
            rule = current_state
            stack = stack[:-len(rule)]  # pop the right side of the rule
            stack.append(rule[0])  # push the left side (non-terminal)
        elif action == 'accept':
            return True
        else:
            return False  # Error in parsing

    return False  # If no action was taken

# Example grammar for arithmetic expressions
grammar = Grammar()
grammar.add_rule('S', ['E'])
grammar.add_rule('E', ['E', '+', 'T'])
grammar.add_rule('E', ['T'])
grammar.add_rule('T', ['T', '*', 'F'])
grammar.add_rule('T', ['F'])
grammar.add_rule('F', ['(', 'E', ')'])
grammar.add_rule('F', ['id'])
grammar.set_start_symbol('S')

# Construct LR(1) items
lr1_items = construct_lr1_items(grammar)
display_lr1_items(lr1_items)

# Merge LR(1) items into LALR items
merged_items = merge_lr1_items(lr1_items)

# Display merged LALR items
print("\nMerged LALR Items:")
display_lr1_items(merged_items)

# Construct the LALR parsing table
action_table, goto_table = construct_lalr_table(grammar, merged_items)

# Display the parse table (action and goto tables)
display_parse_table(action_table, goto_table)

# Example parsing input: 'id+id*id'
input_string = 'id+id*id'
result = lalr_parse(input_string, grammar.get_start_symbol(), action_table, goto_table)
print(f"Parse result for '{input_string}': {result}")