Читайте также:
|
|
МП-автомат называется детерминированным, если для каждых либо
1. содержит не более одного элемента, для каждого и , либо
2. для всех и содержит не более одного элемента.
Язык, определяемый детерминированным автоматом, называется детерминированным КС-языком. Доказано, что каждая LR(k) грамматика порождает детерминированный КС-язык и каждый детерминированный КС-язык определяется LR(1) грамматикой.
/* ------------------------------------------
Магазинный детерминированный автомат вар.1
Разработчик Тимофеев П.А. апрель 14 1994
------------------------------------------ */
#include <iostream.h>
char lenta[120]; // входная лента
char *pread = &lenta[0]; // указатель на текущий символ
char stek[120]; // магазин символов
char *pstek;
char priz[120], *ppriz; // магазин признаков
int errkod; // код ошибки
/* ------------ правые части правил ------------*/
char e[] = "223 TA"; // E -> TA
// признак 0-пустой, 1-терминал, 2-нетерминал
// 3-конец правила
char a0[] = "1223+TA"; // A -> +TA
char a1[] = "1223-TA"; // A -> -TA
char a2[] = "03"; // A -> e
char t[] = "223 FB"; // T -> FB
char b0[] = "1223*FB"; // B -> *FB
char b1[] = "1223/FB"; // B -> /FB
char b2[] = "03"; // B -> e
char f0[] = "1213(E)"; // F -> (E)
char f1[] = "23 D"; // F -> D
char d[] = "223 PG"; // D -> PG
char g0[] = "123.P"; // G ->.P
char g1[] = "03"; // G -> e
char p[] = "223 CH"; // P -> CH
char h0[] = "123 0H"; // H -> 0H
char h1[] = "123 1H"; // H -> 1H
char h2[] = "123 2H"; // H -> 2H
char h3[] = "123 3H"; // H -> 3H
char h4[] = "123 4H"; // H -> 4H
char h5[] = "123 5H"; // H -> 5H
char h6[] = "123 6H"; // H -> 6H
char h7[] = "123 7H"; // H -> 7H
char h8[] = "123 8H"; // H -> 8H
char h9[] = "123 9H"; // H -> 9H
char h10[]= "03"; // H -> e
char c0[] = "13 0"; // C -> 0
char c1[] = "13 1"; // C -> 1
char c2[] = "13 2"; // C -> 2
char c3[] = "13 3"; // C -> 3
char c4[] = "13 4"; // C -> 4
char c5[] = "13 5"; // C -> 5
char c6[] = "13 6"; // C -> 6
char c7[] = "13 7"; // C -> 7
char c8[] = "13 8"; // C -> 8
char c9[] = "13 9"; // C -> 9
char c10[]= "03"; // C -> e
struct prod{ // информация о правилах
int m; // число правил для одного нетерминала
char *pr[11]; // указатель на правую часть первого правила
// для данного нетерминала
} E,A,T,B,F,D,P,G,H,C;
void sntx() {
/* ------- правило E -> TA ---------------------*/
E.m = 1;
E.pr[0] = e;
/* ------- правила A ->...-------------------- */
A.m = 3;
A.pr[0] = a0;
A.pr[1] = a1;
A.pr[2] = a2;
/* ------- правило T -> FB ---------------------*/
T.m = 1;
T.pr[0] = t;
/* ------- правила B ->...---------------------*/
B.m = 3;
B.pr[0] = b0;
B.pr[1] = b1;
B.pr[2] = b2;
/* ------- правила F ->...---------------------*/
F.m = 2;
F.pr[0] = f0;
F.pr[1] = f1;
/* ------- правила D -> PG --------------------*/
D.m = 1;
D.pr[0] = d;
/* ------- правила G ->...---------------------*/
G.m = 2;
G.pr[0] = g0;
G.pr[1] = g1;
/* ------- правила P -> CH ---------------------*/
P.m = 1;
P.pr[0] = p;
/* ------- правила H ->...---------------------*/
H.m = 11;
H.pr[0] = h0;
H.pr[1] = h1;
H.pr[2] = h2;
H.pr[3] = h3;
H.pr[4] = h4;
H.pr[5] = h5;
H.pr[6] = h6;
H.pr[7] = h7;
H.pr[8] = h8;
H.pr[9] = h9;
H.pr[10] = h10;
/* ------- правила C ->...---------------------*/
C.m = 11;
C.pr[0] = c0;
C.pr[1] = c1;
C.pr[2] = c2;
C.pr[3] = c3;
C.pr[4] = c4;
C.pr[5] = c5;
C.pr[6] = c6;
C.pr[7] = c7;
C.pr[8] = c8;
C.pr[9] = c9;
C.pr[10] = c10;
}
/* поиск адреса правой части правил для нетерминала*/
prod *nprod(char *ps) {
switch (*ps) {
case 'E': return &E;
case 'A': return &A;
case 'T': return &T;
case 'B': return &B;
case 'F': return &F;
case 'D': return &D;
case 'P': return &P;
case 'G': return &G;
case 'H': return &H;
case 'C': return &C;
default: cout << "error=1 \n";
}
}
/*-------- программа разбора ------------------- */
void razbor() {
prod *pprod;
int i,j;
errkod = 0; // код ошибки 0-все правильно
pread = &lenta[0];
pstek = &stek[108];
ppriz = &priz[108];
char *psimvol;
stek[109] = 'K'; // символ дна стека
stek[108] = 'E'; // начальный символ грамматики
priz[108] = '2'; // признак нетерминала
while (((*pstek)!= 'K') && (errkod ==0)) {
switch (*ppriz) {
case '1': // в стеке терминал
if ((*pstek) == (*pread)) { // допуск символа
ppriz++;
pstek++;
pread++;
} else errkod = 1; break;
case '2': // в стеке нетерминал
pprod = nprod(pstek);
i = 0; // нет подходящего правила
for (j=1; j <= (*pprod).m; j++) {
psimvol = (*pprod).pr[j-1];
switch (*psimvol) {
case '1': // первый символ правила терминал
if ((*(psimvol+4))!= (*pread))
break;
else { i = j; j = (*pprod).m; break;};
case '2': case '0':
i = j; j = (*pprod).m; break;
default: cout << "error=2 \n";
}
}
if (i == 0) { errkod = 2; break;}
else;
psimvol = (*pprod).pr[i-1];
ppriz++; // удаление нетерминала из стека
pstek++;
if ((*psimvol)!= '0') { // замена нетерминала
while ((*psimvol)!= '3')
psimvol++;
psimvol--;
while (psimvol >= (*pprod).pr[i-1]) {
ppriz--;
pstek--;
(*ppriz) = (*psimvol);
(*pstek) = (*(psimvol+4));
psimvol--;
}
} else;
break;
default: { cout << "error = 3 \n"; errkod = 3;};
}
}
}
/* -------------- головная функция ---------------*/
main()
{
int n,j;
char *pp = &lenta[0];
sntx();
for (n=1; n<11; n++)
{
cout << "\n";
cin >> lenta;
pread = &lenta[0];
pp = pread;
razbor();
cout << " \n Правильная часть предложения -> ";
while (pp < pread) {
cout << (*pp);
pp++;
}
if ((*pread)!= '\0')
{ cout << " \n Предложение имеет ошибку, ошибочные символы -> ";
cout << pread;
};
if (errkod!= 0)
cout << " \n" << " Ошибка в программе = " << errkod << " \n";
}
}
Лекция 4.
Дата добавления: 2014-12-18; просмотров: 12 | Поможем написать вашу работу | Нарушение авторских прав |