Разработка стековой виртуальной машины и компилятора под неё (часть II)

В первой части Разработка стековой виртуальной машины и компилятора под неё (часть I) сделал свою элементарную стековую виртуальную машину, которая умеет работать со стеком, делать арифметику с целыми числами со знаком, условные переходы и вызовы функций с возвратом. Но так как целью было создать не только виртуальную машину, но и компилятор C подобного языка, пришло время сделать первые шаги в сторону компиляции. Опыта никакого. Буду действовать по разумению.

Одним из первых этапов компиляции является синтаксический анализ (parsing) исходного кода нашего «C подобного языка» (кстати, надо какое-то название дать как только он станет более формальным). Задача простая — «нарубить» массив символов (исходный код) на список классифицированных токенов, чтобы последующий разбор и компиляция не вызывали сложности.

Итак, первый шаг — определиться с типами токенов (интуитивно будем ориентироваться на синтаксис C), символами которые будут отделять токены друг от друга, а также определить структуру для хранения токена (тип, текст токена, длина, строка и столбец в исходном коде).

	constexpr char* BLANKS = "\x20\n\t"; 	constexpr char* DELIMETERS = ",;{}[]()=><+-*/&|~^!.";  	enum class TokenType { 		NONE = 0, UNKNOWN, IDENTIFIER, 		CONST_CHAR, CONST_INTEGER, CONST_REAL, CONST_STRING, 		COMMA, MEMBER_ACCESS, EOS,  		OP_BRACES, CL_BRACES, OP_BRACKETS, CL_BRACKETS, OP_PARENTHESES, CL_PARENTHESES, 		BYTE, SHORT, INT, LONG, CHAR, FLOAT, DOUBLE, STRING, IF, ELSE, WHILE, RETURN, 		ASSIGN, EQUAL, NOT_EQUAL, GREATER, GR_EQUAL, LESS, LS_EQUAL, 		PLUS, MINUS, MULTIPLY, DIVIDE, AND, OR, XOR, NOT, SHL, SHR, 		LOGIC_AND, LOGIC_OR, LOGIC_NOT 	};  	typedef struct { 		TokenType type;           		char* text;               		WORD length;              		WORD row;                 		WORD col;                 	} Token; 

