Compiler Design: Implementation of Key Algorithms
Shift-Reduce Parser Implementation (EXP-6)
This section demonstrates a shift-reduce parser implementation in C++.
#include <iostream>
#include <cstring>
using namespace std;
int z = 0, i = 0, j = 0, c = 0;
char a[16], ac[20], stk[15], act[10];
void check() {
strcpy(ac, "REDUCE TO E -> ");
for (z = 0; z < c; z++) {
if (stk[z] == '4') {
cout << ac << "4" << endl;
stk[z] = 'E';
stk[z + 1] = '\0';
cout << "$" << stk << "\t" << a << "$\t";
}
}
for (z = 0; z < c - 2; z++) {
if (stk[z] == '2' && stk[z + 1] == 'E' && stk[z + 2] == '2') {
cout << ac << "2E2" << endl;
stk[z] = 'E';
stk[z + 1] = '\0';
stk[z + 2] = '\0';
cout << "$" << stk << "\t" << a << "$\t";
i = i - 2;
}
}
for (z = 0; z < c - 2; z++) {
if (stk[z] == '3' && stk[z + 1] == 'E' && stk[z + 2] == '3') {
cout << ac << "3E3" << endl;
stk[z] = 'E';
stk[z + 1] = '\0';
stk[z + 2] = '\0';
cout << "$" << stk << "\t" << a << "$\t";
i = i - 2;
}
}
}
int main() {
cout << "GRAMMAR is -\nE->2E2 \nE->3E3 \nE->4\n";
strcpy(a, "32423");
c = strlen(a);
strcpy(act, "SHIFT");
cout << "\nstack \t input \t action";
cout << "\n$\t" << a << "$\t";
for (i = 0; j < c; i++, j++) {
cout << act;
stk[i] = a[j];
stk[i + 1] = '\0';
a[j] = ' ';
cout << "\n$" << stk << "\t" << a << "$\t";
check();
}
check();
if (stk[0] == 'E' && stk[1] == '\0')
cout << "Accept\n";
else
cout << "Reject\n";
return 0;
}
Leading and Trailing Sets Computation (EXP-7)
This section presents the computation of leading and trailing sets for a given grammar.
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <iterator>
using namespace std;
map<string, set<string>> leading, trailing;
map<string, vector<string>> productions;
void computeLeading(string nonTerminal) {
if (!leading[nonTerminal].empty()) return;
for (const string& prod : productions[nonTerminal]) {
if (isupper(prod[0])) {
leading[nonTerminal].insert(prod[0]);
computeLeading(string(1, prod[0]));
} else {
leading[nonTerminal].insert(string(1, prod[0]));
}
}
}
void computeTrailing(string nonTerminal) {
if (!trailing[nonTerminal].empty()) return;
for (const string& prod : productions[nonTerminal]) {
if (isupper(prod.back())) {
trailing[nonTerminal].insert(prod.back());
computeTrailing(string(1, prod.back()));
} else {
trailing[nonTerminal].insert(string(1, prod.back()));
}
}
}
int main() {
productions["E"] = {"E+T", "T"};
productions["T"] = {"T*F", "F"};
productions["F"] = {"(E)", "id"};
for (const auto& prod : productions) {
computeLeading(prod.first);
computeTrailing(prod.first);
}
for (const auto& entry : leading) {
cout << "Leading(" << entry.first << "): ";
for (const auto& elem : entry.second) {
cout << elem << " ";
}
cout << endl;
}
for (const auto& entry : trailing) {
cout << "Trailing(" << entry.first << "): ";
for (const auto& elem : entry.second) {
cout << elem << " ";
}
cout << endl;
}
return 0;
}
Intermediate Code Generation: Quadruples, Triples, Indirect Triples (EXP-10)
This section illustrates the generation of intermediate code in the form of quadruples, triples, and indirect triples.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
struct Quadruple {
string op, arg1, arg2, result;
};
void generateQuadruples(const string& expr, vector<Quadruple>& quads) {
int tempCount = 1;
for (size_t i = 0; i < expr.length(); i++) {
if (expr[i] == '+' || expr[i] == '-' || expr[i] == '*' || expr[i] == '/') {
string arg1 = string(1, expr[i - 1]);
string arg2 = string(1, expr[i + 1]);
string res = "t" + to_string(tempCount++);
quads.push_back({string(1, expr[i]), arg1, arg2, res});
}
}
}
void printQuadruples(const vector<Quadruple>& quads) {
cout << "Quadruples:\nOp\tArg1\tArg2\tResult\n";
for (const auto& q : quads) {
cout << q.op << "\t" << q.arg1 << "\t" << q.arg2 << "\t" << q.result << endl;
}
}
void printTriples(const vector<Quadruple>& quads) {
cout << "\nTriples:\nIndex\tOp\tArg1\tArg2\n";
for (size_t i = 0; i < quads.size(); i++) {
cout << i << "\t" << quads[i].op << "\t" << quads[i].arg1 << "\t" << quads[i].arg2 << endl;
}
}
void printIndirectTriples(const vector<Quadruple>& quads) {
cout << "\nIndirect Triples:\nPointer\tInstruction\n";
for (size_t i = 0; i < quads.size(); i++) {
cout << i << "\t(" << quads[i].op << ", " << quads[i].arg1 << ", " << quads[i].arg2 << ")" << endl;
}
}
int main() {
string expr = "a+b*c";
vector<Quadruple> quads;
generateQuadruples(expr, quads);
printQuadruples(quads);
printTriples(quads);
printIndirectTriples(quads);
return 0;
}
LR(0) Parser Item Set Construction (EXP-8)
This section demonstrates the construction of LR(0) parser item sets.
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <string>
using namespace std;
struct Item {
string lhs, rhs;
int dot;
bool operator<(const Item& other) const {
return tie(lhs, rhs, dot) < tie(other.lhs, other.rhs, other.dot);
}
string str() const {
return lhs + " -> " + rhs.substr(0, dot) + "." + rhs.substr(dot);
}
};
map<string, vector<string>> grammar = {
{"S", {"AA"}},
{"A", {"aA", "b"}}
};
set<Item> closure(set<Item> items) {
bool added;
do {
added = false;
set<Item> newItems;
for (auto& it : items) {
if (it.dot < it.rhs.size() && isupper(it.rhs[it.dot])) {
string B(1, it.rhs[it.dot]);
for (auto& prod : grammar[B]) {
Item ni = {B, prod, 0};
if (items.find(ni) == items.end()) {
newItems.insert(ni);
added = true;
}
}
}
}
items.insert(newItems.begin(), newItems.end());
} while (added);
return items;
}
set<Item> goTo(set<Item> I, char X) {
set<Item> next;
for (auto& it : I) {
if (it.dot < it.rhs.size() && it.rhs[it.dot] == X)
next.insert({it.lhs, it.rhs, it.dot + 1});
}
return closure(next);
}
int main() {
vector<set<Item>> states;
set<Item> start = {{"S'", "S", 0}};
states.push_back(closure(start));
for (size_t i = 0; i < states.size(); ++i) {
for (char X = 'a'; X <= 'z'; ++X) {
set<Item> next = goTo(states[i], X);
if (!next.empty() && find(states.begin(), states.end(), next) == states.end())
states.push_back(next);
}
}
return 0;
}