import random
import re
from collections import OrderedDict


class Grammar:
    EPSILON: str = "epsilon"

    def __init__(self, text: str):
        self.productions: OrderedDict[str, list[list[str]]] = OrderedDict()
        self.start_symbol: str = ""
        self._parse_productions(text)

        self.terminals: set[str] = set()
        self._find_terminals()

        self.first_sets: dict[str, set[str]] = {}
        self._calculate_first_sets()

        self.follow_sets: dict[str, set[str]] = {}
        self._calculate_follow_sets()

        self.lookup_table: dict[str, dict[str, list[str]]] = {}
        self._fill_lookup_table()

        # Сопостовляем уникальный номер с каждым правилом
        self.rule_numbers = {}
        rule_idx = 1
        for nt, rules in self.productions.items():
            for rule in rules:
                self.rule_numbers[(nt, tuple(rule))] = rule_idx
                rule_idx += 1

    def _parse_productions(self, text: str):
        for line in text.splitlines():
            line = line.strip()
            if not line:
                continue

            non_terminal, rule = line.split("->")
            if self.start_symbol == "":
                self.start_symbol = non_terminal.strip()

            non_terminal = non_terminal.strip()
            rules = [
                [
                    symbol.strip('"')
                    for symbol in re.findall(r"\".*?\"|\S+", rule.strip())
                    if symbol.strip('"') != self.EPSILON
                ]
                for rule in rule.split("|")
            ]

            if non_terminal not in self.productions:
                self.productions[non_terminal] = []

            self.productions[non_terminal].extend(rules)

    def _find_terminals(self):
        for rules in self.productions.values():
            for rule in rules:
                for symbol in rule:
                    if symbol not in self.productions:
                        self.terminals.add(symbol)

    def _calculate_first_sets(self):
        # Инициализация FIRST для всех символов
        for non_terminal in self.productions:
            self.first_sets[non_terminal] = set()

        # Для терминалов FIRST содержит только сам терминал
        for terminal in self.terminals:
            self.first_sets[terminal] = {terminal}

        # Вычисление FIRST для нетерминалов
        changed = True
        while changed:
            changed = False
            for non_terminal, rules in self.productions.items():
                for rule in rules:
                    if not rule:  # Пустое правило (эпсилон)
                        if "" not in self.first_sets[non_terminal]:
                            self.first_sets[non_terminal].add("")
                            changed = True
                    else:
                        all_can_derive_epsilon = True
                        for i, symbol in enumerate(rule):
                            # Добавляем все символы из FIRST(symbol) кроме эпсилон
                            first_without_epsilon = self.first_sets[symbol] - {""}
                            old_size = len(self.first_sets[non_terminal])
                            self.first_sets[non_terminal].update(first_without_epsilon)
                            if len(self.first_sets[non_terminal]) > old_size:
                                changed = True

                            # Если symbol не может порождать эпсилон, прерываем
                            if "" not in self.first_sets[symbol]:
                                all_can_derive_epsilon = False
                                break

                        # Если все символы в правиле могут порождать эпсилон,
                        # то и нетерминал может порождать эпсилон
                        if (
                            all_can_derive_epsilon
                            and "" not in self.first_sets[non_terminal]
                        ):
                            self.first_sets[non_terminal].add("")
                            changed = True

    def _calculate_follow_sets(self):
        # инициализировать Fo(S) = { $ }, а все остальные Fo(Ai) пустыми множествами
        for non_terminal in self.productions:
            self.follow_sets[non_terminal] = set()

        # Добавляем символ конца строки $ для начального символа
        self.follow_sets[self.start_symbol].add("$")

        # Повторяем, пока в наборах Follow происходят изменения
        changed = True
        while changed:
            changed = False

            # Для каждого нетерминала Aj в грамматике
            for non_terminal_j, rules in self.productions.items():

                # Для каждого правила Aj → w
                for rule in rules:

                    # Для каждого символа в правиле
                    for i, symbol in enumerate(rule):

                        # Если символ - нетерминал Ai
                        if symbol in self.productions:
                            # w' - остаток правила после Ai
                            remainder = rule[i + 1 :] if i + 1 < len(rule) else []

                            # Если есть терминалы после Ai (w' не пусто)
                            if remainder:
                                # Вычисляем First(w')
                                first_of_remainder = self._first_of_sequence(remainder)

                                # Если терминал a находится в First(w'), то добавляем a к Follow(Ai)
                                for terminal in first_of_remainder - {""}:
                                    if terminal not in self.follow_sets[symbol]:
                                        self.follow_sets[symbol].add(terminal)
                                        changed = True

                                # Если ε находится в First(w'), то добавляем Follow(Aj) к Follow(Ai)
                                if "" in first_of_remainder:
                                    old_size = len(self.follow_sets[symbol])
                                    self.follow_sets[symbol].update(
                                        self.follow_sets[non_terminal_j]
                                    )
                                    if len(self.follow_sets[symbol]) > old_size:
                                        changed = True

                            # Если w' пусто (Ai в конце правила), то добавляем Follow(Aj) к Follow(Ai)
                            else:
                                old_size = len(self.follow_sets[symbol])
                                self.follow_sets[symbol].update(
                                    self.follow_sets[non_terminal_j]
                                )
                                if len(self.follow_sets[symbol]) > old_size:
                                    changed = True

    def _first_of_sequence(self, sequence):
        """Вычисляет множество FIRST для последовательности символов"""
        if not sequence:
            return {""}

        result = set()
        all_can_derive_epsilon = True

        for symbol in sequence:
            # Добавляем First(symbol) без эпсилон к результату
            result.update(self.first_sets[symbol] - {""})

            # Если symbol не может порождать эпсилон, останавливаемся
            if "" not in self.first_sets[symbol]:
                all_can_derive_epsilon = False
                break

        # Если все символы могут порождать эпсилон, добавляем эпсилон к результату
        if all_can_derive_epsilon:
            result.add("")

        return result

    def _fill_lookup_table(self):
        # Для каждого нетерминала A
        for non_terminal, rules in self.productions.items():
            # Формируем таблицу синтаксического анализа
            self.lookup_table[non_terminal] = {}

            # Для каждого правила A → w
            for rule in rules:
                # Вычисляем First(w)
                first_of_rule = self._first_of_sequence(rule)

                # Для каждого терминала a в First(w)
                for terminal in first_of_rule - {""}:
                    self._add_to_lookup_table(non_terminal, terminal, rule)

                # Если эпсилон в First(w), то для каждого b в Follow(A)
                if "" in first_of_rule:
                    for terminal in self.follow_sets[non_terminal]:
                        self._add_to_lookup_table(non_terminal, terminal, rule)

    def _add_to_lookup_table(self, non_terminal, terminal, rule):
        if terminal in self.lookup_table[non_terminal]:
            raise ValueError(
                "\nГрамматика не является LL(1)-грамматикой.\n"
                f'Распознаваемый нетерминал: "{non_terminal}"\n'
                f'Поступающий на вход терминал: "{terminal}"\n'
                f"Неоднозначность между правилами:\n"
                f"{non_terminal} -> {' '.join(rule)}\n"
                f"{non_terminal} -> {' '.join(self.lookup_table[non_terminal][terminal])}"
            )
        self.lookup_table[non_terminal][terminal] = rule

    def format_rules(self) -> str:
        result = []
        sorted_rules = sorted(self.rule_numbers.items(), key=lambda x: x[1])

        for rule, number in sorted_rules:
            non_terminal, symbols = rule
            rule_text = f"{number}: {non_terminal} -> {' '.join(symbols)}"
            result.append(rule_text)

        return "\n".join(result)

    def format_lookup_table(self) -> str:
        """Форматирует таблицу синтаксического анализа в текстовом виде."""
        terminals = sorted(list(self.terminals))
        all_terminals = terminals + ["$"]

        # Определяем ширину каждого столбца
        header_widths = {"": len("") + 2}  # +2 для отступов
        for term in all_terminals:
            header_widths[term] = len(term) + 2

        # Определяем ширину столбцов для содержимого таблицы
        cell_widths = header_widths.copy()
        for non_terminal in self.productions:
            nt_width = len(non_terminal) + 2
            cell_widths[""] = max(cell_widths[""], nt_width)

            for terminal in all_terminals:
                if terminal in self.lookup_table[non_terminal]:
                    rule = self.lookup_table[non_terminal][terminal]
                    rule_num = self.rule_numbers.get((non_terminal, tuple(rule)), "")
                    cell_content = f"{rule_num}: {' '.join(rule)}"
                    cell_widths[terminal] = max(
                        cell_widths[terminal], len(cell_content) + 2
                    )

        # Создаем верхнюю границу таблицы
        border = "+"
        for term in [""] + all_terminals:
            border += "-" * cell_widths[term] + "+"

        # Создаем заголовок
        header = "|" + " " * cell_widths[""] + "|"
        for term in all_terminals:
            header += f" {term.center(cell_widths[term]-2)} |"

        # Создаем разделительную линию
        separator = "+"
        for term in [""] + all_terminals:
            separator += "=" * cell_widths[term] + "+"

        # Формируем строки таблицы
        rows = []
        for non_terminal in sorted(self.productions.keys()):
            row = f"| {non_terminal.ljust(cell_widths['']-2)} |"
            for terminal in all_terminals:
                if terminal in self.lookup_table[non_terminal]:
                    rule = self.lookup_table[non_terminal][terminal]
                    rule_num = self.rule_numbers.get((non_terminal, tuple(rule)), "")
                    cell_content = f"{rule_num}: {' '.join(rule)}"
                    row += f" {cell_content.ljust(cell_widths[terminal]-2)} |"
                else:
                    row += f" {' - '.ljust(cell_widths[terminal]-2)} |"
            rows.append(row)

        # Собираем таблицу
        table = [border, header, separator]
        for row in rows:
            table.append(row)
            table.append(border)

        return "\n".join(table)

    def format_first_sets(self) -> str:
        """Форматирует множества FIRST в читаемый вид."""
        result = []
        result.append("Множества FIRST:")
        result.append("=" * 40)

        # Сортируем для гарантии порядка вывода
        for symbol in sorted(self.first_sets.keys()):
            # Заменяем пустую строку на эпсилон для лучшей читаемости
            first_set = {
                self.EPSILON if item == "" else item for item in self.first_sets[symbol]
            }
            result.append(f"FIRST({symbol}) = {{{', '.join(sorted(first_set))}}}")

        return "\n".join(result)

    def format_follow_sets(self) -> str:
        """Форматирует множества FOLLOW в читаемый вид."""
        result = []
        result.append("Множества FOLLOW:")
        result.append("=" * 40)

        # Обрабатываем только нетерминалы
        for non_terminal in sorted(self.productions.keys()):
            follow_set = self.follow_sets.get(non_terminal, set())
            result.append(
                f"FOLLOW({non_terminal}) = {{{', '.join(sorted(follow_set))}}}"
            )

        return "\n".join(result)

    def analyze(self, input_tokens: list[str]) -> list[int]:
        input_tokens = input_tokens.copy()
        input_tokens += ["$"]
        input_pos = 0

        # Инициализируем стек с терминальным символом и начальным символом
        stack = ["$", self.start_symbol]

        rules_applied = []

        while stack:
            top = stack[-1]

            current_symbol = (
                input_tokens[input_pos] if input_pos < len(input_tokens) else "$"
            )

            # Случай 1: Верхний символ стека - нетерминал
            if top in self.productions:
                # Ищем правило в таблице синтаксического анализа
                if current_symbol in self.lookup_table[top]:
                    # Получаем правило
                    production = self.lookup_table[top][current_symbol]

                    # Удаляем нетерминал из стека
                    stack.pop()

                    # Добавляем правило в rules_applied
                    rule_number = self.rule_numbers[(top, tuple(production))]
                    rules_applied.append(rule_number)

                    # Добавляем правило в стек в обратном порядке
                    for symbol in reversed(production):
                        stack.append(symbol)
                else:
                    expected_symbols = list(self.lookup_table[top].keys())
                    raise ValueError(
                        f"Syntax error: expected one of {expected_symbols}, got '{current_symbol}'"
                    )

            # Случай 2: Верхний символ стека - терминал
            elif top != "$":
                if top == current_symbol:
                    # Удаляем терминал из стека
                    stack.pop()
                    # Переходим к следующему символу ввода
                    input_pos += 1
                else:
                    raise ValueError(
                        f"Syntax error: expected '{top}', got '{current_symbol}'"
                    )

            # Случай 3: Верхний символ стека - $
            else:  # top == "$"
                if current_symbol == "$":
                    # Успешный синтаксический анализ
                    stack.pop()  # Удаляем $ из стека
                else:
                    raise ValueError(
                        f"Syntax error: unexpected symbols at end of input: '{current_symbol}'"
                    )

        return rules_applied

    def generate(self, symbol: str | None = None) -> tuple[list[str], list[int]]:
        """Генерирует предложение по заданной грамматике. Возвращает список терминалов
        и список номеров применённых правил."""

        if symbol is None:
            return self.generate(self.start_symbol)

        # Если символ - терминал, возвращаем его
        if symbol not in self.productions:
            return [symbol], []

        # Выбираем случайное правило для нетерминала
        rules = self.productions[symbol]
        chosen_rule = random.choice(rules)

        # Получаем номер выбранного правила
        rule_number = self.rule_numbers[(symbol, tuple(chosen_rule))]

        # Инициализируем результаты
        terminals = []
        rule_numbers = [rule_number]

        # Разворачиваем каждый символ в правой части правила
        for s in chosen_rule:
            sub_terminals, sub_rules = self.generate(s)
            terminals.extend(sub_terminals)
            rule_numbers.extend(sub_rules)

        return terminals, rule_numbers

    def generate_derivation_steps(self, rule_numbers: list[int]) -> list[str]:
        """Преобразует список номеров правил в последовательность шагов вывода.
        Возвращает список строк, представляющих каждый шаг вывода."""

        # Получаем соответствие между номерами правил и самими правилами
        rule_details = {num: rule for rule, num in self.rule_numbers.items()}

        # Начинаем с начального символа
        current = self.start_symbol
        steps = [current]

        # Применяем каждое правило по порядку
        for rule_num in rule_numbers:
            if rule_num in rule_details:
                non_terminal, replacement = rule_details[rule_num]

                # Находим первое вхождение нетерминала и заменяем его
                words = current.split()
                for i, word in enumerate(words):
                    if word == non_terminal:
                        words[i : i + 1] = replacement
                        break

                current = " ".join(words)
                steps.append(current)

        return steps


