Как это закодить?

Question

[moneymakerXA]

Предположим, что структура данных для представления регулярного выражения следующая

reg_expr	:= { ‘key’ : ‘atm’, ‘val’ : token}
		| {‘key’ : ‘|’, ‘val’ : {‘fst’ : reg_expr, ‘snd’ : reg_expr}}
		| {‘key’ : ‘.’, ‘val’ : {‘fst’ : reg_expr, ‘snd’ : reg_expr}}
		| {‘key’ : ‘*”, ‘val’ : reg_expr}

Напишите функцию, печатающую соответствующее регулярное выражение в следующем предположении:

Priority of the key is following ‘*’ > ‘.’ > ‘|’
‘*’ is postfix
‘.’ and ‘|’ are left associative

Подскажите с чего начать, как понять словарь reg_expr? Буду благодарен любому совету или ссылке на хорошую статью ))

Comments

[moneymakerXA]

VicTHOR, Банят?

Answer 1

[Сергей П]

reg_expr - это не словарь, а грамматика, описывающая некое выражение.
По русски читается примерно как:
Регексп - ЭТО:
ЛИБО Атом
ЛИБО ОператорИли(с двумя аргументами: первый - Регексп; второй - тоже Регексп)
ЛИБО ОператорТочка(с двумя аргументами: первый - Регексп; второй - тоже Регексп)
ЛИБО ОператорЗвёздочка(с одним аргументом, который Регексп).

Ниже важное дополнение:

Priority of the key is following ‘*’ > ‘.’ > ‘|’
‘*’ is postfix
‘.’ and ‘|’ are left associative

Это значит, что у ОператораЗвёздочка самый высокий приоритет, потом идёт ОператорТочка, потом ОператорИли.
ОператорЗвёздочка постфиксный, то есть применяется после своего единственного аргумента.
ОператорТочка и ОператорИли - лево-ассоциативные.

Похоже автору вопроса нужно написать регулярное выражение, которое будет матчиться со строкой, соответствующей описанной грамматике.
Дальше может быть только решение задачи, а автор о нём не спрашивал, а лишь спросил с чего начать.
Не буду ломать ему удовольствие и спойлерить результат=)