Синтаксический анализатор
Задали написать синтаксический анализатор, который бы проверял подходит или вводимая цепочка символов под грамматику.
Цель работы: изучение способов реализации синтаксического анализатрора.
Задание: преобразовать заданную грамматику в 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.p...1&d=1275330069 |