def load_grammar(filename: str = "grammar.txt") -> Grammar | None:
    try:
        with open(filename, "r", encoding="utf-8") as file:
            text = file.read()
        grammar = Grammar(text)

        # Сохраняем информацию о грамматике в файлы
        with open("grammar_rules.txt", "w", encoding="utf-8") as output_file:
            output_file.write(grammar.format_rules())
            print("Правила грамматики с номерами сохранены в grammar_rules.txt")

        with open("grammar_lookup_table.txt", "w", encoding="utf-8") as output_file:
            output_file.write(grammar.format_lookup_table())
            print(
                "Таблица синтаксического анализа сохранена в grammar_lookup_table.txt"
            )

        with open("grammar_first.txt", "w", encoding="utf-8") as output_file:
            output_file.write(grammar.format_first_sets())
            print("Множества FIRST сохранены в grammar_first.txt")

        with open("grammar_follow.txt", "w", encoding="utf-8") as output_file:
            output_file.write(grammar.format_follow_sets())
            print("Множества FOLLOW сохранены в grammar_follow.txt")

        print(f"Грамматика успешно загружена из файла {filename}")
        return grammar
    except FileNotFoundError:
        print(f"Ошибка: Файл {filename} не найден")
        return None
    except ValueError as e:
        print(f"Ошибка при загрузке грамматики: {e}")
        return None
    except Exception as e:
        print(f"Неизвестная ошибка: {e}")
        return None


