使用C++做一个简单的python词法分析器

用到的HashTable：

HashTable.cpp:

#ifndef _HASH_MAP
#define _HASH_MAP

#include <vector>
#include <string>
using namespace std;

int operator % (const string & text, int max) {
	int code = 0;
	for (int i = 0; i < text.size(); ++ i) {
		int code1 = text[i];
		code1 = code1 << (i * 8 % 24);
		code = code ^ code1;
	}
	return code % max;
}

class NoSuchKeyException {};

template <typename K, typename V>
class HashTable
{
private:
		
	class Entry
	{
	public:
		K key;
		V value;
		bool isInUse;
		
		Entry() {
			isInUse = false;
		}
	};
	
	Entry * entries;
	
	int capacity;
	int count;
	
	void initialize(int capacity2) {
		count = 0;
		capacity = capacity2;
		entries = new Entry[capacity];
	}
	
	void assign(const HashTable & map2) {
		count = map2.count;
		capacity = map2.capacity;
		entries = new Entry[capacity];
		for (int i = 0; i < capacity; ++ i) {
			entries[i] = map2.entries[i];
		}
	}
	
public:
	
	HashTable() {
		initialize(2);
	}
	
	~HashTable() {
		delete [] entries;
	}
	
	HashTable(const HashTable & map2) {
		assign(map2);
	}
	
	HashTable & operator = (const HashTable & map2) {
		delete [] entries;
		assign(map2);
		return (*this);
	}
	
	void clear() {
		delete [] entries;
		initialize(2);
	}
	
private:
	
	int hashIndex(const K & key) const {
		return key % capacity;
	}
	
	int find(const K & key) const {
		int index = hashIndex(key);
		while (true) {
			if (! entries[index].isInUse) {
				return index;
			}
			if (entries[index].key == key) {
				return index;
			}
			index = (index + 1) % capacity;
		}
	}
	
	void resize(int capacity2) {
		Entry * entries0 = entries;
		int capacity0 = capacity;
		initialize(capacity2);
		for (int i = 0; i < capacity0; ++ i) {
			if (entries0[i].isInUse) {
				put(entries0[i].key, entries0[i].value);
			}
		}
		delete [] entries0;
	}
	
public:
	
	void put(const K & key, const V & value) {
		int index = find(key);
		entries[index].value = value;
		if (entries[index].isInUse) return;
		
		entries[index].isInUse = true;
		entries[index].key = key;
		
		++ count;
		if (count > capacity / 2) {
			resize(capacity * 2);
		}
	}
	
	V get(const K & key) const {
		int index = find(key);
		if (! entries[index].isInUse) {
			throw NoSuchKeyException();
		}
		return entries[index].value;
	}
	
	bool remove(const K & key) {
		int index = find(key);
		if (! entries[index].isInUse) return false;
		fillNotInUseEntry(index);
		
		-- count;
		if (count < capacity / 4) {
			resize(capacity / 2);
		}
		return true;
	}
	
private:
	
	void fillNotInUseEntry(int index) {
		int next = index;
		while (true) {
			next = (next + 1) % capacity;
			if (! entries[next].isInUse) {
				entries[index].isInUse = false;
				return;
			}
			int index0 = hashIndex(entries[next].key);
			if (index < next) {
				if (index0 > index &&
					index0 <= next) continue;
			}
			else {
				if (index0 > index ||
					index0 <= next) continue;
			}
			entries[index] = entries[next];
			index = next;
		}
	}
	
public:
	
	bool containsKey(const K & key) const {
		int index = find(key);
		return (entries[index].isInUse);
	}
	
	int size() const {
		return count;
	}

	vector<K> getKeys() const {
		vector<K> vec;
		for (int i = 0; i < capacity; ++ i) {
			if (entries[i].isInUse) {
				vec.push_back(entries[i].key);
			}
		}
		return vec;
	}
	
};

#endif

用到的token.cpp

#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <stdexcept>
using namespace std;

#include <cstring>
#include "hashtable.cpp"

struct Token
{
	int line;
	int pos;
	string type;
	string text;
};

int operator % (const Token & t, int base) {
	return (t.line * 12347 + t.pos) % base;
}

bool operator == (const Token & t1, const Token & t2) {
	return t1.line == t2.line && t1.pos == t2.pos;
}

ostream & operator << (ostream & out, const Token & t) {
	out << t.line << '\t' << t.pos << '\t' << t.type << "\t\"" << t.text << "\"";
	return out;
}

void read_lines(const string & filename, vector<string> & lines) {
	ifstream in(filename.c_str());
	stringstream ss;
	ss << "Cannot open file: " << filename;
	if (in.fail()) throw runtime_error(ss.str());
	string line;
	while (getline(in, line)) {
		lines.push_back(line);
	}
	in.close();
}

int find(const string & source, const string & to_find, int start=0) {
	int len_total = source.size();
	int len = to_find.size();
	for (int i = start; i + len < len_total; ++ i) {
		if (source.compare(i, len, to_find) == 0) return i;
	}
	return -1;
}

Token make_token(int line, int pos, int len, const string & source, const string & type) {
	Token t;
	t.line = line;
	t.pos = pos;
	t.type = type;
	t.text = source.substr(pos, len);
	return t;
}

Token find_indent(int line, const string & source) {
	int len = 0;
	for (int i = 0; i < source.size(); ++ i) {
		if (source[i] == '\t')
			++ len;
		else
			break;
	}
	return make_token(line, 0, len, source, "indent");
}

