product.cpp

来自「compiler principle how to ananilyze」· C++ 代码 · 共 363 行

// Product.cpp: implementation of the Product class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "SymbolTable.h"
#include "VLocation.h"
#include <assert.h>
#include <algorithm>
using namespace std;

#include "Product.h"

extern SymbolTable symbol_table;

Product::Product(): countLeft(0), grammarType(Product::UNKNOWN)
{

}

SymbolEntry& Product::se(int index) const {
	return symbol_table[line[index]];
}
const SymbolEntry& Product::cse(int index) const {
	return symbol_table[line[index]];
}

int Product::size() const {

	return line.size();
}

int Product::sizeOfLeft() const {
	return countLeft;	
}

int Product::sizeOfLeft_without_epsilon() const {

	int c = 0;
	int i = 0;

	for(; i< countLeft; ++i) {
		if (cse(i).token_type != SymbolEntry::EPSILON)
			++c;
	}
	return c;
}

int Product::sizeOfRight_without_epsilon() const {
	
	int c = 0;
	int i = countLeft;
	int size = line.size();
	for(; i< size; ++i) {
		if (cse(i).token_type != SymbolEntry::EPSILON)
			++c;
	}
	return c;
}

int Product::sizeOfLeft(int token_type) const {

	int c = 0;
	int i=0;
	for(; i< countLeft; ++i) {
		if (cse(i).token_type == token_type)
			++c;
	}
	return c;
}

int Product::sizeOfRight() const {
	return line.size() - countLeft;
}
int Product::sizeOfRight(int token_type) const {

	int c = 0;
	int i =  countLeft;
	int size = line.size();
	for(; i< size; ++i) {
		if (cse(i).token_type == token_type)
			++c;
	}
	return c;
}


bool Product::isRightInclude(int symbolTableIndex) const {
	int i = countLeft;
	int size = line.size();
	for(; i<size && line[i] != symbolTableIndex; ++i);
	return i<size;
}

void Product::append_Left(int symbolTableIndex) {
	line.push_back(symbolTableIndex);
	++countLeft;
}

//false: the new index isn't inserted
bool Product::append_Right_Epsilon(int symbolTableIndex) {
	SymbolEntry& newEp = symbol_table[symbolTableIndex];
	assert(newEp.token_type == SymbolEntry::EPSILON);

	if (line.size() > countLeft ) {
		return false;			//not inserted if the first right is Epsilon or VT or VN 
	}
	
	line.push_back(symbolTableIndex);
	return true;
}
//false: epsilon is removed
bool Product::append_Right_VN_VT(int symbolTableIndex, int row) {
	
	bool result = true;

	SymbolEntry& newSe = symbol_table[symbolTableIndex];
	assert(newSe.token_type != SymbolEntry::EPSILON);
	if (line.size() > countLeft ) {
		SymbolEntry& firstRight = se(countLeft);
		if (firstRight.token_type == SymbolEntry::EPSILON) {
			
			// remove the firstRight's location info from VLocationSet
			VLocationSet& vs = firstRight.locations;
			VLocation re(row, countLeft);
			VLocationSet::iterator b = vs.begin();
			VLocationSet::iterator e = vs.end();
			VLocationSet::iterator x = find(b,e, re);
			assert(x != e);
			vs.erase(x);
		
			// remove the firstRight from this product 
			vector<int>::iterator xx = line.begin();
			line.erase(xx + countLeft);

			result = false;
		}

	}

	line.push_back(symbolTableIndex);
	return result;
	
}

void Product::copyLeft(Product& product, int newRow) const {
	
	product.countLeft = countLeft;
	int i=0;
	for(; i<countLeft; ++i) {
		product.line.push_back(line[i]);
		
		se(i).locations.push_back(VLocation(newRow, i));
	}
}


bool Product::ggt_PSG_A_epsilon(const vector<Product>& products, 
							int& sum_grammar_type, int startSymbolIndex) {
	
/*
1. A-> epsilon 规则
	1.1 若A为起始符且A在某产生式的右则，则 P是短语文法PSG的产生式
	1.2 否则不影响前面对每条产生式的判定结果，即如下情况不影响判定结果：
		1.2.1 A为起始符且A不在任何产生式右则
		1.2.2 A不为起始符 
*/
	if (line.size() == 2 && countLeft == 1 &&
		line[0] == startSymbolIndex &&
		cse(countLeft).token_type == SymbolEntry::EPSILON) {
		
		int symbolTableIndex = line[0];
		const VLocationSet& vs =  cse(0).locations;
		VLocationSet::const_iterator i = vs.begin();
		VLocationSet::const_iterator e = vs.end();
		for(; i != e ; ++i) {
			const Product& p = products[i->row];
			if (p.isRightInclude(symbolTableIndex)) {
				grammarType = Product::PSG0;
				sum_grammar_type = Product::PSG0;
				return true;
			}
				
		}//for
	}
	return false;
}


