compiler design lab

lead_trail.cpp

#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <sstream>
using namespace std;

map<char, vector<string>> prods;
map<char, set<char>> leading, trailing;
set<char> nonterms, terms;

void findLeading(char nt) {
    for (auto &prod : prods[nt]) {
        if (isupper(prod[0])) {
            if (prod[0] != nt) findLeading(prod[0]);
            leading[nt].insert(leading[prod[0]].begin(), leading[prod[0]].end());
        } else leading[nt].insert(prod[0]);
    }
}
void findTrailing(char nt) {
    for (auto &prod : prods[nt]) {
        char c = prod.back();
        if (isupper(c)) {
            if (c != nt) findTrailing(c);
            trailing[nt].insert(trailing[c].begin(), trailing[c].end());
        } else trailing[nt].insert(c);
    }
}

int main() {
    cout << "Enter productions (e.g., E->E+T|T), end with blank line:\n";
    string line;
    while (getline(cin, line), !line.empty()) {
        char lhs = line[0];
        nonterms.insert(lhs);
        string rhs = line.substr(3);
        stringstream ss(rhs);
        string prod;
        while (getline(ss, prod, '|')) {
            prods[lhs].push_back(prod);
            for (char c : prod)
                if (!isupper(c)) terms.insert(c);
        }
    }
    for (char nt : nonterms) findLeading(nt);
    for (char nt : nonterms) findTrailing(nt);

    cout << "\nLEADING sets:\n";
    for (char nt : nonterms) {
        cout << nt << " : { ";
        for (char t : leading[nt]) cout << t << ' ';
        cout << "}\n";
    }
    cout << "\nTRAILING sets:\n";
    for (char nt : nonterms) {
        cout << nt << " : { ";
        for (char t : trailing[nt]) cout << t << ' ';
        cout << "}\n";
    }
}

lr_parser.cpp

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
using namespace std;

struct Item { string lhs, rhs; int dot; 
    bool operator<(const Item& o) const { return tie(lhs,rhs,dot)<tie(o.lhs,o.rhs,o.dot);}
};
struct State { set<Item> items; map<char,int> trans; };
vector<State> states;
map<pair<int,char>, int> gototab;
map<pair<int,char>, string> actiontab;
string startSym;

set<Item> closure(set<Item> I, map<string,vector<string>>& P) {
    bool add;
    do {
        add=false;
        set<Item> J=I;
        for(auto& it:I) if(it.dot<(int)it.rhs.size()) {
            char B=it.rhs[it.dot];
            if(isupper(B)) for(auto& r:P[string(1,B)]) {
                Item ni={string(1,B),r,0};
                if(J.find(ni)==J.end()) {J.insert(ni);add=true;}
            }
        }
        I=J;
    }while(add);
    return I;
}
set<Item> go(set<Item> I, char X, map<string,vector<string>>& P) {
    set<Item> J;
    for(auto& it:I) if(it.dot<(int)it.rhs.size()&&it.rhs[it.dot]==X)
        J.insert({it.lhs,it.rhs,it.dot+1});
    return closure(J,P);
}
int stateIdx(set<Item> I) {
    for(int i=0;i<states.size();i++) if(states[i].items==I) return i;
    return -1;
}
void buildLR0(map<string,vector<string>>& P) {
    set<Item> st=closure({{startSym+"'",startSym,0}},P);
    states.push_back({st,{}});
    queue<int> q; q.push(0);
    while(!q.empty()) {
        int i=q.front();q.pop();
        set<char> symb;
        for(auto& it:states[i].items) if(it.dot<(int)it.rhs.size())
            symb.insert(it.rhs[it.dot]);
        for(char X:symb) {
            set<Item> g=go(states[i].items,X,P);
            if(g.empty()) continue;
            int j=stateIdx(g);
            if(j==-1) { states.push_back({g,{}});
                j=states.size()-1;q.push(j);}
            states[i].trans[X]=j;
        }
    }
}
void buildTables(map<string,vector<string>>& P) {
    for(int i=0;i<states.size();i++) {
        for(auto& it:states[i].items) {
            if(it.dot==(int)it.rhs.size()) {
                if(it.lhs==startSym+"'") actiontab[{i,'$'}]="acc";
                else for(auto& p:P) for(int k=0;k<p.second.size();k++)
                    if(p.first==it.lhs&&p.second[k]==it.rhs)
                        for(char t='a';t<='z';t++) actiontab[{i,t}]="r"+to_string(k+1);
            }
        }
        for(auto& tr:states[i].trans) {
            if(isupper(tr.first)) gototab[{i,tr.first}]=tr.second;
            else actiontab[{i,tr.first}]="s"+to_string(tr.second);
        }
    }
}
void printStates() {
    cout<<"States:\n";
    for(int i=0;i<states.size();i++) {
        cout<<"State "<<i<<":\n";
        for(auto& it:states[i].items) {
            cout<<"  "<<it.lhs<<"->";
            for(int j=0;j<=it.rhs.size();j++) {
                if(j==it.dot) cout<<".";
                if(j<it.rhs.size()) cout<<it.rhs[j];
            }
            cout<<"\n";
        }
        cout<<"Transitions: ";
        for(auto& tr:states[i].trans) cout<<tr.first<<"->"<<tr.second<<" ";
        cout<<"\n\n";
    }
}
void parse(string inp, map<string,vector<string>>& P) {
    inp+="$"; vector<int> stk={0}; int ip=0;
    cout<<"Parsing steps:\n";
    while(1) {
        int st=stk.back(); char a=inp[ip];
        string act=actiontab[{st,a}];
        cout<<"Stack: "; for(int s:stk) cout<<s<<" "; cout<<", Input: "<<inp.substr(ip)<<", Action: "<<act<<"\n";
        if(act=="acc") {cout<<"Accepted!\n";break;}
        else if(act[0]=='s') {stk.push_back(stoi(act.substr(1)));ip++;}
        else if(act[0]=='r') {
            int pn=stoi(act.substr(1)),cnt=0; string lhs,rhs;
            int idx=1;
            for(auto& p:P) for(auto& r:p.second)
                if(idx++==pn) {lhs=p.first;rhs=r;cnt=r.size();}
            for(int i=0;i<cnt;i++) stk.pop_back();
            int top=stk.back();
            stk.push_back(gototab[{top,lhs[0]}]);
        } else {cout<<"Error!\n";break;}
    }
}
int main() {
    cout<<"Enter up to 2 productions (e.g. E->E+T):\n";
    map<string,vector<string>> P; string l; int c=0;
    while(c<2&&getline(cin,l)&&!l.empty()) {P[l.substr(0,1)].push_back(l.substr(3));c++;}
    startSym=P.begin()->first; P[startSym+"'"]={startSym};
    buildLR0(P); buildTables(P); printStates();
    cout<<"Enter input string:\n"; string inp; getline(cin,inp);
    parse(inp,P);
}

postfix.cpp

#include <iostream>
using namespace std;

string postfix;
size_t pos = 0;
string input;

// Forward declarations
void Expr();
void Term();
void Factor();

void Factor() {
    if (isalnum(input[pos])) postfix += input[pos++];
    else if (input[pos] == '(') {
        pos++; 
        Expr();  // Now recognized due to forward declaration
        pos++; 
    }
}

void Term() {
    Factor();
    while (input[pos] == '*' || input[pos] == '/') {
        char op = input[pos++];
        Factor();
        postfix += op;
    }
}

void Expr() {
    Term();
    while (input[pos] == '+' || input[pos] == '-') {
        char op = input[pos++];
        Term();
        postfix += op;
    }
}

int main() {
    input = "a+b*(c-d)";
    Expr();
    cout << "Postfix: " << postfix << endl;
}

shift_reduce.cpp

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

// Grammar: E -> E+E | E*E | a

bool isOperator(char c) {
    return c == '+' || c == '*';
}

bool reduce(stack<string>& stk) {
    // Try E -> E+E or E*E
    if (stk.size() >= 3) {
        string right = stk.top(); stk.pop();
        string op = stk.top(); stk.pop();
        string left = stk.top(); stk.pop();
        if ((left == "E" && right == "E") && (op == "+" || op == "*")) {
            stk.push("E");
            return true;
        }
        stk.push(left); stk.push(op); stk.push(right);
    }
    // Try E -> a
    if (stk.size() >= 1) {
        string top = stk.top();
        if (top == "a") {
            stk.pop();
            stk.push("E");
            return true;
        }
    }
    return false;
}

void printStack(stack<string> stk) {
    vector<string> v;
    while (!stk.empty()) { v.push_back(stk.top()); stk.pop(); }
    for (int i = v.size() - 1; i >= 0; --i) cout << v[i];
}

int main() {
    string input;
    cout << "Enter input string (e.g. a+a*a): ";
    cin >> input;
    stack<string> stk;
    string buffer = input;
    cout << "Stack\t\tInput\t\tAction\n";
    while (!buffer.empty()) {
        char c = buffer[0];
        buffer.erase(0, 1);
        stk.push(string(1, c));
        cout << "";
        printStack(stk); cout << "\t\t" << buffer << "\t\tShift " << c << endl;
        bool reduced = true;
        while (reduced) {
            reduced = reduce(stk);
            if (reduced) {
                printStack(stk); cout << "\t\t" << buffer << "\t\tReduce to E" << endl;
            }
        }
    }
    // Final reductions after input is empty
    bool reduced = true;
    while (reduced) {
        reduced = reduce(stk);
        if (reduced) {
            printStack(stk); cout << "\t\t" << buffer << "\t\tReduce to E" << endl;
        }
    }
    if (stk.size() == 1 && stk.top() == "E")
        cout << "\nInput string accepted by the grammar." << endl;
    else
        cout << "\nInput string rejected by the grammar." << endl;
    return 0;
}

tac.cpp

#include <iostream>
#include <vector>
#include <stack>
#include <tuple>
using namespace std;

int main() {
    string expr = "a+b*c-(d/e+f)", t; int tc = 0;
    vector<tuple<string, string, string, string>> quads;
    vector<tuple<string, string, string>> triples;
    vector<int> ind_triples;
    stack<string> ops, vals;

    auto nt = [&](){ return "t" + to_string(++tc); };

    auto popop = [&]() {
        string op = ops.top(); ops.pop();
        string b = vals.top(); vals.pop();
        string a = vals.top(); vals.pop();
        t = nt();
        quads.push_back({op, a, b, t});
        triples.push_back({op, a, b});
        ind_triples.push_back(triples.size()-1);
        vals.push(t);
    };

    auto prec = [](char c) { return c=='*'||c=='/'?2:c=='+'||c=='-'?1:0; };

    for (size_t i=0; i<expr.size(); ++i) {
        if (isspace(expr[i])) continue;
        if (isalnum(expr[i])) vals.push(string(1,expr[i]));
        else if (expr[i]=='(') ops.push("(");
        else if (expr[i]==')') { while(ops.top()!="(") popop(); ops.pop(); }
        else {
            while(!ops.empty() && ops.top()!="(" && prec(ops.top()[0])>=prec(expr[i])) popop();
            ops.push(string(1,expr[i]));
        }
    }
    while(!ops.empty()) popop();

    cout << "QUADRUPLES:\nOp\tArg1\tArg2\tRes\n";
    for (auto& q: quads) cout << get<0>(q) << "\t" << get<1>(q) << "\t" << get<2>(q) << "\t" << get<3>(q) << endl;

    cout << "\nTRIPLES:\nIdx\tOp\tArg1\tArg2\n";
    for (int i=0; i<triples.size(); ++i)
        cout << i << "\t" << get<0>(triples[i]) << "\t" << get<1>(triples[i]) << "\t" << get<2>(triples[i]) << endl;

    cout << "\nINDIRECT TRIPLES:\nIdx\tTripleIdx\n";
    for (int i=0; i<ind_triples.size(); ++i)
        cout << i << "\t" << ind_triples[i] << endl;
}