Аналіз синтаксису: типи аналізу компілятора зверху вниз і знизу вгору

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

Навіщо потрібен синтаксичний аналізатор?

• Перевірте, чи код дійсний граматично
• Синтаксичний аналізатор допомагає застосовувати правила до коду
• Допомагає переконатися, що кожна відкривна дужка має відповідний кінцевий баланс
• Кожна декларація має тип, і цей тип повинен існувати

Важлива термінологія синтаксичного аналізатора

Важливі терміни, які використовуються в процесі синтаксичного аналізу:

• Вирок: Речення - це група символів над деяким алфавітом.

• Лексема: Лексема — синтаксична одиниця найнижчого рівня мови (наприклад, total, start).

• Маркерів: Лексема — це лише категорія лексем.

• Ключові та зарезервовані слова – Це ідентифікатор, який використовується як фіксована частина синтаксису оператора. Це зарезервоване слово, яке не можна використовувати як ім’я змінної чи ідентифікатор.

• Шумові слова – Шумні слова є необов’язковими, вони вставляються у висловлювання, щоб покращити читабельність речення.

• Коментарі – Це дуже важлива частина документації. Здебільшого він відображається за допомогою /* */ або//Пусто (пробіл)

• Делімітери – Це синтаксичний елемент, який позначає початок або кінець деякої синтаксичної одиниці. Подібно до оператора чи виразу, «початок»…»кінець» або {}.

• Набір символів – ASCII, Unicode

• Ідентифікатори – Це обмеження на довжину, які допомагають вам зменшити читабельність речення.

• Operaтор символів – + і – виконує дві основні арифметичні операції.
• Синтаксичні елементи мови

Навіщо нам Парсинг?

Розбір також перевіряє, чи вхідний рядок правильно сформований, і якщо ні, відхиляє його.

Нижче наведено важливі завдання, які виконує синтаксичний аналізатор у проекті компілятора:

• Допомагає виявити всі типи синтаксичних помилок
• Знайдіть позицію, в якій сталася помилка
• Чіткий і точний опис помилки.
• Відновлення після помилки, щоб продовжити та знайти подальші помилки в коді.
• Не повинно впливати на компіляцію «правильних» програм.
• Розбір повинен відхиляти недійсні тексти, повідомляючи про синтаксичні помилки

Методи розбору

Методи розбору поділяються на дві різні групи:

• Розбір зверху вниз,
• Розбір знизу вгору

Розбір зверху вниз

У низхідній конструкції розбору дерева розбору починається з кореня, а потім переходить до листів.

Є два типи аналізу зверху вниз:

1. Прогнозний аналіз:

Прогнозний синтаксичний аналіз може передбачити, яке виробництво слід використовувати для заміни певного вхідного рядка. Інтелектуальний аналізатор використовує точку прогнозу, яка вказує на наступні вхідні символи. Зворотне відстеження не є проблемою з цією технікою аналізу. Він відомий як аналізатор LL(1).

2. Розбір рекурсивного спуску:

Ця техніка аналізу рекурсивно аналізує вхідні дані для створення дерева слів. Він складається з кількох невеликих функцій, по одній для кожного нетерміналу в граматиці.

Розбір знизу вгору

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

Помилка – Методи відновлення

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

• Лексичні: Ім'я неправильно введеного ідентифікатора
• Синтаксичний: незбалансована дужка або відсутня крапка з комою
• Семантичний: несумісне призначення значення
• логічний: нескінченний цикл і недосяжний код

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

Відновлення операторного режиму

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

Відновлення режиму паніки

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

Відновлення на рівні фрази

• Компілятор коригує програму, вставляючи або видаляючи маркери. Це дозволяє йому продовжити розбір з того місця, де воно було. Він виконує корекцію вхідних даних, що залишилися. Він може замінити префікс решти вхідних даних деяким рядком, що допомагає синтаксичному аналізатору продовжити процес.

Помилка виробництва

• Відновлення виробництва помилок розширює граматику мови, яка генерує помилкові конструкції. Потім аналізатор виконує діагностику помилок щодо цієї конструкції.

