Распознаватели кс языков с возвратом - Altarena.ru — технологии и ответы на вопросы

Содержание

Принципы работы распознавателей с возвратом
Определение LR(k)-грамматики
Принципы работы распознавателей с возвратом
Главная > Документ
Метод рекурсивного спуска
Распознаватели КС-языков с возвратом
Принципы работы распознавателей с возвратом
Главная > Документ
Видео

Принципы работы распознавателей с возвратом

Распознаватели с возвратом – это самый примитивный тип распознавателей для КС-языков. Логика их работы основана на моделировании недетерминированного МП-автомата.

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

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

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

Второй вариант реализации алгоритма связан с управлением параллельными процессами в вычислительных системах, поэтому сложен в реализации. Кроме того, на каждом шаге работы МП-автомата альтернатив следующих состояний может быть много, а количество возможных параллельно выполняющихся процессов в операционных системах ограничено, поэтому применение второго варианта алгоритма осложнено. По этим причинам большее распространение получил первый вариант алгоритма, который предусматривает возврат к ранее запомненным состояниям МП-автомата – отсюда и название “разбор с возвратами”.

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

Есть еще одна особенность в моделировании МП-автомата: любой практически ценный алгоритм должен завершаться за конечное число шагов (успешно или неуспешно). Алгоритм моделирования работы произвольного МП-автомата в общем случае не удовлетворяет этому условию. Например, даже после считывания всей входной цепочки символов МП-автомат может совершить произвольное (в том числе и бесконечное) число -переходов. В том случае, если цепочка не принята, это может привести к бесконечному количеству шагов моделирующего алгоритма, который по этой причине никогда не будет закончен.

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

Алгоритмы разбора с возвратами обладают экспоненциальными характеристиками. Это значит, что вычислительные затраты алгоритмов экспоненциально зависят от длины входной цепочки символов: α, αVT*, n=|α|. Конкретная зависимость определяется вариантом реализации алгоритма.

Доказано, что в общем случае при первом варианте реализации для произвольной КС-грамматики G(VT,VN,P,S) время выполнения данного алгоритма Тэбудет иметь экспоненциальную зависимость от длины входной цепочки, а необходимый объем памяти Мэ– линейную зависимость от длины входной цепочки: Тэ= О(еn) и Мэ= О(n). При втором варианте реализации, наоборот, время выполнения данного алгоритма Тэбудет иметь линейную зависимость от длины входной цепочки, а необходимый объем памяти Мэ– экспоненциальную зависимость от длины входной цепочки: Тэ= О(n) и Мэ= О(еn).

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

Далее рассмотрены два основных варианта таких алгоритмов.

Источник

Определение LR(k)-грамматики

Восходящие распознаватели КС-языков без возвратов

Восходящие распознаватели выполняют построение дерева вывода снизу вверх. Результатом их работы является правосторонний вывод. Функционирование таких распознавателей основано на модификациях алгоритма «сдвиг-свертка» (или «перенос-свертка»).

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

что следует выполнять: сдвиг (перенос) или свертку;

какую цепочку символов a выбрать из стека для выполнения свертки;

какое правило выбрать для выполнения свертки (в том случае, если существует несколько правил вида A₁->a, A₂->a, … A_n->a).

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

В первую очередь можно использовать тот же самый подход, который был положен в основу определения LL(k)-грамматик. Тогда мы получим другой класс КС-грамматик, который носит название LR(k)-грамматик.

КС-грамматика обладает свойством LR(k), k ³ 0, если на каждом шаге вывода для однозначного решения вопроса о выполняемом действии в алгоритме «сдвиг-свертка» («перенос-свертка») расширенному МП-автомату достаточно знать содержимое верхней части стека и рассмотреть первые k символов от текущего положения считывающей головки автомата во входной цепочке символов.

Грамматика называется LR(k)-грамматикой, если она обладает свойством LR(k) для некоторого k³0.

Название «LR(k)», как и рассмотренное выше «LL(k)», также несет определенный смысл. Первая литера «L» также обозначает порядок чтения входной цепочки символов: слева— направо. Вторая литера «R» происходит от слова «right» и, по аналогии с LL(k), означает, что в результате работы распознавателя получается правосторонний вывод. Вместо «k» в названии грамматики стоит число, которое показывает, сколько символов входной цепочки надо рассмотреть, чтобы принять решение о действии на каждом шаге алгоритма «сдвиг-свертка». Так, существуют LR(0)-грамматики, LR(1)-грамматики и другие классы.

