Використання форми Бекуса-Наура для формалізації синтаксису

Перехід чи крок автомата - це виконання операцій над стеком і вхідною голівкою, а також зміна стану. При цьому не обов'язково, щоб за один крок відбувалися всі зміни. Можливо: або вхідна голівка залишиться на місці, або не відбудеться операції над стеком, або не зміниться стан.

Розпізнавач дужкових виразів. Розглянемо одну з можливих реалізація АМП, для задачі перевірки коректності вкладеності круглих дужок. Коротко опишемо загальний принцип роботи автомата. Якщо вхідна голівка читає «(», то в магазин заштовхується символ А. Якщо вхідна голівка читає»)», то з магазина виштовхується символ, що там міститься. Ланцюжок відкидається, якщо:

1. На вході залишаються праві дужки, а магазин порожній

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

Визначимо даний АМП у такий спосіб:

Множина вхідних символів: {(,), +}.

Множина магазинних символів: {A, С}

Множина станів: t, де t є також і початковим станом автомата, раз він єдиний

Переходи:

1. (, A, S ЮvА, S, >

2. (, С, S ЮvА, S, >

3. ), A, S Ю ^, S, >

4. ), С, S Ю Відкинути

5. +, A, S Ю Відкинути

6. +, С, S Ю Допустити

Загальний зв'язок між граматиками та автоматами з магазинною пам'яттю

Цей зв'язок давно доведений і розглянута в спеціальній літературі для різних класів граматик і методів розбору. У рамках даної роботи немає особою необхідності повторювати матеріал або його витримки з товстих книг. Можна тільки послатися на основні джерела інформації, що дозволяють одержати фундаментальну підготовку по формальних граматиках і методам розбору. Однак, і в цих книгах розглядаються тільки такі граматики й автомати, що можуть бути ефективно реалізовані. З усього розмаїтості граматик, використовуваних для побудови розпізнавачів, нас будуть цікавити тільки КВ(1) граматики, орієнтовані на спадний лівий розбір, при якому вхідний ланцюжок проглядається зліва праворуч.

Варто пояснити, чому подальше вивчення обмежується тільки спадними методами розбору. Методи, використовувані при спадному розборі, досить універсальні і різноманітні. Застосування висхідного розбору дозволяє використовувати більш потужні KВ(1) граматики, у тому числі і граматики з лівою рекурсією, що при спадному розборі використовувати неможливо. Виникають проблеми перетворення таких граматик у граматики з правою рекурсією, орієнтовані на спадний розбір. Таке перетворення не завжди є очевидним. Однак, застосування діаграм Вірта для представлення синтаксису мов програмування дозволяє легко замінити всі ліві рекурсії на ітерації і використовувати отримані правила для спадного розбору. Тому, на мій погляд, при практичній розробці трансляторів, не має особливого змісту використовувати висхідний розбір.



3. Розробка програмно-алгоритмічного забезпечення розпізнання ланцюжка мови

3.1 Опис програми реалізуючої задачі

Програма написана на С++, виконана в Borland C++ Builder 6. Нижче представлений програмний код з коментарями та поясненнями.

char Str[255]; // оголошується рядок Str розміром 255;

int n; // оголошується змінна n типу integer;

int s=1; // оголошується змінна s типу integer, якій привласнюється значення 1, ця змінна визначає початковий стан автомата;

int a1=0; // оголошується змінна a1 типу integer, якій привласнюється значення 0, ця змінна визначає стан, в який автомат переходить прочитавши перший аргумент;

int o=0; // оголошується змінна про типу integer, якій привласнюється значення 0, ця змінна визначає стан, в який автомат переходить прочитавши знак арифметичної операції;

int a2=0; // оголошується змінна a2 типу integer, якій привласнюється значення 0, ця змінна визначає стан, в який автомат переходить прочитавши другий аргумент;

int е=0; // оголошується змінна е типу integer, якій привласнюється значення 0, ця змінна визначає стан, в який автомат переходить прочитавши знак рівності;

int f=0; // оголошується змінна f типу integer, якій привласнюється значення 0, ця змінна визначає завершальний стан автомата, в який автомат переходить прочитавши цифру що йде після знаку рівності;

int er=0; // оголошується змінна er типу integer, якій привласнюється значення 0, ця змінна призначена для перевірки, докладніше перевірка буде описана далі;

char D[]= «0123456789»; // оголошується рядок D без вказівки розмірності [] що містить символи «012345679»;

