whale.h.svn-base

来自「Complete support for EBNF notation; Obje」· SVN-BASE 代码 · 共 422 行

//#define _RWSTD_BOUNDS_CHECKING

#ifndef __WHALE__WHALE_H

#define __WHALE__WHALE_H

#define WHALE_VERSION "0.3.2"
#define WHALE_RELEASE_DATE "17 April, 2002"
#define SHORT_COPYRIGHT_NOTICE "Whale " WHALE_VERSION ", a parser generator. " "(C) A. Okhotin and V. Prus, 1999-2002.\n"
#define COPYRIGHT_NOTICE_FOR_GENERATED_FILES "\t\x22" "%s generated by Whale " WHALE_VERSION " (" WHALE_RELEASE_DATE ").\\n\x22\n" 	"\t\x22" "(C) Alexander Okhotin <[e-mail]>, 1999-2002.\\n\x22\n" "\t\x22" "(C) Vladimir Prus <[e-mail]>, 2000-2002.\\n\x22"
#define FIRST_LINE_FOR_GENERATED_FILES "\n/* %s generated by Whale */\n"
#define COMMAND_LINE_SYNTAX "Command line syntax: whale filename.whl\n"

#if '\xff'<'\x0'
	#error This program requires char to be unsigned.
#endif

#include "assert.h"

#include <string.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <exception>

struct QuietException : std::exception
{
};

struct NullTerminatedStringCompare : std::binary_function<char *, char *, bool>
{
	bool operator ()(const char *s1, const char *s2) const
	{
		return strcmp(s1, s2)<0;
	}
};

class SymbolNumber
{
	int n;

	explicit SymbolNumber(int supplied_n) { n=supplied_n; }

public:
	bool is_terminal() const { return n>0; }
	bool is_nonterminal() const { return n<0; }
	bool is_end_marker() const { return n==1; }
	bool is_start_symbol() const { return n==-1; }
	int nonterminal_number() const { return -(n+1); }
	int terminal_number() const { return n-1; }
	int get_n() const { return n; }

	operator int() const { return n; }

	// these functions should be used as constructors.
	static SymbolNumber for_nonterminal(int n) { return SymbolNumber(-(n+1)); }
	static SymbolNumber for_terminal(int n) { return SymbolNumber(n+1); }
	static SymbolNumber error() { return SymbolNumber(0); }
};

inline bool operator <(SymbolNumber sn1, SymbolNumber sn2)
{
	if(int(sn1)<0 && int(sn2)<0)
		return int(sn1)>int(sn2);
	else
		return int(sn1)<int(sn2);
}

#include "classes.h"
#include "lr.h"
#include "precedence.h"
#include "variables.h"
#include "tuple.h"
#include "tables.h"

namespace Whale
{
	class Terminal;
	class NonterminalExpression;
	class NonterminalExpressionCode;
	class NonterminalExpressionConnectUp;
	class NonterminalExpressionPrecedence;
	class NonterminalOptionStatement;
	class NonterminalS;
}

struct TerminalData
{
	char *name;
	Whale::Terminal *declaration;
	ClassHierarchy::Class *type;

	TerminalData()
	{
		name=NULL;
		declaration=NULL;
		type=NULL;
	}
	void print_where_it_was_declared(std::ostream &os);
};

struct AlternativeData
{
	Whale::Terminal *declaration;
	ClassHierarchy::Class *type;

	Whale::NonterminalExpression *expr;
	std::vector<int> creator_nn;
	bool connect_up;

	AlternativeData()
	{
		declaration=NULL;
		type=NULL;
		expr=NULL;
		connect_up=false;
	}
};

