当前位置:网站首页>【编译原理】词法分析设计实现

【编译原理】词法分析设计实现

2022-07-07 21:50:00 RemainsHll

1总体设计

源码地址
在这里插入图片描述

2中缀表达式转后缀表达式

在这里插入图片描述
核心代码

int priority(char ch)
{
    

	if (ch == '*')
	{
    
		return 3;
	}

	if (ch == '&')
	{
    
		return 2;
	}

	if (ch == '|')
	{
    
		return 1;
	}

	if (ch == '(')
	{
    
		return 0;
	}
}

void insert_behind_n(string& s, int n, char ch)
{
    

	s += '#';

	for (int i = s.size() - 1; i > n; i--)
		s[i] = s[i - 1];

	s[n] = ch;
}

void pre_process(string& s)
{
    

	int i = 0, length = s.size()-1;
	while (i < length)
	{
    
		int in_all_1 = 0, in_all_2 = 0;
        //注意转义
        if(operators.count(s[i])==0 && s[i]!='\\'){
    
            in_all_1 = 1;
        }
        if(operators.count(s[i+1])==0 ){
    
            in_all_2 = 1;
        }

		if (in_all_1 || (s[i] == '*') || (s[i] == ')')){
    
            if (in_all_2 || s[i + 1] == '(')
			{
    
				insert_behind_n(s, i + 1, '&');
				length++;
			}
        }
		i++;
	}
}

string infix_Suffix(string s)
{
    

	pre_process(s);	
	string str;				
	stack<char> oper;		

	for (unsigned int i = 0; i < s.size(); i++)
	{
    
		int in_all = 0;
        if(s[i] == '\\'){
    
            str += s[i];
            i++;
            str += s[i];
            operands.insert(s[i]); 
        }
		if(operators.count(s[i])==0){
    
            in_all = 1;
            operands.insert(s[i]);
        }

		if (in_all)	
		{
    
            str += s[i];
		}
		else							
		{
    

			if (s[i] == '(')			
			{
    
				oper.push(s[i]);
			}

			else if (s[i] == ')')	
			{
    

				char ch = oper.top();
				while (ch != '(')		
				{
    
					str += ch;
					oper.pop();
					ch = oper.top();
				}

				oper.pop();				
			}
			else				
			{
    

				if (!oper.empty())		
				{
    

					char ch = oper.top();
					while (priority(ch) >= priority(s[i]))
					{
    

						str += ch;
						oper.pop();

						if (oper.empty())	
						{
    
							break;
						}
						else ch = oper.top();
					}

					oper.push(s[i]);		
				}

				else				
				{
    
					oper.push(s[i]);
				}
			}
		}
	}

	while (!oper.empty())
	{
    

		char ch = oper.top();
		oper.pop();

		str += ch;
	}
    //cout<<str<<endl;
	return str;
}

3后缀表达式转NFA

在这里插入图片描述
在这里插入图片描述
核心代码

//DFA的状态栈,记录起始状态和终结状态
State stateStack[MAX];
int top;
//获取ID
int stateID = 1;
void CFG_NFA(string cfg){
    
    
    stateID = 1;
    top = 0;
    point = 0;
    for (int i=0;i<cfg.length();i++){
    
        State a;
        State b;
        State c;
        switch (cfg[i])
        {
    
        case '&': 
            //从状态栈中取出两个状态,并更新起始和终结状态
            a = stateStack[top--];
            b = stateStack[top--];
            c.begin = b.begin;
            c.end = a.end;
            stateStack[++top] = c;
            //新建一个状态转移,a状态遇到#转移到b,将a和b状态连接起来
            NFA nfa0;
            nfa0.from = b.end;
            nfa0.to = a.begin;
            nfa0.c = '#';
            nfa[point++] = nfa0;
            break;
        case '|':
            //规则2
            c.begin = stateID++;
            c.end = stateID++;
            a = stateStack[top--];
            b = stateStack[top--];
            stateStack[++top] = c;
            
            NFA nfa1;
            nfa1.from = c.begin;
            nfa1.to = a.begin;
            nfa1.c = '#';
            nfa[point++] = nfa1;
            
            NFA nfa2;
            nfa2.from = c.begin;
            nfa2.to = b.begin;
            nfa2.c = '#';
            nfa[point++] = nfa2;

            NFA nfa3;
            nfa3.from = a.end;
            nfa3.to = c.end;
            nfa3.c = '#';
            nfa[point++] = nfa3;

            NFA nfa4;
            nfa4.from = b.end;
            nfa4.to = c.end;
            nfa4.c = '#';
            nfa[point++] = nfa4;
            break;
        case '*':
            //规则3
            c.begin = stateID++;
            c.end = stateID++;
            a = stateStack[top--];
            stateStack[++top] = c;

            NFA nfa5;
            nfa5.from = c.begin;
            nfa5.to = c.end;
            nfa5.c = '#';
            nfa[point++] = nfa5;
            
            NFA nfa6;
            nfa6.from = c.begin;
            nfa6.to = a.begin;
            nfa6.c = '#';
            nfa[point++] = nfa6;

            NFA nfa7;
            nfa7.from = a.end;
            nfa7.to = a.begin;
            nfa7.c = '#';
            nfa[point++] = nfa7;

            NFA nfa8;
            nfa8.from = a.end;
            nfa8.to = c.end;
            nfa8.c = '#';
            nfa[point++] = nfa8;
            break;
        case '\\':
            //遇到转义字符
            i++;
            c.begin = stateID++;
            c.end = stateID++;
            stateStack[++top] = c;

            NFA nfa10;
            nfa10.from = c.begin;
            nfa10.to = c.end;
            nfa10.c = cfg[i];
            nfa[point++] = nfa10;
            break;
        default:
            //遇到操作数
            c.begin = stateID++;
            c.end = stateID++;
            stateStack[++top] = c;

            NFA nfa9;
            nfa9.from = c.begin;
            nfa9.to = c.end;
            nfa9.c = cfg[i];
            nfa[point++] = nfa9;
            break;
        }
    }
    //输出NFA
    // for(int i=0;i<point;i++){
    
    // cout<<nfa[i].from<<" "<<nfa[i].c<<" "<<nfa[i].to<<endl;
    // }
}

4NFA转DFA

在这里插入图片描述
核心代码

set<int> empty_transfer(int id){
    
    set<int> set1;
    set<int> set2;
    set1.insert(id);
    //遍历NFA,将到达的状态集合加入set1和set2
    for(int i=0;i<point;i++){
    
        if(nfa[i].from==id && nfa[i].c == '#'){
    
            set1.insert(nfa[i].to);
            set2.insert(nfa[i].to);
        } 
    }
    //遍历上述得到的set2,继续求空转移,直到set2为空,得到的set1就是状态的空转移
    while(!set2.empty()){
    
        int temp = *set2.begin();
        set2.erase(set2.begin());
        for(int i=0;i<point;i++){
    
            if(nfa[i].from==temp && nfa[i].c == '#'){
    
                set2.insert(nfa[i].to);
                set1.insert(nfa[i].to);
            } 
        }
    }
    return set1;
}

set<int> empty_move(int id,char c){
    
    //先求move(c)
	set<int> set1;
    for(int i=0;i<point;i++){
    
        if(nfa[i].from==id && nfa[i].c == c){
    
            set1.insert(nfa[i].to);
        } 
    }
    //得到move之后求空转移
    set<int> set2;
    set2.insert(set1.begin(),set1.end());
    set<int>::iterator it1;
    for (it1 = set1.begin(); it1 != set1.end(); it1++){
    
        set<int> set3 = empty_transfer(*it1);
        set2.insert(set3.begin(),set3.end());
    }
    return set2;
}

void NFA_DFA(){
    

	DFA* dfa = new DFA();
	
    //获取开始状态和终结状态
    State ss = stateStack[top];
    int begin = ss.begin;
    int end = ss.end;
    //初始状态的空转移
    set<int> initial = empty_transfer(begin);
    //状态集合
    set< set<int> > states;
    set< set<int> > states_temp;
    states.insert(initial);
    //重命名DFA
    dfa->dfa_id[initial] = ++dfa->id;
    //遍历状态集合
    while(!states.empty()){
    
        set<int> temp = *states.begin();
        states.erase(states.begin());
        set<int>::iterator it1;
        set<char>::iterator it2;
        //遍历操作数求closeuure(move)
        for (it2 = operands.begin(); it2 != operands.end(); it2++){
    
            set<int> new_set;
            for (it1 = temp.begin(); it1 != temp.end(); it1++){
    
                set<int> set_temp = empty_move(*it1,*it2);
                new_set.insert(set_temp.begin(),set_temp.end());
            }
            if(states_temp.count(new_set) == 0 && !new_set.empty()){
    
               
                states.insert(new_set);
                states_temp.insert(new_set);
                dfa->dfa_id[new_set] = ++dfa->id;
            }
			//cout<<dfa->dfa_id[temp]<<" "<<*it2<<" "<<dfa->dfa_id[new_set]<<endl;
            dfa->tran[dfa->dfa_id[temp]][*it2-33] = dfa->dfa_id[new_set];
            if(new_set.count(end)){
    
                dfa->vn[dfa->dfa_id[new_set]] = true;
            }else{
    
                dfa->vn[dfa->dfa_id[new_set]] = false;
            }
        }
    }
	dfas[point_dfa++] = dfa;
}

5最小化DFA

在这里插入图片描述
核心代码

void minimize_DFA(){
    
    set<set<int> > sets;
    DFA* dfa = dfas[point_dfa-1];
    //初始化:初态和终态区分
    int len = dfa->id;
    set<int> set1,set2;
    for(int i=1;i<=len;i++){
    
        if(dfa->vn[i]){
    
            set1.insert(i);
        }else{
    
            set2.insert(i);
        }
    }
    sets.insert(set1);
    sets.insert(set2);

    set<set<int> > begin_set;
    do{
    
        begin_set = sets;
        set<set<int> >::iterator it1;
        set<int> temp;
        //遍历状态集合
        for (it1 = begin_set.begin(); it1 != begin_set.end(); it1++){
    
            temp= *it1;
            set<char>::iterator it2;
            //遍历操作数
            for(it2 = operands.begin();it2 != operands.end();it2++){
    
                map<set<int>,set<int> > map_set;
                set<int>::iterator it3;
                for(it3 = temp.begin();it3 != temp.end();it3++){
    
                    int d = dfa->tran[*it3][*it2-33];
                    //判断属于哪个集合
                    //cout<<*it3<<" "<<*it2<<" "<<d<<endl;
                    set<set<int> >::iterator it4;
                    int flag = 0;
                    set<int>temp2,temp3;
                    for(it4 = begin_set.begin();it4 != begin_set.end();it4++){
    
                        temp2 = *it4;
                        if(temp2.count(d)>0){
    
                            temp3 = map_set[temp2];
                            flag = 1;
                        }
                    }
                    //如果状态产生了新的状态集合, 即可以分割,将原来的状态删除,状态集合存入到map中。
                    if(flag == 1){
    
                        sets.erase(temp);
                        temp3.insert(*it3);
                        map_set[temp2] = temp3;
                    }
                }
                //将map中的集合插入到原集合中
                map<set<int>,set<int> >::iterator it5;
                for(it5 = map_set.begin();it5 != map_set.end();it5++){
    
                    sets.insert(it5->second);
                }
                
            }
        }
        
    }while(begin_set != sets);
    //将最小化的DFA重命名。
    DFA* min_dfa = new DFA();
    set<set<int> >::iterator it6;
    set<set<int> > sets_temp;
    //遍历最小化DFA得到的集合
    for(it6 = sets.begin();it6 != sets.end();it6++){
    

        set<int> t_set = *it6;
        set<char>::iterator it7;
        int f = *t_set.begin();
        int id=0,to=0;
        //新建DFA状态
        if(sets_temp.count(t_set) == 0){
    
            sets_temp.insert(t_set);
            min_dfa->dfa_id[t_set] = ++min_dfa->id;  
        }
        id = min_dfa->dfa_id[t_set];
        //编译操作符,得到状态转移矩阵和终结符数组
        for(it7 = operands.begin();it7 != operands.end();it7++){
    
            to = 0;
            int d = dfa->tran[f][*it7 -33];
            set<set<int> >::iterator it8;
            for(it8 = sets.begin();it8 != sets.end();it8++){
    
                set<int> t_set2 = *it8;
                if(t_set2.count(d)>0){
    
                    if(sets_temp.count(t_set2) == 0){
    
                        min_dfa->dfa_id[t_set2] = ++min_dfa->id;
                        sets_temp.insert(t_set2);
                    }
                    to = min_dfa->dfa_id[t_set2];
                    if(min_dfa->vn[d]){
    
                        min_dfa->vn[to] = true;
                    }
                }
            }
            min_dfa->tran[id][*it7-33] = d;
        }
    }

    dfas[point_dfa] = min_dfa;
}

6识别单词

在这里插入图片描述
核心代码

int distinguish(string s){
    
   for(int i = 0;i<point_dfa;i++){
    
        int cur = 1,flag = 1;
        DFA* dfa  = dfas[i];
        int to = 0;
        //一直转移,知道单词结束
		for(int j = 0;j<s.length();j++){
    
			to = dfa->tran[cur][s[j]-33];
			if(to == 0){
    
				flag = 0;
			}else{
    
				cur = to;
			}
		}
        //如果单词能完成全部状态转移,并且转移到的状态为终态,将DFA的id返回。
		if(flag ==1 && dfa->vn[to]){
    
			return i;
		}
   }
   return -1;
}

7测试结果

在这里插入图片描述

原网站

版权声明
本文为[RemainsHll]所创,转载请带上原文链接,感谢
https://blog.csdn.net/weixin_47402684/article/details/125344752