Алгоритм распознавания

Распознаватель использует единственную таблицу. Таблица содержит три столбца.

В первом столбце таблицы содержится содержимое стека в форме Tu, где Т - любой символ или ограничитель, а U-правая часть правила.

Второй столбец содержит соответствующие правые контексты (либо # - символ конца цепочки).

В третьем столбце записан номер правила, которое использовано при редукции.

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

Если такая строка найдена, осуществляется редукция в соответствии с правилом, номер которого указан в третьем столбце.

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

Последний сканируемый символ помещается в стек, и сканируется следующий символ предложения.

Предшествование m: n

Грамматика m,n предшествования это такая грамматика, которая удовлетворяет условиям:

1. Все правые части правил единственны.

2. Для любой пары цепочек xy таких, что |x| = m; |y| = n, выполняется не более одного из трех рассмотренных ниже отношений.

W = xy |x| = m; |y| = n.

x ∘<y, если первый символ цепочки y является головой основы.

x >∘ y, если последний символ цепочки x является хвостом основы.

x ≗ y,, если последний символ цепочки x и первый символ цепочки y принадлежат основе.

3.3.8. Ограниченный контекст

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

Рассмотрим следующую грамматику:

R:= aUa;

Q:= bVb;

U:= c;

V:= c.

К примеру есть цепочка: аса. Это не контекстно-свободная грамматика и не грамматика простого предшествования, но по контексту легко установить, на какой символ (U или на V) следует заменить символ "с". Данный вывод становится возможным на основе анализа ограниченного числа элементов. В данном случае используется 1:1 ограниченный контекстный преобразователь.

Определение 1:1 ограниченного контекстного распознавателя

Пусть в грамматике G(Z) имеется вывод Z => +xTuRy.

Также пусть имеется правило: U:= u.

Тогда, если в процессе разбора сентенциальной формы в стеке окажется …xTu, а входной символ будет R, то цепочку u следует привести к нетерминалу U. При такой конструкции: …TuR… необходимо уметь определить, является ли цепочка u простой фразой для нетерминала U.

Пример:

Цепочка: Z => …VR…;

Правило: V:= Tu;

То имеем вывод: Z => +…TuR.

Но так как правила U:= u у нас нет, мы не можем произвести замену цепочки u на нетерминал U. Если бы такое правило было, то можно было построить 1:1 ограниченный контекстный преобразователь.

Алгоритм 1:1 ограниченного контекстного преобразователя

Распознаватель пользуется единственной таблицей, которая содержит 3 столбца. В первом находится возможное содержимое стека в форме Tu.

Т - любой символ или ограничитель.

U - правая часть правила.

Во втором столбце находятся соответствующие правые контексты. В третьем столбце указывается номер правила, которое используется в этом случае.

На каждом шаге работы распознаватель среди строк таблицы ищет ту, в которой содержимое первого столбца совпадает с верхней частью стека. А содержимое второго столбца совпадает с последним считанным символом. Если такая строка найдена, осуществляется редукция. Основа в стеке заменяется в соответствии с правилом, номер которого указан в третьем столбце. Если такой строки нет, то редукция невозможна. Последний сканируемый символ помещается в стек, и сканируется следующий символ.

Таблица содержит все возможные конфигурации вида:

Tu

R

i

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

Для пояснения работы алгоритма рассмотрим следующий пример.

Пусть у нас есть следующие привила:

1. Z:=V;

2. Z:=aW;

3. V:=V1;

4. V:=bU;

5. U:=U0;

6. U:=0;

7. W:=0W1;

8. W:=01.

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

	Tu	R
	a01	#
	#aW	#
	#bU
	bU0
	bU0
	#V1
	#V1	#
	#V	#
	a0W1	#
	b0	#

Ниже приведены несколько цепочек, разобранных по данному алгоритму:

Z

a

W

1)

#a01#

4)

Z

b

V

#

U

V

1#

5, 6)

# 5)

U

# 6)

Z

V

#

U

V

b

U

W

a

W

2)

#a0011#

3)

Z

a

W

#aW#

a

W

Z

W

7)

#

#

Теперь рассмотрим разбор первой цепочки более подробно:

Цепочка: Алгоритм разбора:

W

Z

a

W

#a0011#

a #

W a #

# Z #

W   a #

Блок-схема работы по алгоритму 1:1 ограниченного контекста

Примеры разбора цепочек по алгоритму 1:1 ограниченного контекстного преобразователя

Пример №1. Задана цепочка: #a0011#.

Шаг№1.

а) Считываем символ цепочки в переменную R:

R=#.

б) Увеличиваем переменную i на единицу:

i=1.

в) Проверяем совпадение с таблицей - совпадений нет.

г) Переносим символ из переменной R в стек STK:

STK=#.

Шаг№2.

а) Считываем символ цепочки в переменную R:

R=a.

б) Проверяем совпадение с таблицей - совпадений нет.

в) Переносим символ из переменной R в стек STK:

STK=#а.

Шаг№3.

