编译原理实验(2018)

实验1与实验2

Posted by viewsetting on November 12, 2018

实验内容

词法分析器

中型模拟

整数 $[1-9]^{\ast}[0-9]^{\ast}$

浮点 $([1-9]^{+}[0-9]^{\ast}\space \vert \space [0-9]^{+}).[0-9]^{+}$

变量 $[symbol]^{+}([0-9]\space \vert \space [symbol])^*$

所用数据结构
struct rec
{
    string typ;
    string str;
    int line;
    rec(string a,string b,int c)
    {
        str=a;
        typ=b;
        line=c;
    }
};
int line_counter=0;
set<string> id= {"int","float","double","char","return","main","std","include"};
set<char> sym= {'+','-','*','/','%','=','#','!','|','{','}','(',')','&','^'};
bool flag_first=1;
char previous=0;
vector<rec> stk;
自定义函数集
bool check_num(string num)
{
    for(auto &it: num)
    {
        if(it<'0'||it>'9')
            return 0;
    }
    return 1;
}

bool is_id(string id_new)
{
    if(id.count(id_new)!=0)
        return 1;
    else
        return 0;
}
bool is_sym(char id_new)
{
    if(sym.count(id_new)!=0)
        return 1;
    else
        return 0;
}
输入与分词
 while(getline(std::cin,line_str))
    {
        line_counter++;
        string buf="";
        for(int i=0; i<line_str.size(); i++)
        {
            if(!(line_str[i]>='0'&&line_str[i]<='9')&&isalpha(line_str[i])==0&&line_str[i]!='.')
            {
                if(buf=="")
                {
                    if(is_sym(line_str[i]))
                    {
                        buf+=line_str[i];
                    }

                    else
                    continue;
                }
                else if (line_str[i]==' ')
                {
                    check(buf);
                    buf="";
                }
                else
                {

                    if(line_str[i]=='.')
                    {
                        if(check_num(buf))
                        {
                            buf+=".";
                            continue;
                        }
                        else
                        {
                            {
                                check(buf);
                                buf="";
                            }

                        }
                    }
                    else
                    {
                        if(is_sym(line_str[i]))
                        {
                            if(is_sym(line_str[i-1]))
                                buf+=line_str[i];
                            else
                            {
                                check(buf);
                                buf=line_str[i];
                            }
                        }
                        else
                        {
                            check(buf);
                            buf="";
                        }

                    }

                }

                //buf="";
            }
            else
            {
                if(is_sym(buf[buf.size()-1])&&isalpha(line_str[i])!=0&&(line_str[i]>='0'&&line_str[i]<='9'))
                {                  
                    check(buf);
                    buf="";
                }
                buf+=line_str[i];
            }
        }
    }
   
检验正则式函数
void check(string buf)
{
    if(buf.size()==1)
    {
        if(is_sym(buf[0]))
        {
            stk.push_back(rec(buf,"Symbol",line_counter));
        }
        else if(buf[0]>='0'&&buf[0]<='9')
        {
            stk.push_back(rec(buf,"Int",line_counter));
        }
        else if(isalpha(buf[0])!=0)
        {
            stk.push_back(rec(buf,"Name",line_counter));
        }
        else
        {
            stk.push_back(rec(buf,"Invalid Name",line_counter));
        }
    }
    else if(check_num(buf)||std::count(buf.begin(),buf.end(),'.')==1)
    {
        if(std::count(buf.begin(),buf.end(),'.')==1)
        {
            if(buf[buf.size()-1]!='.')
                stk.push_back(rec(buf,"Float",line_counter));
            else
                stk.push_back(rec(buf,"Invalid Name",line_counter));
        }
        else if(check_num(buf))
        stk.push_back(rec(buf,"Int",line_counter));
    }
    else
    {
        if(is_sym(buf[0]))
        {
            stk.push_back(rec(buf,"Symbol",line_counter));
        }
        else if(buf[0]<='9'&&buf[0]>='0')
        {
            stk.push_back(rec(buf,"Invalid Name",line_counter));
        }
        else if(is_id(buf))
        {
            stk.push_back(rec(buf,"Identifier",line_counter));
        }
        else
        {
            stk.push_back(rec(buf,"Name",line_counter));
        }
    }
}

自顶向下的基于递归子程序的语法分析

暴力DFS遍历语法树,在叶子节点时直接字符串判别,相等则return 1; 反之return 0;

所用数据结构
map<char,set<string>> table;
vector<string> vec;
int num;
DFS
bool dfs(string now)
{
    if(now.size()>vec[num].size())
    {
        return 0;
    }

    bool flag=0;
    for(int i=0;i<now.size();i++)
    {
        if(isupper(now[i]))
        {
            for(auto &it : table[now[i]])
            {
                string nxt=now.substr(0,i)+it+now.substr(i+1,now.size()-i-1);
                if(nxt==vec[num]) return 1;
                if(dfs(nxt)) flag=1;
            }
        }
    }
    return flag;

}
处理生成式与建立映射
int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        string ans;
        cin>>ans;
        string tmp="";
        for(int j=3;j<ans.size();j++)
        {
            tmp+=ans[j];
        }
        table[ans[0]].insert(tmp);
    }