Задачка. Контекстно-свободная грамматика для римских чисел.

← →
Sergey Masloff (2007-08-20 11:59) [0]

Сижу ради освежения мозга решаю задачки. И что-то на одной застопорился хотя судя по всему она элементарная - по крайней мере все остальные из этого раздела решил за 5 минут. Если кому не лень и займет немного черкните ваш вариант.

← →
oldman © (2007-08-20 12:01) [1]

Ну и?
Задачка-то где?

← →
Sergey Masloff (2007-08-20 12:06) [2]

Ну собственно это она и есть. Составить вышеозначенную грамматику для римских чисел.

← →
AZIZE © (2007-08-20 12:08) [3]

я когда-то делал и автомат Мура писал, сейчас наверное не вспомню нужно подымать

← →
oldman © (2007-08-20 12:11) [4]

> для римских чисел

Она сильно отличается от грамматики для любого алфавита?
Вроде все определения по грамматикам основаны на абстрактных алфавитах.

← →
oldman © (2007-08-20 12:13) [5]

> oldman © (20.08.07 12:11) [4]

Просто "мозги освежать" как-то влом... :(

← →
AZIZE © (2007-08-20 12:17) [6]

если сильно надо могу дома посмотреть и завтра принести(если не забуду)

← →
Sergey Masloff (2007-08-20 12:20) [7]

AZIZE © (20.08.07 12:08) [3]
Не если напряг не нужно. Это для баловства. Я может тоже писал лет уже скоро 20 назад ;-)

← →
AZIZE © (2007-08-20 12:23) [8]

> Sergey Masloff (20.08.07 12:20) [7]

не напряг просто могу забыть

← →
Mystic © (2007-08-20 12:42) [9]

Чтобы делать некоторые вещи, надо иметь либо светлую голову, либо чугунную задницу. Как по мне, эта задача относится ко второму случаю. Просто перебираем все правила образования чисел и получаем:

1-3: [I] [I] I
1-5: 1-3 | [I] V
1-8: 1-5 | V 1-3
1-9: 1-8 | I X
1-10: 1-9 | X
1-39: 1-9 | [X] [X] X [1-9]
1-50: 1-39 | [1-10] L
...

На самом деле, мне кажется, что римские числа могут быть описаны даже большим регулярным выражением, ввиду того есть ограничения в виде максимально наибольшего обозначения, выше которого числа образуются однотипно. Например, если наибольшее число, это G, то числа выше образуются как G*X, где X регулярное выражение, описывающее все числа, меньшие чем G

...

← →
Sergey Masloff (2007-08-20 13:20) [10]

Mystic © (20.08.07 12:42) [9]
Этот вариант приходил в голову но наверное там как-то проще. Все остальные примеры там выражались в пару-тройку строчек а этот уж слишком объемный получается... Там же кроме I V X L еще есть C D M и черточки умножения на 1000 и правила типа V L D не могут повторяться а I X C M повторяются не более 3 раз... Действительно слишком похоже не чугунную з.

← →
Mystic © (2007-08-20 14:22) [11]

> Все остальные примеры там выражались в пару-тройку строчек
> а этот уж слишком объемный получается...

Объемный но каждый шаг очень простой. А попытаться реализовать небольшим числом правил затруднительно. Например, если у нас есть просто некая сущность "римское число", то любая рекурсивность (определение римского числа через его же) моментально приводит к тому, что становятся допустимы "лишние" представления.

← →
pasha_golub © (2007-08-21 11:57) [12]

Мужики, чего я нашел-то случайно:
Максимальное число, которое можно записать римскими цифрами, не нарушая правил Шварцмана (правил записи римских цифр) - 3999 (MMMCMXCIX) - больше трех цифр подряд писать нельзя.

← →
Sergey Masloff (2007-08-21 12:15) [13]

pasha_golub © (21.08.07 11:57) [12]
Бедные римляне ;-)
На самом деле у них еще есть черточка - множитель на 1000. Пишется над любой буквой. Например над V сверху нарисовать палочку - будет 5000

Но я уже забил. Или путь Mystic ошибочный или формулировка задачи неточная потому что я уже намного дальше прошел и все задания очень простые. А это хоть и простое но слишком объемное получается.

> или формулировка задачи неточная

Скорей, всего просто не полная.

А что за задачник, коли не секрет?
Я вот иногда беру двухтомник Ахо Ульмана (Теория Синтаксического анализа, перевода и компиляции), там есть упражнения :)

> Я вот иногда беру двухтомник Ахо Ульмана (Теория Синтаксического
> анализа, перевода и компиляции)

Кстати, к стыду своему не осилил. Тяжеловата показалась для восприятия. Хотя с этим самым анализом приходится работать

← →
Sergey Masloff (2007-08-21 13:05) [17]

> Да тоже Ахо Ульман только более поздняя - компиляторы принципы
> технологии инструменты.

Я бы сказал, что у этих книг разная направленность, потому как в более поздней книге абсолютна не раскрыта теория (теоремы, доказательства, и т. п.)

> Mystic © (20.08.07 12:42) [9]
> 1-3: [I] [I] I
> 1-5: 1-3 | [I] V
> 1-8: 1-5 | V 1-3
> 1-9: 1-8 | I X
> 1-10: 1-9 | X
> 1-39: 1-9 | [X] [X] X [1-9]
> 1-50: 1-39 | [1-10] L
> ...

И самое главное в этом алгоритме - именно "..."
:)))

Задачка. Контекстно-свободная грамматика для римских чисел. Найти похожие ветки