Учитывая грамматику (a|ab)c, мы можем записать дерево грамматики в виде:
and
/ \
or c
/ \
a ab
Но это невозможно разобрать как есть.Например, если мы дадим ему ввод «abc», он сначала пройдет по левой стороне дерева, найдет совпадение «a», или «вернет true», а «вызывает» c, «c» завершится неудачно, ивсе дерево терпит неудачу без попытки "ab".
Если мы преобразуем дерево следующим образом:
or
/ \
and and
/ \ / \
a c ab c
Что должно быть эквивалентным представлением, то мы движемся вниз влево, как и раньше,нажатие «a», «a» возвращает true, мы пробуем «c» рядом с ним, что не удается, мы возвращаемся к корню и пробуем правую ветвь на этот раз, что успешно.
Итак, чтобы преобразоватьпервое дерево во второе, нам просто нужно «продвинуть» «или», клонировать «и» и смешать детей.Если мы сделаем это, смогу ли я проанализировать любое дерево, состоящее только из "ands", "ors" и листовых узлов?Или есть сценарий, в котором это может потерпеть неудачу?
Я пробовал его с более сложным сценарием (на бумаге), таким как (((a|ab)c)|d)e, и, похоже, он тоже работает.
Править: В этом сценарии, кажется, работает, если я продвигаю оба "или" на один уровень, но это также работает, если я продолжаю продвигать "или", пока они не окажутся на вершине дерева.