Lab Assignment 6

Manish Singh (19103065)

Aim: Write a program in C to create LL (1) parsing table for the grammar and show the
processing of any string that belong to that grammar.

E -> TE’

E’ ->+T E’|Є

T -> F T’

T’ -> *F T’ | Є

F -> (E) | id

Code:

#include <bits/stdc++.h>

using namespace std;

struct Production

char left;

vector<char> rights;

};

struct Grammar

int num;

vector<char> T;

vector<char> N;
 vector<Production> prods;

};

Grammar grammar;

map<char, set<char>> first;

map<char, set<char>> follow;

stack<char> ST;

string str;

vector<char> M[50][50];

int isTerminal(char ch)

for (int i = 0; i < grammar.T.size(); i++)

if (grammar.T[i] == ch)

return i + 1;

return 0;

int isNonTerminal(char ch)

for (int i = 0; i < grammar.N.size(); i++)

if (grammar.N[i] == ch)

return i + 1;

return 0;
}

void FindFirst()

/* The FIRST set of the terminal is itself */

for (int i = 0; i < grammar.T.size(); i++)

char X = grammar.T[i];

set<char> tmp;

tmp.insert(X);

first[X] = tmp;

/* Loop when the FIRST set of non-terminals changes */

bool change = true;

while (change)

change = false;

/* enumerate each production */

for (int i = 0; i < grammar.prods.size(); i++)

Production &P = grammar.prods[i];

char X = P.left;

set<char> &FX = first[X];

if (isTerminal(P.rights[0]) || P.rights[0] == '@')

/* Find out if the symbol already exists in the FIRST set */

auto it = FX.find(P.rights[0]);

/* does not exist */

if (it == FX.end())

change = true; // the label FIRST set has changed, the loop continues

FX.insert(P.rights[0]);

else

/* The current symbol is a non-terminal symbol, and the current symbol can be
deduced to be empty, then the next symbol needs to be judged */

bool next = true;

/* Subscript of the symbol to be judged */

int idx = 0;

while (next && idx < P.rights.size())

next = false;

char Y = P.rights[idx];

set<char> &FY = first[Y];

for (auto it = FY.begin(); it != FY.end(); it++)

/* Add non-empty elements in the FIRST set of the current symbol to the FIRST
set of the left symbol */

// // if (*it != '@')

auto itt = FX.find(*it);

if (itt == FX.end())

change = true;

FX.insert(*it);

/* The FIRST set of the current symbol is empty, mark next as true, idx subscript +1
*/

auto it = FY.find('@');

if (it != FY.end())

next = true;

idx = idx + 1;

}
 cout << "FIRST:" << endl;

for (int i = 0; i < grammar.N.size(); i++)

char X = grammar.N[i];

cout << X << ": ";

for (auto it = first[X].begin(); it != first[X].end(); it++)

cout << *it << " ";

cout << endl;

/* Generate the FIRST set of the alpha string and save it to the FS set */

void getFirstByAlphaSet(vector<char> &alpha, set<char> &FS)

/* The current symbol is a non-terminal symbol, if the current symbol can be pushed out, the
next symbol needs to be judged */

bool next = true;

int idx = 0;

while (idx < alpha.size() && next)

next = false;

/* The current symbol is a terminal or null, add it to the FIRST set */

if (isTerminal(alpha[idx]) || alpha[idx] == '@')

/* Determine if it is already in the FIRST set */

auto itt = FS.find(alpha[idx]);

if (itt == FS.end())

FS.insert(alpha[idx]);

else

char B = alpha[idx];

set<char> &FB = first[B];

for (auto it = first[B].begin(); it != first[B].end(); it++)

/* The current symbol FIRST set contains empty, mark next as true, and skip the
current loop */

if (*it == '@')

next = true;

continue;

/* Add non-empty elements to FIRST set */

auto itt = FS.find(*it);

if (itt == FS.end())

