编译原理实验二:语法分析一 |
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; }