В совокупности все LR(k)-грамматики для всех k ³ 0 образуют класс LR-грамматик.

На рис. 12.4 схематично показано частичное дерево вывода для некоторой LR(k)-грамматики. В нем w обозначает уже разобранную часть входной цепочки a, на основе которой построена левая часть дерева g. Правая часть дерева х — это еще не разобранная часть, а А — это нетерминальный символ, к которому на очередном шаге будет свернута цепочка символов z, находящаяся на верхушке стека МП-автомата. В эту цепочку уже входит прочитанная, но еще не разобранная часть входной цепочки u. Правая часть дерева х будет построена на основе части входной цепочки t. Свойство LR(k) предполагает, что однозначный выбор действия, выполняемого на каждом шаге алгоритма «сдвиг-свертка», может быть сделан на основе цепочки u и k первых символов цепочки t, являющихся частью входной цепочки a. Этим очередным действием может быть свертка цепочки z к символу А или перенос первого символа из цепочки t и добавление его к цепочке z.

Рис. 12.4. Схема построения дерева вывода для LR(k)-грамматики

Рассмотрев схему построения дерева вывода для LR(k)-грамматики на рис. 12.4 и сравнив ее с приведенной выше на рис. 12.1 схемой для LL(k)-грамматики, можно предположить, что класс LR-грамматик является более широким, чем класс LL-грамматик. Основанием для такого предположения служит тот факт что на каждом шаге работы распознавателя LR(k)-грамматики обрабатывается больше информации, чем на шаге работы распознавателя LL(k)-грамматики. Действительно, для принятия решения на каждом шаге алгоритма распознавания LL(k)-грамматики используются первые k символов из цепочки ut, а для принятия решения на шаге распознавания LR(k)-грамматики — вся цепочка u и еще первые k символов из цепочки t. Очевидно, что во втором случае можно проанализировать больший объем информации и, таким образом, построить вывод для более широкого класса КС-языков.

Для LR(k)-грамматик известны следующие полезные свойства:

· всякая LR(k)-грамматика для любого k >= 0 является однозначной;

· существует алгоритм, позволяющий проверить, является ли заданная грамматика LR(k)-грамматикой для строго определенного числа k.

Есть, однако, неразрешимые проблемы для произвольных КС-грамматик (они аналогичны таким же проблемам для других классов КС-грамматик):

· не существует алгоритма, который бы мог проверить, является ли заданная КС-грамматика LR(k)-грамматикой для некоторого произвольного числа k;

· не существует алгоритма, который бы мог преобразовать (или доказать, что преобразование невозможно) произвольную КС-грамматику к виду LR(k)-грамматики для некоторого k.

Кроме того, для LR-грамматик доказано еще одно очень интересное свойство — класс LR-грамматик полностью совпадает с классом детерминированных КС-языков. То есть, во-первых, любая LR(k)-грамматика задает детерминированный КС-язык (это очевидно следует из однозначности всех LR-грамматик), а во-вторых, для любого детерминированного КС-языка можно построить LR-грамматику, задающую этот язык.

В принципе класс LR-грамматик очень удобен для построения распознавателей детерминированных КС-языков (а все языки программирования, безусловно, относятся к этому классу). Но тот факт, что для каждого детерминированного КС-языка существует задающая его LR-грамматика, еще ни о чем не говорит, поскольку из-за неразрешимости проблемы преобразования отсутствует алгоритм, который позволил бы эту грамматику построить всегда. Данный детерминированный КС-язык может быть изначально задан грамматикой, которая не относится к классу LR-грамматик. В таком случае совсем не очевидно, что для этого языка удастся построить распознаватель на основе LR-грамматики, потому что в общем случае нет алгоритма, который бы позволил эту грамматику получить, хотя и известно, что она существует. То, что проблема не разрешима в общем случае, совсем не означает, что ее не удастся решить в конкретной ситуации. И здесь факт существования LR-грамматики для каждого детерминированного КС-языка играет важную роль — всегда есть смысл в каждом конкретном случае пытаться построить такую грамматику.

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

Источник

Принципы работы распознавателей с возвратом

Главная > Документ

Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

