Автор: Пользователь скрыл имя, 09 Марта 2012 в 10:29, курсовая работа
Основная задача лексического анализа - разбить входной текст, состоящий из последовательности одиночных символов, на последовательность слов, или лексем, т.е. выделить эти слова из непрерывной последовательности символов. Все символы входной последовательности с этой точки зрения разделяются на символы, принадлежащие каким-либо лексемам, и символы, разделяющие лексемы (разделители)
ВВЕДЕНИЕ
1. Контекстно-свободные грамматики ………………………….. 6
2. Синтаксические анализаторы ………………………………… 7
3. Табличный распознаватель для КС языков ………………… 8
3.1 Общие принципы работы табличных распознавателей .. 8
3.2 Алгоритм Кока-Янгера-Касами …………………………. 9
4. Описание процедур ……………………….………………….. 15
5. Анализ результатов работы приложения …………………… 16
ЗАКЛЮЧЕНИЕ ………………………………………………….. 17
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ ……………….. 18
На основании последовательности номеров правил, полученной с помощью алгоритма Кока—Янгера—Касами и рекурсивной процедуры 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.
( | L11 | S12 |
| S14 |
| S16 |
) | R21 |
|
|
|
|
|
( | L31 | S32 |
| S34 |
|
|
) | R41 |
|
|
|
|
|
( | L51 | S52 |
|
|
|
|
) | R61 |
|
|
|
|
|
Рис. 2 Таблица разбора для цепочки ( ) ( ) ( )
Второй шаг алгоритма – это восстановление дерева вывода цепочки. Покажем процедуру восстановления дерева вывода цепочки на нашем примере. На рис. 2 для клетки t16 показаны два возможных варианта включения нетерминала S16 в эту клетку: либо в соответствии с правилом S16→S12S36, либо в соответствии с правилом S16→S14S32. Оба варианта возможны, поэтому мы можем построить два дерева вывода этой цепочки в данной грамматике (рис. 3.).
S16
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(
StringGrid1.Cells[1,i]:= StringGrid1.Cells[1,i]+(Copy(
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,
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+
begin
StringGrid1.Cells[j,i] :=StringGrid1.Cells[j,i]+(
end;
end;
end;
if Pos (Copy (Memo1.Lines[0],1,1),
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(
StringGrid1.Cells[1,i]:= StringGrid1.Cells[1,i]+(Copy(
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,
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+
begin
StringGrid1.Cells[j,i] :=StringGrid1.Cells[j,i]+(
end;
end;
end;
if Pos (Copy (Memo1.Lines[0],1,1),
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