一、设计目的

根据某一文法编写调试递归下降分析程序，对任意输入的符号串进行语法分析。本题目的目的主要是加深对递归下降分析方法的理解。

二、设计内容

对文法[E]：
E→TG
G→+TG|-TG|ε
T→FS
S→*FS|/FS|ε
F→(E)|i
编写程序实现对输入串的语法分析。

1.递归下降分析法的功能

递归下降分析方法是利用函数之间的递归调用模拟语法树自上而下的构造过程。

2.递归下降分析法的前提

改造文法：消除二义性，消除左递归，提取公共左因子，判断是否 LL(1)文法。

3.递归下降分析法的设计思想及算法

为文法的每个非终结符 U 构造一个递归过程，可命名为 U()，根据 U 的产生式的右部给出过程 U()的代码结构：若 U 是终结符，则和当前输入符号对照，若匹配则向前进一个符号，否则出错；若 U 是非终结符，则调用与此非终结符对应的过程。当 U的右部有多个产生式时，可用选择结构实现。
具体为：

（1）对于每个非终结符号 U→α1|α2|…|αn

U( ) {
if sym ∈FIRST(α1 )then P(α1) //处理α1 的程序部分
else if sym ∈FIRST(α2 )then P(α2) //处理α2 的程序部分
…
else if sym ∈FIRST(αn )then P(αn)
else if sym ∈FOLLOW(U)then return //处理空产生式情况
else error
}

（2）对于每个右部α =x1x2…xn的处理如下：

P(α) {
P(x1 ); //处理 x1 的程序
P(x2 ); //处理 x2 的程序
… … …
P(xn ); //处理 xn 的程序
}

（3）对于右部中的每个符号 xi

如果 xi为终结符号：
if(sym= a)
sym=下一输入符号 //对于终结符，直接将指针前调
else
error
如果 xi为非终结符号，直接调用相应的过程 xi。

三、功能扩充

如果遇到表达式中的错误，应输出错误提示信息（该信息越详细越好）。
可以给出详细的推导过程，列出每一步使用的产生式规则。

四、算法实现

1.算法流程图

2.程序代码

#include <algorithm>
#include <iostream>
#include <Windows.h>
#include <stdio.h>
#include <ctype.h>

using namespace std;

#define RED SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_RED);
#define GREEN SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_GREEN);
#define PURPLE SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 0x0d); // Sample 紫色
#define INITIAL SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE); // 字体恢复原来的颜色

bool flag = TRUE; // 判断标志位
string token = "";
int i, Sample = 1;

void E(); // E -> TG
void G(); // G -> +TG|-TG|ε
void T(); // T -> FS
void S(); // S -> *FS|/FS|ε
void F(); // F -> (E)|i
void print();

void E()
{
    cout << "E -> TG" << endl;
    T();
    G();
}

void G()
{
    if (token[i] == '+')
    {
        i++;
        cout << "G -> +TG" << endl;
        T();
        G();
    }
    else if (token[i] == '-')
    {
        i++;
        cout << "G -> -TG" << endl;
        T();
        G();
    }
}

void T()
{
    cout << "T -> FS" << endl;
    F();
    S();
}

void S()
{
    if (token[i] == '*')
    {
        i++;
        cout << "S -> *FS" << endl;
        F();
        S();
    }
    else if (token[i] == '/')
    {
        i++;
        cout << "S -> /FS" << endl;
        F();
        S();
    }
}

void F()
{
    if (token[i] == '(')
    {
        i++;
        E();
        if (token[i] == ')')
        {
            i++;
            cout << "F -> (E)" << endl;
        }
        else
        {
            RED // ERROR
            cout << "\n" << "ERROR: ')'miss" << "\n" << endl;
            flag = 0;
        }
    }
    else if (token[i] == 'i')
    {
        cout << "F -> i" << endl;
        i++;
    }
    else
    {
        RED // ERROR
        cout << "\n" << "ERROR: Incorrect Expected" << "\n" << endl;
        flag = FALSE;
    }
}

void Read(FILE *fp)
{
    char ch;
    while (TRUE)
    {
        ch = fgetc(fp);
        if (ch == '\n' || ch == EOF)
        {
            token.push_back('#');
            if (token == "#")
            {
                token = "";
            }
            else
            {
                print();
            }
        }
        else
        {
            token.push_back(ch); // 将读取的字符ch存入token中
        }
        if(ch == EOF)
            break;
    }
}

void print()
{
    i = 0;
    PURPLE
    cout << "Sample-" << Sample << endl;
    Sample++;
    GREEN
    E();
    if(token[i] == '#' && flag)
    {
        cout << "\n" << "Succese" << "\n" << endl;
    }
    if(token[i] != '#' && flag)
    {
        RED
        cout << "\n" << "ERROR: Lack Expression" << "\n" << endl;
    }
    token = "";
    flag = TRUE;
}

int main()
{
    string filename; // 文件路径
    FILE *fp;        // 文件指针
    cout << "Please enter the path: ";
    while (true)
    {
        cin >> filename;
        fp = fopen(filename.c_str(), "r");
        if (fp != NULL)
            break;
        else
            cout << "Wrong Path, Please try again" << endl;
    }
    Read(fp);
    fclose(fp);
    INITIAL
    system("pause");
    return 0;
}