编译原理 文法分析

时间:2023-02-11 03:53:19

编译原理实验二:语法分析一
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 115, Accepted users: 109
Problem 10835 : No special judgement
Problem description
  给定文法编译原理 文法分析 ,其中, P如下:

编译原理 文法分析

可以证明这是一个LL(1)文法,因此可以使用确定性分析。请编写语法分析程序,判断给定的输入是否为该文法的句子。输入可以认为是一不含空格的字符串,长度不超过4001。

该文法实际上是四则运算表达式结构的抽象,凡是符合四则运算表达式结构的均是该文法的句子,反之则不是。


Input
  输入只有一行,是一个长度不超过4001的字符串。
Output
  如果输入的字符串是上述文法的句子,则输出YES;否则输出NO。
Sample Input
i+i*i
Sample Output
YES
Judge Tips
  输入可以使用scanf(“%s”,…)或者gets(…)直接读入一个字符串。然后使用递归下降法或者预测分析法均可完成该实验。
 


int E();
int Ec();
int T();
int Tc();
int F();

char s[5000];
int idx;

int E(){
    return T() && Ec();
}
int Ec(){
    if ( s[idx] == '+' || s[idx] == '-') return idx++ && T() && Ec();
    return 1;
}
int T(){
    return F() && Tc();
}
int Tc(){
    if ( s[idx] == '*' || s[idx] == '/') return idx++ && F() && Tc();
    return 1;
}
int F(){
    if ( s[idx] == '(') return idx++ && E() && s[idx++] == ')';
    if ( s[idx] == 'i') return idx++ ;
    return 0;
}

int main(){
    while(scanf("%s",s+1) != EOF){
        s[0] = '1';
        idx = 1;
        int ans = E() && s[idx] == '\0';
        printf( ans ? "YES\n" : "NO\n");
    }
    return 0;
}

poj 1126


//S :: p~z
//S :: NS;
//S :: CSS | DSS | ESS | ISS
const int SIZE = 1111;
char  s[SIZE];
int idx;
bool Parse(){
    char ch = s[idx];
    switch(ch){
    case 'N': idx++; return Parse();
    case 'C': idx++; return Parse() && Parse();
    case 'D': idx++; return Parse() && Parse();
    case 'E': idx++; return Parse() && Parse();
    case 'I': idx++; return Parse() && Parse();
        default : idx++;return ch >= 'p' && ch <= 'z';
    }
}
int main(){
    while(scanf("%s",s) != EOF){
        idx = 0;
        int ans = (Parse() && '\0' == s[idx]);
        printf( ans ? "YES\n" : "NO\n");
    }
    return 0;
}