21/11/2024 19:54:17

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

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

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 = '+' | '-' ;