Use of CFGs for Parsing OPEN

We can think of using CFGs to detect various language constructs in the token streams freed from simple
syntactic and semantic errors, as it is easier to describe the constructs with CFGs. But CFGs are hard to
apply practically. In this session we first exercise on simpler implementations of CFGs, and then
implement the FIRST and FOLLOW functions that facilitate efficient parsing algorithms for practical
problems.

Session 5 by Nafis Islam on Scribd

	#include<bits/stdc++.h>
	using namespace std;
	int i=0,f=0,l;
	string st;
	void A() {
	if (st[i] == 'a') {
	i++;
	f=1;
	}
	else {
	f=0;
	return;
	}
	if (i<l-1) A();
	}
	void B() {
	if (st[i] == 'b') {
	i++;
	f=1;
	return;
	}
	else {
	f=0;
	return;
	}
	}
	void S() {
	if (st[i] == 'b'){
	i++;
	f = 1;
	return;
	}
	else {
	A();
	if (f) { B(); return;}
	}
	}
	int main(){
	freopen("i1.txt","r",stdin);
	freopen("o1.txt","w",stdout);
	while(getline(cin,st)){
	f = 0;
	i = 0;
	l = st.size();
	S();
	if(l==i && f){
	cout<<"valid\n";
	}
	else{
	cout<<"invalid\n";
	}
	}
	}

view raw grammar1.cpp hosted with ❤ by GitHub

	b
	ab
	aab
	aaab

view raw i1.txt hosted with ❤ by GitHub

	valid
	valid
	valid
	valid

view raw oi.txt hosted with ❤ by GitHub

	#include<bits/stdc++.h>
	using namespace std;
	int i=0,f=0,l;
	string s;
	void X(){
	if(s[i]=='b'){
	i++;
	f = 1;
	}
	else{
	f = 0;
	return;
	}
	if(s[i]=='b'){
	i++;
	f = 1;
	if(i!=l-1) X();
	}
	else if(s[i]=='c'){
	i++;
	f = 1;
	if(i!=l-1) X();
	}
	else{
	f = 0;
	return;
	}
	}
	void A(){
	if(s[i]=='a'){
	i++;
	f = 1;
	}
	else return;
	if(i!=l-1){
	X();
	}
	if(i==l-1 && f){
	if(s[i]=='d'){
	f = 1;
	i++;
	return;
	}
	else{
	f = 0;
	return;
	}
	}
	}
	int main(){
	freopen("i2.txt","r",stdin);
	freopen("o2.txt","w",stdout);
	while(getline(cin,s)){
	f = 0;
	i = 0;
	l = s.size();
	A();
	if(l==i && f){
	cout<<"valid\n";
	}
	else{
	cout<<"invalid\n";
	}
	}
	}

view raw grammar2.cpp hosted with ❤ by GitHub

	asasfas
	bba
	ba
	abbd

view raw i2.txt hosted with ❤ by GitHub

	invalid
	invalid
	invalid
	valid

view raw out.txt hosted with ❤ by GitHub

	#include<bits/stdc++.h>
	using namespace std;
	vector<string>sp,ke,ri;
	map<string,string>mp,mpp;
	string ans;
	bool isTERMINAL(char a){
	if(a>='A' && a<='Z') return true;
	return false;
	}
	void FIRST(string key){
	string val = mp[key];
	if(isTERMINAL(val[0])){
	string p = "";
	p += val[0];
	FIRST(p);
	}
	else{
	ans += val[0];
	ans += ",";
	int flag = 0;
	for(int i=0;i<val.size();i++){
	if(val[i]=='|'){
	flag = 1;
	continue;
	}
	if(flag){
	ans += val[i];
	}
	}
	}
	}
	void FOLLOW(string key,int z){
	int flag = 0;
	for(int i=0;i<ri.size();i++){
	if (ri[i].find(key) != string::npos) {
	if(key.size()==1){
	for(int j=0;j<ri[i].size();j++){
	if(ri[i][j]==key[0]){
	if(j+1<ri.size() && ri[i][j+1]!='\''){
	flag = 1;
	if(isTERMINAL(ri[i][j+1])==false){
	if(z==0)ans += "$,";
	ans += ri[i][j+1];
	}
	else{
	string g = ri[i];
	g.erase(0,1);
	FIRST(g);
	if(z==0)ans += "$,";
	FOLLOW(mpp[ri[i]],1);
	}
	break;
	}
	}
	}
	}
	else{
	flag = 1;
	for(int j=0;j+1<ri[i].size();j++){
	if(ri[i][j]==key[0] && ri[i][j+1]==key[1]){
	if(j+2>=ri[i].size()){
	FOLLOW(mpp[ri[i]],1);
	if(z==0)ans += ",$";
	}
	else{
	}
	}
	}
	break;
	}
	}
	if(flag) break;
	}
	}
	string remove_space(string s){
	string p="";
	for(int i=0;i<s.size();i++){
	if(s[i]!=' ') p = p + s[i];
	}
	return p;
	}
	int main(){
	freopen("input.txt","r",stdin);
	freopen("out.txt","w",stdout);
	string s;
	while(getline(cin,s)){
	sp.push_back(remove_space(s));
	}
	for(int i=0;i<sp.size();i++){
	int flag = 0;
	string key="",val="";
	for(int j=0;j<sp[i].size();j++){
	if(sp[i][j]=='='){
	flag = 1;
	continue;
	}
	if(flag==0) key += sp[i][j];
	else val += sp[i][j];
	}
	mp[key] = val;
	ke.push_back(key);
	}
	cerr<<"FIRST: \n\n";
	cout<<"FIRST: \n\n";
	for(int i=0;i<ke.size();i++){
	ans = "";
	FIRST(ke[i]);
	cerr<<"FIRST("<<ke[i]<<")"<<" = {"<<ans<<"}\n";
	cout<<"FIRST("<<ke[i]<<")"<<" = {"<<ans<<"}\n";
	}
	for(int i=0;i<ke.size();i++){
	string val = mp[ke[i]];
	string v = "";
	for(int j=0;j<val.size();j++){
	if(val[j]=='|') break;
	v += val[j];
	}
	mp[ke[i]] = v;
	mpp[v] = ke[i];
	ri.push_back(v);
	}
	cerr<<"\nFOLLOW: \n\n";
	cout<<"\nFOLLOW: \n\n";
	for(int i=0;i<ke.size();i++){
	ans = "";
	FOLLOW(ke[i],0);
	cerr<<"FOLLOW("<<ke[i]<<")"<<" = {"<<ans<<"}\n";
	cout<<"FOLLOW("<<ke[i]<<")"<<" = {"<<ans<<"}\n";
	}
	}

view raw FIRST and FOLLOW.cpp hosted with ❤ by GitHub

	E = TE'
	E' = +TE' | #
	T = FT'
	T' = *FT' | #
	F = (E) | id

view raw input.txt hosted with ❤ by GitHub

	FIRST:
	FIRST(E) = {(,id}
	FIRST(E') = {+,#}
	FIRST(T) = {(,id}
	FIRST(T') = {*,#}
	FIRST(F) = {(,id}
	FOLLOW:
	FOLLOW(E) = {$,)}
	FOLLOW(E') = {),$}
	FOLLOW(T) = {+,$,)}
	FOLLOW(T') = {+,),$}
	FOLLOW(F) = {*,$,+,)}

view raw output.txt hosted with ❤ by GitHub