Домино Де Ремера

Де Ремер предложил наглядную интерпретацию задачи разбора, представив ее как игру в своеобразное домино. Играющий располагает "костями" домино нескольких типов. Типов столько, сколько правил в грамматике. Каждое правило дает один тип пластинки.

 

Считается, что костяшек каждого типа имеется сколько необходимо. Левой части правила грамматики, нижняя - правой. Верхняя и нижние пластинки соединены резиновыми нитями. Пластинки можно представлять друг другу плоскими сторонами полукруга, если на них записаны одинаковые символы. Фигуры домино нельзя переворачивать и нельзя менять порядок следования символов.

            В начале  игры в верхней части поля помещается полукруг, обращенный выпоклустью вверх, в котором записан начальный нетерминал грамматики. В нижние части игрового поля в полукругах, обращенных плоской частью вверх, размещаются терминальные символы.

Цель состоит в том, чтобы соединить с помощью имеющихся фигур символы терминальной цепочки и начальный нетерминал.

Имея ввиду интерпретацию де Ремера можно представить себе и различные подходы к решению задаче разбора. Если подбор костей удается осуществить так, что однажды поставленную кость никогда не придется убирать, мы имеем дело с детерминированным алгоритмом разбора - выбор применяемого правила грамматики всегда однозначен. Если принятые решения о выборе типа домино приходится отменять - алгоритм работает с возвратами, он недетерминированный. Детерминированные алгоритмы эффективней, и конечно всегда существует стремление найти и использовать такой алгоритм для синтаксического анализа.

 

            Если дерево строится свреху вниз от начального нетерминала в сторону терминальной цепочки, алгоритм относится к классу нисходящих, от цепочки в сторону корня дерева - восходящих. Можно вначале подбирать для левых символов, а можно для правых.