...
#pragma once
#pragma once
#include <algorithm>
#include <deque>
#include <string>
#include <vector>
using namespace std;
#define size_range(what,cont) do{assert(what>=0 && what<(int)cont.size());}while(0);
#define debug_out(what) do{ cout<<ToString::String(what)<<endl;}while(0)
/*
* [下标]
* */
struct Index
{
Index();
Index(int index, bool terminal);
int index; // [非终结符或者终结符的下标]
bool terminal; // [为真表示该下标保存的是终结符]
static bool is_terminal( const Index& idx); // [下标为终结符则返回true]
bool is_terminal()const;
bool is_nonterminal()const;
bool operator == (const Index& idx)const;
bool operator != (const Index& idx)const;
Index& operator = (const Index& idex);
bool operator < (const Index& idx)const;
friend istream& operator>>(istream& is, Index& idx);
friend ostream& operator<<(ostream& os,const Index& idx);
operator string()const;
operator int()const;
};
#pragma once
#include "TypeDefine.h"
#include "CustomCollection.h"
#include <hash_map>
#include <string>
#include <deque>
#include <fstream>
#include <iostream>
#include <hash_map>
using namespace std;
const string g_emptyletter = "@";
const string g_flagletter = "#";
class Grammar
{
public:
typedef CustomCollection<string> StrCollection;
typedef CustomCollection<Index > IndexCollection;
typedef deque<Index > TypeProductionItem;
typedef deque<TypeProductionItem > TypeProduction;
typedef deque<TypeProduction> TypeProductionList;
Grammar(void);
~Grammar(void);
public:
/*
* [读取文法]
* */
void read(const string& filename);
void read(istream& is);
/*
* [消除左递归]
* */
void remove_left_recursice();
/*
* [提取公共因子]
* */
void distill_commonleftgene();
/*
* [写入文件]
* */
void WriteTo(const string& filename);
/*
* [显示文法]
* */
string ToString();
/*
* [清空]
* */
void Clear();
/*
* []
* */
Index get_index_of_start()const{return m_start_index;}
bool get_index_of_terminal(string teminal,Index& index);
bool get_index_of_nonterminal(string nonteminal,Index& index);
const string get_str_terminal(int i)const {size_range(i,m_str_terminals);return m_str_terminals.GetElement(i);}
const string get_str_nonterminal(int i)const {size_range(i,m_str_nonterminals);return m_str_nonterminals.GetElement(i);}
const StrCollection& get_str_terminals() const {return m_str_terminals;}
const StrCollection& get_str_nonterminals()const {return m_str_nonterminals;}
const TypeProduction& get_production(int i)const {size_range(i,m_idx_grammar);return m_idx_grammar[i];}
Index get_index_of_emptyletter()const {return Index((int)m_str_terminals.size()-1,true);}
Index get_index_of_flagletter()const {return Index((int)m_str_terminals.size()-2,true);}
static string get_flagletter() {return g_flagletter;}
protected:
/*
* [消除直接 | 非直接左递归 | 化简]
* */
void remove_directed_left_recursice(const Index& vn_index);
void remove_undirected_left_recursice(const Index& vn_index, const Index& relative_vn_index);
void reduction();
/*
* [删除非终结符]
* */
void delete_nonterminal(int idx_of_it);
/*
* [生成新非终结符]
* */
string generate_unique_nonterminal(int vn_index);
protected:
vector< vector<string >/*产生式右部*/ > m_str_grammar ; // [记录以字符串形式保存的文法]
TypeProductionList m_idx_grammar; // [记录以下标保存的文法]
StrCollection m_str_nonterminals; // [记录非终结符号串]
StrCollection m_str_terminals; // [记录终结符号串]
Index m_start_index; // [拓展后的文法开始符号的下标]
hash_map<string,int > m_unique_helper; // [辅助生成新的非终结符]
};
#include "TypeDefine.h"
#include "Grammar.h"
#include <hash_map>
#include <deque>
using namespace std;
class First
{
public:
typedef Grammar::TypeProductionItem TypeProductionItem;
typedef Grammar::TypeProduction TypeProduction ;
typedef Grammar::TypeProductionList TypeProductionList;
typedef CustomCollection<Index > TypeFirstCollection;
typedef deque<TypeFirstCollection > TypeFirstListCollection;
public:
First(const Grammar& grammar);
~First(void);
/*
* [计算规则的First集]
**/
void Calculate_First();
/*
* [返回First集]
**/
const TypeFirstCollection& GetFirst(const Index& index)const;
TypeFirstCollection& GetFirst(const TypeProductionItem& grammar,TypeFirstCollection& outC)const;
TypeFirstCollection& GetFirst(const TypeProductionItem::const_iterator begin,
const TypeProductionItem::const_iterator end,
TypeFirstCollection& outC)const;
/* —— 2005/06/24 ——
* [返回字符串形式]
* */
string ToString();
/* —— 2005/06/24 ——
* [清空]
* */
void Clear(){m_first_of_terminal.clear();m_first_of_nonterminal.clear();m_has_calculated.clear();}
protected:
/*
* [计算First]
**/
TypeFirstCollection& Calculate_First(const TypeProductionItem& pro_itm, TypeFirstCollection& firstC);
TypeFirstCollection& Calculate_First(TypeProductionItem::const_iterator begin,
TypeProductionItem::const_iterator end,
TypeFirstCollection& firstC);
TypeFirstCollection& Calculate_First(const TypeProduction& production, TypeFirstCollection& firstC);
TypeFirstCollection& Calculate_First(const Index& index, TypeFirstCollection& firstC);
TypeFirstCollection& Calculate_First(
TypeProductionItem::const_iterator begin,
TypeProductionItem::const_iterator end,
TypeFirstCollection& firstC)const;
protected:
const Grammar& m_grammar;
map<Index,bool> m_has_calculated;
TypeFirstListCollection m_first_of_nonterminal;
TypeFirstListCollection m_first_of_terminal;
};
#include "Grammar.h"
#include "First.h"
#include "CustomCollection.h"
#include <deque>
using namespace std;
class Follow
{
public:
typedef Grammar::TypeProductionItem TypeProductionItem;
typedef Grammar::TypeProduction TypeProduction ;
typedef Grammar::TypeProductionList TypeProductionList;
typedef CustomCollection<Index > TypeFollowCollection;
typedef deque<TypeFollowCollection > TypeFollowListCollection;
public:
Follow(const First& _first,const Grammar &_grammar);
~Follow(void);
public:
/*
* [计算规则的Follow集]
* */
void Calculate_Follow();
/*
* [返回某个非终结符的 Follow 集]
* */
const TypeFollowCollection& GetFollow(int vn_index)const;
/* —— 2005/06/24 ——
* [字符串显示]
* */
string ToString()const;
/* —— 2005/06/24 ——
* [清空]
* */
void Clear(){m_follow_of_nonterminal.clear(); m_has_calculated = false;}
protected:
/*
* [根据课本第2个规则计算Follow集]
* */
TypeFollowCollection& Calculate_Follow_2nd_rules(const Index& vn_index,TypeFollowCollection& outC);
/*
* [根据第3个规则计算，注意必须先根据第2个规则计算后才能调用此函数]
* */
TypeFollowCollection& Calculate_Follow_3rd_rules(const Index& vn_index,TypeFollowCollection& outC);
protected:
const First& m_first;
const Grammar& m_grammar;
TypeFollowListCollection m_follow_of_nonterminal;
deque<CustomCollection<Index> > m_helper; // [在根据第三个条件求Follow集时辅助]
bool m_has_calculated;
};
#include "Common/Collection.h"
#include "Common/any.h"
#include "Grammar.h"
#include "First.h"
#include "Follow.h"
#include <deque>
class ParseTable
{
public:
ParseTable(const Grammar& m_grammar,const First& _first,const Follow& _follow);
~ParseTable(void);
/*
* [类型说明]
**/
typedef Grammar::TypeProductionItem TypeProductionItem;
typedef Grammar::TypeProduction TypeProduction ;
typedef Grammar::TypeProductionList TypeProductionList;
typedef First::TypeFirstCollection TypeFirstCollection;
typedef First::TypeFirstListCollection TypeFirstListCollection;
typedef Follow::TypeFollowCollection TypeFollowCollection;
typedef Follow::TypeFollowListCollection TypeFollowListCollection;
typedef deque<deque<Index > > TypeTableItem;
typedef deque< TypeTableItem > TypeTable;
public:
/*
* [返回产生式]
* */
void GetProduction(int vn_index, int vt_index, TypeProductionItem& out_production);
/*
* [计算预测分析表]
**/
void CalculateTable();
/*
* [字符串形式返回]
**/
string ToString()const;
operator string()const{return ToString();}
/*
* [清空]
* */
void Clear(){this->m_table.clear();}
/*
* [写入文件]
* */
void WriteTo(const string& filename);
protected:
TypeTable m_table;
const Grammar& m_grammar;
const First& m_first;
const Follow& m_follow;
};
class LL_1
{
public:
LL_1(void);
~LL_1(void);
/*
* [类型说明]
**/
typedef Grammar::TypeProductionItem TypeProductionItem;
typedef Grammar::TypeProduction TypeProduction ;
typedef Grammar::TypeProductionList TypeProductionList;
typedef First::TypeFirstCollection TypeFirstCollection;
typedef First::TypeFirstListCollection TypeFirstListCollection;
typedef Follow::TypeFollowCollection TypeFollowCollection;
typedef Follow::TypeFollowListCollection TypeFollowListCollection;
public:
/*
* [读取文法]
* */
void Read_Grammar(istream& is);
/*
* [计算规则的First集]
* */
void Calculate_First();
/*
* [计算规则的Follow集]
* */
void Calculate_Follow();
/*
* [计算预测分析表]
* */
void Calculate_ParseTable();
/*
* [消除左递归]
* */
void Remove_LeftRecursive();
/*
* [对输入串进行分析]
* */
bool Analyse(istream & is,ostream &error_os);
bool Analyse(const string& filename,const string& error_file);
/* —— 2005/06/27 ——
* [写入文件]
* */
bool WriteTo(const string& dir_name);
/*
* [字符传返回grammar | first | follow 集 以及 预测分析表]
* */
string grammar();
string first();
string follow();
string table();
/*
* [清空]
* */
void Clear();
protected:
Grammar m_grammar;
First m_first;
Follow m_follow;
ParseTable m_parseTable;
// [标记]
bool m_hasCalFirst;
bool m_hasCalFollow;
bool m_isLL_1;
};
#include "stdafx.h"
#include "ll_1.h"
#include <fstream>
#include <deque>
#include "first.h"
using namespace std;
void main()
{
LL_1 ll_1;
ifstream is_init("init.txt");
string code_file, err_file,result_file,grammar_file;
is_init>>grammar_file;
is_init>>result_file;
is_init>>code_file;
is_init>>err_file;
is_init.close();
/*
* [重定向输出到文件 result.txt]
**/
ofstream os(result_file.c_str());
streambuf* pre_buf = cout.rdbuf(os.rdbuf());
{// [读取规则]
ifstream is(grammar_file.c_str());
ll_1.Read_Grammar(is);
is.close();
ll_1.Remove_LeftRecursive();
}
{// [计算 first 集]
ll_1.Calculate_First();
}
{// [计算 follow 集]
ll_1.Calculate_Follow();
}
{// [计算 预测分析表]
ll_1.Calculate_ParseTable();
}
{// [输出]
cout<<ll_1.grammar()<<endl;
cout<<ll_1.first()<<endl;
cout<<ll_1.follow()<<endl;
cout<<ll_1.table()<<endl;
}
{// [分析]
// [代码以及错误记录文件]
ifstream is_code(code_file.c_str());
ofstream os_error(err_file.c_str());
if(ll_1.Analyse(is_code,os_error))
cout<<"识别成功"<<endl;
else
cout<<"识别失败"<<endl;
}
cout.rdbuf(pre_buf);
}
终于改掉了原来的终结符号和非终结符号一起存储的结构～
