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

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

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

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

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

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

на тему:

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

Выполнил:

                                                                  Приняла:

АННОТАЦИЯ

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

На основании последовательности номеров правил, полученной с помощью алго­ритма Кока—Янгера—Касами и рекурсивной процедуры R, можно построить лево­сторонний вывод для заданной грамматики G(VT,VN,P,S) и цепочки входных сим­волов . Таким образом, с помощью данного алгоритма решается задача разбора.

Алгоритм в формализованном виде:

1.      Присвоить  i = 1  и j’ = n – j + 1

2.      Присвоить k = 1

3.      Присвоить k’ = i + k и j’’ = j – k

4.      Обследовать t(i,k) и t(k’j’’)

              Присвоить t(i,j)=t(i,j) U { A| A->BC P, B t(i,k), Ct(k’,j’’) }

5.      Увеличить k на 1

6.      Если k = j то перейти к шагу 7. Иначе к шагу (3)

7.      Если i=j’ , остановиться. Иначе к шагу (8)

8.      Увеличить на 1 и перейти к шагу (2)

Данную процедуру необходимо применить к каждой строке таблице разбора начиная со 2 шага.

Рассмотрим работу этого алгоритма на примере. В качестве исходной возьмем грамматику в нормальной форме Хомского:

S - b

N - b

S - a

А - а

S - AS

В - b

N - BN

D - b

S - DN

При разборе строки aabb алгоритм CYK строит таблицу T ( рис. 1.).

Рис. 1. CYK-таблица для строки aabb

Клетки левого столбца таблицы (элементы T[l, 1] — T[4, 1]) содержат нетерминалы, из которых можно получить соответствующие строки единичной длины (то есть отдельные символы входной строки). Из S и А можно получить а, из S, N, В и D — b.

Следующий столбец содержит нетерминалы, из которых можно получить строки длиной уже в два символа. Так, верхняя клетка второго столбца содержит нетерминал, из которого выводится строка аа. Строка ab тоже выводится из нетерминала S, а вот строка bb может быть успешно выведена как их нетерминала N, так и из нетерминала S.

Продолжая построение столбцов, получаем в клетке T[l, N] список нетерминалов, из которых может быть выведена вся входная строка. Если в этом списке присутствует стартовый символ грамматики, строка допускается.

По таблице V можно построить и дерево разбора. При выполнении алгоритма CYK получается целая коллекция деревьев.

Поскольку алгоритм Кока-Янгера-Касами содержит три вложенных цикла, каждый из которых выполняет прямо пропорциональное N количество итераций, расходуемое программой время в итоге пропорционально N3. Считается, что для задачи распознавания контекстно-свободного языка кубическая сложность — признак большой эффективности алгоритма.

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

Рис. 2 Таблица разбора для цепочки ( ) ( ) ( )

Второй шаг алгоритма – это восстановление дерева вывода цепочки. Покажем процедуру восстановления дерева вывода цепочки на нашем примере. На рис. 2 для клетки t16 показаны два возможных варианта включения нетерминала S16 в эту клетку: либо в соответствии с правилом S16→S12S36, либо в соответствии с правилом S16→S14S32. Оба варианта возможны, поэтому мы можем построить два дерева вывода этой цепочки в данной грамматике (рис. 3.).

                             S16

                                     S34

        S12                    S32                       S52

  L11               R21    L31         R41      L51             R61

(               )       (             )           (               )

Рис. 3

                                      S16

                              S14

                 S12                       S32                 S52

             L11                   R21       L31          R41   L51         R61

             (                  )      (                 )     (             )

Рис. 4

Рис.3. Два синтаксических дерева для цепочки ( ) ( ) ( ) в грамматике S→SS│LR; L→(; R→)

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

      Основной процедурой программы является процедура Button1Click,в которой  заложен алгоритм разбора:

procedure TForm1.Button1Click(Sender: TObject);

begin

  s:=Edit1.Text;

  kol_s:=Length(s);

For i:=1 to kol_s do

  StringGrid1.Cells[0,i]:=s[i];

For i:=1 to kol_s do

  StringGrid1.Cells[i,0]:= IntToStr (i);

  StringGrid1.RowCount:=kol_s+1;

  StringGrid1.ColCount:=kol_s+1;

  kol_p:=Memo1.Lines.Count;

for i:=1 to kol_s do

   for j:=0 to kol_p-1 do begin

               If (Copy (Memo1.Lines[j],3,length(Memo1.Lines[j])-2) = S[i]) then

                  StringGrid1.Cells[1,i]:= StringGrid1.Cells[1,i]+(Copy(Memo1.Lines[j],1,1));

                  end;