char Ao[] = «+-*/»; // оголошується рядок АО (буква О, не нуль) без вказівки розмірності [] що містить символи «+-*/»;

strcpy (Str, edit1->text.c_str()); // за допомогою функціії strcpy текст з поля Edit1 копіюється в рядок Str, функція c_str() повертає константний покажчик на стандартний рядок C, ідентичний поточному рядку. Повернений рядок закінчується символом кінця рядка '\0';

for (int n=0; n<strlen(Str); n++) // стандартний цикл. int n=0; Яначальноє значення змінної n; n<strlen(Str); Ясовершать цикл стільки раз скільки символів в рядку Str; функція strlen() повертає кількість символів в рядку вказаною в дужках; n++ ітератор циклу, нарощує значення n;

if((s==1)&&(strchr (D, str[n]) >0)) // умова: якщо значення змінної s рівне 1 і n-ний символ рядка Str знайдений в рядку D (функція strchr() повертає значення більше нуля якщо в рядку D знаходиться входження n-нного символу рядка Str), то обнулити (привласнити значення 0) змінній s, і привласнити значення 1 змінній a1; інакше кажучи, якщо автомат знаходячись в початковому стані q1, прочитує символ що входить в рядок D (0,1,2,3,4,5,6,7,8 або 9), то {s=0; a1=1;} // необхідно перейти в стан a1; далі ця умова неодноразово використовується, але з іншими, станами і вхідними символами, тому пояснювати його більш не буду;

else if((a1==1)&&(strchr (D, str[n]) >0))

{a1=1;}

else if((a1==1)&&(strchr (Ао, str[n]) >0))

{a1=0; o=1;} // все, як в попередній умові, тільки з іншим рядком АТ і переходом в інший стан про;

else if((o==1)&&(strchr (D, str[n]) >0))

{o=0; a2=1;}

else if((a2==1)&&(strchr (D, str[n]) >0))

{a2=1;}

else if((a2==1)&&(Str[n]=='=')) // аналогічна умова, різниця тільки в наступному записі (Str[n]=='='), якщо n-тий символ рядка Str рівний `=', то.

{a2=0; e=1;}

else if((e==1)&&(strchr (D, str[n]) >0))

{e=0; f=1;}

else if((f==1)&&(strchr (D, str[n]) >0))

{f=1;}

else // якщо жодна умова не була виконана - автомат прочитавши n-тий символ не змінив стан, то.

{er=1;} // змінній er привласнити значення 1 (автомат переходить в стан er, яке позначає помилку);

if((f==1)&&(er!=1)) // умова: якщо f рівне 1 (автомат знаходитися в кінцевому стані) і er не рівна 1 (якщо рівна, то як було описано в попередньому коментарі відбулася помилка автомата), то.

{Label1->caption= «Арифметичеськое виражение записано коректно»;} // вивести в Label1 напис «Арифметическое виражение записано коректно»;

else // інакше.

{Label1->caption=» Арифметическое виражение записано не коректно»;} // вивести в Label1 напис» Арифметическое виражение записано не коректно»;

3.2 Опис роботи програми при використанні контрольного прикладу

На рисунку зображена схема як працює автомат - спочатку знаходячись в стані S, посимвольно считує введений рядок таким чином:



Рисунок. 3.1 Схема роботи автомата

- считує перший символ рядка, якщо це число від 0 до 9 переходить в А1;

- считує наступний символ, якщо це число від 0 до 9 залишається в А1; якщо це знак арифметичної операції (+ або - або * або /) - переходить в О;

- считується наступний символ, якщо це число від 0 до 9 переходить в А2;

- считує наступний символ якщо це число від 0 до 9 залишається в А2; якщо це знак рівності(=) переходить в Е;

- считує наступний символ, якщо це число від 0 до 9 переходить в F;

- считує наступний символ якщо це число від 0 до 9 залишається в F;

- коли автомат прорахував всі символи, слід подивитися - якщо знаходиться в кінцевому стані (F) означає вираз нам підходить.

Стан ДКА	Символи, по яким здійснюється перехід
	0-9	*,/,+,-	=
S	A1	Ш	Ш
A1	A1	O	Ш
O	A2	Ш	Ш
A2	A2	Ш	E
E	F	Ш	Ш
F	F	Ш	Ш

Рисунок. 3.2 Таблиця переходів функцій кінцевого автомата



Відповідно, вирази наступного вигляду прийматимуться автоматом:

476887-2344=5

3454+87678767=12376

3676*9876=567

