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

Размещено на http://www.allbest.ru/

8

Размещено на http://www.allbest.ru/

Задание

Разработать синтаксический анализатор, получающий на вход поток символов и подсчитывающий в потоке слова, удовлетворяющие условию ?*.doc. Анализатор спроектировать как конечный автомат. Привести его входной и выходной алфавиты, множество внутренний состояний (с их описанием), матрицу переходов-выходов, граф автомата и выполнять его программную реализацию на языке программирования высокого уровня (С, С++). Привести исходный текст программы.

Обозначения принятые в шаблоне: * - последовательность любых символов (длина последовательности может быть любой, включая 0);? - любой один символ; # - цифра (0, 1… 9); ? - любая буква (а, b… z). Остальные символы изображают сами себя. Входной поток состоит из символов нижнего регистра.

Решение

1. Входной алфавит.

Входной алфавит составляют символы входного потока, которые различает автомат (т.е. те, которые влияют на результат его работы). В нашем случае существенными являются следующие символы:

символы-разделители, которые мы рассматриваем как один элемент входного алфавита, т. к. неважно, какой именно из символов-разделителей поступит на вход - любой из них вызовет одну и ту же реакцию автомата. Обозначим символ-разделитель как: b.

символ d

символ o

символ c

символ.

символ ? - элемент входного алфавита, определяющий буквы нижнего регистра, все символы букв нижнего регистра рассматриваются как один элемент входного алфавита ?.

все остальные символы не различаются и рассматриваются как один элемент входного алфавита. Обозначим такой символ как *.

Т. о. входной алфавит будет состоять из шести символов: Х= {b, d, o, c., *}.

2. Выходной алфавит

На выходе после каждого принятого символа анализатор может выдавать одну из двух возможных реакции: «засчитать слово», «ничего не делать». Первая реакция означает, что автомат распознал во входном потоке слово, удовлетворяющее критериям поиска, и его нужно «засчитать» (увеличить счетчик распознанных слов на 1); а вторая реакция - слово не обнаружено (никаких действий производить не нужно). Условно обозначим эти состояния +1 и 0, соответственно.

Т. о. выходной алфавит включает два элемента: Y = {+1, 0}.

3. Множество внутренних состояний

1). Состояние 1

В начальный момент времени автомат находится в состоянии ожидания символа, который является началом слова. В этом состоянии автомат может получать на. вход символы-разделители, которые он будет пропускать. В этом же состоянии он находится после завершения чтения слова (получения символа-разделителя, означающего, что слово закончилось). Это состояние можно назвать «ожидание слова».

2). Состояние 2

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

засчитать (оно заведомо не удовлетворяет условиям подсчета). Такое слово следует пропустить, т.е. считать все символы, которые его составляют, до первого символа-разделителя. Это состояние, когда автомат считывает не то слово, которое он засчитает, назовем «чтение слова».

Состояние 3

Если первый символ - буква нижнего регистра, то автомат может ожидать, что это будет слово, предназначенное для подсчета. Назовем это состояние условно как «?…» подразумевая, что, возможно, это слово будет засчитано, если совпадут остальные условия.

Состояние 4

Если автомат находится в состоянии «?…», т.е. считывает слово, начинающееся на букву нижнего регистра, и при этом получает на вход символ `. `, то вероятность того, что слово будет засчитано, возрастает. Назовем это состояние «?….».

Состояние 5

Если автомат находится в состоянии «?….» и получает символ d на вход, то вероятность увеличивается еще больше. Назовем это состояние «а….d».

Состояние 6

Если автомат находится в состоянии «а….d» и получает символ o на вход, то он переходит в состояние «а….dо».

Состояние 7

Если автомат находится в состоянии «а….dо» и получает символ с на вход, то он переходит в состояние «а….dос».

Семи полученных состояний будет достаточно. Занесем их в таблицу:

4. Матрица переходов-выходов

Матрица переходов-выходов задает алгоритм работы автомата. У матрицы строки - начальные состояния автомата (как они. обозначены в таблице), столбцы - поступающие на. вход символы (как мы выше дали им обозначения - это символы входного алфавита). Элементы матрицы - новые состояния автомата (в числителе) и его реакции (в знаменателе).

5. Граф переходов автомата

6. Программная реализация автомата

Программная реализация автомата выполнена на языке С++. В программе входной поток не ограничен. Конец потока отмечается командой «конец ввода», которой в среде Windows соответствует последовательное нажатие клавиш «ENTER» «Crtl-Z» «ENTER».

 // podschet po shablonu [a*.doc] (a - lubaya iz bukv nignego registra,

 // * - lyubie simvoli, ost.simvoli-sobstvennie)

#include <stdio.h>

#include <conio.h>

#include <iostream.h>

void main(void)

{

int c, s=1, counter=0;

printf («Enter the stream:»);

printf («\nPress <ENTER>, <CRTL-Z>, <ENTER> for command <End of stream> \n»);

c = getchar();

while (c!=EOF)

{

switch (c)

{

case ' ':

case '\t':

case '\n':

if (s==7)

{

counter++;

s=1;

}

else s=1;

break;

case 'a':

case 'b':

 //case 'c':

 //case 'd':

 //case 'o':

case 'e':

case 'f':

case 'g':

case 'h':

case 'i':

case 'j':

case 'q':

case 'k':

case 'l':

case 'm':

case 'n':

case 'p':

case 'r':

case 's':

case 't':

case 'u':

case 'v':

case 'y':

case 'w':

case 'x':

case 'z':

if (s!=2) s=3;

break;

case '.':

if (s==3) s=4;

else if ((s==4)||(s==5)||(s==6)||(s==7)) s=3;

else s=2;

break;

case 'd':

if ((s==1)||(s==2)) s=3;

else if (s==4) s=5;

else s=3;

break;

case 'o':

if ((s==1)||(s==2)) s=3;

else if (s==5) s=6;

else s=3;

break;

case 'c':

if ((s==1)||(s==2)) s=3;

else if (s==6) s=7;

else s=3;

break;

default: if((s==1)||(s==2)) s=2;

else s=3;

}

c = getchar();

}

printf («Result:%d\n», counter);

printf («Press ENTER for exist»);

getchar();

}

Размещено на Allbest.ru