Название: Виведення ланцюжків у формальній граматиці
Вид работы: лабораторная работа
Рубрика: Информатика и программирование
Размер файла: 49.73 Kb
Скачать файл: referat.me-136752.docx
Краткое описание работы: Математична модель формальної граматики та виведення ланцюжків. Розробка програми, що одержує на вході контекстно-вільну граматику, яка визначена правилами підстановки, та друкує в результаті роботи одне або більше виведення термінального ланцюжка.
Виведення ланцюжків у формальній граматиці
Міністерство освіти та науки України
Житомирський державний технологічний університет
ФІКТ
Кафедра ПЗОТ
Група ПІ-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) файлу, яка визначена правилами підстановки, та друкує в результаті роботи одне виведення термінального ланцюжка в граматиці.
Похожие работы
-
Автоматизована реєстрація і облік автомобілей
Розробка програми реєстрації автомобілів для збереження та перегляду інформації про модель машини, рік її випуску, об'єм двигуна і витрати палива. Складання алгоритмів розв'язання поставленої задачі та написання тексту програми в середовищі Turbo Pascal.
-
Обчислення координат курсору миші при переміщенні
Технічне обґрунтування та етапи розроблення програми, яка здатна виводити координати курсору миші при переміщенні, а також відображати відстань та швидкість, з якою проходить курсор між двома обраними точками. Основні елементи та загальні правила роботи.
-
Створення програми "Шаховий кінь"
Створення програми "Шаховий кінь" в системі програмування Turbo Pascal. Генерування відповідно до заданих початкових кординат маршруту руху коня. Алгоритм задачі: початок, виведення зображення та пошук. Реалізація програми та демонтрація її роботи.
-
Оцінка трудомісткості алгоритму
Засвоєння засобів аналізу трудомісткості обчислювальних алгоритмів. Побудова графа алгоритму з отриманої блок-схеми. Мінімізація графа, його подання у вигляді стохастичної матриці. Знаходження кількості звернень до файлів за допомогою Microsoft Excel.
-
Розробка програми "KeyLook"
Створення програми, яка друкує в вікно інформацію про натискання клавіш на клавіатурі в таблицю. Функція виведення назви отриманого програмою повідомлення від клавіатури та певних додаткових даних. Обробка інформації, неопрацьованої віконною процедурою.
-
Сортування даних - пірамідальне сортування
Схема алгоритму програми. Алгоритм процедури введення даних, виведення результатів сортування, побудови дерева, перестановки елементів, "вирішення сімейного конфлікту". Приклад для масиву з 20 елементів. Користувацьке вікно та побудова піраміди.
-
Програма контролю наявності зв’язку комп’ютера з пристроєм через паралельний порт протягом 15 секунд
Програма, яка приймає дані з зовнішнього пристрою через паралельний порт і використовується на комп’ютері з паралельним адаптером, операційною системою MS-DOS. Огляд існуючих пристроїв, систем, програмного забезпечення. Реалізація проекту, текст програми.
-
База даних по обліку вогнепальної зброї
Розробка програми "Облік вогнепальної зброї" для більш простої та оптимальної обробки інформації по зброї. Алгоритм процедури Zap. Занесення відомостей по вогнепальній зброї користувачем та зберігання її до типізованого файлу. Вихідний код програми.
-
Файли config.sys та autoexec.bat
Типова структура та зміст файлів config.sys та autoexes.bat, команди, що можуть включатися до них. Призначення драйверів keycode.exe і mouse.sys. Необхідність та умови створювання віртуального диску, його основна перевага перед жорстким і гнучким диском.
-
Побудова дерева каталогів диску і реалізація можливості переходу у вибраний каталог
Проектування програми за допомогою мови асемблера, яка б дозволяла відобразити на екрані дерево каталогів на диску і перейти в потрібний користувачеві каталог. Вибір методу розв’язання задачі та обґрунтування доцільності. Проведення лістингу програми.