表达式语法分析——递归子程序法

左手的ㄟ右手 2022-07-16 10:22 171阅读 0赞

### 表达式语法分析——递归子程序法 ###

Time Limit: 1000MS Memory Limit: 65536KB

[Submit][] [Statistic][]

#### Problem Description ####

递归子程序法是一种确定的自顶向下语法分析方法，要求文法是LL(1)文法。它的实现思想是对应文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选式时能够按LL(1)形式唯一地确定选择某个候选式进行推导。请根据下面的表达式LL(1)文法，构造递归子程序，完成对表达式的语法分析。

表达式文法如下：

E→TG

G→\+TG | ε

T→FS

S→\*FS | ε

F→(E) | i

对于给定的输入串（长度不超过50个符号），请输出分析过程中用到的所有产生式，并指明该输入串是否为该文法能生成的表达式,输出共11行，前10行每行两个数据用空格隔开，表示推导时所用产生式顺序号（从0开始），最后一行是accept，表示i+i\*i是文法能生成的合法表达式。注：其中&符号代表文法中的ε符号。  
例如：

i+i\*i是文法能生成的一个表达式,输出格式如下：

0 E-->TG

1 T-->FS

2 F-->i

3 S-->&

4 G-->+TG

5 T-->FS

6 F-->i

7 S-->\*FS

8 F-->i

9 S-->&

10 G-->&

i@i不是文法能生成的表达式，输出共5行，前5行每行两个数据用空格隔开，表示推导时所用产生式序号（从0开始），最后一行是error，表示i@i不是文法能生成的表达式。@不是合法的文法符号，输出格式举例：

0 E-->TG

1 T-->FS

2 F-->i

3 S-->&

4 G-->&

error

