Алгоритм Кока-Янгера-Касами.

Алгоритм Рутенхаузера.

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

Выражение должно быть записано в полной скобочной структуре. Например, формула a+b*c запишется в виде a+(b*c).

Обрабатывая выражение с полной скобочной структурой, алгоритм Рутенхаузера присваивает каждому символу S_i из строки с формулой число N_i, согласно алгоритму, приведённому ниже. Здесь S(j) – j-й символ, а N(j) – j-е число и используется переменная содержащая самое большое присвоенное N(j) значение.

Алгоритм: Присвоить.

Присвоить 1: N(0)0; J0

Присвоить 2: JJ+1; Если конец строки, то N(J)0 и выход;

Присвоить 3: Если S(J) это «(» или «операнд», то N(J)N(J-1)+1; перейти к Присвоить 2;

Присвоить 4: Иначе N(J)N(J-1)-1; перейти к Присвоить 2;

Первый символ S(0) является пробелом, являющимся фактически началом строки. Заметим, что конечное значение J на единицу больше длины строки. Например, пусть задана цепочка a+(b*c) тогда присвоение чисел будет происходить согласно следующей таблице:

Далее транслятор ищет наибольшее значение N(J). Это значение, назовем его K, появляется в структуре вида N(J): … (K-1) K (K-1) K (K-1) … Рассматриваемая структура соответствует последовательности символов следующего вида: Z операнд₁ Θ операнд₂ R.

Символ Z – либо левая скобка, либо левый конец выражения.

Точно также R – это правая скобка или правый конец выражения.

Символ Θ представляет ОПЕРАЦИЮ.

При обнаружении такой структуры значение двуместного выражения вычисляется и запоминается во временной ячейке T_i. Тройка T_i <= операнд₁ Θ операнд₂ фиксируется. Обработанные три символа вместе с Z и R (если последние являются скобками) удаляются, а на их место помещается T_i со значением N=(K-1). Если Z и R – концы строки, процесс завершен. В противном случае алгоритм повторяет поиск наибольшего числа N. Приведенный выше пример после однократной обработки имеет такой вид:

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

Более сложный пример применения метода Рутенхаузера, обрабатывающий арифметическое выражение (((a + b)*c) + d)¸(e + (a¸f)).

Стековые методы

Бауэр и Замельзон. Основные его компоненты СТЕК и таблица ПЕРЕХОДОВ. Анализатор использует два стека: один стек используется непосредственно при трансляции выражения, а второй стек – во время исполнения.

Стек транслятора имеет метку Т, а исполнительный – метку Е.

Транслятор прочитывает выражение один раз слева на право и вырабатывает последовательность команд двух видов:

K_I (I – есть идентификатор) является командой «Выбрать число по имени I и заслать его в стек Е »

K_§ (§ - операция) является командой «Выбрать два верхних операнда из стека Е, произвести над ними операцию § и занести результат в вершину стека Е ».

Когда при просмотре входной строки считываемый символ является ОПЕРАНДОМ выдается команда K_I и транслятор переходит к следующему символу.

Когда считываемый символ является операцией § производится одно из нескольких фиксированных действий. Как правило, либо § засылается в стек Т, либо выдается команда К_§.

В таблице переходов указывается, какие действия должен выполнять транслятор. В этой таблице каждой операции соответствует СТРОКА и СТОЛБЕЦ.

Элементами таблицы являются директивы транслятору.

Возможны 4 действия транслятора после прочтения операции § (операция в вершине стека Т обозначается h):

Имеется еще две специальные команды: Конец процесса и Ошибка, которые приказывают транслятору остановится и выдать соответствующую команду. ПРОЦЕССОР выбирает элементы таблицы, используя в качестве одного индекса h, верхнюю операцию стека Т, и в качестве второго, §, операцию, прочитанную последней из входной строки. Таблицу мы приведем для трансляции с языка простых арифметических выражений. В этой таблице L обозначает символ пробела, или пустую строку. Если стек Т пуст или пуста входная строка, то считается что прочитано L § - входной символ h - вершина стека Т.

Таблица переходов для простых алгебраических выражений.

Применим этот процесс к конкретному выражению (a*b+c*d)/(a-d)

Получается последовательность команд, имеющая вид:

K_a, K_b, K_*, K_c, K_d, K_*, K₊, K_a, K_d, K _-, K_/

Более простая запись получается, если опустить все скобки и использовать польскую запись (польский математик Лукасевич): ab*cd*+ad-/bc*+

Исполняющая программа использует стек Е и читает польскую запись слева направо.

При чтении операнда он засылается в стек при чтении операции она применяется к двум верхним элементам E. Для записи, выдаваемой транслятором, не возникает явных или неявных проблем старшинства. Программа выполняется в точности слева направо. Временная память автоматически управляется стеком E, содержащим все временные промежуточные значения. Не требуется стек T для хранения операндов.

Алгоритм Кока-Янгера-Касами.

Обсуждаемый алгоритм предназначен для разбора методом «снизу-вверх» слов любой контекстно-свободной грамматики, т.е. это – универсальный метод. Для его применения грамматика должна быть преобразована к нормальной форме Хомского (т.е. правила имеют вид: A®a или A®BC). Этот алгоритм имеет сложность O(n³) по времени и O(n²) по памяти. На первом этапе алгоритм строит треугольную таблицу с элементами t_ik, в каждую клетку которой помещается множество нетерминалов, из которых можно вывести отрезок слова начинающийся с символа a_i и длиной k.

Формально: t_ik = {A | A a_i…a_i+k-1}. Очевидно, что множества t_ik формально (рекурсивно) можно определить так:

t_i1 = {A | A®a_i - правило грамматики},

t_ij = {A | A®BC - правило грамматики и $k, 1£k<j такое, что BÎt_ik Ù CÎt_i+k,j-k}.

Если в t_1n есть S, то слово Î языку.

Пусть заполнены все строки таблицы до j-1 включительно. Рассмотрим t_ij.

Эта ячейка соответствует фрагменту слова <a_i…a_i+j-1>. Разбиваем этот фрагмент на пары слов всеми способами. Каждому варианту разбиения соответствует пара клеток таблицы, в которых стоят нетерминалы, из которых могут быть выведены соответствующие строки. Пусть это пара (t¢,t²). В t_ij поместим нетерминал A, если есть правило A®BC и BÎt¢, CÎt².

Пример. Рассмотрим неоднозначную грамматику: G = ({S,L,R}, {(,)}, {S®SS | LR, L®(, R®)}, S). Пусть задано слово ()()(). Построим таблицу.

На втором этапе восстанавливаем дерево вывода.

Это можно выполнить с помощью следующей рекурсивной процедуры:

GEN(i,j,A)

| 1. Если j=1 Ù A®a_i – правило с номером m, то выдать m.

| 2. Если j>1. Пусть k – наименьшее из чисел, для которых $ BÎt_ik CÎt_i+k,j-k и A®BCÎR

| имеет номер m. Выбрать это правило, выдать m и выполнить последовательно:

| GEN(i,k,B)???

ë GEN(i+k,j-k,C)???

Старт: GEN(1,n,S)

Замечание. Описанный алгоритм существенно опирается на то, что грамматика имеет форму Хомского.