syntax.h

LL1通用语法分析器

/************************************************************************
                        Copyright IBMTC Written by Xinxi Wang
**************************************************************************/


#ifndef SYNTAX_H
#define SYNTAX_H

#include <string>
#include <set>
#include <vector>
#include <algorithm>
#include <fstream>

#include "Token.h"
#include "Terminal.h"
#include "Variable.h"
#include "Epsilon.h"
#include "Pattern.h"
#include "AnalyzeTable.h"


/**
  * 语法，由所有的产生式构成
  */

class Syntax
{
public:
    typedef std::set<Token *, TokenCompare> TokenSet ;
    typedef std::vector<TokenSet> TokenSets;
    typedef std::map<Variable, TokenSet > TokenSetMap;
public:

    /**
     * @brief 求变元var的FIRST集合
     * @return var的FIRST集合
     * @param  var
     */
    void getFirst (const Variable &var, TokenSet& s ) const;


    /**
     * @brief 求句型pattern的FIRST集合
     * @return pattern的FIRST集合
     * @param  pattern
     */
    void getFirst (const Pattern& pattern, TokenSet &s);


    /**
     * @brief 求var的FOLLOW集合
     */
    void getFollow (const Variable &var, TokenSet& sets) const;


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


    /**
     * @brief 解析文法
     * @param in 输入流
     * @param  in
     */
    void parse (std::istream& in );
    
    
    /**
     * @brief 打印LL1语法分析表
     */
    void printLL1AnalyzeTable() const;

    
    /**
     * @brief 打印文法
     */
    void printGrammar();
    
    
    /**
     * @return AnalyzeTable
     */
    void genLL1AnalyzeTable (AnalyzeTable &table );

    /**
     * @brief 返回变元var的所有产生式右部
     */
    std::vector<Pattern> getPatterns (const Variable& var) const;

    /**
     * @brief 返回所有的变元
     */
    std::vector<Variable> getVariables () const;
    
    
    std::vector<Terminal> getTerminals () const;

    
    Variable getStartVariable() const;
    
    ~Syntax();
    
private:    
    
    /**
     * @brief 削除左递归
     */
    void DeleteLeftRecursion ( );
    
    void grammarError(const std::string& msg, int lineNum);
    void caculateFirstSet();
    void caculateFollowSet();
    void caculateVariables();
    
    void printTokenSet(const TokenSet& s) const;
private:

    Variable startVariable;
    
    typedef std::multimap<Variable, Pattern> ProductionMap;
    
    // 所有的语法规则产生式
    std::multimap<Variable, Pattern> productions;
    
    //first集合
    TokenSets FIRSTSet;
    
    //follow集合
    TokenSets FOLLOWSet;

    //所有的变元集合
    std::vector<Variable > allVars;
    
    //所有终结符
    std::vector<Terminal > allTerms;
    
    //memory pool
    std::vector<Token *> pool;
};

#endif // SYNTAX_H