For j:=2 to kol_s do

   for i:=1 to kol_s-j+1 do

    begin

      for k:=1 to j-1 do

        for c:=0 to kol_p - 1 do begin

          N:=Copy(Memo1.Lines[C],3,length(Memo1.Lines[C])-2);

   if (Length(N)=2)and(N[1] = Copy(StringGrid1.Cells[k,i], Pos(N[1], StringGrid1.Cells[k,i]),1))and

    (N[2]= Copy(StringGrid1.Cells[j-k,i+k], Pos(N[2], StringGrid1.Cells[j-k,i+k]),1))and ( Pos(Copy(Memo1.Lines[c],1,1),StringGrid1.Cells[j,i])=0)  then

    begin

    StringGrid1.Cells[j,i] :=StringGrid1.Cells[j,i]+(Copy(Memo1.Lines[c],1,1));

        end;

      end;

     end;

   if Pos (Copy (Memo1.Lines[0],1,1),StringGrid1.cells[Length (Edit1.Text),1]) >0  then

     ShowMessage('OK') else ShowMessage('NO');

    end;

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

Главное окно приложения:

              Рис. 5

Главное окно приложения после разбора:

              Рис. 6

ЗАКЛЮЧЕНИЕ

Задача синтаксического анализа состоит в построении дерева разбора для любой строки языка или вывода сообщения о том, что строка языку не принадлежит. Таким образом, задача распознавания языка является частным случаем задачи синтаксического анализа.

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

Поскольку на практике недетерминированные устройства недоступны, можно воспользоваться алгоритмом Кока-Янгера-Касами.

LR(1) анализатор, имитируя работу магазинного автомата, распознает любой язык, записанный с помощью так называемой LR(1) грамма­тики. Доказано, что с помощью LR(1) грамматики можно описать любой детерминированный язык.

Программа LL(1) анализа использует более ограниченные LL(1) языки.

Алгоритм Кока-Янгера-Касами, предназначенный для разбора лю­бого контекстно-свободного языка, выполняет порядка N операций при анализе строки длиной N символов. Анализатор, основанный на LR(1) грамматиках, работает гораздо быстрее (линейное время), но контекстно-свободные языки, выходящие за рамки детерминирован­ных, ему не по силам.

ЛИТЕРАТУРА

1.      Грис Д. Конструирование компиляторов для цифровых вычислительных машин. “Мир” 1975г.

2.      Мозговой М.В. Классика программирования: алгоритмы, языки, автоматы, компиляторы. Практический подход. – СПб.: Наука и Техника, 2006. -320c.

3.      А. Ахо, Дж. Ульман  Теория синтаксического анализа, перевода и компиляции. Том 1. Синтаксический анализ, М.: “Мир”, 1978 г.

4.      Кнут Д. Семантика контекстно-свободных языков. М.: Мир, 1980.

ПРИЛОЖЕНИЕ

unit Unit1;

interface

uses

  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

  Dialogs, StdCtrls, ExtCtrls, Grids, Buttons;

type

    m=set of char;

  TForm1 = class(TForm)

    Memo1: TMemo;

    Button1: TButton;

    Edit1: TEdit;

    Label1: TLabel;

    Label3: TLabel;

    StringGrid1: TStringGrid;

    BitBtn1: TBitBtn;

    procedure Button1Click(Sender: TObject);

    procedure BitBtn1Click(Sender: TObject);

  private

    { Private declarations }

  public

    { Public declarations }

  end;

var

  P:set of 'a'..'z';

  P1,N2,m1:set of 'A'..'Z';

  kol_s,kol_p,i,j,k,c:integer;

  S,N,N1:string;

  Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);

begin

  s:=Edit1.Text;

  kol_s:=Length(s);

For i:=1 to kol_s do

  StringGrid1.Cells[0,i]:=s[i];

For i:=1 to kol_s do

  StringGrid1.Cells[i,0]:= IntToStr (i);

  StringGrid1.RowCount:=kol_s+1;

  StringGrid1.ColCount:=kol_s+1;

  kol_p:=Memo1.Lines.Count;

for i:=1 to kol_s do

   for j:=0 to kol_p-1 do begin

               If (Copy (Memo1.Lines[j],3,length(Memo1.Lines[j])-2) = S[i]) then

                  StringGrid1.Cells[1,i]:= StringGrid1.Cells[1,i]+(Copy(Memo1.Lines[j],1,1));

                  end;

For j:=2 to kol_s do

   for i:=1 to kol_s-j+1 do

    begin

      for k:=1 to j-1 do

        for c:=0 to kol_p - 1 do begin

          N:=Copy(Memo1.Lines[C],3,length(Memo1.Lines[C])-2);

   if (Length(N)=2)and(N[1] = Copy(StringGrid1.Cells[k,i], Pos(N[1], StringGrid1.Cells[k,i]),1))and

    (N[2]= Copy(StringGrid1.Cells[j-k,i+k], Pos(N[2], StringGrid1.Cells[j-k,i+k]),1))and ( Pos(Copy(Memo1.Lines[c],1,1),StringGrid1.Cells[j,i])=0)  then

    begin

    StringGrid1.Cells[j,i] :=StringGrid1.Cells[j,i]+(Copy(Memo1.Lines[c],1,1));

        end;

      end;

     end;

   if Pos (Copy (Memo1.Lines[0],1,1),StringGrid1.cells[Length (Edit1.Text),1]) >0  then

     ShowMessage('OK') else ShowMessage('NO');

    end;

procedure TForm1.BitBtn1Click(Sender: TObject);

begin

For i:=0 to StringGrid1.ColCount-1 do

StringGrid1.Cols[i].Clear;

end;

end.

2