Всеукраїнська науково-практична конференція



Сторінка30/60
Дата конвертації11.05.2018
Розмір3.74 Mb.
1   ...   26   27   28   29   30   31   32   33   ...   60

Кушнір О.В., Руснак М.А.


ЧЕРНІВЕЦЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ ІМЕНІ ЮРІЯ ФЕДЬКОВИЧА (УКРАЇНА)

ПОБУДОВА СИНТАКСИЧНИХ АНАЛІЗАТОРІВ



Запропоновано методи реалізації спадного синтаксичного аналізу.
Синтаксичний аналіз (парсинг) - це процес зіставлення лінійної послідовності лексем (слів, токенів) природного або формальної мови з його формальної граматикою . Результатом зазвичай є дерево розбору (синтаксичне дерево). Звичайно застосовується спільно з лексичним аналізом.

Синтаксичний аналізатор (парсер) - це програма або частина програми, що виконує синтаксичний аналіз.

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

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

Області застосування:


  • все що має « синтаксис », піддається автоматичному аналізу;

  • мови програмування - розбір вихідного коду мов програмування, в процесі трансляції (компіляції або інтерпретації );

  • структуровані дані - дані, мови їх опису, оформлення і т.д. Наприклад, XML , HTML , CSS , ini-файли, спеціалізовані конфігураційні файли тощо;

  • SQL -запити (DSL -мова);

  • математичні вирази;

  • регулярні вирази (які, у свою чергу, можуть використовуватися для автоматизації лексичного аналізу);

  • формальні граматики;

  • лінгвістика - людські мови. Наприклад, машинний переклад і інші генератори текстів .

Спадний синтаксичний аналіз - це один з методів визначення приналежності вхідного рядка до деякої формальної мови , описаною LL (k) контекстно-вільною граматикою . Це клас алгоритмів граматичного аналізу , де правила формальної граматики розкриваються, починаючи зі стартового символу, до одержання необхідної послідовності токенів .

Для кожного нетермінального символу K будується функція, яка для будь-якого вхідного слова x робить 2 речі:



Така функція повинна задовольняти наступним критеріям:

  • зчитувати з ще необробленого вхідного потоку максимальний початок A , що є початком деякого слова, виведеного з K

  • визначати чи є A виведеним з K або просто виведеним початком виведеного з K слова

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

Розбір полягає у виклику описаних вище функцій. Якщо для ліченого нетермінала є складене правило, то при його розборі будуть викликані інші функції для розбору вхідних у нього терміналів. Дерево викликів, починаючи з самої «верхньої» функції еквівалентно дереву розбору.

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

Умови застосування:

Нехай в даній формальній граматиці N - це кінцева множина нетермінальних символів; Σ - кінцева множина термінальних символів, тоді метод рекурсивного спуску застосуємо тільки, якщо кожне правило цієї граматики має наступний вигляд:


  • або , де , і це єдине правило висновку для цього нетермінала

  • або для всіх ,

Існує два типи алгоритмів спадного синтаксичного аналізу:

  1. метод рекурсивного спуску;

  2. синтаксичний LL-аналізатор.

Метод рекурсивного спуску - алгоритм синтаксичного аналізу, реалізований шляхом взаємного виклику процедур, які паряться, що відповідають правилам контекстно-вільної граматики або БНФ . Застосування правил послідовно, зліва-направо поглинають токени , отримані від лексичного аналізатора . Це один з найпростіших алгоритмів парсинга, відповідний для повністю ручної реалізації.

Далі описується аналізатор, в основі якого лежить побудова таблиць; альтернативою може служити аналізатор, побудований методом рекурсивного спуску, який зазвичай пишеться вручну (хоча існують і виключення, наприклад, генератор синтаксичних аналізаторів ANTLR для LL (*) граматик).

LL-аналізатор називається LL (k)-аналізатором, якщо даний аналізатор використовує попередній перегляд на k токенів (лексем) при розборі вхідного потоку. Граматика, яка може бути розпізнана LL (k)-аналізатором без повернень до попередніх символам, називається LL (k)-граматикою. Мова, яка може бути представлений у вигляді LL (k)-граматики, називається LL (k)-мовою. Існують LL (k + n)-мови, які не є LL (k)-мовами, тобто не всі контекстно-вільні мови є LL (k)-мовами.

LL (1)-граматики дуже поширені, тому що відповідні їм LL-аналізатори переглядають потік тільки на один символ вперед при ухваленні рішення про те, яке правило граматики необхідно застосувати. Мови, засновані на граматиках з великим значенням k, традиційно вважалися важкими для розпізнавання, хоча при широкому поширенні генераторів синтаксичних аналізаторів, що підтримують LL (k) граматики з довільним k, це зауваження вже неактуально.

LL-аналізатор називається LL (*)-аналізатором, якщо немає строгого обмеження для k і аналізатор може розпізнавати мову, якщо токени належать якійсь регулярній множині (наприклад, використовуючи детерміновані кінцеві автомати).

Існують протиріччя між так званою «Європейською школою» побудови мов, яка ґрунтується на LL-граматиках, і «Американської школою», яка вважає за краще LR-граматики. Такі протиріччя обумовлені традиціями викладання і деталями опису різних методів та інструментів у конкретних підручниках; крім того, свій вплив надав Н. Вірт, чиї дослідження описують різні методи оптимізації LL (1) розпізнавачів і компіляторів.

Синтаксичний LL-аналізатор - спадний синтаксичний аналізатор для підмножини контекстно-вільних граматик . Він аналізує вхідний потік зліва направо, і будує лівий вивід граматики. Клас граматик, для яких можна побудувати LL-аналізатор, відомий як LL-граматики .

Варіанти реалізації:



  1. Пророкуючий парсер. Для парсерів цього типу потрібна відповідна КС-граматика , конкретно LL (k) граматика, що дозволяє по черговому токені або токенам однозначно вибрати (передбачити) один з альтернативних варіантів розкриття кожного нетермінала. Такий парсер працює за лінійний час. Варіантом є LL-парсер - реалізація пророкуючого парсера з автоматичною побудовою «таблиці передбачення», що визначає по заданому нетерміналу і черговому токені підходяще правило для розкриття нетермінала.

  2. Парсер з поверненням. Замість пророкуючого парсеру просто намагається застосувати всі альтернативні варіанти правил по порядку, поки одна з спроб не увінчається успіхом. Такий парсер може вимагати експоненціального часу роботи, і не завжди гарантує завершення, залежно від граматики. Вразливий для лівої рекурсії.

ПЕРЕЛІК ЛІТЕРАТУРИ



  1. Шень А. Програмування: теореми і задачі [Текст] / А. Шень. – М. : МЦНМО, 2004. – 224с.

  2. Хантер Р. Основные концепции компиляторов [Текст] / Р. Хантер. – М. : «Вильямс», 2002. – 256с.


УДК 004.78: 025.4.036


Поділіться з Вашими друзьями:
1   ...   26   27   28   29   30   31   32   33   ...   60


База даних захищена авторським правом ©wishenko.org 2017
звернутися до адміністрації

    Головна сторінка