GS.cpp

#include <string>
#include <vector>
#include <iostream>
#include <fstream>
using namespace std;

struct str_pair {
    string u, v;
};

void shift_numeration(vector<string>& v, int k) {
    for (int i = 0; i < v.size(); ++i) {
        string s = v.at(i);
        if ((s.at(0) == '>') || (s.at(0) == '&'))
            v.at(i) = s.at(0) + to_string(stoi(s.substr(1)) + k);
    }
}

string remove_parentheses(string s) {
    if ((s.at(0) == '(') && (s.at(s.length()-1) == ')')) {
        return s.substr(1, s.length()-2);
    }
    else
        return s;
}

int last_top_level(string s, char op) {
    int pos = -1;
    int braces_open = 0;
    for (int i = 0; i < s.length(); ++i) {
        char c = s.at(i);
        if (c == '(')
            braces_open++;
        else if (c == ')')
            braces_open--;
        else if ((c == op) && (braces_open == 0))
            pos = i;
    }

    return pos;
}

str_pair unfold(string s, char op) {
    int pos = last_top_level(s, op);
    return str_pair {
        s.substr(0, pos),
        s.substr(pos+1)
    };
}

vector<string> parse(string s) {
    str_pair p;
    vector<string> v;

    if (last_top_level(s, ';') != -1) {
        p = unfold(s, ';');

        vector<string> l = parse(remove_parentheses(p.u));
        vector<string> r = parse(remove_parentheses(p.v));

        v.push_back(">" + to_string(l.size() + 3)); // jump to second subarray
        shift_numeration(l, 1); // shift left subarray by one
        v.insert(v.end(), l.begin(), l.end()); // insert the left subarray
        shift_numeration(r, l.size()+2); // shift the numeration of right subarray
        v.push_back("&" + to_string(l.size() + r.size() + 3)); // jump past second subarray
        v.insert(v.end(), r.begin(), r.end()); // insert the right subarray
    }
    else if (last_top_level(s, ',') != -1) {
        p = unfold(s, ',');

        vector<string> l = parse(remove_parentheses(p.u));
        vector<string> r = parse(remove_parentheses(p.v));

        v.insert(v.end(), l.begin(), l.end()); // insert the left subarray
        shift_numeration(r, l.size()); // shift the numeration of right subarray
        v.insert(v.end(), r.begin(), r.end()); // insert the right subarray
    }
    else if (last_top_level(s, '#') != -1) {
        p = unfold(s, '#');

        vector<string> l = parse(remove_parentheses(p.u));
        vector<string> r = parse(remove_parentheses(p.v));

        v.insert(v.end(), l.begin(), l.end()); // insert the left subarray
        v.push_back(">" + to_string(l.size() + r.size() + 3)); // jump past second subarray
        shift_numeration(r, l.size()+2); // shift the numeration of right subarray
        v.insert(v.end(), r.begin(), r.end()); // insert the right subarray
        v.push_back("&" + to_string(1)); // jump to start
    }
    else if (last_top_level(s, '+') != -1) {
        p = unfold(s, '+');

        vector<string> l = parse(remove_parentheses(p.u));

        v.insert(v.end(), l.begin(), l.end()); // insert the processed list
        v.push_back(">" + to_string(l.size() + 3)); // jump out
        v.push_back("&" + to_string(1)); // jump to start
    }
    else if (last_top_level(s, '*') != -1) {
        p = unfold(s, '*');

        vector<string> l = parse(remove_parentheses(p.u));

        v.push_back(">" + to_string(l.size() + 3)); // jump through
        shift_numeration(l, 1);
        v.insert(v.end(), l.begin(), l.end()); // insert the processed list
        v.push_back("&" + to_string(1)); // jump to start
    }
    else {
        v.push_back(s);
    }
    return v;
}

vector<string> process_rule(string s) {
    vector<string> t;
    str_pair p = unfold(s, ':');
    t.push_back("BEG<" + p.u + ">");
    vector<string> l = parse(p.v);
    shift_numeration(l, 1);
    t.insert(t.end(), l.begin(), l.end());
    t.push_back("END<" + p.u + ">");

    return t;
}

int main() {
    ifstream file;
	file.open("gram.txt", std::ifstream::in);

    string s;
    int shift = 0;
    while (getline(file, s)) {
        vector<string> t = process_rule(s);
        shift_numeration(t, shift);
        for (int i = 0; i < t.size(); ++i) {
            cout << i+shift+1 << ": " << t.at(i) << endl;
        }
        shift += t.size();
        cout << endl;
        cout << endl;
    }

    return 0;
}