Задача про регулярные грамматики

← →
Ozone © (2004-09-28 08:03) [0]

Есть такое задание:

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

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

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

{ Правило } 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) и двигаюсь дальше (рандомом) пока не дойду до терминального символа => как только дошел, проверяю попадает ли получившаяся цепочка в заданный диапазон.

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

← →
Ozone © (2004-09-28 09:34) [1]

← →
Defunct © (2004-09-28 09:50) [2]

> Думаю смысл вопроса понятен...

3 раза перечитал - не понял.

E = {0, 1}, что такое E? как трактовать {} - коментарий или множество? что такое 0, 1?

Что такое N, S и A?
Что такое 0A | 1111?
Что такое 1A, почему, например, не 1И?
Что у вас обозначает знак "->" - "эквивалентно" или просто от фонаря поставили?

Вы думаете тут собрались телепаты, которые спят и видят вашу проблему?

> У меня поиск (подбор) идет обычным рандомом,

поиск(подбор) чего?

"обычным рандомом" - т.е. начанию с начального состояния (S) и двигаюсь дальше (рандомом) пока не дойду до терминального символа

что-то тут рандомом и не пахнет. рандомом выбирается индекс или дельта индекса?

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

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

Хотите получить нормальный ответ, задайте нормальный (читать понятный всем) вопрос.

← →
Ozone © (2004-09-28 09:58) [3]

Defunct © (28.09.04 09:50) [2]

Ok. Поясняю.

//E = {0, 1}, что такое E? как трактовать {} - коментарий или
//множество? что такое 0, 1?

E - множество символов грамматики
0,1 - символы

// Что такое N, S и A?

N - множество состояний

// Что такое 0A | 1111?

Правила.

// Что такое 1A, почему, например, не 1И?

Потому что состояние "И" не задано.

Что у вас обозначает знак "->" - "эквивалентно" или просто от фонаря поставили?

Символ "->" означает что дальше идут правила для данного состояния.

// что-то тут рандомом и не пахнет. рандомом выбирается индекс
// или дельта индекса?

Так и есть - рандомом выбирается индекс правила для текущего состояния.

← →
Defunct © (2004-09-28 10:18) [4]

[3] И это называется пояснение?

http://ln.com.ua/~openxs/articles/smart-questions-ru.html

← →
Ozone © (2004-09-28 10:41) [5]

Хммм... Попробую еще раз....

Есть произвольная регулярная грамматика G = {E, N, P, S}, где
E - множество символов алфавита грамматики
N - множество состояний
P - множество правил
S - начальное состояние.

Саму грамматику пользователь задает в форме Бекуса-Наура (т.е. не метасимволами и не графически, а набором правил для каждого состояния).

Введенные им (user"ом) правила я храю в массиве States описанном выше. Для генерации цепочек языка данной грамматики использую следующий алгоритм:
1. User задает нужное кол-во цепочек CHCount и диапазон длин цепочек
2. Count = 0 { кол-во найденых цепочек }
3. IF Count = CHCount THEN EXIT;
4. tmp := ""; // цепочка
5. Начинаю с начального состояния S => I := 0;
6. IF I < 0 THEN GOTO 11 {нашли терминал}
7. indx = random(States[i].CCount) {random"ом выбираем правило}
8. tmp := tmp + States[i].Cross[indx].data;
9. i := States[i].Cross[indx].indx;
10. GOTO 6
11. Проверяем "нужна" ли нам получившаяся цепочка
12. IF Нужна THEN inc(Count), GOTO 3 ELSE Goto 5

Вот... Можно наверно конкретизировать вопросы:
1. Можно ли улучшить алгоритм поиска
2. Как узнать min длину цепочки.

← →
Defunct © (2004-09-28 11:12) [6]

> 9. i := States[i].Cross[indx].indx;

у последнего правила индекс - (-1) я верно понял?

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

> 2. Как узнать min длину цепочки.
мин длинна цепочки = min(legths( Data 0,j)), где j от 1 до CrossesCount в состоянии States[0]. (грубо говоря наименьшая по длине одна единица данных первого состояния и есть ваша возможная min цепочка по вашему алгоритму)

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

← →
Ozone © (2004-09-28 11:25) [7]

// у последнего правила индекс - (-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 по определению.

← →
Ozone © (2004-09-28 12:59) [8]

← →
Суслик © (2004-09-28 13:05) [9]

> [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 13:13) [10]

Суслик © (28.09.04 13:05) [9]

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

← →
Суслик © (2004-09-28 13:18) [11]

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

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

← →
Игорь Шевченко © (2004-09-28 13:55) [12]

Дык можно BISON изучать. Или YACC

← →
Суслик © (2004-09-28 13:56) [13]

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

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

← →
Ozone © (2004-09-28 14:06) [14]

И все-таки, пока нет этой книги и нет возможности сравнивать алгоритмы - есть какие-нить идеи по решению моей задачи?

← →
Игорь Шевченко © (2004-09-28 14:32) [15]

Суслик © (28.09.04 13:56) [13]

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

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

← →
Суслик © (2004-09-28 14:49) [16]

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

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

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

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

← →
Суслик © (2004-09-28 15:09) [17]

Автору.

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

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

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

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

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

← →
DiamondShark © (2004-09-28 15:15) [18]

При чём тут лексы и яксы? Лексы и яксы -- это генераторы распознавателей грамматик. А автору нужен генератор порождаемых грамматикой цепочек.
Задачи обратные.

DiamondShark © (28.09.04 15:15) [18]

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

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

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

уууу.

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

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

Задача, в принципе, ограниченна, т.е. нужно либо левую либо правую КС-грамматику...

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

Суслик © (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 выведите найденные цепочки, остальное вас не должно волновать. Пусть дополняют правила.

Defunct © (29.09.04 05:22) [22]

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

Ozone © (28.09.04 16:02) [21]

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

Игорь Шевченко © (29.09.04 10:05) [24]

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

> Тем более как я могу узнать кол-во попыток которое мне необходимо сделать?

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

Задача про регулярные грамматики Найти похожие ветки