Crafting Interpreters
Запись от Loafer размещена 30.03.2024 в 18:14
Показов 2071
Комментарии 21
Прочитал наконец-то большую книгу по программированию за долгое время - Crafting Interpreters. Если вкратце, то книга про то, как создаются языки программирования. По факту, в книге реализуется язык программирования, который автор назвал Lox, двумя способами - интерпретируемый язык на основе AST, и управляемый язык на основе виртуальной машины. Особенностью книги является то, что ЯП реализуется полностью с нуля, не прибегая ко всякого рода внешним утилитам, вроде yacc или lex. Она очень дружелюбна к новичкам в области построения ЯП, не пестрит каким-то большим количеством формул или сложной теории и написана очень хорошим и понятным языком. Книга требует вдумчивого многомесячного чтения. Некоторые основные вещи из книги:
|
Размещено в Без категории
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Всего комментариев 21
Комментарии
-
Запись от XLAT размещена 31.03.2024 в 17:25 -
Запись от DrType размещена 31.03.2024 в 17:29 -
Сообщение от XLAT
Запись от Loafer размещена 01.04.2024 в 14:49 -
Сообщение от DrType
В книге реализуется динамический ЯП. При создании же статического ЯП, придется проверку типов вынести на этап компиляции, а также запретить переменным менять свой тип во время работы программы.Запись от Loafer размещена 01.04.2024 в 14:51 -
Сообщение от Loafer
ну, не за раз, а за несколько подходов(т.е. в несколько вечеров), скажем, по часу(±), шоп не сильно вспотеть.
я эту книгу не читал, но мне интересно, что может получиться.
если что, я помогу, чем смогу.
Калькулятор должен вычислять типа такого:
ну, как?Code 1 2 3 4 5
/// Пример выражения: - ((sin(10 + 10*3))+(pow(2,3) *((10+6) / 2)) *(2 & 15)) /// & - это побитовое умножение. /// и всякие логические тоже чтобы можно было ЛЕГКО добавить.
Запись от XLAT размещена 02.04.2024 в 10:59 -
пара слов по требованию к калькулятору в кодировании и юзанию:
1.
К чёрту преждевременную оптимизацию: объединять разные задачи в один метод плохой стиль.
Например, на верхнем этаже есть такие задачи:
- парсинг
- генератор дерева.
- тестирование.
- создание внешнего апи(пусть это громко звучит, даже если это будет один метод)
2.
Калькулятор должен быть устойчив: иметь защиту от дурного ввода, т.е. находить ошибку и адекватно реагировать.
Например, выдавать юзеру сообщение об ошибке в веденном им выражении.
3.
Подсвечивать место с ошибкой.
4.
Легко добавлять новые функции и операции: ...
5.
Разумеется, проходить все предложенные тесты.
6.
Уметь использовать переменные аргументы без повторного парсинга.
Например, для рисовки графиков.
7.
Задокументированное внешнее апи. Само апи лаконичное и простое в использовании.
8.
... что-то ещё, но щас забыл ...
Возможно, упрощенный синтаксис без символа умножения, типа 2(3+4) ?
Для затравки начало, типа таск-листа:
C++ 1 2 3 4 5
///----------------------------------------------------------------------------| /// Калькулятор-2024, C++17 /// (-) парсер /// (-) дерево ///----------------------------------------------------------------------------:
Парсер.
1.
Есть класс токена:
2.C++ 1 2 3 4 5 6 7
struct Token : std::string_view { Token ( std::string_view s, size_t pos) : ... ... void debug(){...} void test (){...} };
Есть класс токенов:
C++ 1 2 3 4 5 6 7
struct Tokens : std::vector<Token> { Tokens(std::string_view _expr) : ... ... void debug(){...} void test (){...} };
Дерево.
...
Заюзать абстрактные классы.
- любой токен это узел. т.е. имеет абстрактный интерфейс узла.
- некоторые узлы(унаследованные) это листья(т.е. уже принесенные вместе с выражением извне готовые числа)
- остальные узлы - вычислители ссылающиеся на листья или другие вычислители.
ок.
пока хватит, 2 дня пишем только парсер(черновик).Запись от XLAT размещена 03.04.2024 в 01:36 -
Запись от XLAT размещена 04.04.2024 в 12:03 -
1. добавил централизованное хранение грамматик чтобы можно начать тестить.
2. начала выращивания дерева.C++ 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267
#define C calculate() #define G Grammar #define F [](vecnp_t a) std::vector<Grammar> grammar { { "+", 6, G::OPERATION, F{ return a[0]->C + a[1]->C; } }, { "-", 6, G::OPERATION, F{ return a[0]->C - a[1]->C; } }, { "*", 5, G::OPERATION, F{ return a[0]->C * a[1]->C; } }, { "/", 5, G::OPERATION, F{ return a[0]->C / a[1]->C; } }, { "&", 11, G::OPERATION, F{ return size_t(a[0]->C) & size_t(a[1]->C);}}, { "&&", 14, G::OPERATION, F{ return size_t(a[0]->C) && size_t(a[1]->C);}}, {"sin", 3, G::FUNCTION , F{ return sin( a[0]->C); } }, {"pow", 3, G::FUNCTION , F{ return pow( a[0]->C , a[1]->C); } } }; #undef C #undef G #undef F
Интерфейс узла(ветки) дерева:
пока начало, без скобок и тп..C++ 75 76 77 78 79 80 81 82 83 84
struct Token; struct Node { Node(const Token* _t) : t(_t) {} virtual ~Node(){} virtual double calculate( ) = 0; virtual void add_arg (Node*) = 0; const Token* t; };
ver: 0.1.1
https://onlinegdb.com/L-fY2SjhXZ
текущие тесты:Code 1 2 3 4 5 6 7 8 9 10 11
TESTCLASS::Calculator: ///----------------------------------------| /// ГОТОВО. | ///----------------------------------------: 1+11 -20 = -8 : ОТЛИЧНО 3*40 / 3 + 20+100 = 160 : ОТЛИЧНО 1+2+3+4.123+5.123 = 15.246 : ОТЛИЧНО ///----------------------------------------| /// TODO ... | ///----------------------------------------: 4 + 5 * 3 + 1 = 28 : ПЛОХО
Запись от XLAT размещена 04.04.2024 в 19:13 -
ver: 0.1.2
https://onlinegdb.com/fYQLuO5uX
out
Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
///-------------------------------------------------------------| /// ГОТОВО(Успешная калькуляция). | ///-------------------------------------------------------------: 2024 = 2024 : ОТЛИЧНО 1+11 -20 = -8 : ОТЛИЧНО 3*40 / 3 + 20-100 = -40 : ОТЛИЧНО 1-2+3-4.123+5.123 = 3 : ОТЛИЧНО 4 + 5 * 3 + 1 + sin(100) = 19.4936 : ОТЛИЧНО 4+5 *3 + 4* 6 - 100/25 = 39 : ОТЛИЧНО 100 - sin(100) + pow(2,4) +19 = 135.506 : ОТЛИЧНО (4 + 5) * (3 + 6) = 81 : ОТЛИЧНО pow(5+4, 0.3*0.3) = 1.21866 : ОТЛИЧНО 2024 +(777 + (1 & 2)) = 2801 : ОТЛИЧНО pow(5+4, sin((2+3)*4)) = 7.43312 : ОТЛИЧНО 1&&1 + 2 = 1 : ОТЛИЧНО ///-------------------------------------------------------------| /// TODO ... | ///-------------------------------------------------------------: s.data() = -2024
осталось сделать унарный минус.Запись от XLAT размещена 05.04.2024 в 23:26 -
ver: 0.1.3
https://onlinegdb.com/hfMnUgexQ
outCode 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
///-------------------------------------------------------------| /// ГОТОВО(Успешная калькуляция). | ///-------------------------------------------------------------: 2024 = 2024 : ОТЛИЧНО -2025 = -2025 : ОТЛИЧНО (-202.6E-10) = -2.026e-08 : ОТЛИЧНО fabs(-1.23) = 1.23 : ОТЛИЧНО -(fabs(-2.5)) = -2.5 : ОТЛИЧНО -1+11 -20 = -10 : ОТЛИЧНО 3*40 / 3 + 20-100 = -40 : ОТЛИЧНО 1-2+3-4.123+5.123 = 3 : ОТЛИЧНО 4 + 5 * 3 + 1 + sin(100) = 19.4936 : ОТЛИЧНО 4+5 *3 + 4* 6 - 100/25 = 39 : ОТЛИЧНО 100 - sin(100) + pow(2,4) +19 = 135.506 : ОТЛИЧНО (4 + 5) * (3 + 6) = 81 : ОТЛИЧНО pow(5+4, 0.3*0.3) = 1.21866 : ОТЛИЧНО 2024 +(777 + (1 & 2)) = 2801 : ОТЛИЧНО pow(5+4, cos((2+3)*4)) = 2.45137 : ОТЛИЧНО 1&&1 + 2 = 1 : ОТЛИЧНО (2&&2) + 2 = 3 : ОТЛИЧНО (2&2) + 2 = 4 : ОТЛИЧНО -5+(-3+6)-3.14e3+42.5e-1 = -3137.75 : ОТЛИЧНО - ((sin (-18.7e-2+3.3*3))+(pow(2+1.1,3) *((10+6) /2))*(2&15)) = -476.372 : ОТЛИЧНО
далее, написать тест для переменных...Запись от XLAT размещена 06.04.2024 в 14:04 -
ver: 0.1.4
https://onlinegdb.com/EXEOKlKQn
пример, как используются переменные:
кусок кодаC++ 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084
static void testvars() { BANNER(L"", L"///-------------------------------------------------------------|", L"/// VARS(Переменные). |", L"///-------------------------------------------------------------:"); #define EXPR x * x - 1 * z const char* expr{"x * x - 1 * z"}; std::wcout << "y(x,z) = " << expr << "\n\n"; try { Calculator calc(expr); double x = -2.0; double z = 0.0; if(calc.bindvar ("x", &x)) { std::wcout << LR"(bindvar "x" УСПЕШНО)" << '\n'; } if(calc.bindvar ("z", &z)) { std::wcout << LR"(bindvar "z" УСПЕШНО)" << '\n'; } std::wcout << std::setw(14) << "X" << std::setw(14) << "Z" << std::setw(16) << "Y(X,Z)" << '\n'; for(; x <= 2.0; x+=0.2, z +=0.1) { double result = calc.go( ); std::wcout << "y(" << std::setw(12) << x << ", " << std::setw(12) << z << ") = " << std::setw(12) << result << std::setw(12) << (EXPR == result ? L"ОТЛИЧНО" : L"ПЛОХО") << '\n'; } } catch(const EXEPTION_USER & e) { wl(expr) std::wcout << "\nERROR_USER: " << e << "\n\n"; } #undef EXPR }
outCode 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
///-------------------------------------------------------------| /// VARS(Переменные). | ///-------------------------------------------------------------: y(x,z) = x * x - 1 * z bindvar "x" УСПЕШНО bindvar "z" УСПЕШНО X Z Y(X,Z) y( -2, 0) = 4 ОТЛИЧНО y( -1.8, 0.1) = 3.14 ОТЛИЧНО y( -1.6, 0.2) = 2.36 ОТЛИЧНО y( -1.4, 0.3) = 1.66 ОТЛИЧНО y( -1.2, 0.4) = 1.04 ОТЛИЧНО y( -1, 0.5) = 0.5 ОТЛИЧНО y( -0.8, 0.6) = 0.04 ОТЛИЧНО y( -0.6, 0.7) = -0.34 ОТЛИЧНО y( -0.4, 0.8) = -0.64 ОТЛИЧНО y( -0.2, 0.9) = -0.86 ОТЛИЧНО y(-2.77556e-16, 1) = -1 ОТЛИЧНО y( 0.2, 1.1) = -1.06 ОТЛИЧНО y( 0.4, 1.2) = -1.04 ОТЛИЧНО y( 0.6, 1.3) = -0.94 ОТЛИЧНО y( 0.8, 1.4) = -0.76 ОТЛИЧНО y( 1, 1.5) = -0.5 ОТЛИЧНО y( 1.2, 1.6) = -0.16 ОТЛИЧНО y( 1.4, 1.7) = 0.26 ОТЛИЧНО y( 1.6, 1.8) = 0.76 ОТЛИЧНО y( 1.8, 1.9) = 1.34 ОТЛИЧНО y( 2, 2) = 2 ОТЛИЧНО
далее АПИ на юзверя(который тоже погромист)...Запись от XLAT размещена 06.04.2024 в 17:20 -
ver: 0.1.5
https://onlinegdb.com/3iM_hn80B
это последний пример в онлайн-компиляторе,
потому что переход в многофайловость(явился народу хедер).
файл: "API_calculator.hpp"
апиC++ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148
inline const wchar_t* LOGO = LR"(ver: 0.1.5 [Дем☺] ///----------------------------------------------------------------------------| /// Калькулятор-2024:Апрель, C++17 /// (+) Парсер /// (+) Дерево ///----------------------------------------------------------------------------: )"; ///-----------------| /// Этапы: | /// (-) Демо | /// (+) Релиз | ///-----------------| //#define DEF_DEMO ///<---! #define DEF_LIB #include <iostream> #include <iomanip> #include <string> ... ///----------------------------------------------------------------------------| /// Исключения, два типа: /// 1. Фатальные(исправлять должен разраб --> выход из программы). /// 2. Юзерские (исправлять должен пользователь --> ожидание ввода). ///----------------------------------------------------------------------------: class _EXEPTION_CLASS_FATAL{}; class _EXEPTION_CLASS_USER {}; template<class T> struct exString : std::wstring { exString ( std::wstring s, std::string file, int line) { std::wstring report(std::wstring&, std::string&, int ); (std::wstring)(*this) = report( s, file, line); } ///---------------| /// what. | ///---------------: std::wstring& what() const { return *this; } }; #define EXEPTION_FATAL exString<_EXEPTION_CLASS_FATAL> #define EXEPTION_USER exString<_EXEPTION_CLASS_USER > ///-------------------------------------| /// Методы перечислены в том порядке в | /// котором они должны вызываться. | ///-------------------------------------: struct Calculator; struct API_calculator { ///---------------------------------| /// Регистрация имени переменной | /// в конфиге. | ///---------------------------------: static void regvar2config(std::string_view varname); ///---------------------------------| /// Создание объекта Калькулятора. | /// (можно вызывать повторно, | /// если парсинг строки не удался).| ///---------------------------------: void recreate(std::string_view expression); ///---------------------------------| /// Парсинг и построение дерева. | ///---------------------------------: void build(); ///---------------------------------| /// Связываем внешнюю переменную. | ///---------------------------------: bool bindvar (std::string_view varname, double* var); ///---------------------------------| /// Вычисляем. | ///---------------------------------: double go() const; ///---------------------------------| /// Пример использования-01. | ///---------------------------------: static void example_01() { BANNER(L"", L"///-------------------------------------------------------------|", L"/// Пример-01 использования(Переменные). |", L"///-------------------------------------------------------------:"); #define EXPR x * x - 1.5 * z const char* expr{"x * x - 1.5 * z"}; std::wcout << "y(x,z) = " << expr << "\n\n"; try { API_calculator calc; calc.recreate(expr); calc.build ( ); double x = -2.0; double z = 0.0; if(calc.bindvar ("x", &x)) { std::wcout << LR"(bindvar "x" УСПЕШНО)" << '\n'; } if(calc.bindvar ("z", &z)) { std::wcout << LR"(bindvar "z" УСПЕШНО)" << '\n'; } std::wcout << std::setw(14) << "X" << std::setw(14) << "Z" << std::setw(16) << "Y(X,Z)" << '\n'; for(; x <= 2.0; x += 0.2, z += 0.1) { double result = calc.go(); std::wcout << "y(" << std::setw(12) << x << ", " << std::setw(12) << z << ") = " << std::setw(12) << result << std::setw(12) << (EXPR == result ? L"ОТЛИЧНО" : L"ПЛОХО") << '\n'; } } catch(const EXEPTION_USER & e) { std::wcout << "expr = " << expr << '\n'; std::wcout << "\nERROR_USER: " << e << "\n\n"; } #undef EXPR } private: Calculator* calc = nullptr; }; /*============================================================================*/
Запись от XLAT размещена 06.04.2024 в 22:25 -
скомпилил стат. либу, создал новый проект, подключил апи-хедер + либу, дефолтный пример-01:
C++ 1 2 3 4 5 6 7 8 9 10 11
#include "API_calculator.hpp" int main() { std::wcout << L"Hello world!" << std::endl; API_calculator::example_01(); std::cin.get(); return 0; }
outCode 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
Hello world! ///-------------------------------------------------------------| /// Пример-01 использования(Переменные). | ///-------------------------------------------------------------: y(x,z) = x * x - 1.5 * z bindvar "x" УСПЕШНО bindvar "z" УСПЕШНО X Z Y(X,Z) y( -2, 0) = 4 ОТЛИЧНО y( -1.8, 0.1) = 3.09 ОТЛИЧНО y( -1.6, 0.2) = 2.26 ОТЛИЧНО y( -1.4, 0.3) = 1.51 ОТЛИЧНО y( -1.2, 0.4) = 0.84 ОТЛИЧНО y( -1, 0.5) = 0.25 ОТЛИЧНО y( -0.8, 0.6) = -0.26 ОТЛИЧНО y( -0.6, 0.7) = -0.69 ОТЛИЧНО y( -0.4, 0.8) = -1.04 ОТЛИЧНО y( -0.2, 0.9) = -1.31 ОТЛИЧНО y(-2.77556e-16, 1) = -1.5 ОТЛИЧНО y( 0.2, 1.1) = -1.61 ОТЛИЧНО y( 0.4, 1.2) = -1.64 ОТЛИЧНО y( 0.6, 1.3) = -1.59 ОТЛИЧНО y( 0.8, 1.4) = -1.46 ОТЛИЧНО y( 1, 1.5) = -1.25 ОТЛИЧНО y( 1.2, 1.6) = -0.96 ОТЛИЧНО y( 1.4, 1.7) = -0.59 ОТЛИЧНО y( 1.6, 1.8) = -0.14 ОТЛИЧНО y( 1.8, 1.9) = 0.39 ОТЛИЧНО y( 2, 2) = 1 ОТЛИЧНО
далее десктопная формочка с этой библой.Запись от XLAT размещена 06.04.2024 в 22:25 -
Запись от XLAT размещена 09.04.2024 в 13:02 -
Запись от CoderHuligan размещена 10.04.2024 в 10:33 -
Сообщение от CoderHuligan
беру си,
там, к примеру, реализовываю структуру:
struct str_view{ char* s; int size;};
сразу вопрос,
почему бы мне СРАЗУ НЕ ВЗЯТЬ ТАКУЮ, УЖЕ ГОТОВУЮ std::string_view в С++?
единственный ответ:
я не беру готовое, потому что я садомазохист.
и таких примеров можно привести 100500 штук.
2.
Сообщение от CoderHuligan
и 95% занимает дерево.
3.
Сообщение от CoderHuligan
поэтому, хорошо бы переписать на чем-нить кроссовом.Запись от XLAT размещена 11.04.2024 в 09:39 -
Запись от CoderHuligan размещена 11.04.2024 в 10:43 -
Запись от CoderHuligan размещена 11.04.2024 в 10:48 -
Сообщение от CoderHuligan
всё узнал про парсеры, а код написать забыл))
Сообщение от CoderHuligan
но декомпозиция есть декомпозиция - вещи НУЖНО называть своими именами:
(зачем нужно? чтобы в голове бардака было меньше))
https://ru.wikipedia.org/wiki/... анализатор
не надо дерево называть парсером.
я могу прокалькулировать строку и без билда дерева,
и таких калькуляторов я тут - на форуме уже видел достаточно.
Сообщение от CoderHuligan
Первым делом нужно понять, а зачем ваще вам ваш парсер?
Сообщение от CoderHuligan
например, для такого прожекта:
https://www.cyberforum.ru/game... 34829.html
там должен быть:
- интерпретатор,
- редактор блок-сехмы,
- конвертер блокосхемы в интерпретируемую строку,
но самое главное, это понять, в какие задачи этот интерпретатор должен вкладываться.
Не по теме:
хотя, если хотца шоп было дюже мощно, можно сразу взять LUA или AS...
Сообщение от CoderHuligan
- рекурсия.
- через программный стек.
у мя рекурсия.
Сообщение от CoderHuligan
1. есть конкретные задачи в требованиях которых пофик Си или С++
2. но на С++ проще, поэтому С++.
3. а свой парсер, шоп иметь над ним ПОЛНЫЙ КОНТРОЛЬ, потому что имеется полное понимание, как оно работает.Запись от XLAT размещена 11.04.2024 в 11:11 -
Запись от XLAT размещена 12.04.2024 в 17:28