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

Синтаксичний аналізатор — це програмний компонент, який приймає вхідні дані (часто текст) і створює структуру даних — часто дерево розбору, абстрактне дерево синтаксису або іншу ієрархічну структуру — забезпечує структурне представлення вводу, перевіряє правильність синтаксису в процесі. Аналізу можуть передувати або слідувати інші кроки, або їх можна об'єднати в один крок. Аналізатору часто передує окремий лексичний аналізатор, який створює токени з послідовності введених символів; Крім того, їх можна об'єднати у парсінг без сканування. Аналізатори можуть бути запрограмовані вручну або автоматично, або напів автоматично генератором парсерів.[1] Розбір допомагає шаблону, який виробляє відформатований вихід. Вони можуть використовуватись у різних ділянках, але часто з'являються разом, наприклад, пара scanf/printf, або як вхідний (аналіз вхідних даних) та вихідний етапи (створення кінцевого коду) компілятора.

Вхідними даними для синтаксичного аналізатора часто є текст деякою комп'ютерною мовою, але також може бути текстом природною мовою або менш структурованими текстовими даними, в цьому випадку, як правило, витягуються лише окремі частини тексту, а не дерево розбору. Параметри відрізняються від дуже простих функцій, таких як scanf, до складних програм, таких як інтерфейс компілятора C++ або HTML-аналізатор веб-браузера. Важливий клас простий синтаксичний аналіз виконується за допомогою регулярних виразів, в яких група регулярних виразів визначає регулярну мову та двигун регулярного виразу, автоматично генеруючи аналізатор для цієї мови, що дозволяє узгодити шаблон та вилучення тексту. В інших контекстах регулярні вирази замість цього використовуються перед розбором, як етап лексизації, вихід якого потім використовується аналізатором.

Використання аналізаторів залежить від вхідних даних. У випадку з мовами даних часто використовується синтаксичний аналізатор як функція читання файлів у програмі, наприклад, читання в HTML або XML-тексті; ці приклади є мовами розмітки даних. У випадку мов програмування є компонентом компілятора або інтерпретатора, який аналізує початковий код мови комп'ютерного програмування для створення певної форми внутрішнього представлення; аналізатор є ключовим кроком в інтерфейсі компілятора. Мови програмування, як правило, вказуються в термінах детерміністичної контекстно-вільної граматики, оскільки для них можуть бути написані швидкі та ефективні аналізатори. Для компіляторів сам аналіз може бути виконаний за один прохід або кілька проходів — див. одно-прохідний компілятор і багатопрохідний компілятор.

Майбутні недоліки компілятора з одним прохідним процесом у значній мірі можуть бути вирішені шляхом додавання виправлень, коли передбачається виправлення впродовж прямого переходу, а виправлення застосовуються в зворотньому напрямку, коли поточний сегмент програми є таким, що має бути завершений. Прикладом, коли такий механізм виправлення може бути корисним, є формальне твердженням GOTO, де вказівник GOTO невідомий, доки не буде пройдено сегмент програми. У такому випадку застосування виправлення буде відкладено, доки не буде визначено куди вказує GOTO. Очевидно, що відсталий GOTO не вимагає виправлення.

Контекстні граматики обмежені тією мірою, в якій вони можуть виразити всі вимоги до мови. Неформально причиною є те, що пам'ять в такій мові обмежена. Граматика не запам'ятовує існування конструкції над довільним введенням; це необхідно для мови, в якій, наприклад, ім'я повинно бути оголошено, перш ніж може бути посилання на нього. Однак більш потужні граматики, які можуть обійти це обмеження, не можуть бути ефективно розібрані. Таким чином, загальною стратегією є створення аналізатора для контекстно-вільної граматики, який приймає потрібні конструкції мови (тобто він приймає деякі недійсні конструкції); пізніше, небажані конструкції можуть бути відфільтровані на етапі семантичного аналізу (контекстного аналізу).

Наприклад, в Python такий синтаксичний код:

x = 1
print(x)

Такий код, однак, є синтаксично правильним з точки зору контекстної граматики, яка дає дерево синтаксису з тією ж структурою, що і попередня, але є синтаксично недійсною з точки зору контекстно-залежної граматики, яка вимагає, щоб змінні були ініціалізовані раніше використання:

x = 1
print(y)

Замість того, щоб аналізувати на етапі парсинга, це відбувається шляхом перевірки значень в дереві синтаксису, отже, як частина семантичного аналізу: контекстно-залежний синтаксис на практиці часто більш легко аналізується, ніж семантика.

Схема роботи синтаксичного аналізатору

Наведений нижче приклад демонструє загальний випадок розбору комп'ютерної мови з двома рівнями граматики: лексичної та синтаксичної.

Перший етап — генерація токенів або лексичний аналіз, за допомогою яких потік вхідних символів поділяється на значущі символи, визначені граматикою регулярні вирази. Наприклад, програма калькулятора буде отримувати на вхід, такий рядок "12 * (3 + 4)^2" і розділити його на токени 12, *, (, 3, +, 4, ), ^, 2, кожен з яких є значущим символом в контексті арифметичного виразу. Лексери міститимуть правила, які вказують на те, що символи *, +, ^, ( і ) позначають початок нового токену, так що незначні токени типу"12*" або "(3" не будуть створені).

Наступним етапом є парсинг чи синтаксичний аналіз, який перевіряє, чи токени утворюють допустимий вираз. Це, як правило, робиться з посиланням на контекстну граматику, яка рекурсивно визначає компоненти, які можуть скласти вираз та порядок їх появи. Проте не всі правила, що визначають мови програмування, можуть бути виражені контекстно-вільними граматиками, наприклад, дійсність типу та правильне декларування ідентифікаторів. Ці правила можуть бути формально виражені атрибутивними граматики.

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