递归下降分析法实现文法解析 - C++代码示例

这是一个使用递归下降分析法实现文法解析的程序，用于分析输入的字符串是否符合给定的文法。程序首先定义了需要的头文件和变量，然后依次实现了E、G、T、S、F等函数，这些函数实现了对应的文法规则，如'E-->TG'，'G-->+TG|ε'等。在实现这些函数的过程中，程序会将每一步的分析过程记录下来，并存储在一个字符串类型的向量v中。当分析完成后，程序会检查是否已经到达输入串的末尾，如果是则说明输入串符合该文法，否则输入串不符合该文法。最后程序会输出分析过程和结果。

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
using namespace std;
//变量定义
string s, str, stackStr;//s：输入串、str：中间变量、stackStr : 模拟栈
int i;
string ch;//当前分析字符
vector<string> v;//字符串类型的向量(文法+分析栈)
//函数声明
void E();                   //E-->TG
void G();                   //G-->+TG|ε
void T();                   //T-->FS
void S();                   //S-->*FS|ε
void F();                   //F-->(E)|i
void err();					//提示错误信息
int check();//验证是否已经到栈底
void push(string pre, string value);//将字符串存入输出栈
/**
 * 函数功能：提示错误信息
 */
void err()
{
    cout << "ERROR" << endl;
    exit(0);
}
/**
 * 函数功能：将字符串存入输出栈
 */
void push(string pre, string value)
{
    ch += s[i];
    int idx = stackStr.find_first_of(pre[0], 0);//从头开始找到pre开始的位置
    if (value != "ε")//不是空字时
    {
        string value1;
        value1 = value;
        if (value[0] == '+')value1 = "TG";
        if (value[0] == '*')value1 = "FS";
        if (value[0] == '(')value1 = "E";
        if (value[0] == 'i')value1 = "";
        stackStr.replace(idx, 1, value1);//将第一个pre的位置替换为value
    }
    else
    {
        stackStr.erase(idx, 1);//删除从该位置开始的1个字符
    }
    v.push_back((pre + value + "," + stackStr));//将对应的表达式和栈的内容存加入在向量v尾部
}
/**
 * 函数功能：验证是否已经到栈底
 */
int check()
{
    if (i >= s.size()) {
        return 1;
    }
    else if (s[i] == '#')
    {
        ch += '#';
        return 1;
    }
    return 0;
}
/**
 * 函数功能：E-->TG
 */
void E()
{
    push("E-->", "TG");
    T();
    G();
}
/**
 * 函数功能：G-->+TG|ε
 */
void G() {
    if (s[i] == '+')
    {
        str = s[i];
        str += "TG";
        i++;
        push("G-->", str);
        T();
        G();
    }
    else
    {
        push("G-->", "ε");
    }
}
/**
 * 函数功能：T-->FS
 */
void T()
{
    push("T-->", "FS");
    F();
    S();
}
/**
 * 函数功能：S-->*FS|ε
 */
void S() {
    if (s[i] == '*')
    {
        str = s[i];
        str += "FS";
        i++;
        push("S-->", str);
        F();
        S();
    }
    else
    {
        push("S-->", "ε");
    }
}
/**
 * 函数功能：F-->(E)|i
 */
void F() {
    if (s[i] == '(')
    {
        i++;
        push("F-->", "(E)");
        E();
        if (s[i] == ')')
        {
            i++;
        }
        else
        {
            err();
        }
    }
    else if (s[i] == 'i')
    {
        i++;
        push("F-->", "i");
    }
    else
    {
        err();
    }
}
/**
 * 函数功能：主函数
 */
int main() {

    cout << "请输入字符串 (以#号结束） " << endl;

    while (cin >> s) //输入要分析的字符串
    {
        v.clear();
        i = 0;
        stackStr = "E#";//初始化栈
        E();
        if (check())
        {
            cout << "\t 输入串分析正确！ " << endl;
            cout << "推导过程如下： " << endl;
            cout << "文法\t\t分析栈\t\t当前分析字符\n";
            cout << "E      \t\tE#\t\t" << s[0] << endl;//初始栈的内容
            int i;
            for (i = 0; i < v.size(); i++)
            {
                cout << v[i].substr(0, v[i].find_first_of(",", 0)) << "\t";
                cout << setiosflags(ios::right) << setw(10) << v[i].substr(v[i].find_first_of(",", 0) + 1) << "\t\t";
                cout << ch[i] << endl;
            }
            cout << " 请继续输入字符串 (以#号结束）   " << endl;
        }
        else
            cout << "\t 输入串不符合该文法 " << endl;
    }

    return 0;
}

该程序使用了递归下降分析法，通过定义与文法规则对应的函数，对输入的字符串进行逐个字符的分析，最终判断字符串是否符合给定的文法。程序中使用了栈来模拟分析过程，并使用向量记录分析过程中的每一步。