SVF::CFGNormalizer Class Reference

#include <CFGNormalizer.h>

Public Member Functions
	CFGNormalizer ()
CFGrammar *	normalize (GrammarBase *generalGrammar)
	Binary Normal Form(BNF) normalization with variable attribute expanded. More...
CFGrammar *	fillAttribute (CFGrammar *grammar, const Map< CFGrammar::Kind, Set< CFGrammar::Attribute >> &kindToAttrsMap)
	Expand every variable attribute in rawProductions of grammarbase. More...

Private Member Functions
void	ebnf_bin (CFGrammar *grammar)
	Add nonterminal to tranfer long rules to binary rules. More...
void	ebnfSignReplace (char sign, CFGrammar *grammar)
void	barReplace (CFGrammar *grammar)
void	insertToCFLGrammar (CFGrammar *grammar, GrammarBase::Production &prod)
	Based on prod size to add on suitable member field of grammar. More...
int	ebnfBracketMatch (GrammarBase::Production &prod, int i, CFGrammar *grammar)
GrammarBase::Symbol	check_head (GrammarBase::SymbolMap< GrammarBase::Symbol, GrammarBase::Productions > &grammar, GrammarBase::Production &rule)
void	strTrans (std::string strPro, CFGrammar *grammar, GrammarBase::Production &normalProd)
void	getFilledProductions (GrammarBase::Production &prod, const NodeSet &nodeSet, CFGrammar *grammar, GrammarBase::Productions &normalProds)
void	removeFirstSymbol (CFGrammar *grammar)

Detailed Description

Generate Normalized Grammar (backus naur form) from a grammarbase (Extended extended Backus–Naur form )

To Do: Error Notice for ill formed production, e.g. not end with ';' and '*' not preceding with '()' and extra space before ';' '|' sign support

Definition at line 47 of file CFGNormalizer.h.

Constructor & Destructor Documentation

CFGNormalizer()

SVF::CFGNormalizer::CFGNormalizer ( )

inline

Definition at line 51 of file CFGNormalizer.h.

    {
    }

Member Function Documentation

barReplace()

void CFGNormalizer::barReplace ( CFGrammar *  grammar )

private

Definition at line 296 of file CFGNormalizer.cpp.

{
    for (auto &symbolToProductionsPair : grammar->getRawProductions())
    {
        GrammarBase::Productions productions;
        //GrammarBase::Productions Originalproductions = symbolToProductionsPair.second;
        for (auto ebnfProduction : symbolToProductionsPair.second)
        {
            size_t i = 1;
            size_t j = 1;
            while (i < ebnfProduction.size())
            {
                if (grammar->kindToStr(ebnfProduction[i].kind) == "|")
                {
                    GrammarBase::Production tempPro(ebnfProduction.begin()+j, ebnfProduction.begin()+i);
                    tempPro.insert(tempPro.begin(), symbolToProductionsPair.first );
                    productions.insert(tempPro);
                    j = i+1;
                }
                i++;
            }
            GrammarBase::Production tempPro(ebnfProduction.begin()+j, ebnfProduction.begin()+i);
            tempPro.insert(tempPro.begin(), symbolToProductionsPair.first );
            productions.insert(tempPro);
        }
        symbolToProductionsPair.second.clear();
        symbolToProductionsPair.second = productions;
    }
}

check_head()

GrammarBase::Symbol CFGNormalizer::check_head ( GrammarBase::SymbolMap< GrammarBase::Symbol, GrammarBase::Productions > &  grammar, GrammarBase::Production &  rule  )

private

Definition at line 457 of file CFGNormalizer.cpp.

{
    for(auto symProdPair: grammar)
    {
        for(auto prod: symProdPair.second)
        {
            if (rule == prod)
            {
                return symProdPair.first;
            }
        }
    }
    GrammarBase::Symbol symbol = u32_t(-1);
    return symbol;
}

ebnf_bin()

void CFGNormalizer::ebnf_bin ( CFGrammar *  grammar )

private

Add nonterminal to tranfer long rules to binary rules.

Assign _attribute if target portion of the production contain more than 1 variable then X add no variable attribute if target only contain one variable attribute X share the same variable attribute

Definition at line 92 of file CFGNormalizer.cpp.

{
    GrammarBase::SymbolMap<GrammarBase::Symbol, GrammarBase::Productions> new_grammar = {};
    std::string tempStr = "";
    removeFirstSymbol(grammar);
 
    auto rawProductions = grammar->getRawProductions();
 
    for(auto itr : rawProductions)
    {
        auto head = *(grammar->getRawProductions().find(itr.first));
        for(auto rule: head.second)
        {
            if (rule.size() < 3) continue;
 
            GrammarBase::Symbol first = rule[0];
            GrammarBase::Production long_run(rule.begin() + 1, rule.end());
            auto it = grammar->getRawProductions()[head.first].find(rule);
            grammar->getRawProductions()[head.first].erase(it);
            GrammarBase::Symbol X = check_head(new_grammar, long_run);
            if (X == u32_t(-1))
            {
                X = check_head(grammar->getRawProductions(), long_run);
            }
            if ((X == u32_t(-1)) == false)
            {
                rule = {first, X};
                grammar->getRawProductions()[head.first].insert(rule);
            }
            else
            {
                tempStr = "X";
                std::ostringstream ss;
                ss << grammar->num_generator();
                tempStr.append(ss.str());
                Set<GrammarBase::VariableAttribute> variableAttributeSet = {};
                for (unsigned i = 0; i < long_run.size(); i++)
                {
                    GrammarBase::VariableAttribute variableAttribute = long_run[i].variableAttribute;
                    if ( variableAttribute != 0)
                    {
                        variableAttributeSet.insert(variableAttribute);
                    }
                }
                if ( variableAttributeSet.size() == 1)
                {
                    tempStr += "_";
                    tempStr += char(*variableAttributeSet.begin());
                }
                GrammarBase::Symbol tempSym = grammar->insertNonTerminalSymbol(tempStr);
                rule = {first, tempSym};
                grammar->getRawProductions()[head.first].insert(rule);
                X = tempSym;
            }
            new_grammar[X] = {};
            GrammarBase::Production temp_p = long_run;
            GrammarBase::Symbol RHX;
            if (long_run.size() ==2)
            {
                new_grammar[X].insert(temp_p);
                long_run.clear();
            }
            else
            {
                new_grammar[X].insert(long_run);
                RHX = X;
            }
            while (long_run.size() > 2)
            {
                first = long_run[0];
                GrammarBase::Production prev_rule = long_run;
                long_run.erase(long_run.begin());
 
                X = RHX;
                temp_p = long_run;
 
                RHX = check_head(new_grammar, long_run);
                if (RHX == u32_t(-1))
                {
                    RHX = check_head(grammar->getRawProductions(), long_run);
                }
                if(RHX == u32_t(-1))
                {
                    tempStr = "X";
                    std::ostringstream ss;
                    ss << grammar->num_generator();
                    tempStr.append(ss.str());
                    Set<GrammarBase::VariableAttribute> variableAttributeSet = {};
                    for (unsigned i = 0; i < long_run.size(); i++)
                    {
                        GrammarBase::VariableAttribute variableAttribute = long_run[i].variableAttribute;
                        if ( variableAttribute != 0)
                        {
                            variableAttributeSet.insert(variableAttribute);
                        }
                    }
                    if ( variableAttributeSet.size() == 1)
                    {
                        tempStr += "_";
                        tempStr += char(*variableAttributeSet.begin());
                    }
                    GrammarBase::Symbol tempSym = grammar->insertNonTerminalSymbol(tempStr);
                    auto it = new_grammar[X].find(prev_rule);
                    new_grammar[X].erase(it);
                    new_grammar[X].insert({first, tempSym});
                    new_grammar[tempSym].insert(long_run);
                    RHX = tempSym;
                }
            }
        }
    }
    for (auto new_head : new_grammar)
    {
        for (auto prod : new_head.second)
        {
            auto it = grammar->getRawProductions()[new_head.first].find(prod);
            if (it == grammar->getRawProductions()[new_head.first].end())
            {
                grammar->getRawProductions()[new_head.first].insert(prod);
            }
        }
    }
}

ebnfBracketMatch()

int CFGNormalizer::ebnfBracketMatch ( GrammarBase::Production &  prod, int  i, CFGrammar *  grammar  )

private

Definition at line 282 of file CFGNormalizer.cpp.

{
    int index = i;
    while (index >= 0)
    {
        if (grammar->kindToStr(prod[index].kind) == "(")
        {
            return index;
        }
        index--;
    }
    return 0;
}

ebnfSignReplace()

void CFGNormalizer::ebnfSignReplace ( char  sign, CFGrammar *  grammar  )

private

Replace Sign Group With tempNonterminal 'X' And load the replace in newProductions

If sign associate without group e.i with single symbol

sign associate with group of symbol by brace pair

For Both * and ? need to insert epsilon rule

insert second rule for '*' X -> X E for '+' X -> E

Insert Back the Group

Definition at line 326 of file CFGNormalizer.cpp.

{
    SVF::Map<std::string, std::string> newProductions;
    std::string tempNonterminal = "X";
 
    for (auto &symbolToProductionsPair : grammar->getRawProductions())
    {
        GrammarBase::Productions productions = symbolToProductionsPair.second;
        for (auto ebnfProduction : symbolToProductionsPair.second)
        {
            size_t i = 1;
            while (i < ebnfProduction.size())
            {
                s32_t signGroupStart = -1;
                if (grammar->kindToStr(ebnfProduction[i].kind) == std::string(1, sign))
                {
                    assert(i != 1 && "sign in grammar associate with no symbol");
                    if (grammar->kindToStr(ebnfProduction[i - 1].kind) != std::string(1, ')'))
                    {
                        signGroupStart = i - 1;
                    }
                    else
                    {
                        signGroupStart = ebnfBracketMatch(ebnfProduction, i, grammar);
                    }
                    std::string groupString = "";
                    for (size_t j = signGroupStart; j < i; j++)
                    {
                        groupString.append(grammar->kindToStr(ebnfProduction[j].kind));
                        groupString.append(" ");
                    }
                    groupString.append(grammar->kindToStr(ebnfProduction[i].kind));
                    if (newProductions.find(groupString) != newProductions.end())
                    {
                        productions.erase(ebnfProduction);
                        ebnfProduction.erase(ebnfProduction.begin() + signGroupStart, ebnfProduction.begin() + i + 1);
                        ebnfProduction.insert(ebnfProduction.begin() + signGroupStart, grammar->strToSymbol(newProductions[groupString]));
                        productions.insert(ebnfProduction);
                    }
                    else if ( (signGroupStart == 1) && (i == ebnfProduction.size() -1))
                    {
                        newProductions[groupString] = grammar->kindToStr(ebnfProduction[0].kind);
                        productions.erase(ebnfProduction);
                        ebnfProduction.erase(ebnfProduction.begin() + signGroupStart, ebnfProduction.begin() + i + 1);
 
                    }
                    else
                    {
                        tempNonterminal = "X";
                        std::ostringstream ss;
                        ss << grammar->num_generator();
                        tempNonterminal.append(ss.str());
                        GrammarBase::Symbol tempSym = grammar->insertNonTerminalSymbol(tempNonterminal);
                        productions.erase(ebnfProduction);
                        ebnfProduction.erase(ebnfProduction.begin() + signGroupStart, ebnfProduction.begin() + i + 1);
                        ebnfProduction.insert(ebnfProduction.begin() + signGroupStart, tempSym);
                        newProductions[groupString] = tempNonterminal;
                        productions.insert(ebnfProduction);
                    }
 
                    i = signGroupStart;
                }
                i++;
            }
        }
        symbolToProductionsPair.second = productions;
    }
    for(auto rep: newProductions)
    {
        std::string new_nonterminal = rep.second;
        GrammarBase::Production temp_list = {grammar->strToSymbol(new_nonterminal), grammar->strToSymbol("epsilon")};
        grammar->getRawProductions()[grammar->strToSymbol(new_nonterminal)].insert(temp_list);
        temp_list = {grammar->strToSymbol(new_nonterminal)};
        if (sign == '*' || sign == '?')
        {
            GrammarBase::Production normalProd;
            strTrans(rep.first, grammar, normalProd);
            GrammarBase::Production withoutSign = {};
            if (sign == '*')
            {
                for (auto &word : normalProd)
                {
                    if (word != grammar->strToSymbol("*")  && word != grammar->strToSymbol("(") && word != grammar->strToSymbol(")"))
                    {
                        withoutSign.push_back(word);
                    }
                }
                withoutSign.push_back(grammar->strToSymbol(rep.second));
            }
            if (sign == '?')
            {
                for (auto &word : normalProd)
                {
                    if (word != grammar->strToSymbol("?")  && word != grammar->strToSymbol("(") && word != grammar->strToSymbol(")"))
                    {
                        withoutSign.push_back(word);
                    }
                }
            }
            temp_list.insert(temp_list.end(), withoutSign.begin(), withoutSign.end());
        }
        grammar->getRawProductions()[grammar->strToSymbol(new_nonterminal)].insert(temp_list);
    }
}

fillAttribute()

CFGrammar * CFGNormalizer::fillAttribute	(	CFGrammar *	grammar,
		const Map< CFGrammar::Kind, Set< CFGrammar::Attribute >> &	kindToAttrsMap
	)

Expand every variable attribute in rawProductions of grammarbase.

rawProductions production does not include lhs so append to the begin of the production

Definition at line 62 of file CFGNormalizer.cpp.

{
    NodeSet nodeSet = {};
    for (auto pair: kindToAttrsMap)
    {
        for (auto attri: pair.second)
        {
            nodeSet.insert(attri);
        }
    }
    for(auto symProdsPair: grammar->getRawProductions())
    {
        for(auto prod: symProdsPair.second)
        {
            GrammarBase::Production tempP = prod;
            tempP.insert(tempP.begin(), symProdsPair.first);
            GrammarBase::Productions normalProds;
            getFilledProductions(tempP, nodeSet, grammar, normalProds);
            for (auto  filledProd : normalProds)
            {
                insertToCFLGrammar(grammar, filledProd);
            }
        }
    }
 
    return grammar;
}

getFilledProductions()

void CFGNormalizer::getFilledProductions ( GrammarBase::Production &  prod, const NodeSet &  nodeSet, CFGrammar *  grammar, GrammarBase::Productions &  normalProds  )

private

Loop through provided production based on existence of attribute of attribute variable and expand to productions set e.g Xi -> Y Zi with Xi i = 0, 1, Yi i = 0,2 Will get {X0 -> Y Z0, X1 -> Y Z1, X2 -> Y Z2}

Get the first encounter variable attribute to expand

Check whether all symbol expanded

Definition at line 224 of file CFGNormalizer.cpp.

{
    normalProds.clear();
    CFLFIFOWorkList<GrammarBase::Production> worklist;
    worklist.push(prod);
    while( worklist.empty() == false )
    {
        GrammarBase::Production currentProduction = worklist.pop();
        GrammarBase::VariableAttribute currentVariableAttribute = 0;
        // GrammarBase::Kind baseKind;
        for ( GrammarBase::Symbol &symbol : currentProduction )
        {
            if ( currentVariableAttribute == 0 )
            {
                currentVariableAttribute = symbol.variableAttribute;
                // baseKind = symbol.kind;
            }
        }
        if ( currentVariableAttribute == 0)
        {
            normalProds.insert(currentProduction);
            continue;
        }
        //*(kindToAttriMap.find(baseKind));
        //for (auto attribute : nodeSet.second)
        for (auto attribute : nodeSet)
        {
            GrammarBase::Production fillingProduction = currentProduction;
            for ( GrammarBase::Symbol &symbol : fillingProduction )
            {
                if ( symbol.variableAttribute == currentVariableAttribute)
                {
                    symbol.attribute = attribute;
                    symbol.variableAttribute = 0;
                }
            }
            bool continueToFill = false;
            for ( GrammarBase::Symbol &symbol : fillingProduction )
            {
                if ( symbol.variableAttribute != 0 )
                {
                    continueToFill = true;
                }
            }
            if ( continueToFill == false)
            {
                normalProds.insert(fillingProduction);
            }
            else
            {
                worklist.push(fillingProduction);
            }
        }
    }
}

insertToCFLGrammar()

void CFGNormalizer::insertToCFLGrammar ( CFGrammar *  grammar, GrammarBase::Production &  prod  )

private

Based on prod size to add on suitable member field of grammar.

Definition at line 474 of file CFGNormalizer.cpp.

{
    if (prod.size() == 2)
    {
        if ((std::find(prod.begin(), prod.end(), grammar->strToKind("epsilon")) != prod.end()))
        {
            if (std::find(grammar->getEpsilonProds().begin(), grammar->getEpsilonProds().end(), prod) == grammar->getEpsilonProds().end())
            {
                grammar->getEpsilonProds().insert(prod);
            }
        }
        else
        {
            grammar->getSingleRHSToProds()[prod[1]].insert(prod);
        }
    }
    if (prod.size() == 3)
    {
        grammar->getFirstRHSToProds()[prod[1]].insert(prod);
        grammar->getSecondRHSToProds()[prod[2]].insert(prod);
    }
}

normalize()

CFGrammar * CFGNormalizer::normalize

(

GrammarBase *

generalGrammar

)

Binary Normal Form(BNF) normalization with variable attribute expanded.

Definition at line 42 of file CFGNormalizer.cpp.

{
    CFGrammar *grammar = new CFGrammar();
    grammar->setStartKind(generalGrammar->getStartKind());
    grammar->setTerminals(generalGrammar->getTerminals());
    grammar->setNonterminals(generalGrammar->getNonterminals());
    grammar->setEBNFSigns(generalGrammar->getEBNFSigns());
    grammar->setTotalKind(generalGrammar->getTotalKind());
    grammar->setAttributeKinds(generalGrammar->getAttrSyms());
    grammar->setKindToAttrsMap(generalGrammar->getKindToAttrsMap());
    grammar->setRawProductions(generalGrammar->getRawProductions());
    barReplace(grammar);
    ebnfSignReplace('*', grammar);
    ebnfSignReplace('?', grammar);
    ebnf_bin(grammar);
    fillAttribute(grammar, grammar->getKindToAttrsMap());
    return grammar;
}

removeFirstSymbol()

void CFGNormalizer::removeFirstSymbol ( CFGrammar *  grammar )

private

Definition at line 497 of file CFGNormalizer.cpp.

{
    // Remove First Terminal
    for(auto head : grammar->getRawProductions())
    {
        for(auto rule: head.second)
        {
 
            GrammarBase::Production long_run = rule;
            long_run.erase(long_run.begin());
            auto it = grammar->getRawProductions().at(head.first).find(rule);
            grammar->getRawProductions().at(head.first).erase(it);
            grammar->getRawProductions()[head.first].insert(long_run);
        }
    }
}

strTrans()

void CFGNormalizer::strTrans ( std::string  strPro, CFGrammar *  grammar, GrammarBase::Production &  normalProd  )

private

Definition at line 438 of file CFGNormalizer.cpp.

{
    std::smatch matches;
    std::regex LHSReg("\\s*(.*)");
    std::string delimiter;
    size_t pos;
    std::string word;
    std::regex_search(LHS, matches, LHSReg);
    LHS = matches.str(1);
    delimiter = " ";
    while ((pos = LHS.find(delimiter)) != std::string::npos)
    {
        word = LHS.substr(0, pos);
        LHS.erase(0, pos + delimiter.length());
        normalProd.push_back(grammar->strToSymbol(word));
    }
    normalProd.push_back(grammar->strToSymbol(LHS));
}

---

The documentation for this class was generated from the following files:

• /home/runner/work/SVF/SVF/svf/include/CFL/CFGNormalizer.h
• /home/runner/work/SVF/SVF/svf/lib/CFL/CFGNormalizer.cpp