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

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

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

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

ФІКТ

Кафедра ПЗОТ

Група ПІ-39

Лабораторна робота №2

Тема: «Виведення ланцюжків»

м. Житомир,

2011р.

Мета роботи: вивчити математичну модель формальної граматики, одержати практичні навички виведення ланцюжків в формальній граматиці.

Завдання: потрібно написати програму, що одержує на вході контекстно-вільну граматику, яка визначена правилами підстановки, та друкує в результаті роботи одне або більше виведення термінального ланцюжка в граматиці.

Контекстно-вільну граматику вважати заданою у виді текстового файлу, кожен рядок якого вміщує єдине правило підстановки у вигляді a -> b (a — ідентифікатор нетермінала, b — рядок ідентифікаторів терміналів і нетерміналів, розділених пробільними символами). Пустий ланцюжок ідентифікується відсутністю правою частиною правила підстановки. Довжина ідентифікаторів обмежена 32 символами. Ідентифікатори, які починаються з великої літери вважаються нетерміналами, з маленької — терміналами, нетермінал в лівій частині першого правила підстановки вважається початковим символом.

Припустимо, що на вхід програми поступає граматика виду

Тоді результатом роботи програми лабораторної роботи може бути рядок виведення

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));

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