Создайте проект простого консольного приложения.
Приложение A. Порядок выполнения практических работ
Практические занятия по курсу состоят из тематических работ, включающих одну или несколько лабораторных работ.
Практическая работа №1 (1-3 лаб.)
Спроектировать автоматную грамматику по заданному языку L, построить конечный автомат.
1. Изучить классификацию Хомского (см. раздел 1.1., 1.2., 1.3.). Ответьте на вопрос, какие грамматики называются автоматными. Какие есть виды автоматных грамматик.
2. Спроектировать по заданному языку L автоматную грамматику и конечный автомат. Используйте пример, и последовательность выполнения работы из раздела 1.3. “Практическая работа 1”.
1. Постановка задачи.
2. Входные и выходные данные.
3.Спроектировать грамматику (Лаб 1).
4.Определить свойства грамматики.
5.Спроектировать конечный автомат, составить диаграмму переходов КА и реализовать на С# (Лаб 2.).
5.1. Создать проект – консольное приложение:
5.2. Используйте следующие программы для реализации КА,
распознающего заданный язык.
Создайте проект простого консольного приложения.
using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
namespace ConsoleApplication {
class Program {
static void Main(string[] args) {
ArrayList Q = new ArrayList();
string str;
Console.WriteLine("Hello");
str = Console.ReadLine();
Console.WriteLine("is= "+str);
Console.ReadLine();
}
}
}
Определение автомата и его реализация на С#:
class Automate { // NDKA (Q,Sigma,deltaList,q0,F)
ArrayList Q = null; // множество вcех состояний
ArrayList Sigma = null; // конечный алфавит входных символов
ArrayList DeltaList = new ArrayList(); // множество вcех правил
string Q0 = null; // начальное состояние
ArrayList F = null; // заключительные состояния
// атрибутное программирование на C#
public ArrayList q { get { return Q; } set { Q = value; } }
public ArrayList sigma { get { return Sigma; } set { Sigma = value; } }
public ArrayList deltaList { get { return DeltaList; }
set {DeltaList = value; } }
public string q0 { get { return Q0; } set { Q0 = value; } }
public ArrayList f { get { return F; } set { F = value; } }
public Automate() {
this.Q = new ArrayList();
this.Sigma = new ArrayList();
this.DeltaList = new ArrayList();
this.F = new ArrayList();
}
public Automate(string aname) {
System.Console.WriteLine(aname);
// сделать диалог, инициализирующий NDKA
// альтернативные состояния переходов хранить в массиве см. Test
//init();
Test();
}
Определение правил переходов:
class Delta { // структура Delta правил переписывания
private string LeftNoTerm = null;
private string LeftTerm = null;
private ArrayList Right = null;
public string leftNoTerm { get { return LeftNoTerm; } set { LeftNoTerm = value; } }
public string leftTerm { get { return LeftTerm; } set { LeftTerm = value; } }
public ArrayList right { get { return Right; } set { Right = value; } }
// модель правила
// delta( A, 1) = {qf}
// LeftNoTerm LeftTerm Right
public Delta(string LeftNoTerm, string LeftTerm, ArrayList Right) {
this.LeftNoTerm = LeftNoTerm;
this.LeftTerm = LeftTerm;
this.Right = Right;
}
public void DebugDeltaRight() {
int i = 0;
for (; i < this.right.Count; i++) {
if (i == 0)
System.Console.Write(" (" + this.right[i]);
else
System.Console.Write("," + this.right[i]);
}
if (i == 0)
System.Console.WriteLine();
else
System.Console.WriteLine(") ");
}
} // end class Delta
public void Test(){ // задание правил для тестирования
Q = new ArrayList() { "S0", "A", "B", "qf" }; // "C" для отладки
Sigma = new ArrayList() { "0", "1"};
q0 = "S0";
F = new ArrayList() { "qf" };
Delta delta = null;
// 1. transition
delta = new Delta("S0", "0", new ArrayList() {"A","qf"});
DeltaList.Add(delta);
// 2. transition
delta = new Delta("A", "1", new ArrayList() { "B"});
DeltaList.Add(delta);
// 3. transition
delta = new Delta("B", "0", new ArrayList() { "A","qf"});
DeltaList.Add(delta);
} // end test
Пример считывания символа:
foreach (Delta d in this.DeltaList) {
if (d.leftNoTerm == q && d.leftTerm == chain.Substring(i,1) ) {
…
}
…
}
6.Определить свойства КА. Реализовать алгоритм преобразования НДКА в ДКА (Лаб 3.).
7. Оформить работу согласно указанным шагам.
Практическая работа №2 (4-6 лаб.)
Привести заданную КС-грамматику G = (T, V, P, S) к приведенной форме.
1. Изучить алгоритмы приведения КС-грамматик к приведенной форме. (см. раздел 1.4.). Ответьте на вопрос, какие КС-грамматики называются грамматиками в приведенной форме. Лаб. 4 А,В. Лаб. 5 С,Д., Лаб. 6 F,E.
2. Использовать алгоритмы преобразования КС-грамматик..
A).Устранить из грамматики G бесполезные символы. Применить алгоритм 1.4.3. к грамматике G.
B). Устранить из грамматика G ε–правила, применить алгоритм 1.4.5.
C). Устранить из KС грамматики G цепные правила, применить алгоритм 1.4.6.
D).Устранить левую рекурсию в заданной КС-грамматике G1, порождающей скобочные арифметические выражения. Применить алгоритм 1.4.7. к грамматике G.
F). Определить в какой форме (Грейбах, Хомского) находится КС-грамматика G’.
E). G’– приведенная КС-грамматика.
3. Оформить работу согласно шагам.
Практическая работа №3 (7-8 лаб.)
Построить МП-автомат P и расширенный МП-автомат по КС-грамматики G = (T, V, P, S), без левой рекурсии. Написать последовательность тактов автоматов для выделенной цепочки. Определить свойства автоматов. Лаб. 7. -2.1. Лаб. 8. -2.2.
1. Изучить алгоритмы построения МП-автомат P и расширенного МП-автомата по заданной КС-грамматике (см. раздел 1.4.). Ответьте на вопрос, чем отличается МП-автомат P от расширенного МП-автомата.
2. Выполнить построение согласно алгоритмам.Смотрите пример и последовательность выполнения работы из раздела 1.4. “Практическая работа 4”.
2.1. A). Построить МП-автомат по КС-грамматике G, используя алгоритм 1.4.8.
B). Определить последовательность тактов МП-автомата для выделенной цепочк.
2.2. A). Построить расширенный МП-автомат, используя алгоритм 1.4.9.
B). Определить последовательность тактов расширенного МП-автомата при анализе входной выделенной цепочки P.
3. Определить свойства построенный МП-автоматов.
4. Оформить работу согласно шагам.
Практическая работа №4 (9-10 лаб.)
Разработать контекстно-свободную грамматику по заданной строке (см. раздел 1.3.). Алгоритм разбора реализуется в виде процедур, каждой, из которой соответствует диаграмма.
1. Повторить классификацию Хомского (см. раздел 1.1.). Ответьте на вопрос, какие грамматики называются контекстно-свободными. Какие есть виды контекстно-свободных грамматик.
2.Спроектировать по заданной строке контекстно-свободную грамматику и автомат с магазинной памятью. Используйте пример и последовательность выполнения работы из раздела 1.3. Обратите внимание, что в качестве неявного стека могут выступать: рекурсивная процедура и древовидная структура объектов. Лаб. 9 1-4. Лаб. 10 5-7.
1. Спроектировать контекстно-свободную грамматику.
2. Записать вывод заданной строки по грамматики.
3. Определить свойства грамматики.
4.Устранить левую рекурсию и записать вывод заданной строки по грамматики.
5.Оптимизировать грамматику метасимволами {…} и записать вывод заданной строки по грамматики.
6.Составить синтаксический граф для грамматики.
7. Преобразовать граф в программу.
3. Оформить работу согласно шагам.
Практическая работа №5 (11-10 лаб.)
Реализовать контекстно-свободную грамматику, полученную в работе 5 на основе, таблично-управляемой программы грамматического разбора. Изучить контекстно-зависимые грамматики (см. раздел 1.4.).
1.Повторить классификацию Хомского (см. раздел 1.1.). Ответьте на вопрос, какие грамматики называются контекстно – зависимыми, неограниченными. Какие свойства контекстно – зависимых и неограниченных грамматик, в чем их отличие. Чем они отличаются от изученных раннее грамматик ?
2. Разработать объектно-ориентрованную реализацию для таблично-управляемой программы грамматического разбора.
1. Представить граф грамматики в виде структуры данных (см. раздел 1.3.).
2. Классифицировать типы вершин.
3. Выполнить подстановку графов и получить как можно меньшее число графов.
4. Последовательность вершин графа преобразовать в структуру узлов.
5. Реализовать программу разбора по структуре узлов.
6. Оформить работу согласно шагам.