Как бы я кодировал сложный синтаксический анализатор формул вручную?

Question

Хм, это не зависит от языка, я бы предпочел сделать это на C # или F #, но на этот раз меня больше интересует вопрос "как бы это работало в любом случае".

Что я хочу сделать, это:

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

б) Я немного знаю о EBNF (хотя я пока не знаю, как работает приоритет операторов в EBNF - Irony.NET все делает правильно, я проверил примеры, но это немного зловеще для меня)

в) Мой парсер должен быть в состоянии принять это: 5 * (3 + (2 - 9 * (5/7)) + 9), например, и дать мне правильные результаты

d) Честно говоря, это кажется самой большой проблемой при написании компилятора или даже интерпретатора для меня. У меня не было бы проблем с генерацией даже 64-битного ассемблерного кода (я могу написать ассемблер вручную), но парсер формул ...

e) Еще одна мысль: даже простые компьютеры (например, мой старый Sharp 1246S с оперативной памятью всего около 2 КБ) могут это сделать ... это не может быть ЧТО сложно, верно? И даже очень, очень старые языки программирования имеют оценку формул ... БЕЙСИК с 1964 года, и они уже могли рассчитывать форму формулы, которую я представил в качестве примера

f) Несколько идей, немного вдохновения было бы действительно достаточно - я просто понятия не имею, как сделать приоритет оператора и скобки - я, однако, знаю, что он включает в себя AST и что многие люди используют стек

Итак, что вы думаете?

Answer 1

Вы должны узнать о парсерах рекурсивного спуска .

Проверьте упражнение Code Golf, выполнив 10 разных способов:

Code Golf: средство оценки математических выражений (с учетом PEMDAS)

Некоторые из этих «гольф-решений» представляют собой парсеры рекурсивного спуска, просто кодируемые по-разному.

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

Вас также может интересовать, как выражать синтаксический анализатор с использованием BNF и как что-то делать с этим BNF. Вот пример того, как символически анализировать и манипулировать алгеброй с явным BNF и неявным AST в качестве основы. Это не то, что традиционно делают компиляторы, но механизм, который делает это, глубоко основан на технологии компиляторов.

Answer 2

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

Answer 3

Традиционно процессоры формул на компьютерах используют нотацию POSTFIX. Они используют стек, выталкивают 2 элемента в качестве операндов, выталкивают третий элемент в качестве оператора и отправляют результат.

Что вам нужно, так это преобразователь нотаций INFIX в POSTFIX, который действительно довольно прост. Как только вы приступите к постфиксной обработке, это будет самое простое, что вы когда-либо будете делать.

Answer 4

Если вы хотите использовать существующее решение, я могу порекомендовать работающую , PSR-0-совместимую реализацию алгоритма шунтирования: https://github.com/andig/php-shunting-yard/tree/dev.