===== Кейс 017: Полноценный мини-язык программирования (gram:case-017) ===== === Общая информация === ^ Уровень сложности ^ 🔴 Эксперт ^ ^ Рекомендуемые языки ^ C++, Rust ^ ^ Основные инструменты ^ ANTLR4, LLVM, Flex/Bison (опционально) ^ ^ Требуемые знания ^ Продвинутое программирование, системы типов, управление памятью ^ === Описание кейса === Разработка полноценного статически типизированного языка программирования с поддержкой: - функций и рекурсии - пользовательских типов данных - системы модулей - базовых структур управления - сборки мусора или ручного управления памятью === Грамматика языка === ==== Лексические токены ==== // Ключевые слова LET : 'let' FUNC : 'func' STRUCT : 'struct' IMPORT : 'import' IF : 'if' ELSE : 'else' WHILE : 'while' RETURN : 'return' TRUE : 'true' FALSE : 'false' // Типы INT_TYPE : 'int' FLOAT_TYPE: 'float' BOOL_TYPE : 'bool' STRING_TYPE: 'string' VOID_TYPE : 'void' // Идентификаторы и литералы ID : [a-zA-Z_][a-zA-Z_0-9]* INT_LIT : [0-9]+ FLOAT_LIT : [0-9]+ '.' [0-9]+ STRING_LIT: '"' (~["\\] | '\\' .)* '"' // Операторы и разделители PLUS : '+' MINUS : '-' MUL : '*' DIV : '/' ASSIGN : '=' EQ : '==' NEQ : '!=' LT : '<' GT : '>' LEQ : '<=' GEQ : '>=' AND : '&&' OR : '||' NOT : '!' LPAREN : '(' RPAREN : ')' LBRACE : '{' RBRACE : '}' LBRACKET : '[' RBRACKET : ']' COMMA : ',' COLON : ':' SEMI : ';' ARROW : '->' WS : [ \t\r\n]+ -> skip COMMENT : '//' ~[\r\n]* -> skip BLOCK_COMMENT: '/*' .*? '*/' -> skip ==== Синтаксические правила ==== program : (import_stmt | struct_def | func_def)* EOF import_stmt : IMPORT STRING_LIT SEMI struct_def : STRUCT ID LBRACE (field_decl SEMI)* RBRACE field_decl : ID COLON type func_def : FUNC ID LPAREN params? RPAREN (ARROW type)? block params : param (COMMA param)* param : ID COLON type type : base_type | struct_type | array_type base_type : INT_TYPE | FLOAT_TYPE | BOOL_TYPE | STRING_TYPE | VOID_TYPE struct_type : ID array_type : base_type LBRACKET RBRACKET block : LBRACE statement* RBRACE statement : var_decl | assignment | if_stmt | while_stmt | return_stmt | expr SEMI var_decl : LET ID (COLON type)? ASSIGN expr SEMI assignment : ID ASSIGN expr SEMI if_stmt : IF expr block (ELSE (if_stmt | block))? while_stmt : WHILE expr block return_stmt : RETURN expr? SEMI expr : logic_or logic_or : logic_and (OR logic_and)* logic_and : equality (AND equality)* equality : comparison ((EQ | NEQ) comparison)* comparison : term ((LT | GT | LEQ | GEQ) term)* term : factor ((PLUS | MINUS) factor)* factor : unary ((MUL | DIV) unary)* unary : (NOT | MINUS)? primary primary : literal | ID | call_expr | field_access | index_expr | LPAREN expr RPAREN literal : INT_LIT | FLOAT_LIT | STRING_LIT | TRUE | FALSE call_expr : ID LPAREN (expr (COMMA expr)*)? RPAREN field_access: primary '.' ID index_expr : primary LBRACKET expr RBRACKET === План лабораторных работ === ==== Лабораторная 1: Лексический и базовый синтаксический анализ ==== **Задачи:** - Реализовать полную грамматику токенов - Создать лексический анализатор с поддержкой комментариев - Реализовать парсер для объявлений функций и структур - Обработать вложенные блоки и выражения **Тестовые примеры:** struct Point { x: int; y: int; } func distance(p1: Point, p2: Point) -> float { let dx = p1.x - p2.x; let dy = p1.y - p2.y; return sqrt(dx*dx + dy*dy); } **Результат:** Парсер, способный разбирать сложные конструкций языка. ==== Лабораторная 2: Построение AST и семантический анализ ==== **Задачи:** - Спроектировать иерархию классов AST - Реализовать построение полного AST - Создать систему символов (таблицы символов) - Реализовать проверку типов для всех конструкций **Функции проверки:** - Контроль областей видимости - Вывод и проверка типов выражений - Валидация вызовов функций - Проверка соответствия возвращаемых типов **Результат:** Семантически проверенное AST с полной информацией о типах. ==== Лабораторная 3: Промежуточное представление и оптимизации ==== **Задачи:** - Спроектировать промежуточное представление (IR) - Реализовать трансляцию AST в IR - Внедрить базовые оптимизации: - удаление мертвого кода - постоянное свертывание - inline простых функций - Реализовать управление памятью (стек/куча) **Результат:** Оптимизированное промежуточное представление программы. ==== Лабораторная 4: Генерация машинного кода и runtime ==== **Задачи:** - Интеграция с LLVM для генерации кода - Реализация runtime-библиотеки - Поддержка системных вызовов и ввода-вывода - Создание системы сборки и пакетного менеджера **Особенности реализации:** - Генерация эффективного машинного кода - Поддержка вызовов внешних функций (FFI) - Реализация базовой стандартной библиотеки **Результат:** Полноценный компилятор, способный компилировать и исполнять программы. === Расширенные возможности === Для достижения экспертного уровня рекомендуется реализовать: - **Система типов:** дженерики, алгебраические типы данных, type inference - **Метапрограммирование:** макросы, шаблоны, compile-time вычисления - **Параллелизм:** async/await, корутины, модель акторов - **Инструменты:** отладчик, профилировщик, REPL-окружение - **Оптимизации:** автоматическая векторизация, межпроцедурный анализ === Примеры реализации === ==== Архитектура проекта ==== minilang/ ├── src/ │ ├── compiler/ │ │ ├── lexer/ // Лексический анализ │ │ ├── parser/ // Синтаксический анализ │ │ ├── ast/ // Абстрактное синтаксическое дерево │ │ ├── semantic/ // Семантический анализ │ │ ├── ir/ // Промежуточное представление │ │ └── codegen/ // Генерация кода │ ├── runtime/ // Runtime-библиотека │ │ ├── gc/ // Сборка мусора │ │ ├── stdlib/ // Стандартная библиотека │ │ └── ffi/ // Внешние интерфейсы │ └── tools/ │ ├── debugger/ // Отладчик │ ├── repl/ // Интерактивная среда │ └── package/ // Менеджер пакетов ├── grammar/ │ ├── MiniLangLexer.g4 │ └── MiniLangParser.g4 ├── tests/ │ ├── unit/ // Модульные тесты │ ├── integration/ // Интеграционные тесты │ └── benchmarks/ // Бенчмарки производительности └── examples/ // Примеры программ === Рекомендуемые ресурсы === - [[https://llvm.org/docs/tutorial/MyFirstLanguageFrontend/|LLVM: Implementing a Language]] - [[https://craftinginterpreters.com/|Crafting Interpreters Book]] - [[https://github.com/rust-lang/rust|Rust Compiler Source]] - [[https://github.com/llvm/llvm-project|LLVM Project Source]] === Критерии оценки === ^ Критерий ^ Базовый уровень ^ Экспертный уровень ^ | **Лексический анализ** | Поддержка базовых токенов | Полная грамматика с комментариями и директивами | | **Синтаксический анализ** | Разбор простых конструкций | Полный парсер с обработкой ошибок и восстановлением | | **Семантический анализ** | Базовая проверка типов | Полная система типов с выводом и полиморфизмом | | **Промежуточное представление** | Простое IR | Многоуровневое IR с оптимизациями | | **Генерация кода** | Базовый машинный код | Оптимизированный native-код с поддержкой платформ | | **Инструменты** | Базовый компилятор | Полный toolchain с отладчиком и пакетным менеджером | === Пример программы === // Модуль для работы с геометрией import "math"; struct Circle { center: Point; radius: float; } struct Point { x: float; y: float; } func area(c: Circle) -> float { return math::PI * c.radius * c.radius; } func main() -> int { let center = Point { x: 0.0, y: 0.0 }; let circle = Circle { center: center, radius: 5.0 }; let a = area(circle); print("Area: ", a); return 0; } ---- [[gram:labs|← К списку лабораторных]] | [[gram:main|На главную]] | [[gram:case-016|← Кейс 016]]