Синтаксический анализатор

[пчелка]

Задали написать синтаксический анализатор, который бы проверял подходит или вводимая цепочка символов под грамматику.
Цель работы: изучение способов реализации синтаксического анализатрора.

Задание: преобразовать заданную грамматику в LL(1) грамматику и реализовать для нее синтаксический анализатор.
Заданная грамматика:
1) S->E#
2) E->T
3) E->E+T
4) E->E-T
5) T->F
6) T->T*F
7) T->T/F
8) F->a
9) F->b
10) F->c
11) F->(E)

Ход работы:
1) преобразовываем заданную грамматику в LL(1) грамматику. Для этого а) избавляемся от левой рекурсии:
для правил 3,4:
E->TR
R->+TR
R->-TR
R->e
Для правил 6,7:
T->FW
W->*FW
W->/FW
W->e

Получаем LL(1) грамматику:
1) S->E#
2) E->TR
3) R->+TR
4) R->-TR
5) R->e
6) T->FW
7) W->*FW
8) W->/FW
9) W->e
10) F->a
11) F->b
12) F->c
13) F->(E)

2) Для реализации синтаксического анализатора строим управляющую таблицу.
a b c ( ) / * + - # e
S E#,1 E#,1 E#,1 E#,1
E TR,2 TR,2 TR,2 TR,2
R e,5 e,5 e,5 +TR,3 -TR,4 e,5 e,5
T FW,6 FW,6 FW,6 FW,6
W e,9 /FW,8 *FW,7 e,9 e,9 e,9 e,9
F a,10 b,11 c,12 (E),13
a Выброс
b Выброс
c Выброс
( Выброс
) Выброс
/ Выброс
* Выброс
+ Выброс
- Выброс
# Выброс
$ Допуск

И программа:

#include <vcl.h>
#pragma hdrstop

#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
// Управляющая таблица пробел - ошибка
// таблица в виде двумерного массива строк
String N[18][12]= {{" ", "a", "b", "c", "(", ")", "/", "*", "+", "-", "#", "e"},
{"S", "E#,1", "E#,1", "E#,1", "E#,1", " ", " ", " ", " ", " ", " ", " "},
{"E", "TR,2", "TR,2", "TR,2", "TR,2", " ", " ", " "," ", " ", " ", " ",},
{"R", " "," ", " "," ", "e,5", "e,5", "e,5", "+TR,3 ", "-TR,4", "e,5", "e,5"},
{"T", "FW,6", "FW,6", "FW,6", "FW,6", " ", " ", " ", " ", " "," ", " " },
{"W", " ", " ", " ", " ", "e,9", "/FW,8 ", "*FW,7", "e,9", "e,9", "e,9", "e,9"},
{"F", "a,10", "b,11","c,12 ", "(E),13", " ", " "," "," ", " "," ", " "},
{"a", "выброс"," "," ", " ", " "," ", " ", " ", " ", " ", " "},
{"b", " ","выброс"," ", " ", " "," ", " ", " ", " ", " ", " "},
{"c", " "," ", "выброс "," "," "," ", " ", " ", " ", " ", " "},
{"(", " ", " "," ", "выброс"," "," ", " ", " ", " ", " ", " "},
{")", " ", " ", ""," ", "выброс"," ", " ", " ", " ", " ", " "},
{"/", " ", " ", " "," "," ", "выброс", " ", " ", " ", " ", " "},
{"*", " "," ", " "," ", " "," ", "выброс", " ", " ", " ", " "},
{"+", " "," ", " "," ", " "," ", " ", "выброс", " ", " ", " "},
{"-", " ", " ", " "," ", " "," ", " ", " ", "выброс", " ", " "},
{"#", " "," ", " "," ", " ", " "," ", " ", " ", "выброс",""},
{"$", " "," ", " "," ", " ", " "," ", " ", "", "", "допуск"}
};
//---------------------------------------------------------------------------

__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------

void __fastcall TForm1::Button2Click(TObject *Sender)
{
Close();
}
//---------------------------------------------------------------------------
// Т.к. в таблице терминалы и нетерминалы хранятся в виде символов, а нам нужны соответствующие номера колонки или столбца, то поиск номера выносим в отдельную функцию