struct NonterminalData
{
	enum Category
	{
		NORMAL,		// An ordinary nonterminal.
		EXTERNAL,	// A nonterminal defined by 'external'
				// statement. Its internal data type is hidden
				// from the user.
		START,		// S', the start symbol of the augmented grammar.
		BODY,		// Iteration body. For each iteration used
				// one (or two for iteration_pair) body is
				// created. For example, the EBNF rule
				//	A -> (a (b c)+)*
				// causes bodies A-BodyI and A-BodyII and rules
				//	A -> A-IteratorI
				//	A -> e
				//	A-BodyI -> a A-IteratorII
				//	A-BodyII -> b c
				// to be created.
		ITERATOR,	// Iterator is a symbol used to accumulate
				// a series of bodies. In the example above,
				// two iterators, A-IteratorI and A-IteratorII,
				// and rules
				//	A-IteratorI -> A-IteratorI A-BodyI
				//	A-IteratorI -> A-BodyI
				//	A-IteratorII -> A-IteratorII A-BodyII
				//	A-IteratorII -> A-BodyII
				// would be created.
		INVOKER,	// A purpose of invoker is to invoke user code
				// placed in the middle of a rule. Declaration
				//	B -> a { cout << "Here!\n"; } b;
				// would result in rules
				//	B -> a B-InvokerI b
				//	B-InvokerI -> e
				// where user code is attached to Reduce by
				// the latter rule.
		CREATOR,	// (ought to write it someday)
		UPDATER,
		CONNECTOR
	};

	char *name;
	Whale::Terminal *declaration;
	ClassHierarchy::Class *type;		// the internal type.
	ClassHierarchy::Class *external_type;

	// (category==NORMAL || category==EXTERNAL) <=> is_ancillary==false
	bool is_ancillary;
	Category category;
	int master_nn, master_an; // if is_ancillary==true

	Whale::NonterminalExpressionCode *code_invoker_declaration; // for code invokers
	std::vector<int> rules_where_ancillary_symbol_is_used; // for creators and updaters.
	std::vector<Whale::NonterminalExpressionConnectUp *> requests_to_connect_up;

	bool multiple_alternatives_mode;
	std::vector<AlternativeData> alternatives;

	std::set<int> first;			// a: A ==>* a alpha
	bool is_nullable;			// true if (A ==>* epsilon)
	std::set<int> first_nonterminals;	// B: A ==>* B alpha
	std::set<int> follow;

	int number_of_iterators;
	int number_of_invokers;
	int number_of_creators;
	int number_of_updaters;

	int first_rule, last_rule; // number_of_rules=last_rule-first_rule

	NonterminalData()
	{
		name=NULL;
		declaration=NULL;
		type=NULL;
		external_type=NULL;
		is_ancillary=false;
		code_invoker_declaration=NULL;
		master_nn=-1;
		master_an=-1;
		number_of_iterators=0;
		number_of_invokers=0;
		number_of_creators=0;
		number_of_updaters=0;
	}
	void print_where_it_was_declared(std::ostream &os);
};

struct RuleData
{
	int nn, an;
	std::vector<SymbolNumber> body;
	std::vector<Whale::NonterminalExpression *> expr_body;
	Whale::NonterminalExpressionCode *code_to_execute_upon_reduce;
	std::vector<Whale::NonterminalExpressionPrecedence *> precedence_expressions;

	// creator_nn==-1 <==> create_and_undate_operator_locations.size()==0
	std::vector<int> create_and_update_operator_locations;
	int creator_nn;

	int precedence_symbol_number;
//	bool precedence_symbol_explicitly_set;

	RuleData(int supplied_nn, int supplied_an)
	{
		nn=supplied_nn, an=supplied_an;
		code_to_execute_upon_reduce=NULL;
		precedence_symbol_number=-1;
	//	precedence_symbol_explicitly_set=false;
		creator_nn=-1;
	}

	std::string in_printable_form() const;
};

bool operator <(const RuleData &r1, const RuleData &r2);

struct PrecedenceSymbolData
{
	enum Associativity { ASSOC_UNDEFINED, ASSOC_LEFT, ASSOC_NONE,
		ASSOC_RIGHT };

	char *name;
	Associativity associativity;

	Whale::Terminal *declared_at;
	bool was_implicitly_declared;

	PrecedenceSymbolData()
	{
		name=NULL;
		associativity=ASSOC_LEFT;
		declared_at=NULL;
		was_implicitly_declared=false;
	}
	void print_where_it_was_declared(std::ostream &os);
};

struct AssignmentData
{
	enum ValueType {VALUE_TRUE, VALUE_FALSE, VALUE_ID, VALUE_NUMBER,
		VALUE_STRING, VALUE_CODE};

	Whale::NonterminalOptionStatement *declaration;
	std::vector<std::pair<char *, ValueType> > parameters; // those within brackets
	std::vector<std::pair<char *, ValueType> > values; // those after the '=' sign

	AssignmentData()
	{
		declaration=NULL;
	}
};

class WhaleData
{
public:
	Whale::NonterminalS *S;

