Грамматики с непосредственной составляющей

Правила таких грамматик имеют вид

Это самый общий вид грамматики.

Пример:

Контекстно-зависимые грамматики (КЗ-грамматики)

Правила таких грамматик имеют вид

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

Пример:

Контекстно-свободные грамматики (КС-грамматики)

Правила таких грамматик имеют вид

Левая часть правил в таких грамматиках – всегда один символ

 

Пример:

Регулярные грамматики

Бывают праволинейные – с правилами вида.

Бывают леволинейные – с правилами вида.

Левая часть правил в таких грамматиках – всегда один символ, а в правой части не может быть более одного нетерминала.

Пример:

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

Идентификатор в паскале представляет собой букву, за которой следует нуль или несколько букв или цифр. Множество идентификаторов можно определить с помощью следующего регулярного выражения:

letter(letter|digit)*

Регулярное выражение строится из более простых регулярных выражений с использованием набора правил. Каждое регулярное выражение r обозначает или задает язык L(r).

Рекурсивное определение регулярного выражения над алфавитом A:

1) e (пустая строка) представляет собой регулярное выражение, обозначающее { e }, т.е. множество содержащее пустую строку.

2) Если , то a – регулярное выражение, обозначающее { a }, т.е. множество содержащее строку a.

3) Если r и s – регулярные выражения, обозначающее языки L(r) и L(s), то

· (r)|(s) – регулярное выражение, задающее язык . | - обозначает «или».

· (r)(s) – регулярное выражение, обозначающее . Конкатенация строк.

· (r)* - регулярное выражение, обозначающее . Т.е. регулярное выражение можно повторять 0 или более раз.

· (r) – регулярное выражение, обозначающее L(r).

Язык, задаваемый регулярным выражением, называется регулярным множеством.

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

· Унарный оператор * имеет высший приоритет и левоассоциативен.

· Конкатенация имеет второй по значимости приоритет и левоассоциативна.

· | (объединение) имеет низший приоритет и левоассоциативно.

