Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Вывод цепочек

Читайте также:
  1. III. ВЫВОДЫ
  2. III. ВЫВОДЫ
  3. IV. Выводы и предложения.
  4. Б. Сосудистая и желчевыводящая системы печени
  5. В. Экзокринная часть железы: выводные протоки
  6. Вы думаете о том, какие выводы делают мужчины, глядя на вас
  7. ВЫВОД В РЕМОНТ

 

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

Чтобы формально определить понятие регулярного выражения, введем вначале понятие алфавита. Алфавит представляет собой конечный набор символов, подобный приведенным ниже.

{0,1} {а..я} {0..9}

Если А — алфавит, то к числу регулярных выражений относятся:

нулевая строка (обозначается e);

любой элемента А.

Кроме того, если Р и Q являются регулярными выражениями, то регулярными являются также следующие выражения.

PQ (Q следует после Р)

P | Q (Р или Q)

P* (нуль или более вхождений Р)

Следует отметить, что введенный ранее оператор + (одно или более вхождений элемента), строго говоря, не является оператором регулярного выражения, поскольку при описании любого регулярного выражения можно обойтись и без него. Это связано с тем, что любое выражение, содержащее +, можно заменить эквивалентным выражением, содержащим оператор конкатенации и оператор *. Например, выражение

(abc)+

эквивалентно записывается следующим образом (abc)(abc)*

Регулярные выражения часто употребляются для определения символов языков программирования через составляющие их знаки. Например, во многих языках программирования идентификатор можно представить следующим регулярным выражением

I (I | d)*

Здесь I обозначает букву, a d — цифру. Число с фиксированной запятой можно пред-ставить следующим выражением.

(d*d.d*) | (d*.dd*)

Здесь d также обозначает любую цифру.

Один из языков, ранее рассмотренных в данном разделе,

{ xn yn | n>0}

невозможно определить посредством регулярного выражения, поскольку в регулярных выражениях не существует возможности указать, что количество элементов х должно равняться количеству элементов у. Следовательно, в этом случае нам необходим более мощный механизм, который позволит описать такой очевидно простой язык. Один из методов заключается в использовании продукции (production), подобной приведенным ниже.

S->xSy

S->xy

Здесь символ "->" можно читать как "может иметь вид". Продукции могут использоваться для генерации строк языка с использованием следующих правил:

1. Начать с символа S и заменить его строкой, расположенной справа от знака продукции.

2. Если полученная строка не содержит больше символов S, она является строкой языка. В противном случае следует снова заменить S строкой после знака продукции, а затем снова вернуться к п. 2.

Приведем пример последовательности строк.

S

xSy

xxSyy

хххууу

Обычно подобную последовательность записывают следующим образом:

S => xSy => xxSyy => хххууу

Здесь знак "=>" читается "порождает". Последовательность шагов, использованная для генерации строки с применением продукций грамматики, называется порождением (derivation) строки.

Очевидно, что описанным выше способом могут быть получены все строки языка

{ xn yn | n>0}

При этом не будет порождена ни одна строка, не принадлежащая указанному языку.

Определим понятия грамматики, основываясь на введенном выше понятии продукции.

 


Дата добавления: 2015-07-07; просмотров: 102 | Нарушение авторских прав


Читайте в этой же книге: Структуры данных FAT | Восстанавливаемость | Этапы подготовки программы к выполнению | Операнды команд | Заголовок макроопределения | Присваивание значений переменным макроопределения | Оператор безусловного перехода и метки макроопределения | Тема 2.2.Трансляторы | Лексический, синтаксический и семантический анализаторы | Генератор кода. Распределение памяти. Виды переменных |
<== предыдущая страница | следующая страница ==>
Тема 2.3 Формальные языки и грамматики| Магазинный автомат

mybiblioteka.su - 2015-2024 год. (0.012 сек.)