Табличные распознаватели. Алгоритм Эрли. Алгоритм Кока—Янгера—Касами (Лекция 8) презентация

Табличные распознаватели Полиномиальная трудоемкость Универсальность Использование промежуточной таблицы Алгоритм Эрли Алгоритм Кока—Янгера—Касами

Алгоритм Эрли Начальное состояние определяется как <S'→•#S#; 0>. На каждом очередном шаге множество ситуаций меняется следующими операторами: Предсказатель. Если в множестве ситуаций Мi есть ситуация <А→α•Вβ; q>, то предсказатель добавляет в Мi ситуации <В→•γ; i> для всех альтернатив В→γ нетерминала В. Смысл такого добавления в том, что после символа аi входной цепочки, начиная с аi+1 распознаватель ищет (любую) подцепочку, которую можно вывести из В. Назовем ситуацию <А→α•Вβ; q> родительской, а ситуацию <В→•γ; i> порожденной. • Считыватель. Если в множестве ситуаций Мi есть ситуация <А→α•bβ; q> и если b – это очередной терминал аi+1 входной цепочки то в следующее множество ситуаций Мi+1 считыватель добавляет ситуацию <А→αb•β; q>.

Завершатель. Этот оператор применяется к любой ситуации вида <А→α•; q> в множестве Мi. Завершение правила показывает, что оно успешно применено, и из нетерминала А начиная с шага q выведена цепочка, совпадающая с подцепочкой аq aq+1 aq+2 ... ai. в соответствии с правилом А→α, т. е. формально, А  α  * аq aq+1 ... ai. Завершатель. Этот оператор применяется к любой ситуации вида <А→α•; q> в множестве Мi. Завершение правила показывает, что оно успешно применено, и из нетерминала А начиная с шага q выведена цепочка, совпадающая с подцепочкой аq aq+1 aq+2 ... ai. в соответствии с правилом А→α, т. е. формально, А  α  * аq aq+1 ... ai. Поэтому в множестве ситуаций Мq завершатель ищет ситуацию <А→•α; q>, и для каждой ситуации <В→γ•Аμ; s>, которая является родительской для <А→•α; q>, в Мi он добавляет новую ситуацию <В→γА•μ; s>. Это свидетельство того, что во входной цепочке подстрока аs as+1 ... ai может быть выведена из начальной части правила для нетерминала В, а именно, В  γАμ  * аs a s+1 ... aiμ . С каждым множеством ситуаций Мi все три оператора работают до тех пор, пока в Мi не могут появиться новые ситуации. Очевидно, что входная цепочка будет распознана (т.е. она является цепочкой языка, порождаемой данной грамматикой), если в заключительном множестве ситуаций встретится ситуация вида <S'→#S#•; 0>.

Пример. Пусть дана простая грамматика арифметических выражений: Пример. Пусть дана простая грамматика арифметических выражений: S'→#E# Е →Е+Т|Т Т→Т*Р|Р Р→а Входная строка: # a + a #

Множество существенных ситуаций Множество существенных ситуаций

Списочное представление вывода цепочки #a+a# после работы анализатора Эрли Списочное представление вывода цепочки #a+a# после работы анализатора Эрли

Алгоритм Кока-Янгера-Касами Суть алгоритма – в построении треугольной таблицы разбора T непосредственно по анализируемой цепочке. В каждую клетку tik таблицы помещается множество нетерминалов, из которых можно вывести отрезок входной строки длиной k, начинающийся с аi: tij={A|A* ai...ai+j-1}. Содержимое каждой клетки таблицы вычисляется очень просто по грамматике в нормальной форме Хомского. Действительно, ti1 = {A|A→aiR}, а tij = {A| A→BC  R & (k:1≤k<j):B  tik& C  ti+k, j-k}. Входная цепочка принадлежит языку, порождаемому грамматикой, если в клетке t1n встретится начальный нетерминал.

Таблица разбора для алгоритма Кока-Янгера-Касами для цепочки из шести символов

Пример. Проведем синтаксический анализ цепочки ( )( )( ) в двусмысленной грамматике: S→SS|LR; L→(; R→). В таблице разбора ней нетерминалы, стоящие в клетке tij, помечены индексом ij Пример. Проведем синтаксический анализ цепочки ( )( )( ) в двусмысленной грамматике: S→SS|LR; L→(; R→). В таблице разбора ней нетерминалы, стоящие в клетке tij, помечены индексом ij

Цикл для i от 2 до n Цикл для i от 2 до n Цикл для j от 1 до n-i+1 T[1,j] = . Цикл для k от 1 до i-1 T[1,j] := Т[1,j]  {А |  АВС  Р, BT[k.j], CT[i-k, j+k]} Конец цикла для k Конец цикла для j Конец цикла для i

Второй шаг алгоритма Второй шаг алгоритма – это восстановление дерева вывода цепочки. Это восстановление осуществляется с помощью рекурсивной процедуры GEN(i,j,A), которая порождает левый вывод А*аiai+1 ...aj-1. Эту процедуру легко построить: 1. Если j=1 и А→ai – это правило грамматики с номером m, то выдать m; 2. Пусть j>1. Выберем k – наименьшее из чисел, для которых существуют Вt ik, C  ti+k,j-k и правило А→ВС из R с номером m. Выберем это правило, выдаем m и выволняем последовательно GEN(i,k,В) и GEN(i+1,j-k,B). Вначале запускается GEN(1,n,S).

Неформальный пример работы процедуры: Неформальный пример работы процедуры: Для клетки t61 показаны два возможных варианта включения нетерминала S16 в эту клетку: либо в соответствии с правилом S16→S12S36, либо в соответствии с правилом S16→S14S32.