При этих соглашениях (a)|((b)*(c) эквивалентно a | b * c.

 

Алгебраические свойства регулярных выражений

Аксиома	Описание
r|s=s|r	Оператор | коммутативен
r|(s|t)=(r|s)|t	Оператор | ассоциативен
(rs)t=r(st)	Конкатенация ассоциативна
r (s|t)=rs|rt (s|t)r=sr|tr	Конкатенация дистрибутивна над |
er=r re=r	e является единичным элементом по отношению к конкатенации
r*=(r|e)*	Связь между * и e
r**=r*	Оператор * идемпотентен

 

Для удобства записи регулярным выражениям можно давать имена и определять регулярные выражения с использованием этих имен. Например:

letter ® A | B | …| Z | a | b |…| z

digit ® 0 | 1 | … | 9

id ® letter(letter|digit)*

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

Такие записи называются регулярными определениями.

Конечные автоматы

Распознавателем (recognizer) языка называется программа, которая получает на вход строку x и отвечает “да”, если x – предложение языка, или в противном случае “нет”.

Для регулярных выражений используется частный случай распознавателя – конечный автомат (КА). Конечные автоматы бывают недетерминированные и детерминированные.

Недетерминированным конечным автоматом (НКА, nondeterministic finite automation, NFA) называется пятерка (S, A, m, s0, F) из:

1. Множества состояний S;

2. Множества входных символов A.

3. Функции перехода m, которая отображает пары состояние-символ на множество состояний.

4.

5. Состояния s0, известного как стартовое (начальное).

6. Множества состояний F, известных как допускающие (конечные);

 

Пример:

Автомат распознающий язык м((яу)|(ур*)). Т.е. слова мяу, му, мур, мурр и т.д.

S = {0, 1, 2, 3, 4, 5}

A = {м, я, у, р}

m:

(0, м) ® 1

(0, м) ® 2

(1, я) ® 3

(2, e) ® 3

(2, у) ® 4

(3, у) ® 5

(4, р) ® 4

s0 = 0

F = {4, 5}

 

Для конечного автомата можно построить так называемый граф переходов, вершинами которого являются состояния, а дуги задают функцию перехода. Конечные состояния обозначаются двойным кругом.

Для автомата из примера граф переходов будет выглядеть так:

 

 

Конечный автомат допускает или принимает (accept) входную строку x (а эта строка является допустимой) тогда и только тогда, когда в графе переходов существует некоторый путь от начального состояния к какому-либо из конечных, такой что метки дуг этого пути соответствуют строке x.

Автомат работает следующим образом. Работа начинается в стартовом состоянии. Затем автомат на каждом шаге читает символ и переходит в новое состояние (в зависимости от прочитанного символа и текущего символа). Затем читает следующий символ и опять переходит в новое состояние. И так до тех пор, пока не перейдет в конечное состояние. Недетерминированный конечный автомат может переходить в новое состояние и не читая символ (читая пустой символ e). Такой шаг называется e -переходом. Если встретился символ, для которого в данном состоянии нет дуги, и состояние не конечное, то автомат выдает ошибку (это означает, что строка недопустима, т.е. не принадлежит задаваемому автоматом языку).

В данном примере, проверяя строку «муррр», автомат пройдет через следующую последовательность состояний: .

Детерминированный конечный автомат (ДКА, deterministic finite automation, DFA) – специальный случай недетерминированного конечного автомата, в котором

· отсутствуют состояния, имеющие e -переходы

· для каждого состояния s и входного символа a существует не более одной дуги, исходящей из s и помеченной как a.

Для любого недетерминированного автомата можно построить эквивалентный детерминированный автомат. Существует формальный алгоритм приведения недетерминированного автомата к детерминированному, однако он не будет приведен в данной лекции.

 

Для примера с языком {мяу, му, мур, мурр, …} эквивалентный детерминированный автомат будет выглядеть так:

 

Cвязь между конечными автоматами, регулярными выражениями и регулярными грамматиками

Для любого регулярного автомата можно построить регулярную грамматику, порождающую тот же язык и наоборот. Для любого регулярного выражения можно построить конечный автомат. Обратное неверно.

Это можно изобразить следующим рисунком

 

Для предыдущего примера регулярная грамматика будет выглядеть так:

Применение конечных автоматов для создания интерпретаторов

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

Рассмотрим в качестве примера простой калькулятор, который умеет складывать и вычитать целые числа.

S = {f, p, m, e}

f – чтения первого аргумента

p – чтение слагаемого

m – чтение вычитаемого

e – знак = - окончание вычислений

A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, -, =}

F = {e}

Набор правил опишем графом переходов конечного автомата.

  

class CCalculator

{

    // Состояние

    enum State {sFirstArg, sPlus, sMinus, sEqual};

    State m_State;

 

    public int Calculate(string a_Script, out string a_ErrorMessage)