Далее напишем класс для разбора, ключевым методом которого станет parseToTokens(char*). Тут алгоритм простой: идем до разделителя (BLANKS и DELIMETERS), определяем начало и конец токена, классифицируем его и добавляем в вектор (список) токенов. Особые случаи разбора — это отличать целые числа от вещественных, вещественные числа (например, «315.0«) отличать от применения оператора доступа к членам структуры/объекта («obj10.field1«), а также отличать ключевые слова от других идентификаторов.

 void VMParser::parseToTokens(const char* sourceCode) {  	TokenType isNumber = TokenType::UNKNOWN; 	bool insideString = false;                                         // inside string flag 	bool isReal = false;                                               // is real number flag 	size_t length;                                                     // token length variable  	char nextChar;                                                     // next char variable 	bool blank, delimeter;                                             // blank & delimeter char flags  	tokens->clear();                                                   // clear tokens vector 	rowCounter = 1;                                                    // reset current row counter 	rowPointer = (char*)sourceCode;                                    // set current row pointer to beginning  	char* cursor = (char*)sourceCode;                                  // set cursor to source beginning  	char* start = cursor;                                              // start new token from cursor 	char value = *cursor;                                              // read first char from cursor  	while (value != NULL) {                                            // while not end of string 		blank = isBlank(value);                                          // is blank char found? 		delimeter = isDelimeter(value);                                  // is delimeter found? 		length = cursor - start;                                         // measure token length 		     // Diffirentiate real numbers from member access operator '.' 		isNumber = identifyNumber(start, length - 1);                    // Try to get integer part of real number 		isReal = (value=='.' && isNumber==TokenType::CONST_INTEGER);     // Is current token is real number  		if ((blank || delimeter) && !insideString && !isReal) {          // if there is token separator                    			if (length > 0) pushToken(start, length);                      // if length > 0 push token to vector 			if (value == '\n') {                                           // if '\n' found  				rowCounter++;                                                // increment row counter 				rowPointer = cursor + 1;                                     // set row beginning pointer 			} 			nextChar = *(cursor + 1);                                      // get next char after cursor 			if (!blank && isDelimeter(nextChar)) {                         // if next char is also delimeter 				if (pushToken(cursor, 2) == TokenType::UNKNOWN)              // try to push double char delimeter token 					pushToken(cursor, 1);                                      // if not pushed - its single char delimeter 				else cursor++;                                               // if double delimeter, increment cursor 			} else pushToken(cursor, 1);                                   // else push single char delimeter 			start = cursor + 1;                                            // calculate next token start pointer 		} 		else if (value == '"') insideString = !insideString;             // if '"' char - flip insideString flag  		else if (insideString && value == '\n') {                        // if '\n' found inside string 			// TODO warn about parsing error 		} 		cursor++;                                                        // increment cursor pointer 		value = *cursor;                                                 // read next char 	}  	length = cursor - start;                                           // if there is a last token 	if (length > 0) pushToken(start, length);                          // push last token to vector  } 

Наряду с методом parseToTokens, помогать в разборе и классификации нам будут простые методы, определяющие разделители и тип найденного токена. Плюс метод добавления токена в вектор.

class VMParser { 	public: 		VMParser(); 		~VMParser(); 		void parseToTokens(const char* sourceCode); 		Token getToken(size_t index); 		size_t getTokenCount(); 	   private: 		vector<Token>* tokens; 		WORD rowCounter; 		char* rowPointer;    		bool isBlank(char value); 		bool isDelimeter(char value); 		TokenType pushToken(char* text, size_t length); 		TokenType getTokenType(char* text, size_t length); 		TokenType identifyNumber(char* text, size_t length); 		TokenType identifyKeyword(char* text, size_t length); 	};

Попробуем используя класс VMParser разобрать строку исходного кода C подобного языка (исходный код бессмысленный, просто набор случайных токенов для проверки разбора):

int main() {     printf ("Wow!");     float a = 365.0 * 10 - 10.0 / 2 + 3; 		while (1 != 2) { 		    abc.v1 = 'x'; 		} 		if (a >= b) return a && b; else a || b;  };

В итоге получаем в консоли следующий перечень классифицированных токенов:

Отлично, у нас есть базовый парсер. Теперь его надо как-то применить, например осуществить разбор простого арифметического выражения, а также написать компиляцию такого выражения в инструкции виртуальной машины.

Для простоты сначала реализуем компилятор арифметических выражений с целыми числами (приоритет «*» и «/» над «+» и «-» учитывается), без скобок, унарных операций и других важных вещей, в том числе проверки синтаксических ошибок. Разбор выражений напишем вот так:

void VMCompiler::parseExpression(size_t startIndex, VMImage* destImage) { 	Token tkn; 	currentToken = startIndex; 	parseTerm(destImage); 	tkn = parser->getToken(currentToken); 	while (tkn.type==TokenType::PLUS || tkn.type==TokenType::MINUS) { 		  currentToken++; 		  parseTerm(destImage); 		  if (tkn.type==TokenType::PLUS) destImage->emit(OP_ADD); else destImage->emit(OP_SUB); 		  tkn = parser->getToken(currentToken); 	} }   void VMCompiler::parseTerm(VMImage* destImage) { 	Token tkn; 	parseFactor(destImage); 	currentToken++; 	tkn = parser->getToken(currentToken); 	while (tkn.type == TokenType::MULTIPLY || tkn.type == TokenType::DIVIDE) { 		  currentToken++; 		  parseFactor(destImage); 		  if (tkn.type == TokenType::MULTIPLY) destImage->emit(OP_MUL); else destImage->emit(OP_DIV); 		  currentToken++; 		  tkn = parser->getToken(currentToken); 	} }   void VMCompiler::parseFactor(VMImage* destImage) { 	Token tkn = parser->getToken(currentToken); 	char buffer[32]; 	strncpy(buffer, tkn.text, tkn.length); 	buffer[tkn.length] = 0; 	destImage->emit(OP_CONST, atoi(buffer)); }

Попробуем скормить этому компилятору выражение «3+5*6+2*3+15/5″, запускаем компилятор с выводом скомпилированных команд и сразу запускаем виртуальную машину. Ожидаем, что результат вычисления должен остаться на вершине стека — 42.

Ура! Получилось! Первые шаги в сторону компилятора сделаны.