Формальні мови

🎯 Вступ до формальних мов

Формальні мови - це математичні об'єкти, що використовуються для опису синтаксису програмних мов, протоколів зв'язку та інших формальних систем. Вони є основою компіляторів, інтерпретаторів та багатьох інших інструментів програмування.

🔑 Основні концепції:

Алфавіт та слова: Основи побудови формальних мов

Регулярні вирази: Потужний інструмент для опису патернів

Граматики: Правила генерації мов

Парсери: Аналіз та розпізнавання мов

🔤 Алфавіти та слова

📝 Основні визначення

Алфавіт

Алфавіт Σ - це кінцева непорожня множина символів.

Слово (рядок)

Слово над алфавітом Σ - це скінченна послідовність символів з Σ.

Довжина слова: |w| - кількість символів у слові

Порожнє слово: ε (ε ∈ Σ* для будь-якого алфавіту Σ)

Конкатенація: w₁w₂ - з'єднання двох слів

Мова

Мова L над алфавітом Σ - це підмножина множини всіх слів Σ*.

// Приклади мов: L₁ = {aⁿbⁿ | n ≥ 0} // Мова з рівною кількістю a та b L₂ = {w ∈ {0,1}* | |w| парна} // Мова парних двійкових слів L₃ = {aⁿ | n ≥ 0} // Мова всіх слів з символів 'a'

// Приклади алфавітів: Σ₁ = {a, b, c} // Алфавіт з трьох букв Σ₂ = {0, 1} // Двійковий алфавіт Σ₃ = {a, b, c, ..., z} // Англійський алфавіт Σ₄ = {if, then, else} // Алфавіт ключових слів

🔍 Регулярні вирази

⚡ Синтаксис регулярних виразів

Базові операції

r₁r₂ - спочатку r₁, потім r₂

Приклад: ab - слово "ab"

r₁|r₂ - або r₁, або r₂

Приклад: a|b - або "a", або "b"

r* - нуль або більше повторень r

Приклад: a* - ε, a, aa, aaa, ...

r+ - одне або більше повторень r

Приклад: a+ - a, aa, aaa, ...

r? - нуль або одне повторення r

Приклад: a? - ε або a

📚 Приклади регулярних виразів

^\+?[1-9]\d{1,14}$ // Розбір: // \+? - опціональний плюс // [1-9] - перша цифра не може бути 0 // \d{1,14} - від 1 до 14 цифр

^(?:[0-9]{1,3}\.){3}[0-9]{1,3}$ // Розбір: // (?:[0-9]{1,3}\.){3} - три групи з 1-3 цифр та крапкою // [0-9]{1,3} - остання група з 1-3 цифр

🔧 Розширені можливості

[abc] // a, b або c [^abc] // будь-який символ, крім a, b, c [a-z] // будь-яка мала літера [A-Z] // будь-яка велика літера [0-9] // будь-яка цифра \w // буквено-цифровий символ \s // пробіл \d // цифра

{n} // точно n повторень {n,} // n або більше повторень {n,m} // від n до m повторень * // 0 або більше (еквівалентно {0,}) + // 1 або більше (еквівалентно {1,}) ? // 0 або 1 (еквівалентно {0,1})

^ // початок рядка $ // кінець рядка \b // межа слова \B // не межа слова

^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$ // Розбір: // [a-zA-Z0-9._%+-]+ - один або більше символів // @ - символ собачки // [a-zA-Z0-9.-]+ - доменне ім'я // \. - крапка // [a-zA-Z]{2,} - домен верхнього рівня

🌳 Контекстно-вільні граматики

📝 Визначення CFG

Формальне визначення

Контекстно-вільна граматика G = (V, T, P, S), де:

V: Множина нетермінальних символів (змінних)

T: Множина термінальних символів

P: Множина продукцій (правил) вигляду A → α

S: Початковий символ

🏗️ Приклади граматик

G = ({S, E}, {if, then, else, id, =, ;}, P, S) Продукції: S → if E then S else S S → if E then S S → id = E; E → id // Приклад виводу: // if id then id = id; else id = id;

🔄 Амбігуація

Амбігуозна граматика

Граматика називається амбігуозною, якщо існує рядок, який має більше одного дерева виводу.

// Амбігуозна граматика: E → E + E | E * E | id // Для рядка "id + id * id" існує два дерева виводу: // 1. E → E + E → id + E * E → id + id * id // 2. E → E * E → E + E * id → id + id * id // Рішення - ввести пріоритети операцій: E → E + T | T T → T * F | F F → id