а) Считываем символ цепочки в переменную R:

R=0.

б) Проверяем совпадение с таблицей - совпадений нет.

в) Переносим символ из переменной R в стек STK:

STK=#а0.

Шаг№4.

а) Считываем символ цепочки в переменную R:

R=0.

б) Проверяем совпадение с таблицей - совпадений нет.

в) Переносим символ из переменной R в стек STK:

STK=#а00.

Шаг№5.

а) Считываем символ цепочки в переменную R:

R=1.

б) Проверяем совпадение с таблицей - совпадений нет.

в) Переносим символ из переменной R в стек STK:

STK=#а001.

Шаг№6.

а) Считываем символ цепочки в переменную R:

R=1.

б) Проверяем совпадение с таблицей - совпадение есть.

в) Производим замену верхней части стека по правилам:

STK=#а0W.

г) Проверяем совпадение с таблицей - совпадений нет.

д) Переносим символ из переменной R в стек STK:

STK=#а0W1.

Шаг№7.

а) Считываем символ цепочки в переменную R:

R=#.

б) Увеличиваем переменную i на единицу:

i=2.

в) Проверяем совпадение с таблицей - совпадение есть.

г) Производим замену верхней части стека по правилам:

STK=#аW.

д) Проверяем совпадение с таблицей – совпадения есть.

е) Производим замену верхней части стека по правилам:

STK=#Z.

ж) Проверяем совпадение с таблицей – совпадений нет.

з) Переносим символ из переменной R в стек STK:

STK=#Z#.

и) Так как i=2 и в стеке содержится #Z#, то делаем вывод, что

цепочка построена по правилам.

Пример №2. Задана цепочка: #a001#

Шаг№1.

а) Считываем символ цепочки в переменную R:

R=#.

б) Увеличиваем переменную i на единицу:

i=1.

в) Проверяем совпадение с таблицей - совпадений нет.

г) Переносим символ из переменной R в стек STK:

STK=#.

Шаг№2.

а) Считываем символ цепочки в переменную R:

R=a.

б) Проверяем совпадение с таблицей - совпадений нет.

в) Переносим символ из переменной R в стек STK:

STK=#а.

Шаг№3.

а) Считываем символ цепочки в переменную R:

R=0.

б) Проверяем совпадение с таблицей - совпадений нет.

в) Переносим символ из переменной R в стек STK:

STK=#а0.

Шаг№4.

а) Считываем символ цепочки в переменную R:

R=0.

б) Проверяем совпадение с таблицей - совпадений нет.

в) Переносим символ из переменной R в стек STK:

STK=#а00.

Шаг№5.

а) Считываем символ цепочки в переменную R:

R=1.

б) Проверяем совпадение с таблицей - совпадений нет.

в) Переносим символ из переменной R в стек STK:

STK=#а001.

Шаг№6.

а) Считываем символ цепочки в переменную R:

R=#.

б) Увеличиваем переменную i на единицу:

i=2.

в) Проверяем совпадение с таблицей – совпадений нет.

г) Переносим символ из переменной R в стек STK:

STK=#а001#.

д) Так как i=2 и в стеке не содержится #Z#, то делаем вывод, что

цепочка построена неверно.

Определение m: n - ограниченного контекста

Так же, как и в простом предшествовании, расширим ограниченный контекст до m:n символов.

Пусть имеем правило U:=u,где для каждой пары цепочек:

|V| = m;

|W| = n.

И некоторый вывод: Z => +..VuW...

Цепочка u является основой сентенциальной формы, и данная цепочка u может быть заменена на нетерминал U. Такое правило m:n - ограниченно контекстное, в то время как R[W](то есть R содержит W)содержит R входных символов. В этом случае можно заменить u на U.

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

3.4. Автоматы с магазинной памятью, [ МП-автомат ]

Конечные автоматы успешно решали задачи распознавания цепочек, построенных на основе автоматической грамматики. Но эта грамматика не в состоянии охватить всё множество конструкций языков программирования. Более приемлемой является КС-грамматика. Для распознавания цепочек генерируемых КС-грамматикой вводят понятие МП-автомат. Как и в случае с КА, обработка осуществляется за несколько шагов. В отличие от КА, МП может обработать входной символ в течение нескольких шагов. Каждый шаг процесса определяется несколькими правилами, то есть состоянием автомата, верхним символом магазина и текущим символом входной цепочки.

а1 а2 …

Устройство управления

Операции над магазином:

­ выбрать символ из магазина;

­ заслать в магазин;

­ оставить в магазине без изменения.

Операции над состоянием:

­ оставить в прежнем состоянии;

­ перейти в новое состояние.

Операции над входной цепочкой:

­ перейти к следующему входному символу;

­ остаться на прежнем символе.

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

Автомат задаётся:

­ конечным множеством входных символов;

­ конечным множеством магазинных символов, включая маркер;

­ некоторой функцией, обеспечивающей переход из одного состояния в другое.

