adelnobel's blog

By adelnobel, 11 years ago, In English

Hi, I'm having a really hard time implementing a recursive descent parser for this problem http://www.spoj.com/problems/FOOL/

I made a correct CYK parser implementation for it but it always gets TLE. I'm not very familiar with recursive descent parsers as it seems! I made one that seems to be very terrible and buggy.

I dunno how to approach this problem and how to make a correct recursive descent parser implementation for it. If anyone could help it would be much appreciated!

By the way, my implementation can accept an invalid string by reading just some few characters from the start! I always had this problem with the parsers I make, if a prefix of the string is in the language, the parser may read it and stop and don't continue to the end!!

#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <iostream>
#include <bitset>
#include <map>
#include <ctime>
#include <set>
#include <complex>
 
using namespace std;
 
typedef long long ll;
 
char str[300];
int len, cur;
 
bool Set();
bool list();
bool Element();
bool Set();
bool Atom();
 
bool Set(){
    int save = cur;
    if(str[cur] == '{' && str[cur+1] == '}'){
        cur += 2;
        return true;
    }
    cur = save;
    if(str[cur] == '{'){
        cur++;
        if(list() && str[cur] == '}'){
            cur++;
            return true;
        }
    }
    cur = save;
    return false;
}
 
 
 
bool list(){
    int save = cur, save2;
    if(Element()){
        save2 = cur;
        if(str[cur] == ','){
            cur++;
            if(list()){
                return true;
            }
        }
        cur = save2;
        return true;
    }
    cur = save;
    return false;
}
 
bool Element(){
    int save = cur;
    if(Set()){
        return true;
    }
    cur = save;
    if(Atom()){
        return true;
    }
    cur = save;
    return false;
}
 
bool Atom(){
    if(str[cur] == '{' || str[cur] == '}' || str[cur] == ','){
        cur++;
        return true;
    }
    return false;
}
 
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in", "r", stdin);
#endif
    int t, c = 1;
    
    scanf("%d ", &t);
    
    
    while(t--){
        memset(str, '\0', sizeof str);
        gets(str);
        
        len = strlen(str);
        cur = 0;
        
        printf("Word #%d: ", c++);
        
        if(Set()){
            printf("Set\n");
        }else{
            printf("No Set\n");
        }
        
    }
    return 0;
}
  • Vote: I like it
  • 0
  • Vote: I do not like it