using System;
using System.Collections.Generic;

public class LRParser
{
    private Grammar grammar;
    private LRTable table;

    public LRParser(Grammar grammar, LRTable table)
    {
        this.grammar = grammar;
        this.table = table;
    }


// Метод для разбора входной строки
public void Parse(string input)
{
    // Создаем стек состояний и стек символов
    Stack<int> stateStack = new Stack<int>();
    Stack<Symbol> symbolStack = new Stack<Symbol>();

    stateStack.Push(0); // Инициализация начального состояния

    int index = 0;
    while (index < input.Length)
    {
        int currentState = stateStack.Peek(); // Получаем текущее состояние
        char currentInput = input[index]; // Получаем текущий входной символ
        ActionTableEntry entry = table.GetAction(currentState, currentInput); // Получаем запись из таблицы действий

        if (entry == null)
        {
            Console.WriteLine("Error: Invalid input at index " + index);
            return;
        }

        if (entry.Action == ActionType.Shift) // Если действие - сдвиг
        {
            stateStack.Push(entry.Value); // Переходим к новому состоянию
            symbolStack.Push(new Symbol(currentInput)); // Добавляем текущий входной символ в стек символов
            index++; // Переходим к следующему символу входной строки
        }
        else if (entry.Action == ActionType.Reduce) // Если действие - свертка
        {
            Rule rule = grammar.GetRule(entry.Value); // Получаем правило свертки по индексу из таблицы действий
            List<Symbol> poppedSymbols = new List<Symbol>();

            for (int i = 0; i < rule.Right.Length; i++) // Извлекаем символы из стека символов в соответствии с правилом свертки
            {
                poppedSymbols.Add(symbolStack.Pop());
                stateStack.Pop();
            }

            poppedSymbols.Reverse(); // Разворачиваем извлеченные символы в правильном порядке
            Symbol nonTerminal = rule.Left; // Получаем нетерминальный символ слева от правила свертки
            int nextState = table.GetGoto(stateStack.Peek(), nonTerminal); // Получаем следующее состояние из таблицы переходов

            stateStack.Push(nextState); // Переходим к следующему состоянию
            symbolStack.Push(nonTerminal); // Добавляем нетерминальный символ в стек символов

            Console.WriteLine("Reduced by rule: " + rule);
            // Выполнение семантических действий, связанных с правилом
        }
        else if (entry.Action == ActionType.Accept) // Если действие - принятие
        {
            Console.WriteLine("Input successfully parsed!");
            return;
        }
    }

    Console.WriteLine("Error: Unexpected end of input");
}

}

public class Symbol
{
    public char Value { get; set; }
    public bool IsTerminal { get; set; }

    public Symbol(char value, bool isTerminal = true)
    {
        Value = value;
        IsTerminal = isTerminal;
    }

    public override string ToString()
    {
        return Value.ToString();
    }
}

public class Rule
{
    public Symbol Left { get; set; }
    public Symbol[] Right { get; set; }

    public Rule(Symbol left, params Symbol[] right)
    {
        Left = left;
        Right = right;
    }

    public override string ToString()
    {
        string rightStr = string.Join(" ", Right);
        return Left + " -> " + rightStr;
    }
}

public class Grammar
{
    public List<Symbol> Terminals { get; set; }
    public List<Symbol> NonTerminals { get; set; }
    public List<Rule> Rules { get; set; }
    public Symbol StartSymbol { get; set; }

    public Grammar(List<Symbol> terminals, List<Symbol> nonTerminals, List<Rule> rules, Symbol startSymbol)
    {
        Terminals = terminals;
        NonTerminals = nonTerminals;
        Rules = rules;
        StartSymbol = startSymbol;
    }

    // Метод для получения правила по индексу
    public Rule GetRule(int index)
    {
        if (index >= 0 && index < Rules.Count)
        {
            return Rules[index];
        }

        return null;
    }
}

public enum ActionType
{
    Shift,
    Reduce,
    Accept
}

public class ActionTableEntry
{
    public ActionType Action { get; set; }
    public int Value { get; set; }

    public ActionTableEntry(ActionType action, int value)
    {
        Action = action;
        Value = value;
    }
}

public class GotoTableEntry
{
    public int Value { get; set; }

    public GotoTableEntry(int value)
    {
        Value = value;
    }
}

public class LRTable
{
    private Dictionary<Tuple<int, char>, ActionTableEntry> actionTable;
    private Dictionary<Tuple<int, Symbol>, GotoTableEntry> gotoTable;

    public LRTable()
    {
        actionTable = new Dictionary<Tuple<int, char>, ActionTableEntry>();
        gotoTable = new Dictionary<Tuple<int, Symbol>, GotoTableEntry>();
    }

    // Метод для добавления записи в таблицу действий
    public void AddAction(int state, char input, ActionType action, int value)
    {
        actionTable.Add(new Tuple<int, char>(state, input), new ActionTableEntry(action, value));
    }

    // Метод для добавления записи в таблицу переходов
    public void AddGoto(int state, Symbol symbol, int value)
    {
        gotoTable.Add(new Tuple<int, Symbol>(state, symbol), new GotoTableEntry(value));
    }

    // Метод для получения записи из таблицы действий
    public ActionTableEntry GetAction(int state, char input)
    {
        ActionTableEntry entry;
        actionTable.TryGetValue(new Tuple<int, char>(state, input), out entry);
        return entry;
    }

    // Метод для получения значения перехода из таблицы переходов
    public int GetGoto(int state, Symbol symbol)
    {
        GotoTableEntry entry;
        gotoTable.TryGetValue(new Tuple<int, Symbol>(state, symbol), out entry);
        return entry != null ? entry.Value : -1;
    }
}