765432/5673==156

Тобто головне, щоб перший аргумент складався виключно з чисел, потім йшов обов'язково один знак арифметичної операції, потім другий аргумент, що складається з чисел, після нього повинен бути знак рівності і за ним результат, який складається з чисел.

Наприклад наступні вирази автомат визнає не коректними:

456+-12=65

2п6-65=1

534-800===6

Користувач, відкривши програму, повинен ввести вираз в рядок (Edit1) та натиснути кнопку Проверить(Bottom), перевіривши програма видасть результат: якщо введений вираз належить данній мові внизу з'явиться напис: «Арифметическое выражение записано корректно», а якщо не належить, то напис буде таким: «Арифметическое выражение записано некорректно».

Нижче приведені скріншоти програмного забезпечення в робочому стані:

Рисунок 3.3 Початковий стан програми



Рисунок 3.4 Вираз записаний коректно

Рисунок 3.5 Вираз записаний некоректно



Висновок

Отже, в даній роботі були розглянуті: використання форми Бекуса-Наура для формалізації синтаксису, метамови, формальні і регулярні мови, синтаксичні аналізатори і у третьому розділі був розроблений програмний код виконаної задачі та інструкція для користувача.

Отже, задача належності розв'язується найчастіше шляхом перевірки, чи має слово відповідну структуру, тобто шляхом синтаксичного аналізу, або розпізнавання. Наприклад, структура всіх можливих синтаксично правильних Паскаль-програм визначається скінченною та відносно невеликою сукупністю БНФ. Саме на її основі будуються синтаксичні аналізатори в трансляторах, тобто програми аналізу синтаксичної правильності вхідних програм. Очевидно, що кожна скінченна мова є регулярною, оскільки задається регулярним виразом як скінченне об'єднання одноелементних регулярних мов.

Яким би не був підхід до створення програмного забезпечення, кінцева програма має задовольняти деякі вимоги. Найчастіше зустрічаються такі критерії: ефективність, продуктивність, надійність, стійкість, зручність, переносимість, масштабованість.



Список джерел інформації

1. Пентус А.Е. Теория формальных языков М.: Издптельство Центра прикладных иследований при механико-математическом факультете МГУ, 2004.

2. А. Ахо, Дж. Ульман; Теория синтаксического анализа, перевода и кампиляции. Т.1: Синтаксичский анализ. - М.: Мир, 1978.

3. Гросс М. Теория формальных грамматик - М.: Мир, 1971.

4. Хопкрофт Дж.Э. Введение в теорию автоматов, языков и вычислений. Москва: Издательский дом «Вильяис», 2002.

5. Кук Д. Компьютерная математика - М.: Наука, 1990.

6. Вікіпедія: Вільна енциклопедія: http://uk.wikipedia.org

7. http://www.osvita.org.ua

8. http://www.antibotan.com



Додаток

Програмний код розробленого програмного забезпечення

#include <vcl.h>

#pragma hdrstop

#include «Unit1.h»

#pragma package (smart_init)

#pragma resource «*.dfm»

TForm1 *Form1;

__fastcall TForm1:TForm1 (TComponent* Owner)

: TForm(Owner) {

}

void __fastcall TForm1: Button1Click (TObject *Sender) {

char Str[255];

int n;

int s=1;

int a1=0;

int o=0;

int a2=0;

int e=0;

int f=0;

int er=0;

char D[]= «0123456789»;

char AO[] = «+-*/»;

strcpy (Str, Edit1->Text.c_str());

for (int n=0; n<strlen(Str); n++) {

if((s==1)&&(strchr (D, Str[n])>0)) {s=0; a1=1;}

else if((a1==1)&&(strchr (D, Str[n])>0)) {a1=1;}

else if((a1==1)&&(strchr (AO, Str[n])>0)) {a1=0; o=1;}

else if((o==1)&&(strchr (D, Str[n])>0)) {o=0; a2=1;}

else if((a2==1)&&(strchr (D, Str[n])>0)) {a2=1;}

else if((a2==1)&&(Str[n]=='=')) {a2=0; e=1;}

else if((e==1)&&(strchr (D, Str[n])>0)) {e=0; f=1;}

else if((f==1)&&(strchr (D, Str[n])>0))

{f=1;} else

{er=1;}

}

if((f==1)&&(er!=1))

{Label1->Caption= «Арифметическое выражение записано корректно»;} else

{Label1->Caption= «Арифметическое выражение записано не корректно»;}

}

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