Page 16 - 4761

2 ОСНОВНІ ПРИНЦИПИ ПОБУДОВИ ТРАНСЛЯТОРІВ

2.1 Розпізнавачі. Загальна схема

Розпізнавач – це спеціальний алгоритм,який дозволяє визначити належність
ланцюга символів деякій мові. Задача Розпізнавача полягає в тому, щоб на базі вихідного
ланцюга дати відповідь на питання, чи належить він даній мові.
Розпізнавачі – це один із способів визначення мови. В загальному вигляді
розпізнавач можна відобразити в вигляді умовної схеми (рис. 2.1).

Рисунок 2.1 – Умовна схема розпізнавача

Як видно з рисунка, розпізнавач складається з таках основних компонент:
- стрічки, яка містить вхідний ланцюг символів і зчитуючої головки, яка
спостерігає черговий символ в цьому ланцюгу;
- пристрою керування, який координує роботу розпізнавача, має деякий набір
станів і кінцеву пам'ять ( для зберігання свого стану і деякої проміжної інформації ) ;
- зовнішньої ( робочої памяті), яка може зберігати деяку інформацію в процесі
роботи розпізнавача і, на відміну від пам'яті пристрою керування має необмежений обєм.
Розпізнавач працює з символами свого алфавіту – алфавіту розпізнавача. Алфавіт
розпізнавача – кінцевий. Він включає в себе всі допустимі символи вхідних ланцюгів, а
також деякий додатковий алфавіт символів, які можуть бути оброблені пристроєм
керування і зберігатися в робочій памяті розпізнавача.
В процесі своєї роботи розпізнавач може виконувати деякі елементарні операції:
- читання чергового символу з вхідного ланцюга;
- зсув вхідного ланцюга на задану кількість символів (вправо чи вліво);
- доступ до робочої пам’яті для читання чи запису інформації;
- перетворення інформації в пам’яті пристрою керування, зміна стану
пристрою керування.
Те, які конкретно операції повинен виконуватися в процесі роботи розпізнавач,
визначається в пристрої керування.
Розпізнавач працює по крокам (тактам). На початку такта, як правило, зчитується
черговий символ з вхідного ланцюга, і в залежності від того символа пристрії керування
визначає, які дії необхідно виконати. Вся робота розпізнавача визначається наступними
параметрами:
- вмістом вхідного ланцюга символів і положенням головки для зчитування
інформації в ньому;
- станом пристрою керування;

14