編譯原理：文法分析1-遞歸下降

遞歸下降的預測分析：為每一個非終結符寫一個分析過程。

要求：

1. 使用的文法如下：

   E →TE’

   E → + TE’ | ε

   T → FT’

   T →* FT’ | ε

   F → (E) | id

2. 對于任意給定的輸入串（詞法記号流）進行文法分析，遞歸下降方法實作。

3. 要有一定的錯誤處理功能。即對錯誤能提示，并且能在一定程度上忽略盡量少的記号來進行接下來的分析。可以參考書上介紹的同步記号集合來處理。

   可能的出錯情況：idid*id, id**id, （id+id， +id*+id ……

4. 輸入串以#結尾，輸出推導過程中使用到的産生式。例如：

   輸入：id+id*id#

   輸出：E →TE

   T →FT

   F →id

   E →+ TE

   T →FT

   ……

代碼

#include<iostream>

using namespace std;

static string ahead="";//目前正待處理的輸入記号
static string sub="";//目前待處理記号被處理後的輸入
void E();
void E_();//表示E'
void T();
void T_();//表示T'
void F();
void error();
void match(string t);
string nextToken();
int main()
{
    //不用自己輸入#
    char a[100]={};//儲存使用者輸入，接收輸入，不要超過100個字元，否則getline會設定失效位，接下來的輸入(如果有的話)将被阻斷,需要的話，可以調用cin.clear()恢複輸入
    cin.getline(a,100);//遇見回車表示輸入結束
    sub=a;
    sub+='#';
    ahead=nextToken();
    E();//因為E是開始符号
    return 0;
}
void E()
{
    if(ahead=="("||ahead=="id")//First(T)={(,id}
    {
        cout<<"E→TE'"<<endl;
        T();
        E_();
    }
    else if(ahead==")"||ahead=="#")//Follow(E)加入到E的同步記号集合中
    {
       // error();
       //出錯，但無須跳過任何記号，跳過E即可，即不作任何處理
        ;
    }
    else//出錯，目前記号不在E的同步記号集合中，跳過目前記号
    {
        //error();
        ahead=nextToken();
        E();
    }
}
void E_()
{
    if(ahead=="+")
    {
        cout<<"E'→+TE'"<<endl;
        match("+");
        T();
        E_();
    }
    else if(ahead==")"||ahead=="#")//Follow(E')={),$},這裡#代表$
    {
        cout<<"E'→ε"<<endl;
    }
    else//出錯，目前記号不在E'的同步記号集合中，跳過目前記号
    {
        //error();
        ahead=nextToken();
        E_();
    }
}
void T()
{
    if(ahead=="("||ahead=="id")//First(F)={(,id}
    {
       cout<<"T→FT'"<<endl;
       F();
       T_();
    }
    else if(ahead=="+"||ahead==")"||ahead=="#")//Follow(T)加入到T的同步記号集合中
    {
        // error();
       //出錯，但無須跳過任何記号，跳過T即可，即不作任何處理
        ;
    }
    else//出錯，目前記号不在T的同步記号集合中，跳過目前記号
    {
        //error();
        ahead=nextToken();
        T();
    }
}
void T_()
{
    if(ahead=="*")
    {
        cout<<"T'→*FT'"<<endl;
        match("*");
        F();
        T_();
    }
    else if(ahead=="+"||ahead==")"||ahead=="#")//FOllow(T')={+,),$},這裡#代表$
    {
        cout<<"T'→ε"<<endl;
    }
    else//出錯，目前記号不在T'的同步記号集合中，跳過目前記号
    {
        //error();
        ahead=nextToken();
        T_();
    }
}
void F()
{
    if(ahead=="(")
    {
        cout<<"F→（E）"<<endl;;
        match("(");
        E();
        match(")");
    }
    else if(ahead=="id")
    {
        cout<<"F→id"<<endl;;
         match("id");
    }
    else if(ahead=="+"||ahead=="*"||ahead==")"||ahead=="#")//Follow(F)加入到F的同步記号集合中
    {
         // error();
       //出錯，但無須跳過任何記号，跳過 F 即可，即不作任何處理
        ;
    }
    else//出錯，目前記号不在 F 的同步記号集合中，跳過目前記号
    {
        //error();
        ahead=nextToken();
        F();
    }
}
void error()
{
    cout<<"比對失敗！！！"<<endl;
}
void match(string t)
{
    if(ahead==t)
    {
        cout<<"比對"<<ahead<<endl;
        ahead=nextToken();
    }
    else
        error();
}
string nextToken()//擷取下一個詞法記号
{
    if(sub.substr(0,2)=="id")
    {
         sub=sub.substr(2,sub.size()-2);
         return "id";
    }
    else
    {
        string s=sub.substr(0,1);
        sub=sub.substr(1,sub.size()-1);
        return s;
    }
}

           

運作結果

• 可以與P59表3.2的動作比較一下，發現是一緻的