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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

Кафедра ПОВТ и АС

Курсовая работа

По дисциплине:

«Теория языков программирования»

на тему:

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

Выполнил:

                                                                  Приняла:

АННОТАЦИЯ

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

Курсовая работа содержит следующее количество:

      Рисунков – 6

      Страниц печатного текста – 20.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1.      Контекстно-свободные грамматики ………………………….. 6

2.      Синтаксические анализаторы ………………………………… 7

3.      Табличный распознаватель для КС языков …………………  8

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

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

4.      Описание процедур ……………………….…………………..   15

5.      Анализ результатов работы приложения ……………………  16

ЗАКЛЮЧЕНИЕ …………………………………………………..   17

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ ………………..   18

ПРИЛОЖЕНИЕ ………………………………………………….   19

ВВЕДЕНИЕ

Основная задача  лексического анализа - разбить входной текст, состоящий  из   последовательности  одиночных   символов,   на последовательность слов,  или лексем,  т.е. выделить эти слова из  непрерывной   последовательности  символов.   Все  символы входной последовательности  с этой точки зрения разделяются на символы,  принадлежащие   каким-либо  лексемам,   и   символы,  разделяющие лексемы  (разделители). В  некоторых случаях между лексемами может  и не  быть разделителей.  С другой стороны, в некоторых языках  лексемы могут  содержать незначащие  символы (пробел в  Фортране). В  Си разделительное  значение символов- разделителей может  блокироваться ('\'  в конце  строки внутри "...").

Обычно  все  лексемы  делятся  на  классы.  Примерами  таких классов     являются: числа (целые, восьмеричные, шестнадцатеричные,  действительные  и  т.д.), идентификаторы, строки.  Отдельно   выделяются  ключевые   слова   и   символы пунктуации  (иногда  их  называют  символы-ограничители).  Как правило, ключевые  слова - это некоторое конечное подмножество идентификаторов. В  некоторых языках  (например,  ПЛ/1)  смысл лексемы может  зависеть от  ее контекста и невозможно провести лексический анализ в отрыве от синтаксического.

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

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

1.      Контекстно-свободные грамматики

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

1.      Стартовый символ, задающий вид строк описываемого языка на самом верхнем уровне (S);

2.      Нетерминальные символы (переменные), традиционно обозначаемые заглавными латинскими буквами (V);

3.      Терминальные символы – базовые, атомарные элементы языка, формирующие его алфавит (∑);

4.      Собственно правила вывода, каждое из которых сопоставляет некоторой переменной или стартовому символу строку, состоящую из конкатенации произвольных терминальных и нетерминальных символов (R).

Формально КС-грамматики определяются как объект (∑, V, R, S). При этом правила имеют вид А → с, где А – переменная, а с – строка над алфавитом (∑ U V). Такая грамматика называется контекстно-свободной потому, что правило А → с может применяться независимо от того, в каком контексте встретилась переменная А (то есть независимо от того, какие символы её окружают). Обычно стартовый символ грамматики не выделяют явным образом: по умолчанию считается, что переменная в левой части самого первого правила и есть стартовый символ.

Грамматику можно записать короче, пользуясь вертикальной чертой для объединения правил с одинаковой левой частью.

Например

S → aS | bS | cS

Здесь три правила, а не одно.

2.      Синтаксические анализаторы

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

Задача определения принадлежности строки языку решается в процессе синтаксического анализа строки.

Если при построении вывода строки из стартового символа на каждом шаге происходит замена самого левого нетерминала – вывод называется левым. При замене правого нетерминала – правый вывод.

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

Исходя из этих предположений, можно выделить LL(k) и LR(k) анализаторы. Запись LL(k) означает «просмотр слева направо, левый вывод, k символов предпросмотра». Аналогично, запись LR(k) читается как «просмотр слева направо, правый вывод, k символов предпросмотра».

Грамматики, для которых существует LR(k) анализатор, называются LR(k) грамматиками, аналогично и LL(k) грамматиками.

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

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

  Табличные распознаватели используют для построения цепочки вывода КС-грамматики другие принципы, нежели МП-автоматы. Как и МП-автоматы, они получают на вход цепочку входных символов α = a1a2…an,      α єVT*, |α| = n, а построение вывода основывают на правилах заданной КС-грамматики G(VT,VN,P,S). Принцип их работы заключается в том, что искомая цепочка вывода строится не сразу — сначала на основе входной цепочки порождается некоторое промежуточное хранилище информации объема n*n (промежуточная таблица), а потом уже на его основе строится вывод.

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

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

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

3.2    Алгоритм Кока—Янгера—Касами

Для заданной грамматики G(VT,VN,P,S) и цепочки входных символов ,  = a1a2…an, VT*, || = n строит таблицу Tn*n, такую, что AVN: AT[i,j], тогда и только тогда, если А+аi...ai+j-1. Таким образом, элементами таблицы Tn*n являются множества нетерминальных символов в алфавита VN.

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

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

Для построения вывода по алгоритму Кока—Янгера—Касами грамматика G(VT,VN,P,S) должна быть в нормальной форме Хомского. Поскольку, как было показано выше, любую произвольную КС-грамматику можно преобразовать в нормальную форму Хомского, это не накладывает дополнительных ограничений на применимость данного алгоритма.

Алгоритм Кока—Янгера—Касами фактически состоит из трех вложенных циклов. Поэтому ясно, что время выполнения алгоритма имеет кубическую зависимость от длины входной цепочки символов. Таблица Tn*n, используемая для хранения промежуточных данных в процессе работы алгоритма, является таблицей множеств. Очевидно, что требуемый для ее хранения объем памяти имеет квадратичную зависимость от длины входной цепочки символов.

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

Шаг1.

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

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

Конец цикла для j

Шаг 2.

Цикл для 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

Результатом работы алгоритма будет искомая таблица Tn*n. Для проверки суще­ствования вывода исходной цепочки в заданной грамматике остается только про­верить условие ST[1,n].

Если вывод существует, то необходимо получить цепочку вывода. Для этого существует специальная рекурсивная процедура R. Она выдает последователь­ность номеров правил, которые нужно применить, чтобы получить цепочку вы­вода. Ее можно описать следующим образом: R(i,j,A), где AVN.

1. Если j=1 и существует правило Ааi, то выдать номер этого правила.

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 не требует дополнительной памяти для своего выпол­нения, кроме стека, необходимого для организации рекурсии. Время ее выполне­ния имеет квадратичную зависимость от длины входной цепочки.