Міністерство
освіти та науки України
Житомирський
державний технологічний університет
ФІКТ
Кафедра
ПЗОТ
Група
ПІ-39
Лабораторна
робота №2
Тема:
«Виведення ланцюжків»
м. Житомир,
2011р.
Мета роботи: вивчити математичну модель
формальної граматики, одержати практичні навички виведення ланцюжків в
формальній граматиці.
Завдання: потрібно написати програму, що одержує на
вході контекстно-вільну граматику, яка визначена правилами підстановки, та
друкує в результаті роботи одне або більше виведення термінального ланцюжка в
граматиці.
Контекстно-вільну граматику вважати заданою у виді
текстового файлу, кожен рядок якого вміщує єдине правило підстановки у вигляді a -> b (a —
ідентифікатор нетермінала, b — рядок
ідентифікаторів терміналів і нетерміналів, розділених пробільними символами).
Пустий ланцюжок ідентифікується відсутністю правою частиною правила
підстановки. Довжина ідентифікаторів обмежена 32 символами. Ідентифікатори, які
починаються з великої літери вважаються нетерміналами, з маленької —
терміналами, нетермінал в лівій частині першого правила підстановки вважається
початковим символом.
Припустимо, що на вхід програми поступає граматика виду
S ® a = F ; |
F ® F + T | T
T ® T * E | T / E | E
E ® ( F ) | – ( F ) | a
|
Тоді результатом роботи програми лабораторної роботи
може бути рядок виведення
SÞa = F ; Þa = T ; Þa = E ; Þa = a ;
Порядок виконання лабораторної роботи:
1.
Написати програму на ЕОМ.
2.
Здати працюючу програму викладачу.
3.
Підготувати і захистити звіт.
Демонстрація роботи алгоритму на прикладі виведення речення в граматиці
Граматика, задана у вигляді текстового файлу:
S -> abr = aTest E Test;
Fu1 -> Fu1 + T | T
T -> T * E | E / E | E
E -> ( alma ) | - ( Fu1 ) | -ab-q(
Test -> Quite
Quite -> T | Quite
Результат роботи програми
Фрагменти коду програми
namespace KPZ__Lab2
{
public partial class Form1 : Form
{
Dictionary<string, string[]> list = new
Dictionary<string, string[]>();
public Form1()
{
InitializeComponent( );
}
private void ReadFile(StreamReader files)
{
int indexBegin, indexEnd;
string strFile;
string strCheck;
string strKey;
while ((strFile = files.ReadLine()) != null)
{
List<string> strValue = new List<string>();
indexBegin = strFile.IndexOf(" -> ");
if (-1 != indexBegin)
{
if (strFile[strFile.Length - 1] != 32)
{
strFile += " ";
}
strCheck = strFile.Substring(0, indexBegin + 1);
if (strCheck[0] != 32)
{
strKey = "";
strKey += " ";
strKey += strFile.Substring(0, indexBegin + 1);
}
else
{
strKey = strFile.Substring(0, indexBegin + 1);
}
indexBegin = indexBegin + 3;
indexEnd = strFile.IndexOf(" | ",
indexBegin);
while (indexEnd != -1)
{
strValue.Add(strFile.Substring(indexBegin,
indexEnd + 1 - indexBegin));
indexBegin = indexEnd + 2;
indexEnd = strFile.IndexOf(" | ",
indexBegin);
}
strValue.Add(strFile.Substring(indexBegin));
list.Add(strKey, strValue.ToArray());
}
}
}
private void button1_Click(object sender, EventArgs e)
{
string result = " S ";
int i = 0;
int j = 25;
int terminal = 1;
int random;
string[] strCutted;
list.Clear();
textBox2.Clear();
OpenFileDialog openFileDialog1 = new OpenFileDialog();
openFileDialog1.InitialDirectory = "C:\kpz2";
if (openFileDialog1.ShowDialog() == DialogResult.OK)
{
using (StreamReader files = new
StreamReader(openFileDialog1.FileName))
{
FileInfo infF = new
FileInfo(openFileDialog1.FileName);
ReadFile(files);
}
}
Random rand = new Random();
while(1==1)
{
if (i > j)
{
i = j;
break;
}
terminal = 0;
foreach (string strKeys in list.Keys)
if (result.IndexOf(strKeys) != -1)
{
terminal = 1;
strCutted = result.Split(new string[] {
strKeys }, 2, StringSplitOptions.None);
random = rand.Next(list[strKeys].Length);
result = strCutted[0] + list[strKeys][random]
+ strCutted[1];
textBox2.Text += "S ->" +
result;
textBox2.Text += Environment.NewLine;
break;
}
i++;
}
button1.Enabled = true;
}
}
}
Висновок
математичний формальний граматика ланцюжок термінальний
Виконавши лабораторну роботу, я вивчила математичну модель
формальної граматики, одержала практичні навички виведення ланцюжків в
формальній граматиці.
Я написала програму, що одержує на вході
контекстно-вільну граматику з (.txt) файлу, яка визначена правилами
підстановки, та друкує в результаті роботи одне виведення термінального
ланцюжка в граматиці.
Другие работы по теме:
Виведення лікарської речовини з організму
Реферат на тему: Виведення лікарської речовини з організму Завершувальним етапом взаємодії лікарської речовини й організму є виведення (екскреція) її (або її метаболітів) різними органами і тканинами: нирками, печінкою, легенями, слизовою оболонкою травного каналу, сльозовими, потовими, молочними (під час лактації) залозами тощо.
Інтоксикації пестицидами
Реферат на тему: Інтоксикації пестицидами” ПЛАН Вступ 1. Патогенез 2. Лікування 3. Клінічний протокол надання медичної допомоги хворим на гостре отруєння пестицидами 4. Профілактика інтоксикації пестицидами
Числення висловлень
Реферат на тему: Числення висловлень Числення висловлень ) згідно з поданою у розділі 1 схемою означається таким чином. Алфавіт числення висловлень складається з елементарних і змінних висловлень (пропозиційних змінних): a,b,c,d,...,x,y,z (можливо з індексами), знаків логічних операцій ,,, і круглих дужок ( та ).
Побудова скінченних множин
Множина як визначена сукупність елементів чи об’єктів. Списковий спосіб подання множини. Множина, кількість елементів якої скінченна (скінченна множина). Виведення декартового добутку з кожної заданої комбінації. Алгоритм рішення та реалізація програми.
Канали збуту на промисловому ринку
Визначення сутності поняття "канали розподілу". Порівняльна характеристика "каналів розподілу" та "каналів збуту". Лінійно упорядкована чисельність фізичних чи юридичних осіб або логістичний ланцюжок. Схема логістичних ланцюжків. Використання на практиці.
Обчислення координат курсору миші при переміщенні
Технічне обґрунтування та етапи розроблення програми, яка здатна виводити координати курсору миші при переміщенні, а також відображати відстань та швидкість, з якою проходить курсор між двома обраними точками. Основні елементи та загальні правила роботи.
Створення програми "Шаховий кінь"
Створення програми "Шаховий кінь" в системі програмування Turbo Pascal. Генерування відповідно до заданих початкових кординат маршруту руху коня. Алгоритм задачі: початок, виведення зображення та пошук. Реалізація програми та демонтрація її роботи.
Розробка програми "KeyLook"
Створення програми, яка друкує в вікно інформацію про натискання клавіш на клавіатурі в таблицю. Функція виведення назви отриманого програмою повідомлення від клавіатури та певних додаткових даних. Обробка інформації, неопрацьованої віконною процедурою.
Завантажувач шрифтів
Проблеми друкування шрифтом, який не підтримує програма друку. Створення програми завантаження свого шрифту у принтер. Опис та обґрунтування проектних рішень по проектуванню пристрою системи. Розрахунки та експериментальні матеріали, реалізація проекту.
Растрові та векторні формати зображень
Растрові формати зображень tiff, bmp, pcx, gif, jpeg, png, опис растрової графічної інформації. Зручність та недоліки векторних форматів. Зберігання і обробка зображень, що складаються з ліній, або можуть бути розкладені на прості геометричні об'єкти.
Сортування даних - пірамідальне сортування
Схема алгоритму програми. Алгоритм процедури введення даних, виведення результатів сортування, побудови дерева, перестановки елементів, "вирішення сімейного конфлікту". Приклад для масиву з 20 елементів. Користувацьке вікно та побудова піраміди.
Файли config.sys та autoexec.bat
Типова структура та зміст файлів config.sys та autoexes.bat, команди, що можуть включатися до них. Призначення драйверів keycode.exe і mouse.sys. Необхідність та умови створювання віртуального диску, його основна перевага перед жорстким і гнучким диском.
Форматування даних в програмах C++
Правила відтворення даних при введенні. Введення-виведення даних та їх формування. Буферизований вихідний потік для повідомлення про помилки. Управління форматами за допомогою компонентних функцій класу ios. Визначення користувальницьких маніпуляторів.
Операції над квадратною матрицею
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ Національний технічний університет України «Київський політехнічний інститут» Курсова робота з курсу «Обчислювальна техніка, алгоритмічні мови і програмне забезпечення»
Антикризове управління банківською системою
Потреба та економічна сутність антикризового управління банківської системи у сучасних умовах. Основним критерієм, визначення стабільності банківської системи є її ліквідність. Розгляд заходів щодо стабілізації та виведення з кризи банківського сектора.
Загальний опис внутрішніх пристроїв ПК
Структурна схема комп‘ютера. Поняття про мікропроцесор. Пам’ять та її види. Основні блоки клавіатури. Принтери. Види програм. Персональні комп'ютери, робота яких грунтується на принципі програмного управління, мають схожу структуру, спрощений вигляд якої показано на мал.1
Принципи побудови формальних теорій
Реферат на тему: Принципи побудови формальних теорій Математична логіка як самостійний розділ сучасної математики сформувався відносно нещодавно - на рубежі дев’ятнадцятого і двадцятого століть. Виникнення і швидкий розвиток математичної логіки були пов’язані з так званою кризою основ (засад) математики, одним з проявів якої є відомі парадокси або антиномії канторівської теорії множин.
Асемблер Контрольна - варіант 1
Задача № 1 . Розробіть алгоритм і напишіть програму на мові Асемблера для обчислення функції: М3 = (С - М1) + (Е – (50)16) + (D + М2) , де A, B, C, D, E, H, L – регістри загального призначення мікропроцесора КР580ВМ80А; М1, М2 – операнди, розташовані в пам’яті; М3 – результат обчислень, розташований у пам’яті.
Пристрої введення-виведення інформації
До пристроїв, без яких не може працювати сучасний персональний комп'ютер, належить клавіатура. З її допомогою в комп'ютер вводиться найрізноманітніша інформація, що потрібна для розв'язування задач.
Контекстно-вільні та LA-граматики
Реферат на тему: Контекстно-вільні та LA(1)-граматики 1. Контекстно-вільні граматики Контекстно-вільною , або КВ-граматикою , називається граматика, в якій ліві частини всіх продукцій є нетерміналами. Зміст терміну "контекстно-вільна" полягає в тім, що застосування продукції A w до ланцюжка uAv не залежить, тобто є
Робота в ОС Ms-Dos Загрузка основні файли внитрішні та зовнішні команди ос Ms-Dos
Завантаження MS-DOS починається відразу після «микання комп'ютера.. Є три основні файли операційної системи. Завантажувач заносить з диска до оперативної пам'яті системи: програми IO.SYS (модуль уведення/виведення) та MSDO&SYS (основний модуль). Після цього до оперативної пам'яті заноситься файл командного процесора COMMAND.COM, який забезпечує виконання так званих внутрішніх команд операційної системи.
Примітивні об єкти даних
Реферат на тему: Примітивними об’єктами даних є символи числа конси . muLisp має безліч функцій розпізнання, порівняння, комбінування та обробки цих об’єктів. Це дозволяє конструювати будь-які складні об’єкти даних. Як було сказано раніше, muLisp має два типи даних:
Доведення і спростування способи аргументації
План Доведення тезису. Спростування (критика). Доведення і спростування, їх роль в процесі аргументації. Складний, полемічний характер самої процедури аргументації об’єднує дві різні за своїм напрямком операції: доведення і спростування (обґрунтування і критику).
Ураження блискавкою перша допомога
Ураження блискавкою виникає під дією потужних електричних розрядів (до 10 тис кВт). Окрім цього діє звукова, повітряна і вибухова хвиля. Клініка: переважають ознаки пораження ЦНС і периферичної НС. Спочатку потерпілий непритомніє і може находитись в цьому стані від кількох хвилин до кількох діб. Після цього виникають марення, галюцинації, порушення рівноваги, сильний головний біль.
Боголюбов Микола Миколайович - український математик механік фізик
Реферат На тему: Боголюбов Микола Миколайович - український математик, механік, фізик Народився у 1909 р. в Нижньому Новгороді. Після завершення семирічки самостійно займався математикою і фізикою. У віці 17 років закінчив аспірантуру при Академії наук України. В 1934—1958 рр. працював у Київському університеті (з 1936 р. — професор).