Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Лекция 4. МП-автомат называется детерминированным, если для каждых либо

Читайте также:
  1. Амплитудная селекция
  2. Беседа как метод обучения детей дошкольного возраста диалогической речи (лекция).
  3. Вводная лекция
  4. Вопрос 1.Лекция.
  5. Воскресная лекция Шрилы Радханатхи Свами в Киеве о Бхакти Тиртхе Свами
  6. Временная селекция
  7. Вступительная лекция.
  8. Вступительная лекция.
  9. Дәріс (лекция), зертханалық және зертханалық сабақтар жоспары
  10. Дәріс (лекция), практикалық және зертханалық сабақтар жоспары

 

МП-автомат называется детерминированным, если для каждых либо

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 | Поможем написать вашу работу | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2024 год. (0.016 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав