акож контекстно-вільною граматикою, або будь-яка граматика може бути віднесена до типу 0. У той же час існують вкорочують контекстно-вільні граматики, які не відносяться до типу 1, оскільки можуть містити правила виду, неприпустимі в цьому типі. Загалом, складність граматики обернено пропорційна того максимально можливого номеру типу, до якого може бути віднесена ця граматика. Самими простими є граматики типу 3, найскладнішими - типу 0.
4.5 Класифікація мов
Мови класифікуються відповідно до типами граматик, за допомогою яких вони задані, причому з усіх можливих граматик, які задають один і той же мова, вибирається граматика з максимально можливим номером. Складність мов відповідає складності граматик. Від класифікаційного типу мови залежить і складність распознавателя цієї мови.
Тип 0 - мови з фразової структурою. Це найскладніші мови, для розпізнавання яких потрібні обчислювачі, рівнопотужними машині Тьюринга. Для такої мови неможливо побудувати компілятор, який виконав би розбір за обмежений час на основі обмежених обчислювальних ресурсів.
Практично всі природні мови відносяться до цього типу. Одне і те ж слово в природній мові може мати різний зміст залежно від контексту і грати раз?? ічную роль у реченні. Ми такі мови далі розглядати не будемо.
Тип 1 - контекстно-залежні (КЗ) язикі.В загальному випадку час на розпізнавання мови типу 1 експоненціально залежить від довжини початкового ланцюжка символів.
Мови та граматики цього типу використовуються в перекладі текстів на природних мовах. Розпізнавачі, побудовані на їх основі, дозволяють аналізувати тексти з урахуванням контекстної залежності в пропозиціях вхідної мови, хоча в загальному випадку для точного перекладу все таки потрібне втручання людини. Такі граматики можуть використовуватися в сервісних функціях перевірки орфографії в мовних процесорах.
Однак мови програмування мають більш просту структуру, тому в компіляторах КЗ-мови не застосовуються.
Тип 2 - контекстно-вільні мови. Контекстно-вільні мови лежать в основі більшості сучасних мов програмування, на їх основі працюють деякі командні процесори, що допускають керуючі команди циклу та умови.
У загальному випадку час на розпізнавання речень мови цього типу полиномиально залежить від довжини ланцюжка символів (це кубічна або квадратична залежність залежно від класу мови). Але серед контекстно-вільних мов існує багато класів, для яких ця залежність лінійна, і багато мов програмування можна віднести до одного з таких класів.
Тип 3 - регулярні мови. Це найпростіший тип мов, і вони є найбільш широко поширеним типом, використовуваним в обчислювальних системах. Час на розпізнавання ланцюжків мови лінійно залежить від їх довжини.
Для роботи з такими мовами використовуються регулярні множини і вирази, кінцеві автомати. Далі ми розглянемо їх детально.
4.6 розпізнавачів. Завдання розбору
Граматики і розпізнавачі - два незалежні методу, які реально можуть бути використані для визначення мови. Однак при розробці компілятора для деякої мови програмування виникає завдання, яке вимагає зв'язати між собою ці два методи.
Розробники компілятора мають справу з конкретним мовою програмування, тобто граматика мови вже відома. Завдання розробників полягає в побудові распознавателя даної мови, який з'явиться основою синтаксичного аналізатора в компіляторі.
Отже, завдання розбору формулюється наступним чином: на основі наявної граматики деякої мови необхідно побудувати распознаватель для цієї мови. Задана граматика і распознаватель повинні бути еквівалентні, тобто визначати один і той же мова.
У загальному вигляді ця задача може бути вирішена не для всіх типів мов, хоча для контекстно-вільних і регулярних мов завдання розбору розв'язна і існують деякі формальні методи її вирішення.
Компілятор повинен не просто дати відповідь, чи належить вхідна ланцюжок даному мови, а й визначити її сенс. Фактично робота розпізнавача у складі компілятора полягає в побудові дерева розбору, яке потім використовується для генерації коду. Крім того, якщо вихідна ланцюжок не належить до заданого мови, компілятор повинен не просто встановити факт помилки, але і по можливості визначити її тип і місце розташування.
У числі інших завдань компілятор повинен визначити приналежність деякого тексту до конкретної мови. Відносно вихідної програми компілятор виступає в ролі распознавателя, а людина, що створила програму - в ролі генератора ланцюжків цієї мови.
Розпізнавач - це спеціальний алгоритм, що дозволяє для деякої...