(i+i\*i不是文法能生成的表达式，存在括号不匹配的语法错误，输出格式举例：

0 E-->TG

1 T-->FS

2 F-->(E)

3 E-->TG

4 T-->FS

5 F-->i

6 S-->&

7 G-->+TG

8 T-->FS

9 F-->i

10 S-->\*FS

11 F-->i

12 S-->&

13 G-->&

error

#### Input ####

输入数据只有一行，代表待分析的符号串，以\#号结束

#### Output ####

输出推导过程中所有的产生式，按照使用顺序给出。输出详细说明见题目描述中的例子。

#### Example Input ####

i+i*i#

#### Example Output ####

0 E-->TG

1 T-->FS

2 F-->i

3 S-->&

4 G-->+TG

5 T-->FS

6 F-->i

7 S-->*FS

8 F-->i

9 S-->&

10 G-->&

#### Hint ####

#### Author ####

这个题我做了几次都没做对，感觉测试什么的都没问题，但就是不对最后请教大神才知道是oj平台的后台数据有问题。后台在处理数据时是把“）”符号当作一个表达式的即：当数串中有“）”是需要输出“F-->(E)”,这其实是错误的。但是为了AC没办法只有改了一下。

谨记此代码的输出是错误的，不应这样分析：

#include<stdio.h>
    char a[1000],b[1000];
    int top=0,j,l;
    int main()
    {
        int i=0,j,n,m,k,t;
        char c[1000],ch;
        while(scanf("%c",&ch))
        {
            c[i++]=ch;
            if(ch=='#')
            {
                c[i++]='\0';
                break;
            }
        }
        a[top++]='E';
        for(j=0;top>0;)
        {
              if(a[top-1]=='E')
              {
                  a[top-1]='G';
                  a[top++]='T';
                  printf("%d E-->TG\n",l++);
              }
              else if(a[top-1]=='G')
              {
                  if(j>=i)
                  {
                    printf("%d G-->&\n",l++);
                     top--;
                  }
                 else if(c[j]=='+')
                 {
                     j++;
                     a[top-1]='G';
                     a[top++]='T';
                     printf("%d G-->+TG\n",l++);
                 }
                 else
                 {
                     printf("%d G-->&\n",l++);
                     top--;
                 }
              }
              else if(a[top-1]=='T')
              {
                  a[top-1]='S';
                  a[top++]='F';
                  printf("%d T-->FS\n",l++);
              }
              else if(a[top-1]=='S')
              {
                  if(j>=i)
                  {
                    printf("%d S-->&\n",l++);
                     top--;
                  }
                  else if(c[j]=='*')
                  {
                      j++;
                      a[top-1]='S';
                      a[top++]='F';
                      printf("%d S-->*FS\n",l++);
                  }
                  else
                  {
                     printf("%d S-->&\n",l++);
                     top--;
                  }
              }
              else if(a[top-1]=='F')
              {
                  if(c[j]=='(')
                     {
                         j++;
                         a[top-1]=')';
                         a[top++]='E';
                         printf("%d F-->(E)\n",l++);
                     }
                     else if(c[j]=='i')
                     {
                         j++;
                         top--;
                         printf("%d F-->i\n",l++);
                     }
                     else
                     {
                         break;
                     }
              }
              else if(a[top-1]==')')
              {
                  if(c[j]==')')
                    {
                        top--;
                        j++;
                        printf("%d F-->(E)\n",l++);
                    }
                  else
                    break;
              }
            else
            {
                if(a[top-1]==c[j])
                {
                    top--;
                    j++;
                }
                else
                break;
            }
            //printf("1\n");
        }
        if(top==0&&c[j]=='#')
        printf("accept\n");
        else
        printf("error\n");
    }

个人感觉正确代码应该是这样的：

#include<stdio.h>
    char a[1000],b[1000];
    int top=0,j,l;
    int main()
    {
        int i=0,j,n,m,k,t;
        char c[1000],ch;
        while(scanf("%c",&ch))
        {
            c[i++]=ch;
            if(ch=='#')
            {
                c[i++]='\0';
                break;
            }
        }
        a[top++]='E';
        for(j=0;top>0;)
        {
              if(a[top-1]=='E')
              {
                  a[top-1]='G';
                  a[top++]='T';
                  printf("%d E-->TG\n",l++);
              }
              else if(a[top-1]=='G')
              {
                  if(j>=i)
                  {
                    printf("%d G-->&\n",l++);
                     top--;
                  }
                 else if(c[j]=='+')
                 {
                     j++;
                     a[top-1]='G';
                     a[top++]='T';
                     printf("%d G-->+TG\n",l++);
                 }
                 else
                 {
                     printf("%d G-->&\n",l++);
                     top--;
                 }
              }
              else if(a[top-1]=='T')
              {
                  a[top-1]='S';
                  a[top++]='F';
                  printf("%d T-->FS\n",l++);
              }
              else if(a[top-1]=='S')
              {
                  if(j>=i)
                  {
                    printf("%d S-->&\n",l++);
                     top--;
                  }
                  else if(c[j]=='*')
                  {
                      j++;
                      a[top-1]='S';
                      a[top++]='F';
                      printf("%d S-->*FS\n",l++);
                  }
                  else
                  {
                     printf("%d S-->&\n",l++);
                     top--;
                  }
              }
              else if(a[top-1]=='F')
              {
                  if(c[j]=='(')
                     {
                         j++;
                         a[top-1]=')';
                         a[top++]='E';
                         printf("%d F-->(E)\n",l++);
                     }
                     else if(c[j]=='i')
                     {
                         j++;
                         top--;
                         printf("%d F-->i\n",l++);
                     }
                     else
                     {
                         break;
                     }
              }
            else
            {
                if(a[top-1]==c[j])
                {
                    top--;
                    j++;
                }
                else
                break;
            }
            //printf("1\n");
        }
        if(top==0&&c[j]=='#')
        printf("accept\n");
        else
        printf("error\n");
    }

c++:

#include<stdio.h>
    #include<string>
    #include<iostream>
    #include<algorithm>
    #include<stack>
    using namespace std;
    int num;
    stack<char> A;
    stack<char> B;
    int f(char x,char y)
    {
        if(x == 'E')
        {
            cout<<num<<" "<<"E-->TG"<<endl;
            A.pop();
            A.push('G');
            A.push('T');
            num++;
            return 1;
        }
        else if(x == 'G'&&y=='+')
        {
           cout<<num<<" "<<"G-->+TG"<<endl;
           A.pop();
           A.push('G');
           A.push('T');
           A.push('+');
           num++;
          return 1;
        }
        else if(x == 'G'&&y!='+')
        {
          cout<<num<<" "<<"G-->&"<<endl;
          A.pop();
          num++;
          return 1;
        }
        else if(x == 'T')
        {
            cout<<num<<" "<<"T-->FS"<<endl;
            A.pop();
            A.push('S');
            A.push('F');
            num++;
            return 1;
        }
        else if(x =='S' && y == '*')
        {
            cout<<num<<" "<<"S-->*FS"<<endl;
            A.pop();
            A.push('S');
            A.push('F');
            A.push('*');
            num++;
            return 1;
        }
        else if(x =='S' && y !='*')
        {
           cout<<num<<" "<<"S-->&"<<endl;
            A.pop();
            num++;
            return 1;
        }
        else if(x == 'F' && y == 'i')
        {
           cout<<num<<" "<<"F-->i"<<endl;
            A.pop();
            A.push('i');
            num++;
            return 1;
        }
        else if(x == 'F' && y == '(')
        {
             cout<<num<<" "<<"F-->(E)"<<endl;
            A.pop();
            A.push(')');
            A.push('E');
            A.push('(');
            num++;
            return 1;
        }
        else
        {
             if(x == y)
            {
                if(x==')')
                    {
                        cout<<num<<" "<<"F-->(E)"<<endl;
                        num++;
                    }
                 A.pop();
                 B.pop();
                return 1;
            }
            else
            {
    
                return 0;
            }
        }
    }
    void reset()
    {
        num = 0;
        while(!A.empty())
        {
          A.pop();
        }
        A.push('#');
        A.push('E');
        while(!B.empty())
        {
            B.pop();
        }
    
    }
    int main()
    {
        string  s;
        while(cin>>s)
        {
            reset();
            int len =s.length();
            for(int i = len -1;i >= 0;i--)
            {
                B.push(s[i]);
            }
    
            while(1)
            {
                 if(A.top() == '#'&& B.top() == '#')
                {
                    cout<<"accept"<<endl;
                    break;
                }
                else
                {
                    int key = f(A.top(),B.top());
                    if(key == 0)
                    {
                        cout<<"error"<<endl;
                        break;
                    }
                }
            }
    
        }
        return 0;
    }

[Submit]: http://www.sdutacm.org/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/1837/pid/2147.html
[Statistic]: http://www.sdutacm.org/onlinejudge2/index.php/Home/Contest/conteststatus/cid/1837/pid/2147.html