Парсер для пользовательских инфиксных операторов

Question

Я пишу переводчик для языка, где функции могут использоваться в качестве операторов.Однако содержимое функций будет известно только во время выполнения.

Для этого я рассмотрел два решения:

• Разбор выполняется во время выполнения с использованием информации времени выполнения для функции
• Все пользовательские операторы используют значения по умолчанию для приоритета и ассоциативности.

Я выбрал последнее, так как вижу ряд преимуществ в разборе отдельно для выполнения.

Теперьдоходит до реализации и мне интересно посмотреть, какие есть варианты.Мои первые мысли - парсер с уменьшением сдвига, но у меня мало опыта в создании парсеров.

Пример:

LHS op RHS : LHS * RHS     /* define a binary operator 'op' */
var : 3                    /* define a variable */
print 5 op var             /* should print 15 */

LHS op RHS : LHS / RHS     /* Re-define op */
print var op var           /* Should print 1 */

В последнем случае парсер получит от лексера:1018 * id id id ".Только во время выполнения я знаю, что идентификатор 'op' является оператором.

Answer 1

(публикация результатов комментариев по запросу.)

Решение № 1 определенно некрасивое, сложное в реализации и ненужное, я согласен. Решение № 2 намного проще в реализации и понимании. Вы также можете разрешить настраиваемую ассоциативность и приоритет для операторов, если они известны статически. Главное, что эти факты известны во время разбора.

Что касается фактического синтаксического анализа, большинство синтаксических анализаторов будут работать просто отлично, поскольку любые два выражения, окружающие идентификатор, являются приложением пользовательского инфиксного оператора (это менее верно, если вы разрешите пользовательский приоритет и ассоциативность, в этом случае вам нужен алгоритм что позволяет определять их для каждого оператора во время разбора). В любом случае, мой личный фаворит - это «анализатор приоритета оператора сверху вниз» или анализатор Pratt. Я обнаружил, что следующие ресурсы (упорядоченные по полезности для меня, YMMV) достаточно хорошо описывают это:

• Простой анализ сверху вниз в Python
• Парсеры Pratt: синтаксический анализ выражения - это просто
• Приоритет оператора сверху вниз

Два свойства алгоритма очень хорошо подходят для этой задачи:

• Поиск ассоциативности («сила привязки») происходит динамически для каждого токена (что позволяет анализатору позволить пользователю определять приоритет для своих операторов).
• Это очень просто написать вручную [*], и вам, вероятно, придется сделать это, поскольку такая степень динамичности выходит за рамки большинства (по крайней мере, всех, что я знаю) генераторов синтаксических анализаторов.

[*] Я лично написал парсер для очень большого (не хватает только case, многомерных массивов и, возможно, некоторых неясных тонкостей) подмножества Паскаля в 500 строк Python и 2-3 дня работы, остальные отсутствует только потому, что другие части программного обеспечения, в котором оно использовалось, были в то время более интересными, и у меня не было причин для реализации остальных.