ам'яттю;
з необмеженою зовнішньою пам'яттю.
розпізнавачів без зовнішньої пам'яті моделюються кінцевими автоматами і використовують у процесі роботи тільки кінцеву пам'ять УУ.
Розмір зовнішньої пам'яті распознавателей другого типу обмежений. Ці обмеження можуть носити характер деякої функціональної залежності від довжини початкового ланцюжка символів - лінійної, поліноміальної, експоненційною і т.п. Крім того, може бути зазначений спосіб організації зовнішньої пам'яті - стек, чергу, список і т.п. Наприклад, широко поширені розпізнавачі з пам'яттю магазинного типу, яка організована за стекового принципом.
У розпізнавачів останнього типу передбачається, що для їх роботи може знадобитися зовнішня пам'ять необмеженого обсягу, незалежно від довжини вхідний ланцюжка. У таких распознавателей використовується пам'ять з довільним методом доступу.
Всі три розглянутих складових організовують загальну класифікацію распознавателей. Наприклад, в ній можливий такий тип: «односторонній детермінований повністю певний распознаватель з лінійно обмеженою стековой пам'яттю».
Тип распознавателя в класифікації визначає його складність в цілому. Складність распознавателя безпосередньо пов'язана з типом мови, ланцюжки якого він повинен визначати. ??
Наприклад, для мов типу 1 розпізнавачів є двосторонні недетермінірованние автомати з лінійно обмеженою зовнішньою пам'яттю. Такий алгоритм вже може бути реалізований в ПО комп'ютера. Але Експоненціальна залежність часу розбору від довжини вхідний ланцюжка істотно обмежує застосування распознавателей для контекстно-залежних мов. Такі розпізнавачі, як правило, застосовуються для автоматизованого перекладу текстів на природних мовах, коли тимчасові обмеження на розбір тексту несуттєві.
Для контекстно-вільних мов розпізнавачів є односторонні недетермінірованние автомати з магазинною (стековой) зовнішньою пам'яттю. Крім того, серед усього безлічі контекстно-вільних мов можна виділити підклас детермінованих мов, для яких розпізнавачів є детерміновані автомати з магазинною пам'яттю. Цей клас мов найбільш цікавий для побудови компіляторів.
Для мов програмування більш доцільно будувати компілятори на основі контекстно-вільних мов, доповнюючи їх семантичним аналізатором, ніж використовувати в якості основи контекстно-вільні мови - така комбінація має більш високу швидкість роботи.
Для регулярних мов розпізнавачів є односторонні недетермінірованние розпізнавачі без зовнішньої пам'яті - кінцеві автомати (КА). Крім того, будь недетермінований КА завжди може бути перетворений в детермінований. У компіляторах розпізнавачі на основі регулярних мов використовуються для лексичного аналізу тексту вихідної програми. Регулярні мови знаходять застосування також у багатьох областях, пов'язаних з розробкою ПЗ обчислювальних систем.
4.8 Визначення та властивості регулярних виразів
Проблема генерування нескінченних мов допомогою кінцевих описів вирішується різними способами. Одним з них є використання регулярних виразів для породження нескінченних ланцюжків мови.
Регулярне безліч і регулярний вираз для деякого алфавіту визначається рекурсивно наступним чином:
- регулярний вираз, позначає регулярне безліч;
- регулярний вираз, позначає регулярне безліч;
де позначає регулярне безліч;
якщо і - довільні регулярні вирази, що позначають регулярні множини і, то,, - регулярні вирази, що позначають відповідно регулярні множини,,;
ніщо інше регулярним виразом і регулярним безліччю не є.
Іншими словами, регулярні множини - це ланцюжки символів над заданим алфавітом, побудовані з використанням операцій об'єднання, конкатенації і замикання.
Всі регулярні мови являють собою регулярні множини.
Два регулярних вирази і еквівалентні:, якщо вони позначають одне і те ж безліч.
Кожне регулярний вираз позначає одне й тільки одне регулярне безліч, але для одного регулярного безлічі може існувати скільки завгодно задають його регулярних виразів.
При запису регулярних виразів використовуються круглі дужки, як для звичайних арифметичних виразів. При відсутності дужок операції виконуються зліва направо з урахуванням пріоритету. Найвищим пріоритетом володіє операція ітерації, потім конкатенації, потім - об'єднання множин.
Наприклад, мова, представляє собою безліч всіх ланцюжків з нулів і одиниць довільної довжини, може бути описаний еквівалентними регулярними виразами