	std::vector<TerminalData> terminals;
	std::vector<NonterminalData> nonterminals;
	int start_nonterminal_number, eof_terminal_number, error_terminal_number;
	std::vector<RuleData> rules;
	std::vector<PrecedenceSymbolData> precedence_symbols;

	std::string file_name;

	bool first_computed, first_nonterminals_computed, follow_computed;

	PrecedenceDatabase precedence_database;
	LRAutomaton lr_automaton;
	std::set<LRConflictResolutionPrecedent> lr_conflict_resolution_precedents;

	std::map<char *, std::vector<AssignmentData>, NullTerminatedStringCompare> assignments;
	Variables variables;

	struct Tables
	{
	#if 0
		std::vector<int> rule_bodies;
		std::vector<int> rule_body_indices;
	#endif
		std::vector<int> lr_action;
		std::vector<IndexEntry> lr_action_indices;
		std::vector<int> lr_action_error_map;
		std::vector<IndexEntry> lr_action_error_map_indices;
		std::vector<int> lr_goto;
		std::vector<IndexEntry> lr_goto_indices;

		std::vector<ClassHierarchy::DataMember *> all_data_members;
	};

	Tables tables;

	int find_terminal(const char *s)
	{
		// time is not essential here, using plain linear searching.
		for(int i=0; i<terminals.size(); i++)
			if(!strcmp(s, terminals[i].name))
				return i;
		return -1;
	}
	int find_nonterminal(const char *s)
	{
		for(int i=0; i<nonterminals.size(); i++)
			if(!strcmp(s, nonterminals[i].name))
				return i;
		return -1;
	}
	SymbolNumber find_symbol(const char *s)
	{
		int tn=find_terminal(s);
		if(tn!=-1) return SymbolNumber::for_terminal(tn);

		int nn=find_nonterminal(s);
		if(nn!=-1) return SymbolNumber::for_nonterminal(nn);

		return SymbolNumber::error();
	}
	int find_precedence_symbol(const char *s)
	{
		for(int i=0; i<precedence_symbols.size(); i++)
			if(!strcmp(s, precedence_symbols[i].name))
				return i;

		return -1;
	}
	char *symbol_name(SymbolNumber sn)
	{
		if(sn.is_terminal())
			return terminals[sn.terminal_number()].name;
		else if(sn.is_nonterminal())
			return nonterminals[sn.nonterminal_number()].name;
		else
			return NULL;
	}
	std::string full_symbol_name(SymbolNumber sn, bool capital)
	{
		if(sn.is_terminal())
			return std::string(capital ? "Terminal " : "terminal ")+terminals[sn.terminal_number()].name;
		else if(sn.is_nonterminal())
			return std::string(capital ? "Nonterminal " : "nonterminal ")+nonterminals[sn.nonterminal_number()].name;
		else
			return std::string("(internal error)");
	}
	ClassHierarchy::Class *symbol_type(SymbolNumber sn)
	{
		if(sn.is_terminal())
			return terminals[sn.terminal_number()].type;
		else if(sn.is_nonterminal())
			return nonterminals[sn.nonterminal_number()].type;
		else
			assert(false);
	}
	ClassHierarchy::Class *get_class_assigned_to_alternative(int nn, int an)
	{
		if(nonterminals[nn].multiple_alternatives_mode)
			return nonterminals[nn].alternatives[an].type;
		else
			return nonterminals[nn].type;
	}
	AlternativeData &access_alternative(int nn, int an)
	{
		return nonterminals[nn].alternatives[an];
	}

	WhaleData();

private:
	WhaleData(const WhaleData &prototype)
	{
	}
};

extern WhaleData data;

struct TerminalNamePrinter : std::binary_function<std::ostream &, int, std::ostream &>
{
	std::ostream &operator ()(std::ostream &os, int i)
	{
		os << data.terminals[i].name;
	}
};

struct NonterminalNamePrinter : std::binary_function<std::ostream &, int, std::ostream &>
{
	std::ostream &operator ()(std::ostream &os, int i)
	{
		os << data.nonterminals[i].name;
	}
};

struct PrecedenceNamePrinter : std::binary_function<std::ostream &, int, std::ostream &>
{
	std::ostream &operator ()(std::ostream &os, int i)
	{
		os << data.precedence_symbols[i].name;
	}
};

#endif