Skip to content

Instantly share code, notes, and snippets.

@utkarshsingh99
Last active December 1, 2019 18:02
Show Gist options
  • Save utkarshsingh99/ce68cd0de2810cdd93a7cbf4291dde4d to your computer and use it in GitHub Desktop.
Save utkarshsingh99/ce68cd0de2810cdd93a7cbf4291dde4d to your computer and use it in GitHub Desktop.
A short program to find the First & Follow of a Grammar in CPP (82 Lines of Code)
#include<bits/stdc++.h>
using namespace std;
int main() {
string a[5];
for(int i = 0; i < 5; i++) cin>>a[i];
map <char, string> s;
unordered_map <char, vector <char>> first, follow, t;
for(int i = 0; i < 5; i++) {
cout<<a[i]<<endl;
string h="";
for(int j = 3; j < a[i].size(); j++) {
h+=a[i][j];
}
s[a[i][0]] = h;
}
for(auto i:s) {
bool find = true;
for(auto j:i.second) {
if(j == '|') {
find = true;
} else if(j == '(') {
first[i.first].push_back('(');
continue;
} else if(j >= 65 && j <= 90 && find) {
find = false;
first[i.first].insert(first[i.first].end(), first[j].begin(), first[j].end());
} else if(find) {
first[i.first].push_back(j);
find = false;
}
}
}
follow['E'].push_back('$');
for(auto i= s.end(); i!= s.begin(); i--) {
for(auto find_i:s) {
bool found = false;
for(auto i_string:find_i.second) {
if(found) {
found = false;
if(i_string >= 65 && i_string <= 90) {
follow[i->first].insert(follow[i->first].end(), first[i_string].begin(), first[i_string].end());
for(auto p : first[i_string]) {
{
if(p == '(') {
found = true;
continue;
}
follow[i->first].push_back(p);
}
}
} else if(i_string == '|' || i_string == '.') {
follow[i->first].insert(follow[i->first].end(), follow[find_i.first].begin(), follow[find_i.first].end());
} else {
follow[i->first].push_back(i_string);
}
}
if(i_string == i->first) {
found = true;
}
}
}
}
cout<<"First: \n";
for(auto i:first) {
cout<<i.first<<" : ";
for(auto j:i.second) {
cout<<j<<" ";
}cout<<endl;
}
cout<<"Follow: \n";
for(auto i:follow) {
cout<<i.first<<" : ";
sort( i.second.begin(), i.second.end() );
i.second.erase( unique( i.second.begin(), i.second.end() ), i.second.end() );
for(auto j:i.second) {
if(j == '(')
continue;
cout<<j<<" ";
}
cout<<endl;
}
}
// Conditions for input:
// 1. Epsilon is represented as '('. So if you want to use '(',')', consider using '[',']'
// 2. The Variable Names should be in reverse alphabetical order due to the usage of maps.
// For example, if the Start Symbol is S, the further variables should be named anywhere from [A, R].
// After every production set defined, add a '.' to signify its end. Except for Epsilon '('
// 3. Avoid white spaces in your input. Do not leave spaces after left-hand declaration of variable.
// E -> A -- this is wrong
// E->A -- this is right. Why? Notice line 11 where I'm converting the input grammar into a map
// 4. Terminal names can only be of one character
// An example input:
// E->CD.
// D->+CD.|(
// C->AB.
// B->*AB.|(
// A->i.|[E].
@utkarshsingh99
Copy link
Author

Screenshot from 2019-12-01 22-58-54

An example input and output for the following program.
In case you need a documentation of the above code, please refer by blog: https://thegoodindian.in

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment