Головна

Польський інверсний запис для регулярних виразів

  1. CD-RW - накопители на перезаписываемых CD-дисках
  2. I ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
  3. I. ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
  4. I. ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
  5. I. Пояснительная записка
  6. I. ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
  7. I. ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

Польський інверсний запис (ПОЛІЗ) для регулярних виразів будується на основі початкового регулярного виразу на основі наступних правил:

- Порядок операндів в початковому виразі і в перетвореному виразі співпадають.

- Операції в перетвореному виразу йдуть з урахуванням пріоритету безпосередньо за операндами.

Наприклад, ПОЛІЗ для виразу (a*+b)*c має такий вигляд: a*b+*c. .

В цьому прикладі в стандартному записі регулярного виразу бінарна операція конкатенація ( . ) природньо опущена, але в ПОЛІЗ потрібно завжди цю операцію явно вказувати. Важливою характеристикою ПОЛІЗ є відсутність дужок в запису виразу.

Алгоритм. Перетворення регулярного виразу в ПОЛІЗ.

Для перетворення виразу в ПОЛІЗ необхідно з кожною операцією зв'язати деяке число, яке будемо називати "пріоритет" ( 0 - найвищий пріоритет присвоїмо дужці '(' ).

П0. Прочитати поточну лексему.

П1. Якщо поточна лексема операнд, то занести її в поле результату та перейти

на П0.

П2. Якщо поточна лексема '(', то занести її в стек та перейти на П0.

П3. Якщо поточна лексема код операції, то доки пріоритет операції на вершині стека більший або рівний пріоритетові поточної операції, елементи з вершини стека перенести в поле результату. Поточну лексему занести в стек та перейти на П0.

П4. Якщо поточна лексема ')', то з вершини стека в поле результату перенести всі коди операцій, які передують в стеку ')'. Дужку '(' зняти з вершини стека та перейти на П0.

П5. Якщо досягли кінця вхідного виразу, то всі елементи із стека перенести в поле результату.



Регулярні множини та регулярні вирази | Застосування скінчених автоматів при розробці лексичних аналізаторів

Мови програмування та мовні процесори | Структура транслятора | Скінчені автомати | Мінімізація детермінованих скінчених автоматів | Скінчені автомати та праволінійні граматики | На основі поточного стану. | Методика програмування лексичних аналізаторів на основі скінчених автоматів. | Лабораторний практикум побудови лексичних аналізаторів. | Синтаксичний аналіз в мовних процесорах | Мал. 2. |

© um.co.ua - учбові матеріали та реферати