ПрактическаяРабота1 (Практическая работа - Разработка синтаксических анализаторов для регулярных языков)

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПРИБОРОСТРОЕНИЯ И ИНФОРМАТИКИ

ОТЧЕТ

о выполнении практической работы по дискретной математике №1

«Разработка синтаксических анализаторов для регулярных языков.»

Выполнил: студент группы ИТ-6 Васильев О.М.

Проверил: старший преподаватель кафедры ИТ-6 Русаков А.М.

Москва 2011г.

Цель практической работы: Написание, отладка и проверка работоспособности синтаксического анализатора на основе графа детерминированного конечного автомата, соответствующего заданному регулярному выражению, порождающему конкретный язык.

Задание: Для регулярного выражения (babb)*(aacb)*(ccab)* написать регулярную грамматику. Представить детерминированный конечный автомат, соответствующий регулярной грамматике. Написать и проверить работоспособность соответствующего синтаксического анализатора.

Регулярное выражение (babb)*(aacb)*(ccab)* порождает предложения языка:

L = {(babb)^m(aacb)ⁿ(ccab)^p: m, n, p > 0}.

Языку L соответствует регулярная порождающая грамматика:

G = ({a, b, c}, (А, В, С, D, Е, F, G, H, I, J, K, S}, P, S), где

Р={ S→bA; А→aВ; В→bC; С→bS; S→ε;

S→aD; D→aЕ; Е→cF;F→bG; G→aD; G→ε;

G→cH; S→cH; H→cI; I→aJ; J→bK; K→cH; K→ ε} — порождающие правила;

{ a, b, c } — множество терминальных символов;

{А, В, С, D, Е, F, G, H, I, K, S} — множество нетерминальных символов;

S — аксиома;

ε — пустая строка.

Регулярной грамматике G соответствует автомат:

M = ({А, В, С, D, Е, F, G, H, I, K, S}, { a, b, c }, d, {S}, (S, G, K}), где

{А, В, С, D, Е, F, G, H, I, K, S}— конечное множество состояний;

{b} — конечный входной алфавит;

d — множество переходов:

{d(S,a)=D d(S,c)=H d(S,b)=A

d(A,a)=B d(B,b)=C d(C,b)=S

d(D,a)=E d(E,c)=F d(F,b)=G

d(G,a)=D d(G,c)=H d(H,c)=I

d(I,a)=J d(J,b)=K d(K,c)=H};

S - начальное состояние (S {А, В, С, D, Е, F, G, H, I, K, S});

{S, G, K} - множество последних состояний

({S, G, K} {А, В, С, D, Е, F, G, H, I, K, S}).

Графическое представление множества переходов d:

Табличное представление множества переходов d:

Текст программы на языке Pascal:

program grammatika;

uses crt;

type perehod = record

old, term, new: char;

end;

var sost:array [1 .. 15] of perehod;

stroka: string [255];

sim, neterm: string [1];

dlina, n, i: integer;

ok: boolean;

begin

sost[1].old :='S'; sost[1].term :='b'; sost[1].new := 'A';

sost[2].old :='A'; sost[2].term :='a'; sost[2].new := 'B';

sost[3].old :='B'; sost[3].term :='b'; sost[3].new := 'C';

sost[4].old :='C'; sost[4].term :='b'; sost[4].new := 'S';

sost[5].old :='S'; sost[5].term :='a'; sost[5].new := 'D';

sost[6].old :='D'; sost[6].term :='a'; sost[6].new := 'E';

sost[7].old :='E'; sost[7].term :='c'; sost[7].new := 'F';

sost[8].old :='F'; sost[8].term :='b'; sost[8].new := 'G';

sost[9].old :='G'; sost[9].term :='a'; sost[9].new := 'D';

sost[10].old :='S'; sost[10].term :='c'; sost[10].new := 'H';

sost[11].old :='G'; sost[11].term :='c'; sost[11].new := 'H';

sost[12].old :='H'; sost[12].term :='c'; sost[12].new := 'I';

sost[13].old :='I'; sost[13].term :='a'; sost[13].new := 'J';

sost[14].old :='J'; sost[14].term :='b'; sost[14].new := 'K';

sost[15].old :='K'; sost[15].term :='c'; sost[15].new := 'H';

clrscr;

while TRUE do begin

writeln ('Vvedite stroku:');

readln (stroka);

dlina := length (stroka);

n := 0;

ok := TRUE;

neterm := 'S';

while ok and (n < dlina) do begin

i := 0;

n := n + 1;

sim := copy (stroka, n, 1);

ok := FALSE;

repeat

i := i+1;

if ((sost[i].old = neterm) and (sost[i].term = sim)) then begin

ok := TRUE;

neterm := sost[i].new;

end;

until ( ok or (i = 15));

end;

if ((neterm = 'S') or (neterm = 'G') or (neterm = 'K')) and ok then

writeln (' + Stroka prinadlejit')

else

writeln (' - Stroka ne prinadlejit');

writeln('');

end;

end.

Результат работы программы: