Assignment - 4
Q)Design Operator Precedence parser for user input CFG with the following
operations:
1. Find out Trailing of NT
2. Find out Leading of NT
3. Build precedence table
4. Validate input string using stack
CODE-:
#include <bits/stdc++.h>
using namespace std;
map<char, vector<string>> grammar;
map<char, set<char>> leading, trailing;
set<char> terminals, non_terminals;
char start_symbol;
bool is_terminal(char ch) {
return !isupper(ch) && ch != 'ε';
}
void compute_leading(char nt) {
for (auto prod : grammar[nt]) {
if (is_terminal(prod[0]))
leading[nt].insert(prod[0]);
else {
if (prod[0] != nt) {
compute_leading(prod[0]);
leading[nt].insert(leading[prod[0]].begin(), leading[prod[0]].end()); }
}
}
}
void compute_trailing(char nt) {
for (auto prod : grammar[nt]) {
int len = prod.length();
if (is_terminal(prod[len - 1]))
trailing[nt].insert(prod[len - 1]);
else {
if (prod[len - 1] != nt) {
compute_trailing(prod[len - 1]);
trailing[nt].insert(trailing[prod[len - 1]].begin(), trailing[prod[len - 1]].end()); }
}
}
}
map<pair<char, char>, char> precedence_table;
void build_table() {
for (auto &g : grammar) {
for (auto &prod : g.second) {
for (size_t i = 0; i < prod.length() - 1; ++i) {
char a = prod[i];
char b = prod[i + 1];
if (is_terminal(a) && is_terminal(b)) {
precedence_table[{a, b}] = '=';
}
if (is_terminal(a) && isupper(b)) {
for (char l : leading[b]) {
precedence_table[{a, l}] = '<';
}
}
if (isupper(a) && is_terminal(b)) {
for (char t : trailing[a]) {
precedence_table[{t, b}] = '>';
}
}
if (i + 2 < prod.length() && is_terminal(prod[i]) && isupper(prod[i + 1]) &&
is_terminal(prod[i + 2])) {
precedence_table[{prod[i], prod[i + 2]}] = '=';
}
}
}
}
}
bool validate_input(const string &input) {
stack<char> st;
st.push('$');
string str = input + "$";
size_t i = 0;
while (!st.empty()) {
char top = st.top();
char current = str[i];
if (top == '$' && current == '$') return true;
char relation = 0;
auto temp_stack = st;
char top_terminal = '$';
while (!temp_stack.empty()) {
if (is_terminal(temp_stack.top()) || temp_stack.top() == '$') {
top_terminal = temp_stack.top();
break;
}
temp_stack.pop();
}
if (precedence_table.find({top_terminal, current}) != precedence_table.end()) {
relation = precedence_table[{top_terminal, current}];
} else {
return false;
}
if (relation == '<' || relation == '=') {
st.push(current);
i++;
} else if (relation == '>') {
while (!st.empty()) {
char s_top = st.top();
st.pop();
char next_terminal = '$';
auto temp_stack2 = st;
while (!temp_stack2.empty()) {
if (is_terminal(temp_stack2.top()) || temp_stack2.top() == '$') {
next_terminal = temp_stack2.top();
break;
}
temp_stack2.pop();
}
if (precedence_table[{next_terminal, s_top}] == '<' ||
precedence_table[{next_terminal, s_top}] == 0)
break;
}
} else {
return false;
}
}
return false;
}
int main() {
int n;
cout << "Enter number of productions: ";
cin >> n;
cin.ignore();
cout << "Enter productions (e.g., E->E+T):\n";
for (int i = 0; i < n; ++i) {
string line;
getline(cin, line);
char lhs = line[0];
start_symbol = start_symbol == 0 ? lhs : start_symbol;
non_terminals.insert(lhs);
string rhs = line.substr(3);
stringstream ss(rhs);
string prod;
while (getline(ss, prod, '|')) {
grammar[lhs].push_back(prod);
for (char ch : prod) {
if (is_terminal(ch) && ch != 'ε')
terminals.insert(ch);
else if (isupper(ch))
non_terminals.insert(ch);
}
}
}
for (char nt : non_terminals) {
compute_leading(nt);
compute_trailing(nt);
}
cout << "\nLEADING:\n";
for (auto &p : leading) {
cout << p.first << " : ";
for (char ch : p.second) cout << ch << " "; cout
<< endl;
}
cout << "\nTRAILING:\n";
for (auto &p : trailing) {
cout << p.first << " : ";
for (char ch : p.second) cout << ch << " "; cout
<< endl;
}
build_table();
cout << "\nOperator Precedence Table:\n";
for (char a : terminals) {
for (char b : terminals) {
auto it = precedence_table.find({a, b});
if (it != precedence_table.end())
cout << a << " " << it->second << " " << b << endl; }
}
string test_input;
cout << "\nEnter input string to validate (no spaces):
"; cin >> test_input;
bool result = validate_input(test_input);
cout << "Result: " << (result ? "Valid" : "Invalid") << endl;
return 0;
}
OUTPUT :
