text2.cpp

语法分析关于first集和follow集。可运行可使用。自己看吧。没问题的。 还有不知为什么不能归为源码一栏 那个谁谁有空看下

        char InputSymbol[30];
        char NonTeminalSymbol[30];
        char * First(char *ch);
        char * Follow(char ch);       
        bool IsTeminal(char ch);
        void Error();
public:
        Parse();
        ~Parse();
        void GetGrammar();
        void FormParseTable();
        void OutputParseTable();
        void MadeMoves(char * pt);
        void Run();
        bool IsInString(char *st,char ch);
        int GetPos(char *str,char ch);
        int GetPos(char ch);
};
Parse::Parse()
{
        NumOfGrammar = 0;
        NumOfTeminal = 0;
        NumOfNonTeminal = 0;
        gra = new Grammar();
}
Parse::~Parse()
{
        delete gra;       
        delete pt;
        delete ff;
}
//获取输入文法
void Parse::GetGrammar()
{
        int i = 0,j = 0,k = 0;
        int len = 0;
        char lPro;
        char rPro[30];
        cout<<"\n 请你输入文法的条数：";
        cin >>NumOfGrammar;
        cout<<"\n 请输入你的文法\n （如S→DEｂａｓｅ 终结符用小写，非终结符用大写，e表示空串）"<<endl;
        for (i=0;i<NumOfGrammar;i++)
        {
                char temp[30];
                cout<<" "<<i+1<<": ";
                lPro = getch();
                NonTeminalSymbol[NumOfNonTeminal++] = lPro;
                cout<<lPro<<"→";
                cin >>rPro;
                len = strlen(rPro);
                //把文法分开保存在文法段中
                k = 0;
                if (i == 0)
                {
                        gra->SetStartState(lPro);
                }
                 for (j=0;j<len;j++)
                {
                        if (rPro[j] == '|')
                        {
                                gra->Insert(lPro,temp);
                                k = 0;
                                strcpy(temp,"\0");
                        }
                        else if (j == len-1)
                        {
                                temp[k++] = rPro[j];
                                temp[k] = '\0';
                                gra->Insert(lPro,temp);
                                k = 0;
                                strcpy(temp,"\0");
                        }
                        else
                        {
                                temp[k++] = rPro[j];
                                 temp[k] = '\0';
                        }
                }
                //获取终结符的数目
                for (j=0;j<len;j++)
                {
                        if (!isupper(rPro[j])&&rPro[j]!='|'&&rPro[j]!='e')
                        {
                                for(k=0;k<NumOfTeminal;k++)
                                {
                                        if (rPro[j] == InputSymbol[k])
                                                break;
                                }
                                if (k == NumOfTeminal)
                                        InputSymbol[NumOfTeminal++] = rPro[j];
                        }
                }
        }
        NonTeminalSymbol[NumOfNonTeminal] = '\0';
        cout<<"\n 你输入的文法是：";
        Production pro;
        for (i=0;i<gra->GetNumOfGra()-1;i++)
        {
                pro = gra->GetGrammar(i);
                for (j=i+1;j<gra->GetNumOfGra();j++)
                {
                        Production prod= gra->GetGrammar(j);
                        if ((pro.From == prod.From)&&(strcmp(pro.To,prod.To)==0))
                        {
                                gra->Delete(j);
                                break;
                        }
                }
        }
        for (i=0;i<gra->GetNumOfGra();i++)
        {
                pro = gra->GetGrammar(i);
                cout<<"\n "<<i+1<<": "<<pro.From<<"→"<<pro.To;
        }
        cout<<"\n 非终结符是：";
        for (i=0;i<NumOfNonTeminal;i++)
        {
                cout<<NonTeminalSymbol[i]<<"  ";
        }
        cout<<"\n 终结符的：";
        for (i=0;i<NumOfTeminal;i++)
        {
                cout<<InputSymbol[i]<<"  ";
        }
        InputSymbol[NumOfTeminal++] = '$';
        InputSymbol[NumOfTeminal] = '\0';
        cout<<endl;
}
//判断字符ch 是否在string st中
bool Parse::IsInString(char *st,char ch)
{
        int len = strlen(st);
        for (int i=0;i<len;i++)
        {
                if (st[i] == ch)
                {
                        return true;
                }
        }
        if (i == len)
        {
                return false;
        }
        return true;
}
//求出FIRST 集合
char * Parse::First(char *ch)
{
        int count=0,len=0;
        int i=0,j=0,k=0;
        char *protemp = new char[30];
        char *temp = new char[30];
        strcpy(protemp,"\0");
        strcpy(temp,"\0");
        Production pro;
        if (strlen(ch) == 1)
        {
                if (isupper(ch[0]))
                {
                        for (j=0;j<(gra->GetNumOfGra());j++)
                        {
                                pro = gra->GetGrammar(j);
                                if (ch[0] == pro.From)
                                {
                                        if (strcmp(pro.To,"e")==0)
                                        {                                               
                                                temp[len++] = 'e';
                                                temp[len] = '\0';
                                                break;
                                        }
                                        else
                                        {
                                                count = strlen(pro.To);
                                                for (k=0;k<count;k++)
                                                {
                                                        protemp[0] = pro.To[k];
                                                        protemp[1] = '\0';
                                                        strcpy(protemp,First(protemp));
                                                        for (i=0;protemp[i]!='\0';i++)
                                                        {
                                                                if (!IsInString(temp,protemp[i]))
                                                                {
                                                                        temp[len++] = protemp[i];
                                                                        temp[len] = '\0';
                                                                }                                               
                                                        }
                                                        if (!IsInString(temp, 'e'))
                                                        {
                                                                break;
                                                        }
                                                }       
                                                if (k==count)
                                                {
                                                        if (!IsInString(protemp,'e'))
                                                        {
                                                                temp[len++] = 'e';
                                                                temp[len] = '\0';
                                                        }
                                                }
                                        }
                                }
                        }
                }
                else
                {
                        temp[len++] = ch[0];
                        temp[len] = '\0';
                }
        }
        else
        {
                count = strlen(ch);
                for (i=0;i<count;i++)
                {
                        protemp[0] = ch[i];
                        protemp[1] = '\0';
                        strcpy(protemp,First(protemp));
                        for (i=0;protemp[i]!='\0';i++)
                        {
                                if (!IsInString(temp,protemp[i]))
                                {
                                        temp[len++] = protemp[i];
                                        temp[len] = '\0';
                                }                                               
                        }
                        if (!IsInString(temp, 'e'))
                        {
                                break;
                        }
                }       
                if (k==count)
                {
                        if (!IsInString(protemp,'e'))
                        {
                                temp[len++] = 'e';
                                temp[len] = '\0';
                        }
                }
        }
        len = strlen(temp);
        for (i=0;i<len;i++)
        {
                for (j=i+1;j<len;j++)
                {
                        if (temp[i] == temp[j])
                        {
                                temp[j] = temp[len-1];
                                temp[len-1] = '\0';
                                len--;
                        }
                }
        }
        return temp;
}
//求出FOLLOW 集合
char * Parse::Follow(char ch)
{
        int count=0,len=0;
        int i=0,j=0,k=0;
        bool flag = false;
        char *protemp = new char[30];
        char *temp = new char[30];
        strcpy(protemp,"\0");
        strcpy(temp,"\0");
        Production pro;
        if (ch == gra->GetstartState())
        {
                temp[len++] = '$';
                temp[len] = '\0';
        }
        for (j=0;j<(gra->GetNumOfGra());j++)
        {
                pro = gra->GetGrammar(j);
                if (IsInString(pro.To,ch))
                {
                        flag = false;
                        for (j=0;pro.To[j]!='\0';j++)
                        {
                                if (ch == pro.To[j])
                                {
                                        flag = true;
                                }
                                if (flag)
                                {
                                        count = 0;
                                        for (k=j+1;k<(int)strlen(pro.To);k++)
                                        {
                                                protemp[count++] = pro.To[k];
                                        }
                                        protemp[count] = '\0';
                                        if (strlen(protemp)==0)
                                        {
                                                temp[len++] = 'e';
                                                temp[len] = '\0';
                                        }
                                        //把后面的 First 集合附给前面的Follow集合
                                        strcat(temp,First(protemp));
                                        len = strlen(temp);
                                        for (k=0;k<len;k++)
                                        {
                                                if (temp[k]=='e')
                                                {
                                                        temp[k] = temp[len-1];
                                                        temp[len-1] = '\0';
                                                        len--;
                                                        break;
                                                }
                                        }
                                        if (IsInString(First(protemp),'e')&&(pro.From!=ch))
                                        {
                                                strcat(temp,Follow(pro.From));
                                        }
                                        flag = false;
                                }
                        }
                }
        }
        len = strlen(temp);
        for (i=0;i<len-1;i++)
        {
                for (j=i+1;j<len;j++)
                {
                        if (temp[i] == temp[j])
                        {
                                temp[j] = temp[len-1];
                                temp[len-1] = '\0';
                                len--;
                        }
                }
        }
        return temp;
}
//获取ch 在数组中的位置
int Parse::GetPos(char * str,char ch)
{
        int len = strlen(str);
        for (int i=0;i<len;i++)
        {
                if (ch == str[i])
                        break;
        }
        return i;
}
//获取ch 在数组中的位置
int Parse::GetPos(char ch)
{
        for (int i=0;i<NumOfNonTeminal;i++)
        {
                if (ch == ff[i].ch)
                        break;
        }