[C++, Виртуализация, Компиляторы, C] Разработка стековой виртуальной машины и компилятора под неё (часть II)
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
В первой части Разработка стековой виртуальной машины и компилятора под неё (часть 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;
};
В итоге получаем в консоли следующий перечень классифицированных токенов:
Результат разбора исходного кода 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.
Ура! Получилось! Первые шаги в сторону компилятора сделаны.
===========
Источник:
habr.com
===========
Похожие новости:
- [Программирование] Вышел MPS 2021.1
- [Программирование, C++, Работа с 3D-графикой, Разработка игр, CGI (графика)] Vulkan. Руководство разработчика. Проходы рендера (Render passes) (перевод)
- [Машинное обучение, Здоровье, Natural Language Processing] Тематическое исследование распознавания именованных сущностей в биомедицине (перевод)
- [Анализ и проектирование систем, CAD/CAM, Производство и разработка электроники, Электроника для начинающих] Ускорение проектирования РЧ-, СВЧ-устройств (3/5)
- [Программирование, C++] Почти безопасные: пару слов о псевдо-нормальных числах с плавающей запятой (перевод)
- [Высокая производительность, Управление разработкой, Agile, IT-компании] Как масштабировать разработку при 400 000 RPM и не надорваться
- [Высокая производительность, DevOps, Микросервисы, Kubernetes] Заболел – не значит умер
- [Информационная безопасность, Серверное администрирование, Хранение данных, Удалённая работа] Обучающие вебинары Dell Technologies: новые серверы, VDI, хранение и защита данных, модернизация ЦОД, удалённая работа
- [Высокая производительность, Веб-дизайн, Визуализация данных, Дизайн] Топ-5 софт-навыков дизайнера в банке
- [Космонавтика, Будущее здесь] Генри Форд в космосе: как стартап Phantom Space разрабатывает новую модель запусков (перевод)
Теги для поиска: #_c++, #_virtualizatsija (Виртуализация), #_kompiljatory (Компиляторы), #_c, #_virtualnaja_mashina (виртуальная машина), #_kompiljatory (компиляторы), #_hobbi (хобби), #_c++, #_virtualizatsija (
Виртуализация
), #_kompiljatory (
Компиляторы
), #_c
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 23-Ноя 05:58
Часовой пояс: UTC + 5
Автор | Сообщение |
---|---|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
В первой части Разработка стековой виртуальной машины и компилятора под неё (часть 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; 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 } 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); }; 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)); } Ура! Получилось! Первые шаги в сторону компилятора сделаны. =========== Источник: habr.com =========== Похожие новости:
Виртуализация ), #_kompiljatory ( Компиляторы ), #_c |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 23-Ноя 05:58
Часовой пояс: UTC + 5