syntax.cpp

LL1通用语法分析器

/************************************************************************
                        Copyright IBMTC Written by Xinxi Wang
**************************************************************************/
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cctype>
#include <cassert>
#include "Syntax.h"

using namespace std;


/**
 * @brief 求变元var的FIRST集合
 * @return var的FIRST集合
 * @param  var
 */ 
void Syntax::getFirst (const Variable& var, TokenSet& s ) const
{
    s.clear();
    
    for(int i = 0; i < allVars.size(); i++){
        if(allVars[i] == var){
            s =  FIRSTSet[i];            
            break;
        }
    }
}


/**
 * @brief 求句型pattern的FIRST集合
 * @return pattern的FIRST集合
 * @param  pattern
 */
void Syntax::getFirst (const Pattern& pattern, TokenSet& s )
{
    Epsilon e;
    s.clear();
    
    for(int i = 0; i < pattern.length(); i++){
        Token *p;
        switch(pattern.at(i)->getType()){
            case TERMINAL:
                p = pattern.at(i)->clone();
                pool.push_back(p);
                s.insert(p);
                return;
                
            case VARIABLE:
            {
                
                TokenSet newSet;
                TokenSet firstV;
                getFirst(dynamic_cast<Variable &>(*pattern.at(i)), firstV);
                bool hasEpsilon = (firstV.count(&e) > 0);
                if(i != pattern.length() - 1)
                    firstV.erase(&e);

                set_union(s.begin(), s.end(),
                          firstV.begin(), firstV.end(),
                          insert_iterator<TokenSet>(newSet, newSet.begin()));
                s = newSet;
                
                if(!hasEpsilon)
                    return;
            }
            
            case EPSILON:
                if(i == pattern.length() - 1){
                    Token *p = e.clone();
                    pool.push_back(p);
                    s.insert(p);
                }
                break;
        }
    }
}


/**
 * @brief 求var的FOLLOW集合
 */
void Syntax::getFollow (const Variable& var, TokenSet& s) const
{
    for(int i = 0; i < allVars.size(); i++){
        if(allVars[i] == var){
            TokenSet s =  FOLLOWSet[i];
            break;
        }
    }
}


/**
 * @brief 削除左递归
 */
void Syntax::DeleteLeftRecursion ( )
{
    vector<Variable> &vars = allVars;
    vector<vector<Pattern> > patterns;


    for(int i = 0; i < vars.size(); i++)
        patterns.push_back(getPatterns(vars[i]));
    
    vector<vector<Pattern> > newPatterns(vars.size());
    vector<vector<Pattern> > withoutRecursion;
    vector<Variable> newVars;
    
    for(int i = 0; i < vars.size(); i++){
        vector<Pattern> & pi = patterns[i]; // 所有第i个变元的产生式
        
        //消除间接左递归
        for(int k = 0; k < pi.size(); k++){ //对第i个变元的第k条产生式进行替换
            bool changed = false;
            
            for(int j = 0; j < i; j++){
                // A[i] -> A[j]beta 产生式，用 A[j]的所有产生式，替换所有的A[i]的产生式
                if(*pi[k].at(0) == vars[j]){
                    vector<Pattern> & pj = patterns[j]; // 所有第j个变元的产生式
                    Pattern tmp = pi[k];
                    tmp.deleteTokens(0, 1);
                    
                    for(int l = 0; l < pj.size(); l++){
                        Pattern newPattern(tmp);
                        newPattern.insertPattern(pj[l], 0);
                        newPatterns[i].push_back(newPattern);
                    }
                    changed = true;
                }
            }
            if(!changed)
                newPatterns[i].push_back(pi[k]);
        }
                //消除直接左递归
        bool noRecursion = true;
        
        for(int k = 0; k  < newPatterns[i].size(); k++){
            if(vars[i] == *newPatterns[i][k].at(0)){
                noRecursion = false;
                break;
            }
        }
        
        
        if(noRecursion){
            withoutRecursion.push_back(newPatterns[i]);
            newVars.push_back(vars[i]);
        }
        else {
            vector<Pattern> patternsA;
            vector<Pattern> patternsA1;
            Variable A1(vars[i].getName() + "1");
            
            for(int k = 0; k  < newPatterns[i].size(); k++){
                Pattern &p = newPatterns[i][k];
                
                if(vars[i] == *p.at(0)){ //Aalpha
                    p.deleteTokens(0, 1);
                    p.insertToken(A1.clone());
                    patternsA1.push_back(p);
                } else { //beta
                    p.insertToken(A1.clone());
                    patternsA.push_back(p);
                }
            }
            patternsA1.push_back(Pattern(new Epsilon()));
            
            newVars.push_back(vars[i]);
            newVars.push_back(A1);
            withoutRecursion.push_back(patternsA);
            withoutRecursion.push_back(patternsA1);
        }
    }
    
    // 更新文法
    productions.clear();
    for(int i = 0; i < newVars.size(); i++){
        for(int j = 0; j < withoutRecursion[i].size(); j++){
            productions.insert(make_pair(Variable(newVars[i]),
                                         Pattern(withoutRecursion[i][j])));
        }
    }
}


/**
 * @brief 获取所有的产生式
 */
vector<Production> Syntax::getProductions ( ) const
{
    
}


/**
 * @brief 返回变元var的所有产生式右部
 */
vector<Pattern> Syntax::getPatterns (const Variable& var) const
{
    vector<Pattern> patterns;
    
    pair<ProductionMap::const_iterator, ProductionMap::const_iterator> range;
    range = productions.equal_range(var);
    
    while(range.first != range.second){
        patterns.push_back(range.first->second);
        range.first++;
    }

    return patterns;
}


/**
 * @brief 返回所有的变元
 */
vector<Variable> Syntax::getVariables () const
{
    return allVars;
}


/**
 * @brief 返回所有终结符
 */
vector<Terminal> Syntax::getTerminals () const
{
    return allTerms;
}


/**
 * @brief 解析文法
 * @param in 输入流
 * @param  in
 */
void Syntax::parse (istream& in )
{
    int lineNum = 0;
    bool first = true;
    string line;

    while (getline(in, line)) {
        lineNum++;
        line += " |";
        
        istringstream ss(line);
        string var;
        
        ss >> var;
        if(!Variable::isVariable(var))
            grammarError("invalid variable name", lineNum);

        if(first){
            startVariable = var;
            first = false;
        }
        
        string def;
        ss >> def;
        if(def != "::=")
            grammarError("invalid define symbol", lineNum);
        
        vector<Token*> tokens;
        string token;
        while(ss >> token){

            if(token == "|") {
                
                productions.insert(make_pair(Variable(var), Pattern(tokens)));
                
                tokens.resize(0);
                continue;
            }
            
            if(Variable::isVariable(token)){
                tokens.push_back(new Variable(token));
            } else if(Epsilon::isEpsilon(token)){
                tokens.push_back(new Epsilon());
            } else if(Terminal::isTerminal(token)){
                tokens.push_back(new Terminal(token));
                if(find(allTerms.begin(), allTerms.end(), 
                        Terminal(token)) == allTerms.end())

                    allTerms.push_back(Terminal(token));
            }
        }
    }
    
    caculateVariables();
#ifdef DEBUG
    cout << "原始文法：\n";
    printGrammar();
#endif

    DeleteLeftRecursion();

#ifdef DEBUG
    cout << "\n删除左递归后的文法：\n";
    printGrammar();
#endif 

    caculateVariables();

#ifdef DEBUG
    cout << "\nFIRST集合：\n";
#endif 

    caculateFirstSet();
#ifdef DEBUG
    cout << "\nFOLLOW集合：\n";
#endif

    caculateFollowSet();
}


/**
 * @brief 打印文法
 */
void Syntax::printGrammar()
{
    Variable last;
    bool firstLine = true;
    
    for (ProductionMap::iterator it = productions.begin(); 
         it != productions.end(); it++) {
        
        if(!(it->first == last)){
            last = it->first;
            
            if(!firstLine){
                cout << endl;
            }
            
            firstLine = false;
            cout << it->first.getName() << "\t::= \t";
            
        } else {
            cout << " | ";