def tokenize_string(input_string: str) -> list[str]:
    input_string = input_string.replace(",", " , ").replace(".", " . ")
    return input_string.split()


def check_string(grammar: Grammar | None, input_string: str) -> None:
    if not grammar:
        print("Ошибка: Грамматика не загружена")
        return

    print(f"Проверка строки: '{input_string}'")
    try:
        input_tokens = tokenize_string(input_string)

        if not input_tokens:
            parse_result = grammar.analyze(input_tokens)
        else:
            try:
                input_tokens[0] = input_tokens[0][0].lower() + input_tokens[0][1:]
                parse_result = grammar.analyze(input_tokens)
            except ValueError as e:
                input_tokens[0] = input_tokens[0][0].upper() + input_tokens[0][1:]
                parse_result = grammar.analyze(input_tokens)

        print(f"Результат: Строка соответствует грамматике")
        print(f"Применённые правила: {parse_result}")

        # Сохраняем результат анализа в файл
        with open("analysis_result.txt", "w", encoding="utf-8") as f:
            f.write(f"Input: {input_string}\n")
            f.write("Applied rules: ")
            f.write(str(parse_result))
            f.write("\n\n")
            f.write("Derivation steps:\n")

            derivation_steps = grammar.generate_derivation_steps(parse_result)
            for step in derivation_steps:
                f.write(f"{step}\n")

        print("Подробный результат анализа сохранен в analysis_result.txt")
    except ValueError as e:
        print(f"Результат: Строка не соответствует грамматике")
        print(f"Ошибка: {e}")
    except Exception as e:
        print(f"Произошла ошибка при анализе: {e}")


