В тему компиляций и вычислений выражений.
В далёком 1973 году Воган Прэтт (
Vaughan Pratt) предложил простой и эффективный метод разбора выражений, не использующий ни автоматы, ни грамматику как таковую.
Идея заключается в том, что каждый символ (token) наделяется свойствами:
lbp = приоритет связывания символа слева,
nud = функция, определяющая результат применения оператора в начале выражения,
led = функция, определяющая результат применения в середине выражения.
Основной разбор осуществляется по схеме:
разбор(приоритет продолжения):
вытолкнуть символ из входного потока
результат = вызов nud этого символа
пока приоритет lbp следующего в потоке символа > приоритета продолжения:
вытолкнуть символ из входного потока
результат = применени led этого символа к текущему результату
Константы и переменные имеют приоритет связывания 0, а функция nud возвращает их значение (или ссылку). Поэтому применение разбора к константам сразу возратит их значение.
Для бинарных операторов функция led рекурсивно вызывает продолжение разбора (справа) вплоть до более низкого приоритета, и делает что-нибудь с уже накопленым (слева) результатом, и полученным рекурсивно.
Результат применения оператора аггрегируется для внешнего вызова.
Много-арные операторы — получают аргументы дополнительным вызовом функции разбора.
Префиксные операторы делаются с помощью определения для них функции nud.
Для правостороннего связывания меняется приоритет продолжения рекурсивного разбора.
На
сайте effbot.org приводится подробная реализация на питоне.
Там же есть ссылки для жаваскрипта и схемы.