G = ({E, T, F}, {+, *, (, ), id}, P, E) Продукції: E → E + T | T T → T * F | F F → (E) | id // Приклад виводу для "id + id * id": E → E + T → T + T → F + T → id + T → id + T * F → id + F * F → id + id * F → id + id * id

🔍 Синтаксичний аналіз

📊 Типи парсерів

Top-down парсери

Почінають з початкового символу та будують дерево виводу зверху вниз.

Читають вхід зліва направо (Left-to-right)

Використовують лівий вивід (Leftmost derivation)

Рекурсивний спуск

LL(1) - один символ заздалегідь

Bottom-up парсери

Почінають з терміналів та будують дерево виводу знизу вгору.

Читають вхід зліва направо (Left-to-right)

Використовують правий вивід (Rightmost derivation)

LR(0), SLR(1), LALR(1), LR(1)

⚙️ Алгоритми парсингу

// Основний цикл LR парсера: while (true) { state = stack.top(); action = action_table[state][current_token]; if (action == "shift") { stack.push(current_token); stack.push(goto_table[state][current_token]); advance(); } else if (action == "reduce") { // Зменшити за правилом pop(2 * rule_length); state = stack.top(); stack.push(rule_lhs); stack.push(goto_table[state][rule_lhs]); } else if (action == "accept") { break; } else { error(); } }

// Для граматики: E → E + T | T function parseE() { result = parseT(); while (currentToken == '+') { consume('+'); result = new AddNode(result, parseT()); } return result; } function parseT() { // Аналогічно для T return parseF(); }

🔧 Лексичний аналіз

📖 Токенізація

Лексеми та токени

Лексичний аналізатор перетворює вхідний текст у послідовність токенів.

🔍 Регулярні вирази для лексем

if|then|else|while|for|function|return|class // Або більш точний підхід: \b(if|then|else|while|for|function|return|class)\b

[a-zA-Z_][a-zA-Z0-9_]* // Починається з літери або підкреслення, // потім літери, цифри або підкреслення

// Цілі числа: [0-9]+ // Числа з плаваючою крапкою: [0-9]+\.[0-9]+([eE][+-]?[0-9]+)? // Шістнадцяткові числа: 0[xX][0-9a-fA-F]+

// Вхідний код: if (x > 0) then y = x + 1; // Лексеми та токени: // "if" → KEYWORD(IF) // "(" → PUNCTUATION(LPAREN) // "x" → IDENTIFIER("x") // ">" → OPERATOR(GT) // "0" → NUMBER(0) // ")" → PUNCTUATION(RPAREN) // "then" → KEYWORD(THEN) // "y" → IDENTIFIER("y") // "=" → OPERATOR(ASSIGN) // "x" → IDENTIFIER("x") // "+" → OPERATOR(PLUS) // "1" → NUMBER(1) // ";" → PUNCTUATION(SEMICOLON)

🏗️ Генератори парсерів

⚡ Популярні інструменти

ANTLR

ANother Tool for Language Recognition - потужний генератор парсерів для багатьох мов програмування.

Yacc/Bison

Генератори LALR(1) парсерів для C/C++.

// Приклад граматики Yacc: %token NUMBER %left '+' '-' %left '*' '/' %% expr: expr '+' expr | expr '-' expr | expr '*' expr | expr '/' expr | '(' expr ')' | NUMBER ;

Flex/Lex

Генератори лексичних аналізаторів.

// Приклад Lex файлу: %{ #include "y.tab.h" %} %% [0-9]+ { return NUMBER; } "+" { return '+'; } "-" { return '-'; } "*" { return '*'; } "/" { return '/'; } "(" { return '('; } ")" { return ')'; } [ \t\n] { /* skip whitespace */ } . { return yytext[0]; } %%

// Приклад граматики ANTLR: grammar Expr; expr: expr '+' term | term; term: term '*' factor | factor; factor: '(' expr ')' | NUMBER; NUMBER: [0-9]+; WS: [ \t\r\n]+ -> skip;

🎯 Практичні застосування

💻 Компілятори

Лексичний аналіз, синтаксичний аналіз, генерація коду

🔍 Пошук у текстах

Регулярні вирази для пошуку та заміни в текстах

📊 Валідація даних

Перевірка формату електронних адрес, номерів телефонів

🌐 Веб-розробка

Парсинг HTML, JSON, XML документів

📚 Рекомендована література

"Compilers: Principles, Techniques, and Tools" - Aho, Sethi, Ullman

"Modern Compiler Implementation in C" - Andrew Appel

"The Definitive ANTLR 4 Reference" - Terence Parr

"Programming Language Pragmatics" - Michael Scott

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Spirograph і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.