ь також повідомлення про наявність у вхідному тексті помилок. Цей алгоритм послужить надалі базою для побудови дерева виведення в 3 частини курсової роботи.
4. ПОБУДОВА СІТАКСІЧЕСКОГО АНАЛІЗАТОРА
. 1 Дерево виведення
Лексичний аналізатор виділяє в тексті лексеми мови. Отримана після лексичного аналізу ланцюжок у другій частині програми розглядатися відповідно до алгоритму розбору. Після побудови ланцюжка виводу на її основі будується дерево розбору.
Програма виконує лексичний аналіз вхідної мови, породжує таблицю лексем і виконує синтаксичний розбір тексту по заданій граматиці з побудовою дерева розбору. Текст на вхідній мові задається у вигляді символьного (текстового) файлу. Програма повинна видавати повідомлення про наявність у вхідному тексті помилок.
Довжину ідентифікаторів і строкових констант вважати обмеженою 32 символами.
. 2 Синтаксичний аналізатор
Перед синтаксичним аналізатором стоять дві основні завдання: перевірити правильність конструкцій програми, яка представляється у вигляді вже виділених слів вхідного мови, і перетворити її в вигляд, зручний для подальшої семантичної (смисловий) обробки і генерації коду. Одним з таких способів подання є дерево синтаксичного розбору.
Програмування роботи недетермінірованного МП-автомата - це складне завдання. Розроблений алгоритм, дозволяє для довільної КС-граматики визначити, чи належить їй задана вхідна ланцюжок (алгоритм Кока-Янгера-Касамі).
Доведено, що час роботи цього алгоритму пропорційно n 3, де n - довжина вхідної ланцюжка. Для однозначної КС-граматики при використанні іншого алгоритму (алгоритм Ерлі) цей час пропорційно n 2. Подібна залежність робить ці алгоритми вимогливими до обчислювальних ресурсів. На практиці і не потрібен аналіз ланцюжка довільного КС-мови - більшість конструкцій мов програмування може бути віднесено в один з класів КС-мов, для яких розроблені алгоритми розбору, лінійно залежать від довжини вхідний ланцюжка.
КС-мови поділяються на класи відповідно до структури правил їх граматик. У кожному з класів накладаються додаткові обмеження на допустимі правила граматики.
Одним з таких класів є клас граматик передування. Вони використовуються для синтаксичного розбору ланцюжків за допомогою алгоритму зрушення-згортка. Виділяють такі типи граматик передування:
- простого передування;
- розширеного передування;
- слабкого передування;
- змішаної стратегії передування;
- операторного передування.
Алгоритм побудови синтаксичного аналізатора включає наступні етапи:
) складання правил граматики мови;
) виявлення безлічі крайніх правих і Кайно лівих термінальних і нетермінальних символів;
) побудова матриці передування.
Розглянемо ці етапи більш докладно.
4.3 Таблиці передування
Безліч правил граматики має вигляд:
lt; буква gt;? A | .... | < i align="justify"> Z | .... | a |.... | z | _
lt; аріфм.опер. gt;? + | - | * | /
lt; цифра gt;? 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
lt; ID gt;? Lt; буква gt;
| lt; ID gt; lt; буква gt;
| lt; ID gt; lt; цифра gt;
lt; сімв.конст. gt; ? lt; буква gt;
| lt; цифра gt;
<...
