Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Задача про регулярные грамматики [D7, WinXP]

Страницы: 1 2 >
Ozone © (2004-09-28 08:03:00)
Есть такое задание:

Написать программу, которая по заданной КС-грамматике будет генерировать цепочки языка (исп. только левосторонний или правосторонний вывод). Диапозон длин генерируемых цепочек должен задаваться пользователем.

ЗЫ: пользователь вводит состояния и правила для них

Я использовал в своей программе след. упрощенную структуру

{ Правило } TCross = record data: string; // символы indx: integer; // куда указывает end; { Состояние } TState = record Name : string[1]; // Имя A..Z Cross: array of TCross; // массив правил CCount: integer; // кол-во правил end; States : array of TState;

Собственно генератор я ужо написал... остается одна проблема.

К примеру, есть такая грамматика:
E = {0,1}; N = {S,A}
P:
S -> 1A
A -> 0A | 1111

Пользователь ввел кол-во цепочек = 5 и длину от 3 до 4 => ни одной такой цепочки не найдется... Как решить проблему?

У меня поиск (подбор) идет обычным рандомом, т.е. начанию с начального состояния (S) и двигаюсь дальше (рандомом) пока не дойду до терминального символа => как только дошел, проверяю попадает ли получившаяся цепочка в заданный диапазон.

Думаю смысл вопроса понятен... Есть идеи?

Defunct (2004-09-29 23:06:00) [1]
> Тем более как я могу узнать кол-во попыток которое мне необходимо сделать?

Из комбинаторики N! попыток, где N - количество правил. Но из той же комбинаторики, никто не требует точного решения NP-полной задачи, т.е. вы можете определить число попыток случайным числом, или N^2 или даже просто N.

Ozone (2004-09-29 10:43:00) [2]
Игорь Шевченко © (29.09.04 10:05) [24]

Я тоже об этом думал. НО как это поможет решить проблему? Как избавлюсь от зацикливания?

Игорь Шевченко (2004-09-29 10:05:00) [3]
Ozone © (28.09.04 16:02) [21]

А глупый совет такой - если начинать с терминальных символов и выводить из них нетерминалы, согласно правилам ?

Ozone (2004-09-29 09:32:00) [4]
Defunct © (29.09.04 05:22) [22]

Тоже конечно вариант, но мне кажется он не универсален. Тем более как я могу узнать кол-во попыток которое мне необходимо сделать? У вдруг на n+1 попытке будет нужный результат...

Defunct (2004-09-29 05:22:00) [5]
Суслик © (28.09.04 13:05) [9]
> [4] Defunct © (28.09.04 10:18)
> Ну ты даешь - зачем лезть туда, где ни в зуб ногой.

А откуда ты это взял?

PS: Ты меня уже достал своими коментариями

>Суслик © (28.09.04 15:41) [20]
>уууу.
>Я тоже невнимательно прочел :)))

Кто-то, конечно же это не ты, даже задачу понять не смог.

> 1. Если min длина цепочки превышает заданный дианазон, то цикл будет бесконечным :(

Сделайте так, определите количество попыток формирования цепочки.

Если найденая цепочка подходит - обновите число попыток.
Цепочка не подходит, тогда уменьшить число попыток, чило попыток = 0 - выход с сообщением "невозможно сформировать цепочку".

> 2. Если задано кол-во, например 100, на диапазоне от 1 до 10 => не для всякой граматики такое кол-во цепочек возможно для этих критериев.

Ну и хорошо с учетом ответа на 1 выведите найденные цепочки, остальное вас не должно волновать. Пусть дополняют правила.

Ozone (2004-09-28 16:02:00) [6]
Задача, в принципе, ограниченна, т.е. нужно либо левую либо правую КС-грамматику...

2 вопроса: см. [7]

Суслик (2004-09-28 15:41:00) [7]
уууу.

Я тоже невнимательно прочел :)))

Прошу прощения.

Игорь Шевченко (2004-09-28 15:35:00) [8]
DiamondShark © (28.09.04 15:15) [18]

Oops...Невнимательно прочитал, каюсь.

> А автору нужен генератор порождаемых грамматикой цепочек.

Это проще. Насколько я помню, такая задачка у Маккимана сотоварищи была.

