syntax.cpp~

LL1通用语法分析器

        
        Pattern p = it->second;
        vector<Token *> tokens = p.getTokens();
        
        for (vector<Token *>::iterator i = tokens.begin(); i != tokens.end(); i++) {
            (*i)->print();
            cout << " ";
        }
    }
    cout << endl;
}


void Syntax::caculateFirstSet()
{
    vector<Variable> vars = getVariables();
    int varNum = vars.size();
    
    TokenSetMap  firstSets;
    vector<vector<Pattern> > patterns;

    for(int i = 0; i < varNum; i++)
        patterns.push_back(getPatterns(vars[i]));

    bool increase = true;
    while(increase){
        for(int i = 0; i < varNum; i++){
            TokenSet &setI = firstSets[vars[i]];
            int oldSize = setI.size();
            
            for(int j = 0; j < patterns[i].size(); j++){
                bool cont = true;
                for(int k = 0; k < patterns[i][j].length() && cont; k++){

                    Token *p = patterns[i][j].at(k);
                    
                    switch(p->getType()){
                        case TERMINAL:
                        case EPSILON:
                            setI.insert(p);
                            cont = false;
                            break;
                            
                        case VARIABLE:
                            TokenSet newSet;
                            Variable v = *dynamic_cast<Variable *>(p);
                            set_union(setI.begin(), setI.end(), firstSets[v].begin(), firstSets[v].end(),
                                      insert_iterator<TokenSet>(newSet, newSet.begin()), TokenCompare());
                            
                            Epsilon e;
                            if(firstSets[v].count(&e) != 0){
                                //产生式右部不全是变元，且原来的first集合没有epsilon, 则epsilon不在新的FIRST集合中。
                                if(setI.count(&e) == 0 && k != patterns[i][j].length() - 1){
                                    setI = newSet;
                                    setI.erase(&e);
                                } else { //新的FIRST集合中含有epsilon
                                    setI = newSet;
                                }
                            } else {
                                setI = newSet;
                                cont = false; //不会遇到产生epsilon的变元。
                            }
                            break;
                    }
                }
            }
            //如果迭代集合发生变化
            increase = (setI.size() > oldSize);
        }
    }
    
    FIRSTSet = TokenSets(varNum);
    for(int i = 0; i < varNum; i++){
        TokenSet &setI = firstSets[vars[i]];
        
#ifdef DEBUG
        cout << "FIRST(" << vars[i].getName() << ") =\t{ ";
#endif
        for(TokenSet::const_iterator it = setI.begin(); it != setI.end(); it++){
            FIRSTSet[i].insert((*it)->clone());
        }
#ifdef DEBUG
        printTokenSet(setI);
        cout << " } " << endl;
#endif
    }
}


void Syntax::caculateFollowSet()
{
    std::vector<Variable> &vars = allVars;
    
    TokenSets &firstSets = FIRSTSet;

    map<Variable, TokenSet> firstSetMap;
    vector<vector<Pattern> > patterns;

    
    int varNum = vars.size();
    for(int i = 0; i < varNum; i++){
        patterns.push_back(getPatterns(vars[i]));
        firstSetMap[vars[i]] = firstSets[i];
    }

    map<Variable, TokenSet> followSetMap;
    
    //将#加入起始变元的FOLLOW集合中。
    followSetMap[startVariable].insert(new Terminal("$"));
    
    Epsilon e;
    bool increase = true;
    while(increase){
        increase = false;
        
        for(int i = 0; i < varNum; i++){
            for(int j = 0; j < patterns[i].size(); j++){
                
                for(int k = 0; k < patterns[i][j].length(); k++){
                    if(patterns[i][j].at(k)->getType() == VARIABLE){
                        
                        bool cont = true;
                        Variable v = *dynamic_cast<Variable *>(patterns[i][j].at(k));
                        int oldSize = followSetMap[v].size();
                        
                        bool behindGenerateE = (k == patterns[i][j].length() - 1);
                        
                        for(int l = k + 1; l < patterns[i][j].length() && cont; l++){
                            if(patterns[i][j].at(l)->getType() == VARIABLE){
                                TokenSet newSet;
                                
                                Variable vl = *dynamic_cast<Variable *>(patterns[i][j].at(l));
                                set_union(followSetMap[v].begin(), followSetMap[v].end(), 
                                          firstSetMap[vl].begin(), firstSetMap[vl].end(),
                                          insert_iterator<TokenSet>(newSet, newSet.begin()));
                                if(newSet.count(&e) != 0){
                                    newSet.erase(&e);            
                                    followSetMap[v] = newSet;
                                    if(l == patterns[i][j].length() - 1){ //将产生式左边的变元的FOLLOW集合合并到集合里。
                                        behindGenerateE = true;
                                    }
                                } else {
                                    followSetMap[v] = newSet;
                                    cont = false;
                                }
                            } else if(patterns[i][j].at(l)->getType() == TERMINAL){ //变元后面是一个终结符
                                followSetMap[v].insert(patterns[i][j].at(l));
                                cont = false;
                            }
                        }
                        
                        // 如果变元v产生式后面剩余部分为空或者能生成epsilon，将产生式前面的变元vars[i]
                        // 的FOLLOW集合变元V的FOLLOW集合上
                        if(behindGenerateE){ 
                            TokenSet newSet;
                            set_union(followSetMap[v].begin(), followSetMap[v].end(), 
                                      followSetMap[vars[i]].begin(), followSetMap[vars[i]].end(),
                                      insert_iterator<TokenSet>(newSet, newSet.begin()));
                            followSetMap[v] = newSet;
                        }

                        if(followSetMap[v].size() > oldSize){
                            increase = true;
                        }
                    }
                }
            }
        }
    }

    FOLLOWSet = TokenSets(varNum);
    for(int i = 0; i < varNum; i++){
#ifdef DEBUG
        cout << "FOLLOW (" << vars[i].getName() << ") =\t{ ";
#endif
        TokenSet &setI = followSetMap[vars[i]];
        for(TokenSet::const_iterator it = setI.begin(); it != setI.end(); it++){
            FOLLOWSet[i].insert((*it)->clone());
        }
        
#ifdef DEBUG
        printTokenSet(setI);
        cout << " }" << endl;
#endif
    }
}


void Syntax::caculateVariables()
{
    allVars.resize(0);
    for(ProductionMap::const_iterator it = productions.begin();
        it != productions.end(); it++){
        if(allVars.empty() || !(it->first == allVars.back()))
            allVars.push_back(it->first);
    }
}


/**
 * @return AnalyzeTable
 */
void Syntax::genLL1AnalyzeTable (AnalyzeTable & table)
{
    Epsilon e;
    vector<Pattern> patterns;
    
#ifdef DEBUG
    cout << "\n句式的FIRST集合: \n";
#endif 
    int varNum = allVars.size();
    for(int i = 0; i < varNum; i++){
        patterns = getPatterns(allVars[i]);
        TokenSet first;
        bool hasEpsilon = false;
        
        for(int j = 0; j < patterns.size(); j++){
            getFirst(patterns[j], first);
            
#ifdef DEBUG
            cout << "FIRST(";
            patterns[j].print();
            cout << ") = { ";
            printTokenSet(first);
            cout << " } \n";
#endif 
            if(first.count(&e) != 0){
                if(!hasEpsilon){
                    hasEpsilon = true;
                } else{
                    cerr << "Warning : 此文法不是LL(1)文法，存在两条产生式，都生成Epsilon" << endl;
                }
            }

            for(TokenSet::const_iterator it = first.begin(); it != first.end(); it++){
                Index idx;
                switch((*it)->getType()){
                    case TERMINAL:
                        idx = Index(allVars[i], dynamic_cast<Terminal &>(**it));
                        try{
                            table.addProduction(idx, Production(allVars[i], patterns[j]));
                        } catch (ProductionAlreadyExists &e){
                            cerr << "Warning : 此文法不是LL(1)文法, 分析表冲突" << endl;
                        }
                        
                        break;
                        
                    case EPSILON :
                        for(TokenSet::const_iterator follow = FOLLOWSet[i].begin();
                            follow != FOLLOWSet[i].end(); follow++){
                            if((*follow)->getType() == TERMINAL){
                                Index idx(allVars[i], dynamic_cast<Terminal &>(**follow));
                                try{
                                    table.addProduction(idx, Production(allVars[i], patterns[j]));
                                } catch (ProductionAlreadyExists &e){
                                    cerr << "Warning : 此文法不是LL(1)文法，分析表冲突" << endl;
                                }
                            }
                        }
                }
            }
        }
    }

#ifdef DEBUG
    cout << "\n分析表：\n";
    
    for(int i = 0; i < allVars.size(); i++){
        for(int j = 0; j < allTerms.size(); j++){
            Index idx(allVars[i], allTerms[j]);
            cout << "(" << idx.getVariable().getName() << ", "
                 << idx.getTerminal().getString() << " ) -- ";            
            try{
                table.getProduction(idx).getRhs().print();
            } catch (...){
            }
            cout << endl;
        }
        
        Index idx(allVars[i], Terminal("$"));
        cout << "(" << idx.getVariable().getName() << ", "
             << idx.getTerminal().getString() << " ) -- ";
        try{
            table.getProduction(idx).getRhs().print();
        } catch (...){
        }
        cout << endl;
    }
#endif
}


void Syntax::printLL1AnalyzeTable() const
{
}


void Syntax::grammarError(const string& msg, int lineNum)
{
    cerr << lineNum << ": " << msg;
    exit(1);
}


Syntax::~Syntax()
{
    for(int i = 0; i < allVars.size(); i++){
        for(TokenSet::const_iterator it = FIRSTSet[i].begin(); it != FIRSTSet[i].end(); it++){
            delete *it;
        }
        
        for(TokenSet::const_iterator it = FOLLOWSet[i].begin(); it != FOLLOWSet[i].end(); it++){
            delete *it;
        }
    }
    
    for(int i = 0; i < pool.size(); i++)
        delete pool[i];
}


void Syntax::printTokenSet(const TokenSet& s) const
{
    bool first = true;
    for(TokenSet::const_iterator it = s.begin(); it != s.end(); it++){
        if(first)
            first = false;
        else 
            cout << ", ";
        
        (*it)->print();
    }
}


Variable Syntax::getStartVariable() const
{
    return startVariable;
}