Page 25 - 4625

2. Операції в перетвореному виразі йдуть з урахуванням
пріоритету безпосередньо за операндами.
∗
∗
Наприклад: ПОЛІЗ для виразу ( + ) c має такий
∗
∗
вигляд: + c. У цьому прикладі в стандартному записі
регулярного виразу бінарна операція конкатенація ( ) при-
*
родно опущена, але в ПОЛІЗ потрібно завжди цю операцію
явно вказувати. Важливою характеристикою ПОЛІЗ є відсут-
ність дужок у запису виразу.
Алгоритм. Перетворення регулярного виразу в ПОЛІЗ.
Для перетворення виразу в ПОЛІЗ необхідно з кожною
операцією зв’язати деяке число, яке будемо називати “пріо-
ритет” ( 0 – найвищий пріоритет присвоїмо дужці '(' ).
П0. Прочитати поточну лексему.
П1. Якщо поточна лексема операнд, то занести її в поле
результату та перейти на П0.
П2. Якщо поточна лексема '(', то занести її в стек та
перейти на П0.
П3. Якщо поточна лексема код операції, то доки пріо-
ритет операції на вершині стека більший або рівний пріори-
тетові поточної операції, елементи з вершини стека перенести
в поле результату. Поточну лексему занести в стек та перейти
на П0.
П4. Якщо поточна лексема ')', то з вершини стека в поле
результату перенести всі коди операцій, які передують у
стеку ')'. Дужку '(' зняти з вершини стека та перейти на П0.
П5. Якщо досягли кінця вхідного виразу, то всі еле-
менти із стека перенести в поле результату.

2.6 Інтерпретація ПОЛІЗ регулярного виразу
Результат інтерпретації ПОЗІЗ – це скінчений автомат
М, який розпізнає (сприймає) множину ланцюжків, котрі поз-
начає регулярний вираз.
П0. Причитати поточну лексему.
П1. Якщо поточна лексема операнд , то побудувати

скінченний автомат М, такий що L(M)={ }. Занести автомат

24