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.
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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"; | |
| } | |
| } | |
| } | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| b | |
| ab | |
| aab | |
| aaab |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| valid | |
| valid | |
| valid | |
| valid |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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"; | |
| } | |
| } | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| asasfas | |
| bba | |
| ba | |
| abbd |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| invalid | |
| invalid | |
| invalid | |
| valid |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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"; | |
| } | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| E = TE' | |
| E' = +TE' | # | |
| T = FT' | |
| T' = *FT' | # | |
| F = (E) | id |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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) = {*,$,+,)} |