int Product::getGrammarType(const vector<Product>& products, 
							int& sum_grammar_type, int startSymbolIndex) {

//					                 左侧
//                                    |
//  |VN| =0 -------------------------|VN|=1 --------------------- |VN| > 1           
//    |                               |    
//   PSG                             右侧                           |
//                                    |                PSG[other]--------CSG if |右侧| >= |左侧|  |epsilon| =0
//                                    |
//            |---------------------------------------------
//          CFG if |VN| >1         |VN|=1               |VN| = 0
//                                    |
//            |-----------------|------                      |              
//  左or 右线性 if |right|=1    |                            |
//                              |                            |
//                              |    左 or 右线性 [other]------------PSG if S->epsilon且起始符S在某产生式右侧 
//                              |
//  左线性 if VN在最左----------------------右线性 if VN在最右
//                              |
//                             CFG

// enum {UNKNOWN=0, LEFT_RIGHT_LINE=2, LEFT_LINE=4, RIGHT_LINE=5, 
//		  RG3=7, CFG2=9, CSG1=11, PSG0=13 };

	int countLeftVN = sizeOfLeft(SymbolEntry::VN);

	switch(countLeftVN) {

	case 0:
		if (sizeOfLeft() == 0) return Product::UNKNOWN;		//the product's left is empty 

		grammarType = Product::PSG0;
		sum_grammar_type = grammarType;
		return grammarType;

	case 1: {
		int countRightVN = sizeOfRight(SymbolEntry::VN);
		switch(countRightVN) {
		case 0:
			if (!ggt_PSG_A_epsilon(products, sum_grammar_type, startSymbolIndex)) {
				grammarType = Product::LEFT_RIGHT_LINE;
				if (sum_grammar_type == UNKNOWN)
					sum_grammar_type = grammarType;

			}
			return grammarType;

		case 1:
			if (sizeOfRight() == 1)
				grammarType = Product::LEFT_RIGHT_LINE;
			else if (cse(countLeft).token_type == SymbolEntry::VN)
				grammarType = Product::LEFT_LINE;
			else if (cse(line.size()-1).token_type == SymbolEntry::VN)
				grammarType = Product::RIGHT_LINE;
			else {
				grammarType = Product::CFG2;
				if (sum_grammar_type < grammarType)
					sum_grammar_type = grammarType;
				return grammarType;
			}

			if (sum_grammar_type <= Product::RIGHT_LINE) {
				if (sum_grammar_type <= Product::LEFT_RIGHT_LINE)
					sum_grammar_type = grammarType;
				else if (sum_grammar_type != grammarType)
					sum_grammar_type = Product::RG3;

			}
			return grammarType;

		default: // right |VN|>1
			grammarType = Product::CFG2;
			if (sum_grammar_type < grammarType)
				sum_grammar_type = grammarType;
			return grammarType;

		}//iner switch
		break;
	}//case 1

	default: //left |VN| > 1
		if (sizeOfRight_without_epsilon() >= sizeOfLeft_without_epsilon()) {
			grammarType = Product::CSG1;
		}
		else
			grammarType = Product::PSG0;
		
		if (sum_grammar_type < grammarType)
			sum_grammar_type = grammarType;
		return grammarType;
	
	}//out switch

}

string Product::display() const {
	
	int size = line.size();
	if (size <=0 ) return "";
	
	string str;
	int i =0;
	for(; i < countLeft; ++i) {
		str += " ";
		str += cse(i).display();
	}

	str += " ";
	str += SymbolEntry::p_ARROW;

	for(; i<size; ++i) {
		str += " ";
		str += cse(i).display();
	}

	str += " ";
	str += SymbolEntry::c_DELIMITER;

	str += " ";
	str += "( ";
	str += Product::grammarTypeString(grammarType);
	str += " )";
	
	return str;
}

string Product::grammarTypeString(int aGrammarType) {

	string str;

//	enum {UNKNOWN=0, LEFT_RIGHT_LINE=2, LEFT_LINE=4, RIGHT_LINE=5, 
//		  RG3=7, CFG2=9, CSG1=11, PSG0=13 };
	switch(aGrammarType) {

	case Product::UNKNOWN:
		str += "Unknown";
		break;

	case Product::LEFT_RIGHT_LINE:
		str += "left or right line";
		break;

	case Product::LEFT_LINE:
		str += "left line";
		break;

	case Product::RIGHT_LINE:
		str += "right line";
		break;

	case Product::RG3:
		str += "regular-3";
		break;

	case Product::CFG2:
		str += "context free-2";
		break;

	case Product::CSG1:
		str += "context sensitive-1";
		break;

	case Product::PSG0:
		str += "phrase structure-0";
		break;
	
	default:
		error("Product::display()..unknown grammartype: " + iToString(aGrammarType));
		break;
	}

	return str;
}