int koordX(char ch){// ищет в первой строке нужный символ, возвращает номер
for (int i=1; i<12; i++)
if (N[0][i] == ch) return i;
return 0;
}

int koordY(char ch){// ищет в первом столбце нужный символ, возвращает номер
for (int i=1; i<18; i++)
if (N[i][0] == ch) return i;
return 0;
}

void __fastcall TForm1::Button1Click(TObject *Sender){
String k1=Edit1->Text, k2="S$", k3="", st1,st2,st3;
// q1 - цепочка символов на входе
// q2 - магазин
// q3 - порядок правил, которые надо применить для вывода цепочки
int x,y;
do {// цикл - делать, пока условие внизу (q2!="$") выполняется
f=1;
x=koordX(k1[f]);// находим координаты в таблице
y=koordY(k2[f]);
f++;
if ((N[y][x]==" ")||(x==0)||(y==0)){// если координаты равны нулю или значение по координатам равно ошибке, то цепочка неправильная. Сообщаем и выходим из функции
ShowMessage("Данная грамматика не реализует заданную строку");
return;
}else
if (N[y][x]=="допуск"){;//если в таблице "допуск" - ничего не делаем, все разобрали, условие while (q2!="$") выполнится и мы выйдем
}else
if (N[y][x]=="выброс"){// если в таблице "выброс"
k1.Delete(1,1);// удаляем первый символ из входной цепочки (якобы сместили читающую головку на автомате)
k2.Delete(1,1);// удаляем первый символ из магазина
if (k1=="") k1="e";// если входная цепочка кончилась, записываем пустой символ
}else {// если не сработало все вышеперечисленное, значит по этим координатам в таблице записано правило, тогда
k2.Delete(1,1);// удаляем первый символ из магазина
st1=N[y][x];// сохраняем ячейку-строку из таблицы
st2=N[y][x];
int k=0;
while(st1 != ","){
st2.Delete(1,1);
k++;}
st1.Delete(k,st1.Length()-k);
k2.Insert(st1,1);
k3 = k3+st2+" ";
if (k3[1]=='e') k3.Delete(1,1);
if (k2[1]=='e') k2.Delete(1,1);
}
} while (k2!="$");
ShowMessage("Данная грамматика выводит заданную строку по следующим правилам: " + k3);}


Прога на билдере 6 циклится очень, что не так?
Вот она http://forum.oszone.net/attachment.php?attachmentid=45564&stc=1&d=1275330069

[lxa85]

пчелка, а можно литературку какую-нибудь синтаксическому анализатору?
Я просто не совсем понимаю что требуется от грамматики, и как с ней потом работать.
Почему прошу найти, а не ищу сам? Потому что могу чего-нить не того найти, сам запутаюсь и тебя запутаю.

[пчелка]

ну вот в вики есть хороший алгоритм, примерно так и надо, но я не умею работать со стеками....
http://ru.wikipedia.org/wiki/LL-анализатор

[пчелка]

ну в результате преобразований, получился такой код:
//---------------------------------------------------------------------------

#include <vcl.h>
#pragma hdrstop

