Образовательный ресурс edu.irnok.net

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
===== Кейс 017: Полноценный мини-язык программирования (gram:case-017) =====

=== Общая информация ===

^ Уровень сложности ^ 🔴 Эксперт ^
^ Рекомендуемые языки ^ C++, Rust ^
^ Основные инструменты ^ ANTLR4, LLVM, Flex/Bison (опционально) ^
^ Требуемые знания ^ Продвинутое программирование, системы типов, управление памятью ^

=== Описание кейса ===

Разработка полноценного статически типизированного языка программирования с поддержкой:
  - функций и рекурсии
  - пользовательских типов данных  
  - системы модулей
  - базовых структур управления
  - сборки мусора или ручного управления памятью

=== Грамматика языка ===

==== Лексические токены ====

<code>
// Ключевые слова
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
</code>

==== Синтаксические правила ====

<code>
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
</code>

=== План лабораторных работ ===

==== Лабораторная 1: Лексический и базовый синтаксический анализ ====

**Задачи:**
  - Реализовать полную грамматику токенов
  - Создать лексический анализатор с поддержкой комментариев
  - Реализовать парсер для объявлений функций и структур
  - Обработать вложенные блоки и выражения

**Тестовые примеры:**
<code>
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);
}
</code>

**Результат:** Парсер, способный разбирать сложные конструкций языка.

==== Лабораторная 2: Построение AST и семантический анализ ====

**Задачи:**
  - Спроектировать иерархию классов AST
  - Реализовать построение полного AST
  - Создать систему символов (таблицы символов)
  - Реализовать проверку типов для всех конструкций

**Функции проверки:**
  - Контроль областей видимости
  - Вывод и проверка типов выражений
  - Валидация вызовов функций
  - Проверка соответствия возвращаемых типов

**Результат:** Семантически проверенное AST с полной информацией о типах.

==== Лабораторная 3: Промежуточное представление и оптимизации ====

**Задачи:**
  - Спроектировать промежуточное представление (IR)
  - Реализовать трансляцию AST в IR
  - Внедрить базовые оптимизации:
    - удаление мертвого кода
    - постоянное свертывание
    - inline простых функций
  - Реализовать управление памятью (стек/куча)

**Результат:** Оптимизированное промежуточное представление программы.

==== Лабораторная 4: Генерация машинного кода и runtime ====

**Задачи:**
  - Интеграция с LLVM для генерации кода
  - Реализация runtime-библиотеки
  - Поддержка системных вызовов и ввода-вывода
  - Создание системы сборки и пакетного менеджера

**Особенности реализации:**
  - Генерация эффективного машинного кода
  - Поддержка вызовов внешних функций (FFI)
  - Реализация базовой стандартной библиотеки

**Результат:** Полноценный компилятор, способный компилировать и исполнять программы.

=== Расширенные возможности ===

Для достижения экспертного уровня рекомендуется реализовать:

  - **Система типов:** дженерики, алгебраические типы данных, type inference
  - **Метапрограммирование:** макросы, шаблоны, compile-time вычисления
  - **Параллелизм:** async/await, корутины, модель акторов
  - **Инструменты:** отладчик, профилировщик, REPL-окружение
  - **Оптимизации:** автоматическая векторизация, межпроцедурный анализ

=== Примеры реализации ===

==== Архитектура проекта ====

<code>
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/               // Примеры программ
</code>

=== Рекомендуемые ресурсы ===

  - [[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 с отладчиком и пакетным менеджером |

=== Пример программы ===

<code>
// Модуль для работы с геометрией
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;
}
</code>

----
[[gram:labs|← К списку лабораторных]] | [[gram:main|На главную]] | [[gram:case-016|← Кейс 016]]