Переход выполняется операцией над магазином, входом и состоянием. Цепочка символов входного алфавита допускается распознавателем, если над действием этой цепочки начать работу в некотором выделенном состоянии и с начальным содержимым магазина и делать последовательность переходов, попадая в заключительное состояние, при котором магазин пуст. Таким образом, МП - автомат есть семёрка символов:

МП={Q,, Г,, q₀, Г₀, F};

Q - множество состояний;

S - входной алфавит;

Г - алфавит магазинных символов;

- функция отображения, обеспечивающая преобразование:;

q₀- начальное состояние;

Г₀- начальный символ магазина;

F - множество заключительных символов:.

Конфигурация автомата определяется символами (q, W, S), где (цепочка входных символов).

Переход из одного состояния в другое - бинарная операция:

(q₀, W, Z)|- (q₁, W, Z).

Это имеет место тогда и только тогда, когда.

Цепочка принимается автоматом, если возможен переход: |―,

где - начальное состояние, е - пустая цепочка ().

Любая программа может быть записана в постфиксной форме.

Функция отображения:, где - символ, - подмножество символов.

Автоматы могут не считывать ничего из входной цепочки, а работать только с магазином. Если магазин пуст, то автомат считывает символ из входной цепочки.

Язык:. Верхний символ магазина - левый символ цепочки - загружаем в магазин и сравниваем. Если цепочка считана и в магазине - маркер дна, то цепочка принята автоматом.

I.

- загрузка, - сравнение, - заключительное состояние (цепочка принята или нет).

, - не знаем;

- начальное состояние;

Z- начальные символы магазина; МП=;

- заключительное состояние.

Функция отображения:

Автомат детерминированный.

1) - 0 в магазин;

2) - загрузка магазина;

3) - сравнение 1 и 0;

4) - убираем маркер.

Рассмотрим 0011:

|- |- |- |- |-.

Рассмотрим:

|- за n шагов |- |- |- за (n-1) шаг |- |-.

Автомат может продолжить работу далее, если он прочёл всю входную цепочку, но не сделает следующего шага, так как магазин пуст.

II.;

(обращение);

;

;

1);

2);

3) - появилась недетерминированность;

4).

Однозначно можно сравнить и загрузить в автомат:

;

;

;

.

Рассмотрим aabbbbaa:

|- |- |-;

|- ^(*) (*)|- |- (**)|-;

|- |- |- |-.

Если автомат недетерминированный, его распознавательная способность гораздо мощнее.

да

нет

начало

Загрузка начального (выделенного) состояния

Сканирование символа входной цепочки

Входная цепочка пуста?

Цепочка символов входного алфавита является недопустимой

нет

да

нет

Выполнение операций, задаваемых управляемым устройством

магазин пуст ?

Цепочка символов входного алфавита является допустимой

да

Входная цепочка пуста?

Цепочка символов входного алфавита является недопустимой

Рис.1. Блок-схема алгоритма

Пример:.

- загрузка (начальное состояние), - сравнение, - заключительное

состояние (принята или нет цепочка).

,

Z- начальные символы магазина;

МП=;

Функция отображения:

1. - 0 в магазин;

2. - загрузка магазина;

3. - сравнение 1 и 0 при q₀;

4. - сравнение 1 и 0 при q₁;

5. - убираем маркер.

I. Рассмотрим допустимую цепочку 0011.

Загрузка начального (выделенного) состояния

Итерация 1:

Входная цепочка пуста? Нет.

Сканирование символа входной цепочки 0.

Выполнение операций, задаваемых управляемым устройством |―.

Магазин пуст? Нет.

Итерация 2:

Входная цепочка пуста? Нет.

Сканирование символа входной цепочки 0.

Выполнение операций, задаваемых управляемым устройством |― |.

Магазин пуст? Нет.

Итерация 3:

Входная цепочка пуста? Нет.

Сканирование символа входной цепочки 1.

Выполнение операций, задаваемых управляемым устройством |― |.

Магазин пуст? Нет.

Итерация 4:

Входная цепочка пуста? Нет.

Сканирование символа входной цепочки 1.

Выполнение операций, задаваемых управляемым устройством |―.

Магазин пуст? Да.

Входная цепочка пуста? Да.

Цепочка символов входного алфавита является допустимой.

II. Рассмотрим недопустимую цепочку 001.

Загрузка начального (выделенного) состояния.

Итерация 1:

Входная цепочка пуста? Нет.

Сканирование символа входной цепочки 0.

Выполнение операций, задаваемых управляемым устройством |―.

Магазин пуст? Нет.

Итерация 2:

Входная цепочка пуста? Нет.

Сканирование символа входной цепочки 0.

Выполнение операций, задаваемых управляемым устройством |― |.

Магазин пуст? Нет.

Итерация 3:

Входная цепочка пуста? Нет.

Сканирование символа входной цепочки 1.

Выполнение операций, задаваемых управляемым устройством |― |.

Магазин пуст? Нет.

Итерация 4:

Входная цепочка пуста? Да.

Цепочка символов входного алфавита является недопустимой.