Есть ли известный алгоритм, который разбирает выражения на сложных языках типа JS и C?

Question

[dollar]

Для примера возьмём только JavaScript и C++, потому что синтаксис похож.
Я знаю, что в общем случае делается так:
1) Строка с выражением токенизируется, то есть разбивается на последовательные куски, где точно известно, что каждый токен из себя представляет - число, скобку, оператор, литерал и т.д.
2) Порядок токенов меняется в соответствии с польской нотацией. Это такая своеобразная сортировка, чтобы последовательность вычислений совпадала с порядком токенов в массиве.
3) Собственно подсчет, где переменные заменяются их значениями, функции вызываются по именам и т.д.

Проблема в том, что польская нотация слишком простая. Она учитывает только операции с двумя параметрами. И она не учитывает унарные операторы, то есть выражение 1+ +1 уже будет ошибочным. А также не учитывает сложные операторы типа A ? B : C. Не поддерживаются функции с произвольным количеством параметров, например Math.max(a, b, c, d, и т.д.).

Есть ли более универсальный алгоритм?

Comments

[RidgeA]

польской нотацией тут не обойтись
Сам не разбирался с этой темой, но, говорят, хорошей отправной точкой может служить https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BC%D...

[Roman]

https://ru.wikipedia.org/wiki/LALR(1)

Answer 1

[Денис Загаевский]

Польская нотация учитывает всё, что угодно. В смысле, что напишешь, то и будет.
унарные операторы? Делай две операции - UNARY_MINUS, MINUS. 1 1 UNARY_MINUS MINUS == 2
Сложные операторы? A B C TERNARY (не лениво? ну можно и лениво сделать)
Функции? a b c d 4 max call. Здесь a, b, c, d, 4, max - аргументы, они все ложатся в стек. Интерпретатор видит call, достает из стека функцию (max), понимает, что это функция с переменным числом аргументов, достает это число (4), достает остальные аргументы по количеству, вызывает функцию max(a b c d).
В Полизе могут быть инструкции, управляющие потоком выполнения 1234 JUMP - переводит курсор на адрес 1234.
Всё зависит от твоей извращенности, короче.
Чтобы не быть голословным, вот мой пет-проект, там вычисление как раз на Полизе реализовано.

У польской нотации есть минусы - сложно анализировать программу, вычислять типы. Сложно оптимизировать. Для этого лучше подходят AST.