{
 FS.insert(*it);

idx = idx + 1;

/* If next is true when it reaches the end of the right part of the production, it means that alpha
can be pushed empty, and the empty will be added to the FIRST set */

if (next)

FS.insert('@');

void FindFollow()

/* Initialize the FOLLOW set of the terminal to the empty set */

for (int i = 0; i < grammar.N.size(); i++)

char B = grammar.N[i];

follow[B] = set<char>();

/* Add $ to the FOLLOW set of grammar start symbols */

char S = grammar.N[0];
 follow[S].insert('$');

bool change = true;

while (change)

change = false;

/* enumerate each production */

for (int i = 0; i < grammar.prods.size(); i++)

Production &P = grammar.prods[i];

for (int j = 0; j < P.rights.size(); j++)

char B = P.rights[j];

/* The current symbol is a non-terminal */

if (isNonTerminal(B))

set<char> &FB = follow[B];

set<char> FS;

/* alpha is the symbol string starting from the symbol next to the current symbol */

vector<char> alpha(P.rights.begin() + j + 1, P.rights.end());

/* Find the FIRST set of alpha, ie FS */

getFirstByAlphaSet(alpha, FS);

/* Add all non-empty elements in alpha's FIRST set to the current symbol's
FOLLOW set */

for (auto it = FS.begin(); it != FS.end(); it++)

if (*it == '@')

continue;

auto itt = FB.find(*it);

if (itt == FB.end())

change = true;

FB.insert(*it);

/* If alpha can be pushed empty, or the current symbol is the end of the right-hand
side of the production, add the FOLLOW set of the left-hand symbol of the grammar to the
FOLLOW set of the current symbol */

auto itt = FS.find('@');

if (itt != FS.end() || (j + 1) >= P.rights.size())

char A = P.left; // A is the left symbol

for (auto it = follow[A].begin(); it != follow[A].end(); it++)

auto itt = FB.find(*it);

if (itt == FB.end())

change = true;

FB.insert(*it);
 }

cout << "FOLLOW:" << endl;

for (int i = 0; i < grammar.N.size(); i++)

char X = grammar.N[i];

cout << X << ": ";

for (auto it = follow[X].begin(); it != follow[X].end(); it++)

cout << *it << " ";

cout << endl;

/* Insert the generation into the corresponding item in the predictive analysis table */

void insertToTable(char A, char a, Production &P)

/* Find the corresponding table entry according to A and a */

int j = isTerminal(a) - 1;

/* Insert P.left->P.rights */

M[i][j].push_back(P.left);

M[i][j].push_back('-');

M[i][j].push_back('>');

for (auto it = P.rights.begin(); it != P.rights.end(); it++)

M[i][j].push_back(*it);

/* Take out the production in the item corresponding to the predictive analysis table */

void getFromTable(char A, char a, vector<char> &s)

/* Find the corresponding table entry according to A and a */

int i = isNonTerminal(A) - 1;

int j = isTerminal(a) - 1;

/* take out */

s.assign(M[i][j].begin(), M[i][j].end());

/* Build the predictive analysis table */

void BuildTable()

/* enumerate all productions */

/* Suppose P is A->alpha */

Production &P = grammar.prods[i];

set<char> FS;

/* put A->alpha into M[A, a] for each a in FIRST(alpha) */

getFirstByAlphaSet(P.rights, FS);

for (auto it = FS.begin(); it != FS.end(); it++)

insertToTable(P.left, *it, P);

/* If alpha can be pushed empty, put each b in FOLLOW(A) and put A->alpha into M[A,
b]*/

auto itt = FS.find('@');

if (itt != FS.end())

for (auto it = follow[P.left].begin(); it != follow[P.left].end(); it++)

insertToTable(P.left, *it, P);

cout << "LL(1) table:" << endl;

cout << "\t";

cout << grammar.T[i] << "\t\t";

cout << endl;

for (int i = 0; i < grammar.N.size(); i++)

cout << grammar.N[i] << "\t";

for (int j = 0; j < grammar.T.size(); j++)

for (auto k = M[i][j].begin(); k != M[i][j].end(); k++)

cout << *k;

cout << "\t\t";

