Bottom-Up-Parser: когда применять какое правило редукции?

Самый простой восходящий подход к анализу грамматик, подобных вашей (в основном, грамматик выражений), — это анализ приоритета операторов.

Напомним, что синтаксический анализ снизу вверх включает в себя построение дерева синтаксического анализа слева направо снизу. Другими словами, в любой момент во время синтаксического анализа у нас есть частично собранное дерево с только терминальными символами справа от того места, где мы читаем, и комбинацией терминалов и нетерминалов слева («префикс»). . Единственная возможная редукция относится к суффиксу префикса; если редукция не применяется, мы должны иметь возможность сместить терминал с входа на префикс.

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

Анализатор приоритета операторов по существу слеп к нетерминалам; он просто не различает их. Таким образом, у вас не может быть двух продукций, правые части которых содержат точно такую ​​же последовательность терминалов, потому что синтаксический анализатор op-prec не будет знать, какую из этих двух продукций применить. (Это традиционная точка зрения. На самом деле ее можно немного расширить, чтобы вы могли иметь две продукции с одними и теми же терминалами, при условии, что нетерминалы находятся в разных местах. Это позволяет использовать грамматики, которые имеют унарные операторы -, например, поскольку правые стороны <non-terminal> - <non-terminal> и - <non-terminal> можно различить, не зная имен нетерминалов, только их присутствие.

Другое требование состоит в том, что вы должны иметь возможность строить отношения приоритета между терминалами. Точнее, мы определяем три отношения предшествования, обычно обозначаемые как <·, ·> и ·=· (или некоторые типографские вариации на эту тему), и настаиваем на том, что для любых двух терминалов x и y истинно только одно из отношений x ·> y, x ·=· y и x <· y. .

Грубо говоря, < и > в отношениях соответствуют краям производства. Другими словами, если x <· y, это означает, что за x может следовать нетерминал с продукцией, первый терминал которой y. Точно так же x ·> y означает, что y может следовать за нетерминалом с продуктом, последним терминалом которого является x. И x ·=· y означает, что есть некоторая правая часть, где x и y являются последовательными терминалами в этом порядке (возможно, с промежуточным нетерминалом).

Если ограничение на одно отношение истинно, то мы можем разобрать его следующим образом:

Пусть x будет последним терминалом в префиксе (то есть либо последним, либо предпоследним символом), а y будет упреждающим символом, который должен быть терминалом. Если x ·> y то уменьшаем, и повторяем правило. В противном случае мы сдвигаем y на префикс.

Для того, чтобы уменьшить, нам нужно найти начало производства. Мы перемещаемся назад по префиксу, сравнивая последовательные терминалы (все они должны иметь отношения <· или ·=·), пока не найдем один с отношением <·. Тогда терминалы между <· и ·> будут правой стороной искомого произведения, и мы можем вставить нетерминалы в правую сторону, как указано.

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

Обратите внимание, что обычно очень легко найти производство, потому что большинство производств имеют только один (<non-terminal> * <non-terminal>) или два (( <non-terminal> )) терминала. Наивная реализация может просто объединить терминалы в строку и использовать ее в качестве ключа в хеш-таблице.

Классической реализацией синтаксического анализа приоритета операторов является так называемый «алгоритм маневровой станции», разработанный Эдсгером Дейкстрой. В этом алгоритме отношения предшествования моделируются с помощью двух функций, левого приоритета и правого приоритета, которые отображают терминалы в целые числа, так что x <· y истинно, только если right-precedence(x) < left-precedence(y) (и аналогично для других операторов). Не всегда возможно найти такие отображения, и отображения являются прикрытием реальных отношений предшествования, потому что часто бывают пары терминалов, для которых не применяется отношение предшествования. Тем не менее, часто бывает так, что эти отображения можно найти, и почти всегда это имеет место для простых грамматик выражений.

Надеюсь, этого достаточно, чтобы вы начали. Я рекомендую вам на самом деле прочитать некоторые тексты о анализе снизу вверх, потому что я думаю, что уже написал слишком много для SO-ответа, и я еще не включил ни одной строки кода. :)