Виведення ланцюжків у формальній граматиці
Міністерство
освіти та науки України
Житомирський
державний технологічний університет
ФІКТ
Кафедра
ПЗОТ
Група
ПІ-39
Лабораторна
робота №2
Тема:
«Виведення ланцюжків»
м.
Житомир,
р.
Мета роботи:
вивчити математичну модель формальної граматики, одержати практичні навички
виведення ланцюжків в формальній граматиці.
Завдання:
потрібно написати програму, що одержує на вході контекстно-вільну граматику,
яка визначена правилами підстановки, та друкує в результаті роботи одне або
більше виведення термінального ланцюжка в граматиці.
Контекстно-вільну граматику вважати
заданою у виді текстового файлу, кожен рядок якого вміщує єдине правило
підстановки у вигляді a -> b
(a - ідентифікатор нетермінала, b
- рядок ідентифікаторів терміналів і нетерміналів, розділених пробільними
символами). Пустий ланцюжок ідентифікується відсутністю правою частиною правила
підстановки. Довжина ідентифікаторів обмежена 32 символами. Ідентифікатори, які
починаються з великої літери вважаються нетерміналами, з маленької -
терміналами, нетермінал в лівій частині першого правила підстановки вважається
початковим символом.
Припустимо, що на вхід програми
поступає граматика виду
|
S ® a = F ;
|
|
F ® F + T | T T ® T * E | T
/ E | E E ® (
F ) | - ( F ) | a
|
Тоді результатом роботи програми
лабораторної роботи може бути рядок виведення
Þa = F ; Þa
= T ; Þa = E ; Þa
= a ;
Порядок виконання лабораторної
роботи:
1. Написати
програму на ЕОМ.
2. Здати
працюючу програму викладачу.
3. Підготувати
і захистити звіт.
Демонстрація
роботи алгоритму на прикладі виведення речення в граматиці
Граматика, задана у вигляді
текстового файлу:
-> abr = aTest E Test;-> Fu1 +
T | T-> T * E | E / E | E-> ( alma ) | - ( Fu1 ) | -ab-q(-> Quite->
T | Quite
Результат роботи програми
Фрагменти коду програми
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)
{
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) файлу, яка визначена правилами
підстановки, та друкує в результаті роботи одне виведення термінального
ланцюжка в граматиці.