#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
// Управляющая таблица пробел - ошибка
// таблица в виде двумерного массива строк
String M[18][12]= {{" ", "a", "b", "c", "(", ")", "/", "*", "+", "-", "#", "e"},
{"S", "E#,1", "E#,1", "E#,1", "E#,1", " ", " ", " ", " ", " ", " ", " "},
{"E", "TR,2", "TR,2", "TR,2", "TR,2", " ", " ", " "," ", " ", " ", " ",},
{"R", " "," ", " "," ", "e,5", "e,5", "e,5", "+TR,3 ", "-TR,4", "e,5", "e,5"},
{"T", "FW,6", "FW,6", "FW,6", "FW,6", " ", " ", " ", " ", " "," ", " " },
{"W", " ", " ", " ", " ", "e,9", "/FW,8 ", "*FW,7", "e,9", "e,9", "e,9", "e,9"},
{"F", "a,10", "b,11","c,12 ", "(E),13", " ", " "," "," ", " "," ", " "},
{"a", "выброс"," "," ", " ", " "," ", " ", " ", " ", " ", " "},
{"b", " ","выброс"," ", " ", " "," ", " ", " ", " ", " ", " "},
{"c", " "," ", "выброс "," "," "," ", " ", " ", " ", " ", " "},
{"(", " ", " "," ", "выброс"," "," ", " ", " ", " ", " ", " "},
{")", " ", " ", ""," ", "выброс"," ", " ", " ", " ", " ", " "},
{"/", " ", " ", " "," "," ", "выброс", " ", " ", " ", " ", " "},
{"*", " "," ", " "," ", " "," ", "выброс", " ", " ", " ", " "},
{"+", " "," ", " "," ", " "," ", " ", "выброс", " ", " ", " "},
{"-", " ", " ", " "," ", " "," ", " ", " ", "выброс", " ", " "},
{"#", " "," ", " "," ", " ", " "," ", " ", " ", "выброс",""},
{"$", " "," ", " "," ", " ", " "," ", " ", "", "", "допуск"}
};
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------

void __fastcall TForm1::Button2Click(TObject *Sender)
{
Close();
}
//---------------------------------------------------------------------------
// Т.к. в таблице терминалы и нетерминалы хранятся в виде символов, а нам нужны соответствующие номера колонки или столбца, то поиск номера выносим в отдельную функцию
int findX(char ch){ // ищет в первой строке нужный символ, возвращает номер
//вообще-то, строка нулевая :-)
for (int i=1; i<12; i++)
if (M[0][i] == ch) return i;
return 0;
}

int findY(char ch){// ищет в первом столбце нужный символ, возвращает номер
for (int i=1; i<18; i++)
if (M[i][0] == ch) return i;
return 0;
}

void __fastcall TForm1::Button1Click(TObject *Sender){
String q1=Edit1->Text, q2="S$", q3="", st; // q1,q2,q3 - для алгоритма.
// q1 - цепочка символов на входе
// q2 - магазин
// q3 - порядок правил, которые надо применить для вывода цепочки
int x,y,f;
do { // цикл - делать, пока условие внизу (q2!="$") выполняется
x=findX(q1[1]);// находим координаты в таблице
y=findY(q2[1]);
if ((M[y][x]==" ")||(x==0)||(y==0)){// если координаты равны нулю или значение по координатам равно ошибке, то цепочка неправильная. Сообщаем и выходим из функции
ShowMessage("Данная входная цепочка нереализуема.");
return;
}else // иначе
if (M[y][x]=="допуск"){; //если в таблице "допуск" - ничего не делаем, все разобрали, условие while (q2!="$") выполнится и мы выйдем
}else
if (M[y][x]=="выброс"){ // если в таблице "выброс"
q1.Delete(1,1); // удаляем первый символ из входной цепочки (якобы сместили читающую головку на автомате)
q2.Delete(1,1); // удаляем первый символ из магазина
if (q1=="") q1="e"; // если входная цепочка кончилась, записываем пустой символ
}else { // если не сработало все вышеперечисленное, значит по этим координатам в таблице записано правило, тогда
q2.Delete(1,1);// удаляем первый символ из магазина
st=M[y][x]; // сохраняем ячейку-строку из таблицы
st.Delete(st.Length()-1,2);// убираем запятую и цифру(номер правила) - оставляем только символы из правила перехода
q2.Insert(st,1); //вставляем их в начало магазина
q3 = q3+M[y][x][M[y][x].Length()];//цифру добавляем в порядок правил
if (q3[1]=='e') q3.Delete(1,1); // пустой символ - он и есть пустой символ. Убираем его
if (q2[1]=='e') q2.Delete(1,1);
}
} while (q2!="$");
// выводим сообщение
ShowMessage("Данная цепочка выводима этой грамматикой. Правила: " + q3);
}
//---------------------------------------------------------------------------

Но почему-то всегда выводит, что чепочка нереализуема, хотя это не так. Этот анализатор должен читать правильно составленные строки из символов: a b c + - * / ( )