Магазинные автоматы. Как магазинные автоматы воспринимают языки программирования

Теперь кратко опишем работу нашего ”Распознавателя скобок”

Если входная головка читает "(", то в магазин заталкивается  символ А. Если входная головка читает ")", то из магазина выталкивается  содержащийся там символ.

Рассмотрим критические ситуации:

1. На входе остаются правые скобки, а магазин пуст.
2. Входная цепочка прочитана до конца, а в магазине остаются символы А, соответствующие левым скобкам, для которых не нашлось пары.

Опишем нашу задачу:

Теперь предположим первая цепочка будет иметь следующий вид:

   ( ( ) ( ) )

  Тогда осуществляемые автоматом переходы можно представить в виде следующей       последовательности текущих состояний его устройств.

Комбинация принята. Теперь рассмотрим случай, когда  она будет отвергнута.

Есть комбинация : ()))

В этот раз комбинация будет отвергнута. Такие же схемы работы можно построить для любого автомата.

Мы построили абстрактные  и  математические модели магазинных автоматов , описали аналитическим примером нашу задачу и узнали всё для того чтобы можно было написать программу которая будет осуществлять проверку правильности расставления скобок. Но для полного понимания я хочу привести небольшое приложение к программе в котором опишу q  грамматику и построю схему переходов с помощью которого будет реализован магазинный автомат программно.

10. Приложение к программе.

При реализации программно магазинного  автомата таблицей переходов нам  необходимо  построить набор магазинных и входных символов, смоделировать основные устройства автоматов и написать процедуру реализующую таблицу переходов. В программе автомат реализован q-грамматикой. То для того чтобы понять как написать программу, или  понять всё её устройство необходимо привести таблицу переходов.

Немного о q грамматике :

Контекстно-свободная грамматика называется q-грамматикой тогда и  только тогда, когда выполняются  два условия:

1. Правая часть каждого правила либо представляет собой пустую цепочку e, либо начинается с терминального символа.

2. Множество выбора правил с одной и той же левой частью не пересекаются.

При построении таблицы переходов  введём следующее обозначения в  соответствии с грамматикой :

Если правило грамматики имеет  вид: A→αb, где b - терминал, α   - цепочка терминалов и нетерминалов, то определим множество выбора для правила A ® b равным b. Обозначим данную запись следующим образом:

ВЫБОР(A→bα) = b.

Если правило имеет вид: A →ε , то определим:

ВЫБОР(A  →ε) = СЛЕД(A).

Теперь построим нашу грамматику для  распознавания скобок:

 1. S -> (B)B

 2. B -> (B)B

3. B -> empty

Правила выбора выглядят следующим  образом:

ВЫБОР(1) = ВЫБОР (S→  (B)B ) = {(}

ВЫБОР(2) = ВЫБОР (B→  (B)B ) = {(}

ВЫБОР(3) = ВЫБОР (B→ε  ) = СЛЕД (B) = {), }

Теперь для полной ясности построим таблицу переходов  которую в программе мы будем анализировать:

  У нас может быть на входе ( , ) , или знак конца комбинации  , сопоставляя возможные комбинации, учитывая магазинные символы мы получили таблицу магазинного автомата.

Теперь можно привести код программы.

 

 

 

 

 

 

11.Исходный код программы

// BrackStack.cpp - автомат с магазинной памятью, распознающий вложенность

// круглых скобок.

// Построен на основе таблицы переходов созданной по следующей q-грамматике:

//

// 1. S -> (B)B

// 2. B -> (B)B

// 3. B -> empty

//

#include <iostream>

#include <string>

#include <vector>

#include <stack>

 

using namespace std;

 

// Магазинными символами автомата являются S, B, маркер дна (botoom).

// Их значение должно быть  за пределами видимых символов.

enum stackSymb {S = 256, B, bottom};

 

string str; // Строка с входной цепочкой, имитирующая входную лденту

int i; // Текущее положение входной головки

 

stack <int, vector<int> > stck; // Стек для магазинных символов

 

// Функция, реализующая чтение  символов в буфер из входного  потока.

// Используется для ввода с  клавиатуры распознаваемой строки.

// Ввод осуществляется до нажатия  на клавишу Enter.

// Символ '\n' яляется концевым маркером входной строки.

void GetOneLine(istream &is, string &str) {

char ch;

str = ""; //пустая строка

for(;;) {

is.get(ch);//считываем символ

if(is.fail() || ch == '\n') break;//проверяем

str += ch;// Если прошёл проверку значит добавляем в строку для вывода в дальнейшем

}

str += '\n'; // Добавляется концевой маркер

}

 

// Инициализация устройств АМП

void Init() { //перед работой со стеком мы должны его инициализировать во избежании  ошибок

// Инициализация стека

while(!stck.empty()) // пока не пустой

stck.pop(); //вытаскиваем

stck.push(bottom); // вставляем дно

stck.push(S);

 

// Инициализация входной головки

i = 0;

}

 

// Устройство управления АМП,  анализирующего вложенность скобок.

// Имитирует таблицу пееходов АМП.

bool Parser() { // булева процедура если скобки расставлены верно- возвращает тру если нет False

// Инициализация устройств АМП

Init();//инициализируем стек

 

int step = 0;

// Цикл анализа состояний

for(;;) {

// Тестовый вывод информации  о текущем шаге, текущем символе,  вершине стека

cout<<"step " << step++ << ": str[" << i << "] = "<< str[i]

<< " Top = "<< stck.top() << "\n";

// Проверка содержимого на вершине  стека

switch(stck.top()) {

                                           //теперь в соответстивии с таблицей переходов мы должны проверить выражения

// Анализ первой строки таблицы  переходов

case S:// первая строка

switch(str[i]) { // смотрим какой же у нас элемент

case '(': // [S, (]

stck.top() = B; // эквивалентно stck.pop(); stck.push(B);

stck.push(')');

stck.push(B);

i++; // следующий входной символ

break;

case ')': // [S, )] - ) не может стоять в начале

cout  << "Position " << i << ", "

<< "Error 1: \')\' can not is in begin!\n";

return false;

case '\n': // [S, концевой маркер]

cout  << "Position " << i << ", "

<< "Error 2: Empty string!\n";

return false;

default: // Ошибка, такой символ не допустим

cout  << "Position " << i << ", "

<< "Incorrect symbol! " << str[i] << "\n";

return false;

}

break;

 

// Анализ второй строки таблицы  переходов

case B:

switch(str[i]) {

case '(': // [B, (]

stck.top() = B; // эквивалентно stck.pop(); stck.push(B);

stck.push(')');

stck.push(B);

i++; // следующий входной символ

break;

case ')': // [B, )] - вытолкнуть без сдвига

stck.pop();

break;

case '\n': // [B, концевой маркер] - вытолкнуть без сдвига

stck.pop();

break;

default: // Ошибка, такой символ не допустим

cout  << "Position " << i << ", "

<< "Incorrect symbol! " << str[i] << "\n";

return false;

}

break;

 

case ')':

// Анализ третьей строки таблицы  переходов

switch(str[i]) {

case '(': // [), (] - в принципе недостижимо

cout  << "Position " << i << ", "

<< "Error 3: I want \')\'!\n";

return false;

case ')': // [), )] - вытолкнуть со сдвигом

stck.pop(); // вытолкнуть

i++;  // сдвиг

break;

case '\n': // [), концевой маркер]

cout  << "Position " << i << ", "

<< "Error 4: I want \')\'!\n";