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