2. Иначе (если j > 1) возьмем k как наименьшее из чисел, для которых  АВХ  Р, BT[k,j], CT[i-k,j+k] (таких правил может быть несколько, для определенности берем наименьшее k). Пусть правило АВС имеет номер m. Тогда нужно выдать этот номер m, потом вызвать сначала R(i,k,B), а затем — R(i-k,j+k,C).

Для получения всей последовательности номеров правил нужно вызвать R(1,n,S).

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

Алгоритм Эрли (основные принципы)

Алгоритм Эрли подробно здесь не рассматривается. Его описание можно найти, например, в книге [6, т.1].

В целом алгоритм Эрли имеет лучшие характеристики среди всех универсальных алгоритмов распознавания входных цепочек для произвольных КС-грамматик. Он превосходит алгоритм Кока—Янгера—Касами для однозначных грамматик (которые представляют интерес в первую очередь), хотя и является более сложным в реализации.

Метод рекурсивного спуска

Алгоритмы анализа, расходующие на обработку входной цепочки линейное время, применимы только к некоторым подклассам КС-грамматик. Рассмотрим один из таких методов.

Пример : пусть дана грамматика G =(, , P, S), где

и надо определить, принадлежит ли цепочка caba языку L(G).

Построим вывод этой цепочки:

S  AB  cAB  caB  cabA  caba

Следовательно, цепочка принадлежит языку L(G). Последовательность применений правил вывода эквивалентна построению дерева разбора методом «сверху вниз»:

Пример: совокупность процедур рекурсивного спуска для грамматики G = (, , P, S), где

FILE fp; / указатель на файл, в котором находится

void ERROR(); / функция обработки ошибок /

Источник

Распознаватели КС-языков с возвратом

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

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

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

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

Хотя МПА представляет собой односторонний распознаватель, алгоритм моделирования его работы предусматривает возврат к уже прочитанной цепочке символов.

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

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

Вычислительная сложность алгоритмов:

В общем случае при первом варианте реализации время выполнения алгоритма для произвольной КС-грамматики имеет экспоненциальную, а необходимый объём памяти – линейную зависимость от длины входной цепочки: T=O(e n ), M=O(n). При втором варианте ситуация обратная – время имеет линейную зависимость, а требуемый объём памяти – экспоненциальную: T=O(n), M=O(e n ). В любом случае, непомерно большие вычислительные затраты на реализацию алгоритма существенно ограничивают возможности его применения. Для конкретных классов КС-языков существуют более эффективные алгоритмы распознавания.

Основные варианты разбора с возвратом – это нисходящий распознаватель и распознаватель на основе алгоритма «сдвиг-свёртка».

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

Источник

Принципы работы распознавателей с возвратом

Главная > Документ

Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

Принципы работы распознавателей с возвратом

Распознаватели с возвратом — это самый примитивный тип распознавателей для КС-языков. Логика их работы основана на моделировании недетерминированного МП-автомата.

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

Второй вариант реализации алгоритма связан с управлением параллельными процессами в вычислительных системах, поэтому сложен в реализации. Кроме того, на каждом шаге работы МП-автомата альтернатив следующих состояний может быть много, а количество возможных параллельно выполняющихся процессов в операционных системах ограничено, поэтому применение второго варианта алгоритма осложнено. По этим причинам большее распространение получил первый вариант алгоритма, который предусматривает возврат к ранее запомненным состояниям МП-автомата — отсюда и название «разбор с возвратами».

При втором варианте реализации, наоборот, время выполнения данного алгоритма Т э будет иметь линейную зависимость от длины входной цепочки, а необходимый объем памяти М э — экспоненциальную зависимость от длины входной цепочки: Т э = O(n) и М э = O(е n ).

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

Для многих классов КС-языков существуют более эффективные алгоритмы распознавания, поэтому алгоритмы разбора с возвратами применяются редко.

Далее рассмотрены два основных варианта таких алгоритмов.

Нисходящий распознаватель с возвратом

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

Функция переходов МП-автомата строится на основе правил грамматики:

Этот МП-автомат уже был рассмотрен выше.

Работу данного МП-автомата можно неформально описать следующим образом:

если на верхушке стека автомата находится нетерминальный символ А, то его можно заменить на цепочку символов , если в грамматике языка есть правило А, не сдвигая при этом считывающую головку автомата (этот шаг работы называется «подбор альтернативы»);

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

