В первой части Разработка стековой виртуальной машины и компилятора под неё (часть 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 flagbool isReal = false; // is real number flagsize_t length; // token length variablechar nextChar; // next char variablebool blank, delimeter; // blank & delimeter char flagstokens->clear(); // clear tokens vectorrowCounter = 1; // reset current row counterrowPointer = (char*)sourceCode; // set current row pointer to beginningchar* cursor = (char*)sourceCode; // set cursor to source beginning char* start = cursor; // start new token from cursorchar value = *cursor; // read first char from cursorwhile (value != NULL) { // while not end of stringblank = 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 numberisReal = (value=='.' && isNumber==TokenType::CONST_INTEGER); // Is current token is real numberif ((blank || delimeter) && !insideString && !isReal) { // if there is token separator if (length > 0) pushToken(start, length); // if length > 0 push token to vectorif (value == '\n') { // if '\n' found rowCounter++; // increment row counterrowPointer = cursor + 1; // set row beginning pointer}nextChar = *(cursor + 1); // get next char after cursorif (!blank && isDelimeter(nextChar)) { // if next char is also delimeterif (pushToken(cursor, 2) == TokenType::UNKNOWN) // try to push double char delimeter tokenpushToken(cursor, 1); // if not pushed - its single char delimeterelse cursor++; // if double delimeter, increment cursor} else pushToken(cursor, 1); // else push single char delimeterstart = 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 pointervalue = *cursor; // read next char}length = cursor - start; // if there is a last tokenif (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; };
В итоге получаем в консоли следующий перечень классифицированных токенов:
Результат разбора исходного кода C подобного языка
Отлично, у нас есть базовый парсер. Теперь его надо как-то
применить, например осуществить разбор простого арифметического
выражения, а также написать компиляцию такого выражения в
инструкции виртуальной машины.
Для простоты сначала реализуем компилятор арифметических выражений
с целыми числами (приоритет "*" и "/" над "+" и "-" учитывается),
без скобок, унарных операций и других важных вещей, в том числе
проверки синтаксических ошибок. Разбор выражений напишем вот
так:
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.
Ура! Получилось! Первые шаги в сторону компилятора сделаны.
