✅Двусвязный список (Doubly Linked List)

Двусвязный список — структура данных, где каждый узел хранит:

✔️значение
✔️ссылку на следующий узел (next)
✔️ссылку на предыдущий узел (prev)

1️⃣Узел списка:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

2️⃣Двусвязный список:

class DoublyLinkedList:
    def __init__(self):
        self.head = None

3️⃣Вставка в начало — O(1)

    def add_front(self, data):
        new_node = Node(data)
        if self.head:
            self.head.prev = new_node
            new_node.next = self.head
        self.head = new_node

4️⃣Обход списка — O(n)

    def print_list(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

#ComputerScience #algorithms

🗄 S3-хранилище — просто и практично

📚S3 (Simple Storage Service) — это объектное хранилище.
Вместо папок и файлов — бакеты и объекты.

Используется для:
✔️загрузки файлов (аватарки, документы, видео)
✔️бэкапов
✔️логов
✔️статики для сайтов
✔️микросервисов (через API)


💡Базовые понятия
✔️Bucket — контейнер (как корневая папка)
✔️Object — файл + метаданные
✔️Key — путь к объекту (images/avatar.png)
✔️S3 API — HTTP API для работы с файлами

🐳 Локальный запуск S3 хранилища через Docker (MinIO):

# docker-compose.yml
version: "3.9"

services:
  minio:
    image: minio/minio
    container_name: minio
    command: server /data --console-address ":9001"
    ports:
      - "9000:9000" # S3 API
      - "9001:9001" # Web UI
    environment:
      MINIO_ROOT_USER: admin
      MINIO_ROOT_PASSWORD: admin123
    volumes:
      - minio-data:/data

volumes:
  minio-data:

▶️ После запуска:

* S3 endpoint: http://localhost:9000

* UI: http://localhost:9001

* Логин: admin / admin123

Продолжение 👇

После запуска S3, можно подключится к ниму, через любой язык программирования.

✅Пример кода (Python — самый короткий и читаемый)

pip install boto3

import boto3

s3 = boto3.client(
    "s3",
    endpoint_url="http://localhost:9000",
    aws_access_key_id="admin",
    aws_secret_access_key="admin123",
    region_name="us-east-1",
)

bucket = "files"

# создать бакет
s3.create_bucket(Bucket=bucket)

# загрузить файл
s3.put_object(
    Bucket=bucket,
    Key="hello.txt",
    Body=b"Hello S3!"
)

# скачать файл
obj = s3.get_object(Bucket=bucket, Key="hello.txt")
print(obj["Body"].read().decode())

💡 Где это реально применяют

Backend → загружает файлы → отдает ссылку

Frontend → загружает напрямую в S3 (presigned URL)

Kubernetes → хранение артефактов

#backend #devOps

Только devOps могли его видеть

#memes

Работа языко программирования №1

Многие из вас, сейчас читающих данный пост, умеют писать код на разных языках. Но немногие понимают и знают работу этих языков, то, как они реализованы, и то, что происходит, когда вы запускаете свой код. Данный пост открывает арку постов, связанных с этой темой; все последующие посты — 3–4 шт.

Любой написанный код является просто набором байтов в памяти, но с компилятором наш код обретает логическую интерпретацию. Данное превращение из набора символов в набор команд делится на 8 этапов:

1. Лексический анализ (Lexical analysis)

2. Синтаксический анализ (Parsing)

3. Семантический анализ

4. Построение промежуточного представления (IR)

5. Оптимизации (Compile-time optimizations)

6. Генерация кода

7. Линковка (Linking)

8. Бинарник / байткод

Каждый из этапов мы отдельно рассмотрим, и пример реализации каждого слоя будет представлен на Node.js или Python.

Лексический анализ — это первый этап компиляции.
На этом этапе исходный код разбивается на последовательность токенов.
Лексер читает поток символов, группирует их в лексемы и классифицирует согласно правилам языка.
Пробелы, табуляции, переносы строк и комментарии обычно игнорируются.
Результатом работы является поток токенов, который передаётся на этап синтаксического анализа.

Пример:

int a = 10 + b

выходит:

KEYWORD(int)
IDENTIFIER(a)
ASSIGN
NUMBER(10)
PLUS
IDENTIFIER(b)
SEMICOLON

Пример кода на python:

python main.py
from core.lexer import Lexer


def main():
    code = "int a = 10 + b;"
    lexer = Lexer(code)
    tokens = lexer.tokenize()

    for token in tokens:
        print(token)


if __name__ == "__main__":
    main()

python core.lexer.py
import re
from dataclasses import dataclass


@dataclass
class Token:
    type: str
    value: str
    position: int


class Lexer:
    def __init__(self, source: str):
        self.source = source
        self.position = 0
        self.tokens = []

        self.token_specification = [
            ("NUMBER", r"\d+"),
            ("IDENTIFIER", r"[a-zA-Z_]\w*"),
            ("PLUS", r"\+"),
            ("MINUS", r"-"),
            ("MULTIPLY", r"\*"),
            ("DIVIDE", r"/"),
            ("ASSIGN", r"="),
            ("LPAREN", r"\("),
            ("RPAREN", r"\)"),
            ("SEMICOLON", r";"),
            ("SKIP", r"[ \t\n]+"),
            ("MISMATCH", r"."),
        ]

        self.regex = re.compile(
            "|".join(
                f"(?P<{name}>{pattern})" for name, pattern in self.token_specification
            )
        )

    def tokenize(self) -> list[Token]:
        for match in self.regex.finditer(self.source):
            kind = match.lastgroup
            value = match.group()
            position = match.start()

            if kind == "SKIP":
                continue
            elif kind == "MISMATCH":
                raise SyntaxError(f"Unexpected character {value} at {position}")
            else:
                # Проверка на ключевое слово
                if kind == "IDENTIFIER" and value == "int":
                    kind = "KEYWORD"

                self.tokens.append(Token(kind, value, position))

        return self.tokens

При запуске:

Token(type='KEYWORD', value='int', position=0)
Token(type='IDENTIFIER', value='a', position=4)
Token(type='ASSIGN', value='=', position=6)
Token(type='NUMBER', value='10', position=8)
Token(type='PLUS', value='+', position=11)
Token(type='IDENTIFIER', value='b', position=13)
Token(type='SEMICOLON', value=';', position=14)

Token(type=<Вид токена>, value=<Значение>, position=<метоположение токена в строке>)

Синтаксический анализ (Parsing) - исходня из названию, данный слой получает на вход набор токенов, которые мы получили с слоя lexer и на выходе получаем AST.

Parsing:
- корректен ли порядок токенов
- соблюдены ли правила языка
- можно ли из этого построить осмысленную конструкцию

Данный слой позволяет нам связать token в структуру под названием AST

AST(Абстрактное сентаксическое дерево) - это структура данных, позволяющия в данной задаче, описавать связи между токенами

реализация на python:

main.py

from core.lexer import Lexer
from core.parser import Parser


def main():
    code = """
    int a = 10 + b;
    int c = a * 2;
    """
    lexer = Lexer(code)
    tokens = lexer.tokenize()

    for token in tokens:
        print(token)

    parser = Parser(tokens)
    ast = parser.parse()

    print(ast)


if __name__ == "__main__":
    main()

ast.py

from dataclasses import dataclass


class ASTNode:
    pass


@dataclass
class Number(ASTNode):
    value: int


@dataclass
class Identifier(ASTNode):
    name: str


@dataclass
class BinaryOp(ASTNode):
    left: ASTNode
    operator: str
    right: ASTNode


@dataclass
class VarDeclaration(ASTNode):
    var_type: str
    name: str
    value: ASTNode

parser.py

from core.ast import BinaryOp, Identifier, Number, VarDeclaration
from core.lexer import Token


class Parser:
    def __init__(self, tokens):
        self.tokens = tokens
        self.position = 0

    def current(self) -> Token | None:
        if self.position < len(self.tokens):
            return self.tokens[self.position]
        return None

    def eat(self, token_type):
        token = self.current()
        if token and token.type == token_type:
            self.position += 1
            return token
        raise SyntaxError(f"Expected {token_type}, got {token}")

    def parse(self):
        declarations = []

        while self.current() is not None:
            declarations.append(self.parse_declaration())

        return declarations

    def parse_declaration(self) -> VarDeclaration:
        self.eat("KEYWORD")
        identifier = self.eat("IDENTIFIER")
        self.eat("ASSIGN")
        expr = self.parse_expression()
        self.eat("SEMICOLON")

        return VarDeclaration(var_type="int", name=identifier.value, value=expr)

    def parse_expression(self):
        return self.parse_term()

    def parse_term(self) -> BinaryOp:
        node = self.parse_factor()

        while self.current() and self.current().type in ("PLUS", "MINUS"):
            operator = self.eat(self.current().type)
            right = self.parse_factor()
            node = BinaryOp(node, operator.value, right)

        return node

    def parse_factor(self):
        node = self.parse_primary()

        while self.current() and self.current().type in ("MULTIPLY", "DIVIDE"):
            operator = self.eat(self.current().type)
            right = self.parse_primary()
            node = BinaryOp(node, operator.value, right)

        return node

    def parse_primary(self):
        token = self.current()

        if token.type == "NUMBER":
            self.eat("NUMBER")
            return Number(int(token.value))

        elif token.type == "IDENTIFIER":
            self.eat("IDENTIFIER")
            return Identifier(token.value)

        elif token.type == "LPAREN":
            self.eat("LPAREN")
            expr = self.parse_expression()
            self.eat("RPAREN")
            return expr

        else:
            raise SyntaxError(f"Unexpected token {token}")

output

Token(type='KEYWORD', value='int', position=5)
Token(type='IDENTIFIER', value='a', position=9)
Token(type='ASSIGN', value='=', position=11)
Token(type='NUMBER', value='10', position=13)
Token(type='PLUS', value='+', position=16)
Token(type='IDENTIFIER', value='b', position=18)
Token(type='SEMICOLON', value=';', position=19)
Token(type='KEYWORD', value='int', position=25)
Token(type='IDENTIFIER', value='c', position=29)
Token(type='ASSIGN', value='=', position=31)
Token(type='IDENTIFIER', value='a', position=33)
Token(type='MULTIPLY', value='*', position=35)
Token(type='NUMBER', value='2', position=37)
Token(type='SEMICOLON', value=';', position=38)
[VarDeclaration(var_type='int', name='a', value=BinaryOp(left=Number(value=10), operator='+', right=Identifier(name='b'))), VarDeclaration(var_type='int', name='c', value=BinaryOp(left=Identifier(name='a'), operator='*', right=Number(value=2)))]

После проверки структуры кода и создания AST идёт этап Семантического анализа(Semantic Analyzer)

Semantic Analyzer - это процесс когда код программы, проверяется на осмысленность программы, к примеру:
————
Код:

int a = b + 10;

Ошибка

Variable 'b' not defined

————
Код:

int a = 10;
int a = 20;

Ошибка

Variable 'a' already declared

————

и еще довольно большой раяд подобных проверок.

На выходе данного layer мы получаем таблицу символов(Symbol Table):
Код:

int a = 5;
int b = 10;

Выходные данные(в Symbol Table):

{
   "a": { type: "int" },
   "c": { type: "int" }
}

Порядок исполнения: AST -> Semantic Analyzer -> Validated AST -> Symbol Table

Реализация на python

core.semantic.py

class SemanticAnalyzer:
    def __init__(self):
        self.symbol_table = {}

    def analyze(self, nodes):
        for node in nodes:
            self.visit(node)

    def visit(self, node):
        method_name = f"visit_{type(node).__name__}"
        method = getattr(self, method_name, self.generic_visit)
        return method(node)

    def generic_visit(self, node):
        raise Exception(f"No visit method for {type(node).__name__}")

    

    def visit_VarDeclaration(self, node):
        name = node.name

        if name in self.symbol_table:
            raise Exception(f"Variable '{name}' already declared")

        self.symbol_table[name] = node.var_type

        self.visit(node.value)

    

    def visit_BinaryOp(self, node):
        self.visit(node.left)
        self.visit(node.right)

   

    def visit_Identifier(self, node):
        if node.name not in self.symbol_table:
            raise Exception(f"Variable '{node.name}' not defined")

   

    def visit_Number(self, node):
        pass

main.py

from core.lexer import Lexer
from core.parser import Parser
from core.semantic import SemanticAnalyzer


def main():
    code = """
    int b = 3;
    int a = 10 + b;
    int c = a * 2;
    """
    lexer = Lexer(code)
    tokens = lexer.tokenize()

    for token in tokens:
        print(token)

    parser = Parser(tokens)
    ast = parser.parse()

    print(ast)

    semantic = SemanticAnalyzer()
    semantic.analyze(ast)

    print("Semantic analysis passed")
    print("Symbol table:", semantic.symbol_table)


if __name__ == "__main__":
    main()

Вывод:

...
Semantic analysis passed
Symbol table: {'b': 'int', 'a': 'int', 'c': 'int'}

После проверки программы на осмысленные конструкции, идёт следующий этап

Intermediate Representation (IR) - данный слой решает проблему, связанную с тем что AST является удобным для анализа

Напомню AST:

[VarDeclaration(var_type='int', name='b', value=Number(value=3)), VarDeclaration(var_type='int', name='a', value=BinaryOp(left=Number(value=10), operator='+', right=Identifier(name='b'))), VarDeclaration(var_type='int', name='c', value=BinaryOp(left=Identifier(name='a'), operator='*', right=Number(value=2)))]

Но является совершенно не удобным для оптимизаций и генерации кода. Данный слой испровляет данную проблему и AST преобразует в IR(промежуточное престовление)

Пример:
Source code

int c = a * 2 + 10;

AST to IR

t1 = a * 2
t2 = t1 + 10
c = t2

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

Реализация на python

core.ir.py

@dataclass
class IRInstruction:
    op: str
    arg1: str | None = None
    arg2: str | None = None
    result: str | None = None

core.ir.py

class IRBuilder:

    def __init__(self):
        self.instructions = []
        self.temp_count = 0

    def new_temp(self):
        self.temp_count += 1
        return f"t{self.temp_count}"

    def build(self, nodes):
        for node in nodes:
            self.visit(node)

        return self.instructions

    def visit(self, node):
        method_name = f"visit_{type(node).__name__}"
        method = getattr(self, method_name)
        return method(node)

    
    def visit_VarDeclaration(self, node):
        value = self.visit(node.value)

        self.instructions.append(
            IRInstruction(
                op="STORE",
                arg1=value,
                result=node.name
            )
        )

    

    def visit_BinaryOp(self, node):
        left = self.visit(node.left)
        right = self.visit(node.right)

        temp = self.new_temp()

        op_map = {
            "+": "ADD",
            "-": "SUB",
            "*": "MUL",
            "/": "DIV",
        }

        self.instructions.append(
            IRInstruction(
                op=op_map[node.operator],
                arg1=left,
                arg2=right,
                result=temp
            )
        )

        return temp

    

    def visit_Number(self, node):
        temp = self.new_temp()

        self.instructions.append(
            IRInstruction(
                op="LOAD_CONST",
                arg1=node.value,
                result=temp
            )
        )

        return temp

    

    def visit_Identifier(self, node):
        return node.name

main.py

from core.ir import IRBuilder
from core.lexer import Lexer
from core.parser import Parser
from core.semantic import SemanticAnalyzer


def main():
    code = """
    int b = 3;
    int a = 10 + b;
    int c = a * 2;
    """
    lexer = Lexer(code)
    tokens = lexer.tokenize()

    for token in tokens:
        print(token)

    parser = Parser(tokens)
    ast = parser.parse()

    print(ast)

    semantic = SemanticAnalyzer()
    semantic.analyze(ast)

    print("Semantic analysis passed")
    print("Symbol table:", semantic.symbol_table)

    ir_builder = IRBuilder()
    ir = ir_builder.build(ast)

    for instr in ir:
        print(instr)


if __name__ == "__main__":
    main()

При запуске на выходе:

...
IRInstruction(op='LOAD_CONST', arg1=3, arg2=None, result='t1')
IRInstruction(op='STORE', arg1='t1', arg2=None, result='b')
IRInstruction(op='LOAD_CONST', arg1=10, arg2=None, result='t2')
IRInstruction(op='ADD', arg1='t2', arg2='b', result='t3')
IRInstruction(op='STORE', arg1='t3', arg2=None, result='a')
IRInstruction(op='LOAD_CONST', arg1=2, arg2=None, result='t4')
IRInstruction(op='MUL', arg1='a', arg2='t4', result='t5')
IRInstruction(op='STORE', arg1='t5', arg2=None, result='c')