Token find_blank(int line, const string & source, int start) {
	int len = 0;
	for (int i = start; i < source.size(); ++ i) {
		if (source[i] == '\t' || source[i] == ' ')
			++ len;
		else
			break;
	}
	return make_token(line, start, len, source, "blank");
	
}

Token find_string(int line, const string & source, int start) {
	int len = 0;
	bool was_backslash = false;
	for (int i = start; i < source.size(); ++ i) {
		char c = source[i];
		if (i == start) {
			if (c == '"') ++ len;
			else break;
		}
		else {
			if (was_backslash) {
				if (c == '\\' || c == 'r' || c == 'n' ||
					c == 't' || c == '"')
					++ len;
				else break;
				was_backslash = false;
			}
			else {
				if (c == '"') {
					++ len;
					break;
				}
				++ len;
				was_backslash = (c == '\\');
			}
		} 
	}
	return make_token(line, start, len, source, "string");	
}

Token find_int(int line, const string & source, int start) {
	int len = 0;
	for (int i = start; i < source.size(); ++ i) {
		if ((i != start && source[i] >= '0' && source[i] <= '9' ) ||
			(source[i] >= '1' && source[i] <= '9'))
			++ len;
		else
			break;
	}
	return make_token(line, start, len, source, "int");	
}

Token find_id(int line, const string & source, int start) {
	int len = 0;
	for (int i = start; i < source.size(); ++ i) {
		if ((i != start && source[i] >= '0' && source[i] <= '9') ||
			(source[i] >= 'A' && source[i] <= 'Z') ||
			(source[i] >= 'a' && source[i] <= 'z') ||
			source[i] == '_')
			++ len;
		else
			break;
	}
	return make_token(line, start, len, source, "id");
}

const char *keywords[] = {
	"def", "(", ")", ":", "if", "else", "for", "in", "+", "-", "*", "/", "%"
};

Token find_keyword(int line, const string & source, int start) {
	int keyword = -1;
	for (int i = 0; i < sizeof(keywords) / sizeof(const char *); ++ i) {
		if (source.compare(start, strlen(keywords[i]), keywords[i]) == 0)
			keyword = i;
	}
	if (keyword == -1)
		return make_token(line, start, 0, source, "keyword");
	return make_token(line, start, strlen(keywords[keyword]), source, "keyword");	
}

Token find_comment(int line, const string & source, int start) {
	int len = 0;
	for (int i = start; i < source.size(); ++ i) {
		if (i != start || source[i] == '#')
			++ len;
		else
			break;
	}
	return make_token(line, start, len, source, "comment");

}

typedef Token (* find_function)(int, const string &, int);

void add_tokens(HashTable<Token, Token> & tokens, int lineno, const string & line, find_function find, bool can_conflict) {
	int start = 0;
	while (start < line.size()) {
		Token t = find(lineno, line, start);
		if (t.text.size() > 0) {
			if (can_conflict) {
				if (tokens.containsKey(t)) {
					Token old_t = tokens.get(t);
					if (old_t.text.size() < t.text.size())
						tokens.put(t, t);
				}
				else {
					tokens.put(t, t);
				}
			}
			else {
				if (tokens.containsKey(t)) {
					Token old_t = tokens.get(t);
					stringstream ss;
					ss << "Conflicting tokens:" << endl;
					ss << old_t << endl;
					ss << t << endl;
					throw runtime_error(ss.str());
				}
				tokens.put(t, t);
			}
			start += t.text.size();
		}
		else
			++ start;
	}
}

void get_tokens(const string & filename, vector<vector<Token> > & tokens) {
	vector<string> lines;
	read_lines(filename, lines);
	HashTable<Token, Token> all_tokens;
	for (int i = 0; i < lines.size(); ++ i) {
		Token indent = find_indent(i, lines[i]);
		if (indent.text.size() > 0)
			all_tokens.put(indent, indent);
		add_tokens(all_tokens, i, lines[i], find_string, false);
		add_tokens(all_tokens, i, lines[i], find_int, false);
		add_tokens(all_tokens, i, lines[i], find_comment, false);
		add_tokens(all_tokens, i, lines[i], find_keyword, false);
		add_tokens(all_tokens, i, lines[i], find_id, true);
		add_tokens(all_tokens, i, lines[i], find_blank, true);
	}
	Token index;
	for (int i = 0; i < lines.size(); ++ i) {
		tokens.push_back(vector<Token>());
		index.line = i;
		index.pos = 0;
		while (index.pos < lines[i].size()) {
			if (! all_tokens.containsKey(index)) {
				stringstream ss;
				ss << "Lexical error at line #" << (index.line + 1) << " char #" << index.pos;
				throw runtime_error(ss.str());
			}
			Token t = all_tokens.get(index);
			if (t.type != "blank")
				tokens[i].push_back(t);
			index.pos += t.text.size();
		}
	}
}

int main() {
	vector<vector<Token> > tokens;
	get_tokens("test.py", tokens);
	for (int i = 0; i < tokens.size(); ++ i)
		for (int j = 0; j < tokens[i].size(); ++ j)
			cout << tokens[i][j] << endl;
}

测试的python：
test.py

# this is a comment

def test_loop(n):
	for i in range(n):
		print(100 + i)

def test_condition(c):
	if c and True:
		print("yes, I'd a coffee")
	else:
		print("no\r\t\n\\\"")

test_loop(10)
test_condition(False)