    {

          // Начальное состояние

          m_State = State.sFirstArg;

          // Строки, в которой будут сохраняться прочитанные числа

          int zResult = 0;

          string zArg = "";

 

          int i = 0; // Текущая позиция в строке

          while ((m_State!= State.sEqual) && (i < a_Script.Length))

          {

                switch (m_State)

                {

                     // Чтение первого аргумента

                     case State.sFirstArg:

                     {

                           // Читаем цифры числа

                           if ((a_Script[i] >= '0') && (a_Script[i] <= '9'))

                           {

                                 zArg += a_Script[i];

                           }

                                 // Если встретили + или -,

// запоминаем считанное число

                           else if (a_Script[i] == '+')

                           {

                                 if (zArg == "") zResult = 0;

                                 else zResult = int.Parse(zArg);

                                 zArg = "";

                                 m_State = State.sPlus;

                           }

                           else if (a_Script[i] == '-')

                           {

                                 if (zArg == "") zResult = 0;

                                 else zResult = int.Parse(zArg);

                                 zArg = "";

                                 m_State = State.sMinus;

                           }

                              else if (a_Script[i] == '=')

                              {

                                    if (zArg!= "") zResult = int.Parse(zArg);

                                    zArg = "";

                                    m_State = State.sEqual;

                              }

                           else

                           {

                                 a_ErrorMessage =

"Ошибка на позиции " + i.ToString() + ": недопустимый символ";

                                 return 0;

                           }

                           break;

                     }

                         

// Чтение слагаемого

                     case State.sPlus:

                     {

                           if ((a_Script[i] >= '0') && (a_Script[i] <= '9'))

                           {

                                 zArg += a_Script[i];

                           }

                           else if (a_Script[i] == '+')

                           {

                                 if (zArg!= "") zResult += int.Parse(zArg);

                                 zArg = "";

                                 m_State = State.sPlus;

                           }

                           else if (a_Script[i] == '-')

                           {

                                 if (zArg!= "") zResult += int.Parse(zArg);

                                 zArg = "";

                                 m_State = State.sMinus;

                           }

                           else if (a_Script[i] == '=')

                           {

                                 if (zArg!= "") zResult += int.Parse(zArg);

                                 zArg = "";

                                 m_State = State.sEqual;

                           }

                           else

                           {

                                 a_ErrorMessage =

"Ошибка на позиции " + i.ToString() + ": недопустимый символ";

                                 return 0;

                           }

                           break;

                     }

                     // Чтение вычитаемого

                     case State.sMinus:

                     {

                           if ((a_Script[i] >= '0') && (a_Script[i] <= '9'))

                           {

                                 zArg += a_Script[i];

                           }

                           else if (a_Script[i] == '+')

                           {

                                 if (zArg!= "") zResult -= int.Parse(zArg);

                                 zArg = "";

                                 m_State = State.sPlus;

                           }

                           else if (a_Script[i] == '-')

                           {

                                 if (zArg!= "") zResult -= int.Parse(zArg);

                                 zArg = "";

                                 m_State = State.sMinus;

                           }

                           else if (a_Script[i] == '=')

                           {

                                 if (zArg!= "") zResult -= int.Parse(zArg);

                                 zArg = "";

                                 m_State = State.sEqual;

                           }

                           else

                           {

                                 a_ErrorMessage =

"Ошибка на позиции " + i.ToString() + ": недопустимый символ";

                                 return 0;

                           }

                           break;

                     }                           

                }

                i++;

          }

          if (m_State == State.sEqual)

          {

                if (i == a_Script.Length)

                {

                     a_ErrorMessage = "";

                     return zResult;

                }

                else

                {

                     a_ErrorMessage =

"Ошибка на позиции " + i.ToString() + " символы после знака =";

                     return 0;

                }

          }

          a_ErrorMessage = "Ошибка: Скрипт не закончен";

          return 0;

    }

}

 

Конечные автоматы и ООП

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

Явное выделение состояний и конечного автомата позволяет более четко описать алгоритм работы объекта. Это, в свою очередь, позволяет избежать ошибок, возникающих, когда какое-то из состояний не учтено, например, попыток использовать объект, который не инициализирован. Также конечный автомат позволяет достаточно легко менять поведение объекта. Если функция перехода из состояние в состояние описана вне программы (в файле или базе данных), то поведение программы можно менять, не меняя ее текст.

Конечный автомат удобно использовать для описания логики пользовательского интерфейса. Нажимая кнопки и выполняя другие действия, пользователь переводит интерфейс из состояния в состояние. В зависимости от текущего состояния интерфейсные элементы (кнопки, поля ввода и др.) включаются и выключаются. Включение и выключение интерфейсных элементов удобно вынести в отдельный метод формы – так называемый активатор (enabler). Это более удобно и надежно, чем раскидывать включение и выключение кнопок в разные обработчики событий. Благодаря явному выделению автомата можно отследить все возможные действия пользователя (которые могут происходить в разной последовательности)  и обеспечить корректную реакцию на них.

Конечные автоматы используются в разных областях, когда нужно формально описать некоторое поведение: в компьютерных играх для описания поведения персонажей, в драйверах различных устройств, в прикладных системах (при обработе заказов клиентов, в системах документооборота и т.д.).

 

 

[1] Сборка (assembly) – это программная единица в C# - exe или dll-файл. При подключении dll-сборки к проекту в.NET можно использовать то, что не объявлено как internal.