cout << endl;

void parser()

cout << "Please enter the String to be checked:" << endl;

cin >> str;

if (str[str.size() - 1] != '$')
 str += '$';

string curr_stack = "";

ST.push('$');

ST.push(grammar.N[0]);

curr_stack += '$';

curr_stack += grammar.N[0];

int idx = 0;

cout << endl

<< "Parsing steps: " << endl

<< endl;

cout << "Stack \t\t\tInput \t\t\tAction" << endl;

cout <<
"====================================================================
===" << endl;

do

if (isTerminal(ST.top()))

if (ST.top() == str[idx])

cout << left << setw(18) << curr_stack

<< setw(18) << str.substr(idx, str.length() - idx)

<< "Pop Action for " << ST.top() << endl;

ST.pop();
 curr_stack.pop_back();

idx++;

else

cout << endl

<< "The answer: Rejected (mismatch error)" << endl;

return;

else

vector<char> s;

getFromTable(ST.top(), str[idx], s);

if (!s.empty())

/* Pop the stack and push the right symbol string on the stack in reverse order */

cout << left << setw(18) << curr_stack

<< setw(18) << str.substr(idx, str.length() - idx)

<< "applied production rule ";

ST.pop();

curr_stack.pop_back();

for (int i = s.size() - 1; i >= 3; i--)

{
 if (s[i] != '@')

ST.push(s[i]);

curr_stack += s[i];

for (int i = 0; i < s.size(); i++)

cout << s[i];

cout << endl;

else

cout << endl

<< "The answer: Rejected (empty error)" << endl;

return;

} while (ST.top() != '$');

cout << endl

<< "The answer: Accepted";

}
int main()

cout << "Please enter the number of production:" << endl;

cin >> grammar.num;

string s;

cout << "Please enter the productions:" << endl;

for (int i = 0; i < grammar.num; i++)

cin >> s;

Production temp;

temp.left = s[0];

for (int j = 3; j < s.size(); j++)

temp.rights.push_back(s[j]);

grammar.prods.push_back(temp);

// terminals

for (int i = 0; i < grammar.prods.size(); i++)

Production &P = grammar.prods[i];

char X = P.left;

if (!isNonTerminal(X))

grammar.N.push_back(X);
}

// non-terminals

for (int i = 0; i < grammar.prods.size(); i++)

Production &P = grammar.prods[i];

for (int j = 0; j < P.rights.size(); j++)

char Y = P.rights[j];

if (!isNonTerminal(Y) & Y != '@')

grammar.T.push_back(Y);

grammar.T.push_back('$');

cout << endl

<< "--------------------------------------------" << endl;

cout << "Terminals: ";

for (int i = 0; i < grammar.T.size(); i++)

cout << grammar.T[i] << " ";

cout << endl;

for (int i = 0; i < grammar.T.size(); i++)

cout << grammar.N[i] << " ";

cout << endl;

cout << endl

<< "--------------------------------------------" << endl;

FindFirst();

cout << endl

<< "--------------------------------------------" << endl;

FindFollow();

cout << endl

<< "--------------------------------------------" << endl;

BuildTable();

cout << endl

<< "--------------------------------------------" << endl;

parser();

return 0;

Output:
Aim: Write a recursive descent parser for the grammar-

S-> cAd

A->a | ab

Code:

#include <bits/stdc++.h>

using namespace std;

void advance(int &idx) { idx++; }

void S(string str, int &idx);

void A(string str, int &idx);

string str;

cout << "Enter String : ";

cin >> str;

if (str[str.size() - 1] != '$')

str += '$';

int idx = 0;

S(str, idx);

if (str[idx] == '$')

cout << "success";

else

cout << "failed";

return 0;

void S(string str, int &idx)

if (str[idx] == 'c')

advance(idx);
 else

return;

A(str, idx);

if (str[idx] == 'd')

advance(idx);

else

return;

void A(string str, int &idx)

if (str[idx] == 'a')

advance(idx);

else

return;

if (str[idx] == 'b')

advance(idx);

Output: