Разработка компиляторов

       

Регулярные выражения


Определим следующие операции над множествами:

Тогда регулярные выражения над алфавитом T и языки, представляемые ими, могут быть определены следующим образом:

  • Символ , представляющий пустое множество, является регулярным выражением.
  • является регулярным выражением и представляет множество .
  • Для каждого символа a является регулярным выражением и представляет множество {a}.
  • Если p и q - регулярные выражения, представляющие множества P и Q , то (pq) , (p+q) и (p*) являются регулярными выражениями, представляющими множества PQ, и P* соответственно.

Отметим, что в этом определении подразумевается следующая система приоритетов: знак * обладает наивысшим приоритетом, за ним следует символ конкатенации, за которым следует символ |. Приоритеты можно изменять с помощью использования скобок.

Пример. Регулярное выражение 1(0+1)*1+1 представляет множество цепочек, начинающихся и заканчивающихся символом 1.

Упомянем без доказательства, что регулярные выражения эквивалентны праволинейным грамматикам. Таким образом, регулярным выражениям также соответствует естественный класс распознавателей в виде конечных автоматов.

Пример. Рассмотренная выше грамматика для идентификатора может быть записана с помощью следующего регулярного выражения: Letter (Letter | Digit)*.



Содержание раздела