def post_process_string(string: str) -> str:
    if string:
        string = string[0].upper() + string[1:]
    string = string.replace(" ,", ",")
    string = string.replace(" .", ".")
    string = string.replace(",.", ".")
    return string


def generate_string(grammar: Grammar | None) -> None:
    if not grammar:
        print("Ошибка: Грамматика не загружена")
        return

    try:
        terminals, rules = grammar.generate()
        generated_string = " ".join(terminals)
        generated_string = post_process_string(generated_string)
        print(f"Сгенерированная строка: {generated_string}")
        print(f"Применённые правила: {rules}")

        # Сохраняем результат генерации в файл
        with open("generation_result.txt", "w", encoding="utf-8") as f:
            f.write(f"Generated string: {generated_string}\n")
            f.write("Applied rules: ")
            f.write(str(rules))
            f.write("\n\n")
            f.write("Derivation steps:\n")

            derivation_steps = grammar.generate_derivation_steps(rules)
            for step in derivation_steps:
                f.write(f"{step}\n")

        print("Подробный результат генерации сохранен в generation_result.txt")
    except Exception as e:
        print(f"Произошла ошибка при генерации: {e}")


def main():
    print("Программа для работы с LL(1)-грамматиками")
    print("=" * 60)
    print("Варианты команд:")
    print(" - load <файл> - загрузить грамматику из файла (по умолчанию grammar.txt)")
    print(" - check <строка> - проверить, соответствует ли строка грамматике")
    print(" - generate - сгенерировать случайную строку по грамматике")
    print(" - exit - выход из программы")
    print("=" * 60)

    # Загружаем грамматику по умолчанию при старте
    grammar = load_grammar()

    while True:
        command = input("\nВведите команду: ").strip()

        if not command:
            continue

        parts = command.split(maxsplit=1)
        cmd = parts[0].lower()

        if cmd == "exit":
            print("Выход из программы.")
            break

        elif cmd == "load":
            filename = "grammar.txt"
            if len(parts) > 1:
                filename = parts[1].strip()
            grammar = load_grammar(filename)

        elif cmd == "check":
            input_string = ""
            if len(parts) > 1:
                input_string = parts[1].strip()
            check_string(grammar, input_string)

        elif cmd == "generate":
            generate_string(grammar)

        else:
            print(f"Неизвестная команда: {cmd}")
            print("Доступные команды: load, check, generate, exit")


if __name__ == "__main__":
    main()