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

拼搏现实的明天。 2023-06-14 13:53 10阅读 0赞

## 欢迎访问我的个人博客： ##

[苦酒的个人小站][Link 1]

# 题目介绍 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70][]

# 题目思路 #

题目给的表达式文法为：

*  E→TG
 *  G→+TG | ε
 *  T→FS
 *  S→\*FS | ε
 *  F→(E) | 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–>&
 *  accept

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

当你输入符号串的时候：

*  首先要进行E（）函数，该函数的意思是直接输出E所对应的文法**E–>TG**，可以直接跑到T（）和G（）
 *  对于T函数来说，直接根据题目输出**T–>FS**，来进入到F函数和S函数
 *  对于G函数来说，题目给的是**G→+TG | ε**，所以需要判断当前的字符是否为+号，如果当前字符为+的话，直接输出**G–>+TG**，num要加一位并且进入T函数和G函数，反之直接输出**G–>&**
 *  对于F函数来说，题目给的是**F→(E) | i**，所以需要判断当前的字符是否为i和（，如果当前是i的话，输出**F–>i**，如果是（的话，输出**F–>(E)**，并且num++和进入E函数，这里需要再一次判断当前的字符串是否为（，防止只有右括号没有左括号的现象
 *  对于S函数来说，题目给的是**S→\*FS | ε**如果当前字符串是\*,*直接输出\*\*S→*FS\*\*，否则输出**S→&**\*

# 易错点 #

1.  在判断字符的时候忘记进行num++
2.  num++一定要在递归之前

# 代码 #

/*
    author:苦酒
    QQ:1793929520
    blog:huangliangshuai.com
    */
    #include <iostream>
    #include <string>
    #include <cstdlib>
    #include <cstring>
    #include <stdio.h>
    
    using namespace std;
    
    char str[101];
    int sum = 0;
    int num = 0;
    
    void E();
    void T();
    void G();
    void F();
    void S();
    
    void E()
    {
        cout<<sum++<<" "<<"E-->TG"<<endl;
        T();
        G();
    }
    
    void T()
    {
        cout<<sum++<<" "<<"T-->FS"<<endl;
        F();
        S();
    }
    
    void G()
    {
        if(str[num] == '+')
        {
            cout<<sum++<<" "<<"G-->+TG"<<endl;
            num++;
            T();
            G();
        }
        else
        {
            cout<<sum++<<" "<<"G-->&"<<endl;
        }
    }
    
    void F()
    {
        if(str[num] == 'i')
        {
            cout<<sum++<<" "<<"F-->i"<<endl;
            num++;
        }
        else if(str[num] == '(')
        {
            cout<<sum++<<" "<<"F-->(E)"<<endl;
            num++;
            E();
            if(str[num] == ')')
            {
                num++;
            }
            else
            {
                printf("error\n");
                exit(0);
            }
        }
        else
        {
            printf("error\n");
            exit(0);
        }
    }
    
    void S()
    {
        if(str[num] == '*')
        {
            cout<<sum++<<" "<<"S-->*FS"<<endl;
            num++;
            F();
            S();
        }
        else
        {
            cout<<sum++<<" "<<"S-->&"<<endl;
        }
    }
    
    
    int main()
    {
        scanf("%s", str);
        E();
        if(str[num] != '#')
        {
            cout<<"error"<<endl;
        }
        else
        {
            cout<<"accept"<<endl;
        }
    }
    
    
    /***************************************************
    User name: jk170631黄良帅
    Result: Accepted
    Take time: 0ms
    Take Memory: 192KB
    Submit time: 2019-11-19 19:24:50
    ****************************************************/

[Link 1]: https://www.huangliangshuai.com/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191119203714649.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5,size_16,color_FFFFFF,t_70