def compute_first(productions):
    first = {nt: set() for nt in productions}
    def first_string(s):
        r = set()
        if s == "": r.add('ε'); return r
        for symbol in s:
            if not symbol.isupper():
                r.add(symbol); break
            else:
                r |= (first[symbol] - {'ε'})
                if 'ε' not in first[symbol]: break
        else: r.add('ε')
        return r
    changed = True
    while changed:
        changed = False
        for nt, prods in productions.items():
            for prod in prods:
                temp = set()
                if prod == 'ε' or prod == '': temp.add('ε')
                else:
                    for symbol in prod:
                        if not symbol.isupper():
                            temp.add(symbol); break
                        else:
                            temp |= (first[symbol] - {'ε'})
                            if 'ε' not in first[symbol]: break
                    else: temp.add('ε')
                before = len(first[nt])
                first[nt] |= temp
                if len(first[nt]) != before: changed = True
    return first
def compute_follow(productions, first, start_symbol):
    follow = {nt: set() for nt in productions}
    follow[start_symbol].add('$')
    changed = True
    while changed:
        changed = False
        for nt, prods in productions.items():
            for prod in prods:
                for i, symbol in enumerate(prod):
                    if symbol.isupper():
                        beta = prod[i+1:]
                        first_beta = set()
                        if beta == "": first_beta.add('ε')
                        else:
                            for s in beta:
                                if not s.isupper():
                                    first_beta.add(s); break
                                else:
                                    first_beta |= (first[s] - {'ε'})
                                    if 'ε' not in first[s]: break
                            else: first_beta.add('ε')
                        before = len(follow[symbol])
                        follow[symbol] |= (first_beta - {'ε'})
                        if 'ε' in first_beta: follow[symbol] |= follow[nt]
                        if len(follow[symbol]) != before: changed = True
    return follow
def build_parsing_table(productions, first, follow, nts_order, terms_order):
    table = {nt: {t: None for t in terms_order} for nt in productions}
    for nt, prods in productions.items():
        for prod in prods:
            first_prod = set()
            if prod == 'ε' or prod == '': first_prod.add('ε')
            else:
                for symbol in prod:
                    if not symbol.isupper():
                        first_prod.add(symbol); break
                    else:
                        first_prod |= (first[symbol] - {'ε'})
                        if 'ε' not in first[symbol]: break
                else: first_prod.add('ε')
            for t in (first_prod - {'ε'}):
                table[nt][t] = f"{nt}->{prod}"
            if 'ε' in first_prod:
                for t in follow[nt]:
                    table[nt][t] = f"{nt}->{prod}"
    return table
def simulate_parsing(inp, start, table):
    stack = [start, '$']; ip = 0; actions = []
    while True:
        curr_stack = "".join(stack)
        curr_inp = inp[ip:]
        top = stack[0]
        if not top.isupper():
            if top == inp[ip]:
                actions.append((curr_stack, curr_inp, "POP ACTION"))
                stack.pop(0); ip += 1
            else:
                actions.append((curr_stack, curr_inp, f"Error: expected '{top}'"))
                return actions, False
        else:
            curr_sym = inp[ip] if ip < len(inp) else '$'
            rule = table[top].get(curr_sym)
            if rule is None:
                actions.append((curr_stack, curr_inp, f"Error: no rule for {top} on '{curr_sym}'"))
                return actions, False
            else:
                actions.append((curr_stack, curr_inp, rule))
                stack.pop(0)
                prod = rule.split("->")[1]
                if prod != 'ε' and prod != '':
                    for symbol in prod[::-1]:
                        stack.insert(0, symbol)
        if stack == ['$'] and inp[ip:] == '$':
            actions.append(("$", "$", "POP ACTION"))
            stack.pop(0); ip += 1; break
    return (actions, True) if ip == len(inp) else (actions, False)
def print_parsing_table(table, nts_order, terms_order):
    print("\n\t\t\t\t\t\t\t The LL(1) Parsing Table for the above grammer :-")
    print("\t\t\t\t\t\t\t^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n")
    sep = "  " + "=" * 101
    print("\t\t\t" + sep)
    print("\t\t\t\t|\t" + "\t\t".join(terms_order))
    print("\t\t\t" + sep.replace("=", "-"))
    for nt in nts_order:
        row = f"\t\t\t   {nt}\t|\t" + "\t\t".join(table[nt].get(t) or "" for t in terms_order)
        print(row)
        print("\t\t\t" + sep.replace("=", "-"))
def print_parsing_steps(actions):
    print("\n\t\t\t\t\t===========================================================================\n")
    print("\t\t\t\t\t\tStack\t\t\tInput\t\t\tAction")
    print("\t\t\t\t\t===========================================================================\n")
    for s, i, a in actions:
        print(f"\t\t\t\t\t\t{''.join(reversed(s)):<24}{i:<24}{a}")
    print("\n\t\t\t\t\t===========================================================================\n")
def main():
    count = int(input("How many productions? : "))
    print(f"\nEnter {count} productions in form A->B where A and B are grammar symbols:")
    productions, order = {}, []
    for _ in range(count):
        prod_str = input().strip()
        if '->' not in prod_str:
            print("Incorrect production format. Expected A->B."); return
        left, right = map(str.strip, prod_str.split('->', 1))
        if left == "":
            print("Nonterminal missing in production."); return
        if left not in productions:
            productions[left] = []; order.append(left)
        productions[left].append(right)
    start = order[0]
    first = compute_first(productions)
    follow = compute_follow(productions, first, start)
    print("\nFirst sets:")
    for nt in order:
        print(f"First({nt}) = {{ {', '.join(sorted(first[nt]))} }}")
    print("\nFollow sets:")
    for nt in order:
        print(f"Follow({nt}) = {{ {', '.join(sorted(follow[nt]))} }}")
    terms_order = ['+', '*', '(', ')', 'i', '$']
    table = build_parsing_table(productions, first, follow, order, terms_order)
    print_parsing_table(table, order, terms_order)
    inp = input("\nPlease enter the desired INPUT STRING = ").strip()
    if inp[-1] != '$': inp += '$'
    actions, accepted = simulate_parsing(inp, start, table)
    print_parsing_steps(actions)
    print("\n\t\t\t" + "=" * 90)
    print("\t\t\t\t\t\t\t\tYOUR STRING HAS BEEN ACCEPTED !!" if accepted else "\t\t\t\t\t\t\t\tYOUR STRING HAS BEEN REJECTED !!")
    print("\t\t\t" + "=" * 90)
if __name__ == "__main__":
    main()