РефератыИнформатика, программированиеВиВиведення ланцюжків у формальній граматиці

Виведення ланцюжків у формальній граматиці

Міністерство освіти та науки України


Житомирський державний технологічний університет


ФІКТ


Кафедра ПЗОТ


Група ПІ-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) файлу, яка визначена правилами підстановки, та друкує в результаті роботи одне виведення термінального ланцюжка в граматиці.

Сохранить в соц. сетях:
Обсуждение:
comments powered by Disqus

Название реферата: Виведення ланцюжків у формальній граматиці

Слов:727
Символов:6636
Размер:12.96 Кб.