syntax.cpp

词法分析,语法分析,文件中有语言的文法,根据文法写出的程序样例,还有根据样例进行词法分析得出的文件

// 语法分析器 Syntax.cpp
// 作者: 吴建平
// 学号：20021071 班级：20021013
// 完成日期：2005-6-19
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;	

// 产生式 vn————终结符 vt————非终非符
// produce————终结符遇到非终结符时选择的产生式
class Produce {
public:
	Produce(const char* s1, const char* s2, const char* s3) :
		vn(s1), vt(s2), produce(s3)
		{}

	string vn;
	string vt;
	string produce;
};

// 定义仿函数,与find_if算法配合使用搜寻产生式
class SelectProduce
{
public:
	SelectProduce(const string& s1, const string& s2) :
		vn(s1), vt(s2)
	{}

	bool operator ()(const Produce& pd)
	{
		return (pd.vn == vn && pd.vt == vt);
	}

private:
	string vn;
	string vt;
};

vector<Produce> producer;	// 产生式列表
vector<string> predictStack;// 分析栈
vector<string> identifers;	// 标识符
vector<string> terminators;	// 终结符列表

void FillTerminator();
void FillProducer();
void SyntaxParser();
void Parser(const string&);
void ReplaceParserStack(const string&);
bool IsVTerminate(const string&);

int main(int argc, char* argv[])
{
	FillTerminator();
	FillProducer();
	SyntaxParser();
	return 0;
}

// 填充终结符
void FillTerminator()
{
	const string vt[] = {"0", "1", "2", "3", "4", "5", "6", "7", 
			"8", "9", "10", "11", "20", "21", "22", "23", "24", 
			"25", "99", "@"};	// @ 表示空串
	for (int i = 0; i < 20; ++i)
		terminators.push_back(vt[i]);
}

// 填充产生式
void FillProducer()
{
	producer.push_back(Produce("P", "99" ,"99 1 2 3 SList 4"));
	producer.push_back(Produce("SList", "3", "3 SList 4"));
	producer.push_back(Produce("SList", "0", "S SList'"));
	producer.push_back(Produce("SList", "22", "S SList'"));
	producer.push_back(Produce("SList", "25", "S SList'"));
	producer.push_back(Produce("SList", "21", "S SList'"));
	producer.push_back(Produce("SList", "24", "@"));
	producer.push_back(Produce("SList'", "4", "@"));
	producer.push_back(Produce("SList'", "5", "5 SList"));
	producer.push_back(Produce("S", "22", "22 B 23 SList 24 SList"));
	producer.push_back(Produce("S", "25", "25 E"));
	producer.push_back(Produce("S", "21", "Decl"));
	producer.push_back(Produce("S", "0", "0 6 E"));
	producer.push_back(Produce("Decl", "21", "21 VList"));
	producer.push_back(Produce("VList", "0", "0 VList'"));
	producer.push_back(Produce("VList'", "11", "11 VList"));
	producer.push_back(Produce("VList'", "5", "@"));
	producer.push_back(Produce("B", "0", "E B'"));
	producer.push_back(Produce("B'", "9", "9 E"));
	producer.push_back(Produce("B'", "10", "10 E"));
	producer.push_back(Produce("E", "1", "T E'"));
	producer.push_back(Produce("E", "0", "T E'"));
	producer.push_back(Produce("E", "20", "T E'"));
	producer.push_back(Produce("E'", "2", "@"));
	producer.push_back(Produce("E'", "7", "7 T E'"));
	producer.push_back(Produce("E'", "10", "@"));
	producer.push_back(Produce("E'", "9", "@"));
	producer.push_back(Produce("E'", "23", "@"));
	producer.push_back(Produce("E'", "5", "@"));
	producer.push_back(Produce("E'", "4", "@"));
	producer.push_back(Produce("T", "1", "F T'"));
	producer.push_back(Produce("T", "0", "F T'"));
	producer.push_back(Produce("T", "20", "F T'"));
	producer.push_back(Produce("T'", "2", "@"));
	producer.push_back(Produce("T'", "8", "8 F T'"));
	producer.push_back(Produce("T'", "7", "@"));
	producer.push_back(Produce("T'", "10", "@"));
	producer.push_back(Produce("T'", "9", "@"));
	producer.push_back(Produce("T'", "5", "@"));
	producer.push_back(Produce("T'", "23", "@"));
	producer.push_back(Produce("T'", "4", "@"));	
	producer.push_back(Produce("F", "1", "1 E 2"));
	producer.push_back(Produce("F", "20", "20"));
	producer.push_back(Produce("F", "0", "0"));
}

// 语法分析
void SyntaxParser()
{
	ifstream inFile("a.out");
	if (!inFile) {
		cerr << "Can't open input file \"a.out\"" << endl;
		exit(EXIT_FAILURE);
	}

	predictStack.push_back("#");
	predictStack.push_back("P");

	char c;
	string word;
	int count = 1;
	while (inFile.get(c)) {
		if (c == '\t') {	// 由TAB分开单词种类值和内码值
			copy(predictStack.begin(), predictStack.end(), 
				ostream_iterator<string>(cout, " "));
			cout << endl;
			cout << count++ << ": " << word << endl;
			Parser(word);
			word = "";
		}
		else if (c == '\n') { // 
			identifers.push_back(word);
			word = "";
		}
		else
			word += c;
	}
	if (predictStack.back() == "#")
		cout << "OK" << endl;
}

// 分析
void Parser(const string& word)
{
	while (true) {
		if (IsVTerminate(predictStack.back())) {
			if (predictStack.back() == "@")
				predictStack.pop_back();
			if (word == predictStack.back()) {
				predictStack.pop_back();
				return;
			}
		}

		// 查找与预测栈顶非终结符、读进来单词相匹配的产生式
		vector<Produce>::iterator pos = find_if(producer.begin(), producer.end(),
			SelectProduce(predictStack.back(), word));
		if (pos == producer.end()) {
			cerr << "Error" << endl;
			exit(EXIT_FAILURE);
		}
		else {
			predictStack.pop_back();
			ReplaceParserStack(pos->produce);
			copy(predictStack.begin(), predictStack.end(), 
				ostream_iterator<string>(cout, " "));
			cout << endl;
			
			if (IsVTerminate(predictStack.back())) {
				// 如果预测栈顶是空串，将其弹出
				if (predictStack.back() == "@")	
					predictStack.pop_back();
				// 如果预测栈顶字符与所读字符相同也将其弹出
				if (word == predictStack.back()) { 
					predictStack.pop_back();
					return;
				}
			}
		}
	}
}

// 根据产生式替换分析栈栈顶字符
void ReplaceParserStack(const string& pd)
{
	string::size_type begIdx, endIdx;
	begIdx = pd.find_first_not_of(' ');
	int i = 0;
	while (begIdx != string::npos) {
		endIdx = pd.find_first_of(' ', begIdx);
		string word = pd.substr(begIdx, endIdx-begIdx);
		vector<string>::iterator pos = predictStack.end() - i++;
		predictStack.insert(pos, word);
		begIdx = pd.find_first_not_of(' ', endIdx);
	}
}

// 判断是否为终结符
bool IsVTerminate(const string& word)
{
	vector<string>::iterator pos = find(terminators.begin(), 
		terminators.end(), word);
	return pos != terminators.end();
}