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

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

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

Контекстно-вільну граматику вважати заданою у виді текстового файлу, кожен рядок якого вміщує єдине правило підстановки у вигляді 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[]>();

--> ЧИТАТЬ ПОЛНОСТЬЮ <--