text2.cpp

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

#include <iostream.h>
#include <stdio.h>
#include <string.h>
#include <conio.h>
#include <stdlib.h>
#include <ctype.h>

//定义结点类
template <class Elem> class link
{
        public:
                link* next;
                Elem element;
                int sign;
                link(const Elem& elementValue,link* nextValue = NULL)
                {
                        element = elementValue;
                        next = nextValue;
                        sign = -1;
                }
                link(link* nextValue = NUll)
                {
                        next = nextValue;
                        sign = -1;
                }
};
//定义堆栈类
template <class Elem> class stack
{
        private:
                link<Elem> *top;
                int size;
        public:
                stack(int sz = DefaultSize)
                {
                        top = NULL;
                        size = 0;
                }
                ~stack(){        clear();        }
                void clear()
                {
                        while(top!=NULL)
                        {
                                link<Elem>* temp = top;
                                top = top->next;
                                size = 0;
                                delete temp;
                        }
                }
                //入栈函数
                bool push(const Elem& item)
                {
                        top = new link<Elem>(item,top);
                        size++;
                        return true;
                }
                //出栈函数
                Elem pop()
                {
                        Elem item;
                        if (size == 0)
                                return false;
                        item = top->element;
                        link<Elem>* temp = top->next;
                        delete top;
                        top = temp;
                        size--;
                        return item;
                }
                //获取栈顶元素的值
                Elem GetTop() const
                {
                        Elem item;
                        if(size == 0)
                                return false;
                        item = top->element;
                        return item;
                }
                //获取堆栈的深度
                int length() const         {        return size;        }
                //判断栈是否为空
                bool IsEmpty() const         {        return top == NULL;        }
                //设置标志位
                void SetSign(int s)                {        top->sign = s;        }
                //获取标志位
                int GetSign() const                {        return top->sign;  }
};
//////////////////////////////////
//定义产生式的数据结构
class Production
{
public:
        char From;
        char To[120];
};
//////////////////////////////////
//定义保存first和follow的数据结构
class FirstFollow
{
public:
        char ch;
        char first[30];
        char follow[30];
};
//////////////////////////////////
//定义输入文法数据结构
class Grammar
{
private:
        char startState;
        Production pro[30];
        int NumOfGra;
public:
        Grammar()
        {
                NumOfGra = 0;
        }
        ~Grammar()
        {
        }
        //插入一条文法
        bool Insert(char fr,char * temp)
        {
                NumOfGra++;
                pro[NumOfGra-1].From = fr;
                strcpy(pro[NumOfGra-1].To,temp);
                return true;
        }
        //插入一条文法
        bool Insert(int pos,char fr,char *temp)
        {
                for(int i=NumOfGra;i>pos;i++)
                {
                        pro[i] = pro[i-1];
                }
                pro[pos].From = fr;
                strcpy(pro[pos].To,temp);
                NumOfGra++;
                return true;
        }
        //设置和获取开始状态
        bool SetStartState(char ch)
        {
                startState = ch;
                return true;
        }
        char GetstartState()
        {
                return startState;
        }
        //删除一条文法
        bool Delete(char fr,char * temp)
        {
                for (int i=0;i<NumOfGra;i++)
                {
                        if ((pro[i].From == fr)&&(strcmp(pro[i].To,temp)==0))
                        {
                                pro[i] = pro[NumOfGra-1];
                                NumOfGra--;
                        }
                }
                return true;
        }
        //删除一个文法
        bool Delete(int pos)
        {
                pro[pos] = pro[NumOfGra-1];
                NumOfGra--;
                return true;
        }
        //获取文法的条数
        int GetNumOfGra()
        {
                return NumOfGra;
        }
        //获取一条文法
        Production GetGrammar(int pos)
        {
                return pro[pos];
        }
};
//////////////////////////////////
//文法分析表的数据结构
class ParseTable
{
private:
        int row;
        int col;
        char InputSymbol[20];
        char NonTerminal[20];
        Production ** table;
public:
        //构造函数
        ParseTable(char * in,char * Non)
        {
                row = strlen(Non);
                col = strlen(in);
                strcpy(InputSymbol,in);
                strcpy(NonTerminal,Non);
                table = (Production **)(new Production * [row]);
                for (int i=0; i<row; i++)
                {
                        table[i] = new Production[col];
                }
                for (i=0;i<row;i++)
                {
                        for (int j=0;j<col;j++)
                        {
                                table[i][j].From = '\0';
                                strcpy(table[i][j].To,"\0");
                        }
                }
        }
        ~ParseTable()
        {
                delete table;
        }
        //添加一个产生式
        bool Add(char ch,Production pro)
        {
                for (int i=0;i<row;i++)
                {
                        if (NonTerminal[i] == pro.From)
                        {
                                for (int j=0;j<col;j++)
                                {
                                        if (InputSymbol[j] == ch)
                                        {
                                                if (table[i][j].From != '\0')
                                                {
                                                        return false;
                                                }
                                                else
                                                {
                                                        table[i][j] = pro;
                                                        return true;
                                                }
                                        }
                                }
                        }
                }
                if (i==row)
                {
                        return false;
                }
                return true;
        }
        //获取一个表达式
        Production GetProduction(char from,char terminal)
        {
                int i,j;
                for (i=0;i<row;i++)
                {
                        if (NonTerminal[i] == from)
                        {
                                for (j=0;j<col;j++)
                                {
                                        if (InputSymbol[j] == terminal)
                                        {
                                                if (table[i][j].From!='\0')
                                                {
                                                        return table[i][j];
                                                }
                                        }
                                }
                        }
                }
                return table[i][j];
        }
        //看表中是否有产生式
        bool IsEmpty(char from,char terminal)
        {
                for (int i=0;i<row;i++)
                {
                        if (from == NonTerminal[i])
                        {
                                for (int j=0;j<col;j++)
                                {
                                        if (InputSymbol[j] == terminal)
                                        {
                                                if (table[i][j].From == '\0')
                                                        return true;
                                                else
                                                        return false;
                                        }
                                }
                        }
                }               
                return false;
        }
        //输出分析表
        void OutPut()
        {
                int i, j;
                int len1;
                len1 = strlen(InputSymbol);
                cout << "\n LL1文法的预测分析表如下：" << endl;
                cout<<"\n ━━━┯";
                for (i=0;i<len1;i++)
                {
                        cout<<"━━━━━";
                }
                cout<<"\n   非终│                输入字符 ";
                cout<<"\n       ┝";               
                for (i=0;i<len1;i++)
                {
                        cout<<"━━━━━";
                }
                cout<<"\n   结符│";
                for (i=0;i<col;i++)
                {
                        cout<<"  "<<InputSymbol[i]<<"   \t";
                }
                cout<<"\n ━━━┿";               
                for (i=0;i<len1;i++)
                {
                        cout<<"━━━━━";
                }
                for (i=0;i<row;i++)
                {
                        cout<<"\n   "<<NonTerminal[i]<<"   │";
                        for (j=0;j<col;j++)
                        {
                                if (!IsEmpty(NonTerminal[i],InputSymbol[j]))
                                {
                                        cout<<table[i][j].From<<"→"<<table[i][j].To<<"\t";
                                }
                                else
                                {
                                        cout<<"  --\t";
                                }
                        }
                }
                cout<<"\n ━━━┷";               
                for (i=0;i<len1;i++)
                {
                        cout<<"━━━━━";
                }
        }
};
//////////////////////////////////
// 建立文法分析表类
class Parse
{
private:
        Grammar * gra;
        ParseTable * pt;
        FirstFollow * ff;
        int NumOfGrammar;
        int NumOfTeminal;
        int NumOfNonTeminal;