images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
26/04/2024 21:28:10

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

2390. РБНФ

Ограничения: время – 250ms/500ms, память – 512MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Бетти изучает синтаксис сложного языка заклинаний. К сожалению, его синтаксис описан с помощью расширенной формы Бэкуса-Наура (РБНФ), а Бетти пока понимает только описания, сделанные с помощью простой БНФ. Правила РБНФ имеют следующий синтаксис:
rule = ?symbol? "=" variant-list ";"
variant-list = elem-list | variant-list "|" elem-list
elem-list = | elem-list elem
elem = ?symbol? | ?literal? | “{“ variant-list “}” | “(“ variant-list “)” | “[“ variant-list “]”
где ?symbol? — это последовательность латинских букв, цифр и символов _ и -(минус), начинающаяся с буквы или символа _, ?literal? – последовательность непробельных символов в кавычках, апострофах или между символами ??. Через | указываются возможные варианты получения символа. Скобки { } означают повторение значения в скобках 0 или более раз. Скобки [ ] означают повторение значения в скобках 0 или 1 раз. Скобки ( ) служат для группировки, указания порядка применения операций.
В БНФ нет { }, ( ) и [ ], поэтому при переводе необходимо ввести вспомогательные символы и правила, как показано в таблице ниже. Введённые вспомогательные символы должны начинаться со знака подчеркивания, затем следует номер вспомогательного символа. Нумерация должна быть сквозная, по всем правилам, начиная с 1. Меньший номер получает символ, соответствующий более левой скобке.
РБНФБНФ
a = { b } ;a = _1 ;
_1 = | _1 b ;
a = b ( c | d ) ;a = b _1 ;
_1 = c | d ;
a = [ b ] ;a = _1 ;
_1 = | b ;
Напишите программу, которая переведёт описание синтаксиса языка заклинаний в БНФ.
Формат ввода
Ввод содержит не более 10 строк длиной до 1000 символов. Каждая строка содержит правило в РБНФ. Лексемы в правиле разделены ровно одним пробелом. Гарантируется, что в правилах нет символов, начинающихся с символа _.
Формат вывода
Для каждого правила выведите его представление в БНФ в аналогичной форме. Правила для новых символов должны быть выведены после правил, в которых они используются, в порядке возрастания номеров символов. Для каждой пары скобок должен быть добавлен ровно один вспомогательный символ и правило для него, как показано в таблице выше.

Пример ввода

cast = "cast" ?id? "(" [ a { "," a } ] ")" ;
a = ?id? | ?num? | a ( '+' | '-' ) a ;

Пример вывода

cast = "cast" ?id? "(" _1 ")" ;
_1 = | a _2 ;
_2 = | _2 "," a ;
a = ?id? | ?num? | a _3 a ;
_3 = '+' | '-' ;
loading