=begin
Таблица нетерминалов
0)<программа>
1)<последовательность операторов>
2)<оператор>
3)<структура>
4)<условие>
5)<выражение>
6)<арифм. операция>
7)<знак отношения>
8)<присваивание>

Таблица терминалов
1)константа
2)идентификатор
Остальные терминалы нас не интересуют в данный момент


Цель - программа на языке С
Дано - разобранное дерево для цепочки языка Милан
Алгоритм:
1)Составим и пронумеруем правила вывода в обеих грамматиках
2)В дереве цепочки Милан заменим все правила вывода их номерами
3)Заменяем номера правилами из грамматики языка С
4)Свернем дерево
    Пусть первая строка дерева будет шаблоном для нашей программы, сохраним ее отдельно (OutProg)
      Пока в шаблоне есть нетерминалы вида <ЯНетерминалХаХа>
        Если в строке нетерминал
          Ищем в левой части следующей строки этот нетерминал
          Берем все, что в этой строке стоит после пробела и заменяем нетерминал на это все
        Иначе
          Выдаем ошибку (при синтаксическом разборе должен был соблюдаться именно такой порядок правил)
5)Проходимся по основному коду программы и заносим в стек перменные и константы в порядке их использования
6)Переворачиваем стек и высыпаем получившееся на шаблон выходной программы С.
=end

#1)Составим и пронумеруем правила вывода в обеих грамматиках
Milan = {"<программа> = BEGIN <последовательность операторов> END" => 1,
         "<последовательность операторов> = <оператор>; <последовательность операторов>" => 2,
         "<последовательность операторов> = <структура> <последовательность операторов>" => 3,
         "<оператор> = <присваивание>" => 4,
         "<присваивание> = идентификатор := <выражение>" => 5,
         "<выражение> = константа" => 6,
         "<выражение> = идентификатор" => 7,
         "<выражение> = идентификатор <арифметическая операция> идентификатор" => 8,
         "<выражение> = константа <арифметическая операция> константа" => 9,
         "<выражение> = константа <арифметическая операция> идентификатор" => 10,
         "<выражение> = идентификатор <арифметическая операция> константа" => 11,
         "<арифметическая операция> = +" => 12,
         "<арифметическая операция> = -" => 13,
         "<арифметическая операция> = *" => 14,
         "<арифметическая операция> = /" => 15,
         "<структура> = IF <условие> THEN <последовательность операторов> ENDIF" => 16,
         "<структура> = IF <условие> THEN <последовательность операторов> ELSE <последовательность операторов> ENDIF" => 17,
         "<структура> = WHILE <условие> DO <последовательность операторов> ENDDO" => 18,
         "<условие> = идентификатор <знак отношения> идентификатор" => 19,
         "<условие> = идентификатор <знак отношения> константа" => 20,
         "<условие> = константа <знак отношения> идентификатор" => 21,
         "<условие> = константа <знак отношения> константа" => 22,
         "<знак отношения> = =" => 23,
         "<знак отношения> = <>" => 24,
         "<знак отношения> = >" => 25,
         "<знак отношения> = <" => 26,
         "<знак отношения> = >=" => 27,
         "<знак отношения> = <=" => 28,
         "<присваивание> = идентификатор := READ" => 29, 
         "<оператор> = OUTPUT(<выражение>)" => 30,
         "<последовательность операторов> = ничего" => 31}

#Для С нужен обратный порядок (28 => "<знак отношения> = <=")
C = {1=>  "<программа> = int main (int argc, char * argv[]) {<последовательность операторов> return 0}",
     2=>  "<последовательность операторов> = <оператор>; <последовательность операторов>",
     3=>  "<последовательность операторов> = <структура> <последовательность операторов>",
     4=>  "<оператор> = <присваивание>",
     5=>  "<присваивание> = идентификатор = <выражение>",
     6=>  "<выражение> = константа",
     7=>  "<выражение> = идентификатор",
     8=>  "<выражение> = идентификатор <арифметическая операция> идентификатор",
     9=>  "<выражение> = константа <арифметическая операция> константа",
     10=> "<выражение> = константа <арифметическая операция> идентификатор",
     11=> "<выражение> = идентификатор <арифметическая операция> константа",
     12=> "<арифметическая операция> = +",
     13=> "<арифметическая операция> = -",
     14=> "<арифметическая операция> = *",
     15=> "<арифметическая операция> = /",
     16=> "<структура> = IF (<условие>) {<последовательность операторов>}",
     17=> "<структура> = IF (<условие>) {<последовательность операторов>} ELSE {<последовательность операторов>}",
     18=> "<структура> = WHILE (<условие>) {<последовательность операторов>}",
     19=> "<условие> = идентификатор <знак отношения> идентификатор",
     20=> "<условие> = идентификатор <знак отношения> константа",
     21=> "<условие> = константа <знак отношения> идентификатор",
     22=> "<условие> = константа <знак отношения> константа",
     23=> "<знак отношения> = ==",
     24=> "<знак отношения> = !=",
     25=> "<знак отношения> = >",
     26=> "<знак отношения> = <",
     27=> "<знак отношения> = >=",
     28=> "<знак отношения> = <=",
     29=> "<присваивание> = идентификатор := getchar()", 
     30=> "<оператор> = putchar(<выражение>)",
     31=> "<последовательность операторов> = ничего"}

class CodeGen
    def initialize(syntTree, stack_of_consts_and_ids)
        #Входные данные
        @tree_milan = syntTree
        @size = syntTree.size

        #Промежуточные данные
        @numeric_tree = []
        @tree_c = []

        #Выходные данные
        @out_prog = []

        #Вспомогательные данные
        @stack_of_consts_and_ids = stack_of_consts_and_ids
    end

    #Входные данные
    @tree_milan
    @size

    #Промежуточные данные
    @numeric_tree
    @tree_c

    #Вспомогательные данные
    #Массив из 2 элементов
    #1 элемент - стек идентификаторов
    #2 элемент - стек констант
    @stack_of_consts_and_ids

    #Выходные данные
    @out_prog

    public
    def codeGen
        TreeMilanToNumericTree()
        NumericTreeToCTree()
        TreeToProgram()
        DeleteAllNothing()
        InsertIdsAndConsts()
    end

    #Вывод числового дерева выходной программы
    def printResults
        puts("\nNUMERIC_TREE\n_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+\n")
        puts @numeric_tree.join("\n")
        puts("_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+\n")
        puts @out_prog
    end


    private
    #Заменим словесную форму дерева на более короткую и однозначную (цифры)
    #Условимся называть получившееся дерево "цифровым деревом""
    def TreeMilanToNumericTree
        @tree_milan.each { |rule|  @numeric_tree.push(Milan[rule])}     
    end

    #Перейдем от цифрового дерева к дереву на С
    def NumericTreeToCTree
        @numeric_tree.each { |rule|  @tree_c.push(C[rule])} 
        puts("\nTREE_IN_C\n_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+\n")  
        puts @tree_c.join("\n")
        puts("_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+\n")    
    end

    #Свернем дерево в программу
    def TreeToProgram
        @tree_c = @tree_c.reverse
        @out_prog = @tree_c.pop #Можно сменить на tree_milan
        @out_prog = @out_prog[14,100]
        #Время псевдокода
        #Пока в строке еще есть нетерминалы ...
          #Берем нетерминал через регулярку из out_prog
            #Если найден он и индекс его в строке - 0 (он стоит в левой части правила)
              #Ищем в этой строке пробел
              #Берем остаток строки (после пробела)
              #Заменяем нетерминал в исходной строке этим остатком строки
            #Иначе - ошибка

        begin
            #Нетерминал в исходной строку, который будем заменять
            variable_nonterminal = @out_prog[/(<[а-я]+>)|(<[а-я]+ [a-я]+>)/]
            #Ищем в следующей строке дерева этот же нетерминал в левой части (просматриваем 1 строку)
            rightPartOfRule = @tree_c.pop
            unless rightPartOfRule.include?(variable_nonterminal)
                puts("Неверно построено синтаксическое дерево")
                break
            end

            
            rightPartOfRule = rightPartOfRule[rightPartOfRule.index("=")+2, 100]
            @out_prog[variable_nonterminal] = rightPartOfRule

        end while variable_nonterminal !=nil && @tree_c.size > 0
    end

    #Удаляет все вхождения терминала "ничего" из строки
    #Входной параметр - @out_prog, он должен быть подготовлен к работе
    def DeleteAllNothing 
        while @out_prog["ничего"]!=nil
            @out_prog["ничего"] = ""
        end
    end


    #Заменить все нетерминалы "константа" "идентификатор" на их реальные эквиваленты из программы
    def InsertIdsAndConsts 
      while @out_prog["идентификатор"]!=nil
          @out_prog["идентификатор"] = @stack_of_consts_and_ids[0].pop
      end

      while @out_prog["константа"]!=nil
          @out_prog["константа"] = @stack_of_consts_and_ids[1].pop
      end
    end
end