Глобальна корекція

• Компілятор повинен вносити якомога менше змін під час обробки неправильного вхідного рядка. Враховуючи неправильний вхідний рядок a та граматику c, алгоритми шукатимуть дерево аналізу для пов’язаного рядка b. Подібно до деяких вставок, видалень і модифікацій, зроблених з токенів, необхідних для перетворення an у b, є якомога менше.

Граматика

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

Правила форми граматики

• Нетермінальний символ має з’явитися ліворуч від принаймні одного виробництва
• Символ цілі ніколи не повинен відображатися праворуч від::= будь-якої продукції
• Правило є рекурсивним, якщо LHS з’являється в його RHS

Умовні позначення

Умовні позначення символу можна вказати, заключивши елемент у квадратні дужки. Це довільна послідовність екземплярів елемента, яку можна вказати, уклавши елемент у фігурні дужки за символом зірочки { … }*.

Це вибір альтернативи, яка може використовувати символ в межах одного правила. За потреби його можна взяти в круглі дужки ([,]).

Два типи нотаційних умовних позначень: термінальні та нетермінальні

1. Термінали:

• Малі літери в алфавіті, такі як a, b, c,
• Operaабо символи, такі як +,-, * тощо.
• Знаки пунктуації, такі як круглі дужки, решітка, кома
• 0, 1, …, 9 цифр
• Рядки, виділені жирним шрифтом, наприклад ідентифікатор або якщо, будь-що, що представляє один символ терміналу

2.Нетермінали:

• Великі літери, наприклад A, B, C
• Назви курсивом у нижньому регістрі: вираз або деякі

Безконтекстна граматика

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

expression -> expression -+ term
expression -> expression – term 
expression-> term
term  -> term * factor
term -> expression/ factor
term  -> factor factor
factor ->  ( expression )
factor -> id

Граматична деривація

Граматичне похідне – це послідовність граматичного правила, яке перетворює початковий символ у рядок. Виведення доводить, що рядок належить до мови граматики.

Крайнє ліве відведення

Коли реченнєва форма введення сканується та замінюється в послідовності зліва направо, це називається крайнім лівим виведенням. Форма речення, яка утворюється крайньою лівою деривацією, називається формою лівого речення.

Крайнє праве похідне

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

Синтаксис проти лексичного аналізатора

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

Недоліки використання синтаксичних аналізаторів

• Він ніколи не визначить, дійсний маркер чи ні
• Not допомагає вам визначити, чи є операція, виконана з типом маркера, дійсною чи ні
• Ви не можете вирішити, що маркер оголошено та ініціалізовано до його використання

Підсумки

• Синтаксичний аналіз — це друга фаза процесу проектування компілятора, яка йде після лексичного аналізу
• Синтаксичний аналізатор допомагає застосовувати правила до коду
• Речення, лексема, маркер, ключові слова та зарезервовані слова, шумові слова, коментарі, роздільники, набір символів, ідентифікатори – це деякі важливі терміни, які використовуються в синтаксичному аналізі під час побудови компілятора.
• Parse перевіряє, чи вхідний рядок правильно сформований, і якщо ні, відхиляє його
• Методи синтаксичного аналізу поділяються на дві різні групи: Синтаксичний аналіз зверху вниз, Синтаксичний аналіз знизу вгору
• Лексичні, синтаксичні, семантичні та логічні помилки є деякими типовими помилками, які виникають під час аналізу
• Граматика - це набір структурних правил, які описують мову
• Умовні позначення символу можна вказати, заключивши елемент у квадратні дужки
• CFG — це ліворекурсивна граматика, яка має принаймні одну продукцію типу
• Граматичне похідне – це послідовність граматичного правила, яке перетворює початковий символ у рядок
• Синтаксичний аналізатор в основному має справу з рекурсивними конструкціями мови, тоді як лексичний аналізатор полегшує завдання синтаксичного аналізатора в СУБД
• Недоліком методу аналізатора синтаксису є те, що він ніколи не визначить, дійсний маркер чи ні