DiamondShark (2004-09-28 15:15:00) [9]
При чём тут лексы и яксы? Лексы и яксы -- это генераторы распознавателей грамматик. А автору нужен генератор порождаемых грамматикой цепочек.
Задачи обратные.

Суслик (2004-09-28 15:09:00) [10]
Автору.

Все зависит от твоей задачи.

Если нужно отмотаться от лабораторной работы, то найди в сети готовый алгоритм и в путь.

Если у тебя действительно задание написать лексический и синтаксический анализатор (иными словами работа за бабло) , то тебе нужно одновременно делать два дела:
1) Читать указанную книгу.
2) Искаль форумы, где бы обсуждались интересующие тебя вопросы.

Иного пути я не вижу.

Это сложная тема, как с математической точки зрения, так и с точки зрения реализации. В указанной книге тебе нужна первая половина. По моим рассчетам на ее чтение и понимание уйдет 2-3 недели.

Суслик (2004-09-28 14:49:00) [11]

> [14] Ozone © (28.09.04 14:06)

За все мое время тут я общался с одним человеком свободно владеющим КС-грамматиками. Так, что жди :)))

> [15] Игорь Шевченко © (28.09.04 14:32)

Не понял. Ты согласен, что лексы и яксы полный отстой?

Игорь Шевченко (2004-09-28 14:32:00) [12]
Суслик © (28.09.04 13:56) [13]

> Лексы и яксы полный отстой.

Подпись мою сам поставь, плз.

Ozone (2004-09-28 14:06:00) [13]
И все-таки, пока нет этой книги и нет возможности сравнивать алгоритмы - есть какие-нить идеи по решению моей задачи?

Суслик (2004-09-28 13:56:00) [14]
Лексы и яксы полный отстой.

Я много пересмотрел. Тот код, который они генерят просто ужасен.

Игорь Шевченко (2004-09-28 13:55:00) [15]
Дык можно BISON изучать. Или YACC

Суслик (2004-09-28 13:18:00) [16]

> [10] Ozone © (28.09.04 13:13)

На такое дело не дорого.
Поверь книга охренительная. Она разбирает до фига методов посроения автоматов. Я вообще остановился на переводе недетерминированные автоматы в детерминированные, т.е. на полкниги. Она разбирает способов. В этом и есть сложность ее чтения - нужно прочесть все методы, чтобы выбрать один.

Ozone (2004-09-28 13:13:00) [17]
Суслик © (28.09.04 13:05) [9]

Хм.. дороговато, млин. Спасибо.
Пока вопрос открыт.

Суслик (2004-09-28 13:05:00) [18]

> [4] Defunct © (28.09.04 10:18)

Ну ты даешь - зачем лезть туда, где ни в зуб ногой.

> [8] Ozone © (28.09.04 12:59)

Нашел, где спрашивать :))))

-------
Я немного в этом разбирался. Но возможный ответ явно не для форума.
Тебе нужно вот, что
http://www.books.ru/shop/search?search_type=+&query=%EA%EE%EC%EF%E8%EB%FF%F2%EE%F0%FB

Там есть все алгоритмы.

Ozone (2004-09-28 12:59:00) [19]
UP

Ozone (2004-09-28 11:25:00) [20]
// у последнего правила индекс - (-1) я верно понял?

У терминального. Т.е. оно никуда не указывает.
Например, правило S -> aaaA, говорит что нужно записать "aaa" и перейти в состояние "A" => в массиве Cross состояния S будет такой элемент (data:='aaa'; indx:={индекс состояния A в массиве States}). А indx = -1когда правило имеет вид, например S -> aaa или S->bb.

// а нужно ли? ну раз пользователь ввел недостаточно правил для // формирования цепочки, то это его проблема. Причем тут ваш
// алгоритм.

В том то и проблема:
1. Если min длина цепочки превышает заданный дианазон, то цикл будет бесконечным :(
2. Если задано кол-во, например 100, на диапазоне от 1 до 10 => не для всякой граматики такое кол-во цепочек возможно для этих критериев.

Так вот, как отследить все эти возможные варианты?

// Можно начальное состояние задавать случайно.

Нельзя. Оно всегда S по определению.

Страницы: 1 2 >

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »