LL(1)文法--递归下降程序

递归下降程序

递归下降程序一般是针对某一个文法的。而递归下降的预测分析是为每一个非终结符号写一个分析过程，由于文法本身是递归的，所以这些过程也是递归的。
以上是前提。

Sample

1. 假如给的是正规式子，首先要做的是将其改为文法表示:
   ((int | float) id(,id)^*)
2. 以上式子为例，将其改为文法表示
   (D --> TL)
   (T-->int | float)
   (L--> L,id | id)
3. 然后消除其左递归
   (D --> TL)
   (T-->int | float)
   (L--> idR)
   (L-->, idR|ε)
4. 求其(FIRST表和FOLLOW表)
   (FIRST(D)=(int,float))
   (FIRST(T)=(int,float))
   (FIRST(L)=(id))
   (FIRST(L)=(,ε))
   (FOLLOW(D)=()$())
   (FOLLOW(L)=()$())
   (FOLLOW(T)=(id))
   (FOLLOW(R)=()$())
5. (Code)

//递归下降分析程序

#include<iostream>
#include<cstdio>
#include<sstream>
#include<cstring>
#include<string>
#include<cstdlib>
using namespace std;
string str;
size_t lookahead = 0;
string alphabet[] = {
    "int","float","(",")","id",","
};
//( int | float )id(,id)* 
//正规式表达
void D();
void T();
void L();
void R();
void error();

void error() {
    cout<<"Syntax Error!"<<endl;
}
void D() {
    T();
    L();
}

void T() {
    string m1 = str.substr(lookahead, 3);
    string m2 = str.substr(lookahead, 5);
    if (m1 == "int")
    {
        lookahead += 3;
    }
    else if (m2 =="float") {
        lookahead += 5;
    }
    else
        error();
}

void L() {
    string m3 = str.substr(lookahead, 2);
    if (m3 == "id") {
        lookahead += 2;
        R();
    }
    else
        error();
}

void R() {
    if (str[lookahead] == ',') {
        lookahead += 1;
        string m4 = str.substr(lookahead, 2);
        if (m4 == "id") {
            lookahead += 2;
            R();
        }
        else
            error();
    }
}

int main(void) {
    int n;
    cout<<"Test Number:" << endl;
    cin >> n;
    while (n--)
    {
        cout << "Input:";
        cin >> str;
        str.append("$");
        str.append("");
        D();
        if (str[lookahead] == '$')
            cout << "Accepted" << endl;
        else
            error();
        lookahead= 0;
    }
    return 0;
}