Данный МП-автомат может быть недетерминированным, поскольку при подборе альтернативы в грамматике языка может оказаться более одного правила вида А, следовательно, тогда функция (q,,A) будет содержать более одного следующего состояния — у автомата будет несколько альтернатив.

Рассмотренный МП-автомат строит левосторонние выводы и читает цепочку входых символов слева направо. Поэтому для него естественным является построение дерева вывода сверху вниз. Такой распознаватель называется нисходящим.

Распознаватель на основе алгоритма «сдвиг-свертка»

Начальная конфигурация автомата определяется так: (q,,) — автомат пребывает в своем единственном состоянии q, считывающая головка находится в начале входной цепочки символов  VT *, стек пуст.

Конечная конфигурация автомата определяется так: (q,,S) — автомат пребывает в своем единственном состоянии q, считывающая головка находится за концом входной цепочки символов, в стеке лежит символ, соответствующий целевому символу грамматики S. Функция переходов МП-автомата строится на основе правил грамматики:

Неформально работу этого расширенного автомата можно описать так: если на верхушке стека находится цепочка символов , то ее можно заменить на нетерминальный символ А, если в грамматике языка существует правило вида А, не сдвигая при этом считывающую головку автомата (этот шаг работы называется «свертка»); с другой стороны, если считывающая головка автомата обозревает некоторый символ входной цепочки а, то его можно поместить в стек, сдвинув при этом головку на одну позицию вправо (этот шаг работы называется «сдвиг» или «перенос»). Сам алгоритм, моделирующий работу такого расширенного автомата, называется алгоритмом «сдвиг-свертка» или «перенос-свертка» (по названиям основных действий алгоритма).

Этот расширенный МП-автомат строит правосторонние выводы и читает цепочку входных символов слева направо. Поэтому для него естественным является построение дерева вывода снизу вверх. Такой распознаватель называется восходящим.

Преимущество у данного алгоритма то же, что и у алгоритма нисходящего разбора с возвратами — простота реализации. Поэтому и использовать его можно практически в тех же случаях — когда известно, что длина исходной цепочки символов заведомо не будет большой (не больше нескольких десятков символов).

Этот алгоритм также универсален. На его основе можно распознавать входные цепочки языка, заданного любой КС-грамматикой, достаточно лишь преобразовать ее к приведенному виду (а это можно сделать с любой грамматикой, см. раздел «Преобразование КС-грамматик. Приведенные грамматики»), чтобы она не содержала цепных правил и -правил.

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

В принципе два рассмотренных алгоритма — нисходящего и восходящего разбора с возвратами — имеют схожие характеристики по потребным вычислительным ресурсам и одинаково просты в реализации. То, какой из них лучше взять для реализации простейшего распознавателя в том или ином случае, зависит прежде всего от грамматики языка. Вопрос о выборе типа распознавателя — нисходящий либо восходящий — достаточно сложен. В компиляторах на него кроме структуры правил грамматики языка влияют и другие факторы, например, необходимость локализации ошибок в программе, а также то, что предложения всех языков программирования строятся в нотации «слева направо». Этот вопрос будет затронут далее, при рассмотрении других вариантов распознавателей для КС-языков; пока же эти два типа распознавателей можно считать сопоставимыми по эффективности (отметим — низкой эффективности) своей работы и простоте реализации.

Табличные распознаватели для КС-языков

Общие принципы работы табличных распознавателей

Табличные алгоритмы обладают полиномиальными характеристиками требуемых вычислительных ресурсов в зависимости от длины входной цепочки. Для произвольной КС-грамматики G( VT,VN,P, S) время выполнения алгоритма Т э имеет кубическую зависимость от длины входной цепочки, а необходимый объем памяти М э — квадратичную зависимость от длины входной цепочки: Т э = О(n 3 ) и М э = O(n 2 ). Квадратичная зависимость объема необходимой памяти от длины входной цепочки напрямую связана с использованием промежуточного хранилища данных.

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

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

Тогда существованию вывода S* соответствует условие ST[1,n].

При условии существования вывода по таблице T n*n можно найти всю полную цепочку вывода S*.

Сам алгоритм Кока—Янгера—Касами можно описать следующим образом:

Цикл для j от 1 до n

Т[1,j] := <А |  Аa j  Р >— в T[1,j] включаются все нетерминальные символы для которых в грамматике G существует правило Aa j

Источник