Как я кодировал бы синтаксический анализатор сложной формулы вручную?
Гм, это - язык - агностик, я предпочел бы делать его в C# или F#, но я больше интересуюсь на этот раз вопросом, "как это работало бы так или иначе".
Что я хочу выполнить ist:
a) Я хочу ИЗУЧИТЬ это - это о моем эго на этот раз, это для забавного проекта, где я хочу показать меня, что я - действительно хорошее в этом материале
b) Я знаю крошечное немного о EBNF (хотя я еще не знаю, как работы приоритета оператора в EBNF - Irony.NET делает его правильно, я проверил примеры, но это является немного зловещим мне),
c) Мой синтаксический анализатор должен смочь взять это: 5 * (3 + (2 - 9 * (5 / 7)) + 9), например, и дают мне правильные результаты
d) Быть вполне откровенно говоря, этим, кажется, самая большая проблема в записи компилятора или даже интерпретатора для меня. У меня не было бы проблемы при генерировании даже ассемблерного кода на 64 бита (я ассемблер записи CAN вручную), но синтаксический анализатор формулы...
e) Другая мысль: даже простые компьютеры (как мои старые 1246 Sharp только с приблизительно 2 КБ RAM) могут сделать это... это не может быть ЭТО трудно, правильно? И даже очень, очень старые языки программирования имеют оценку формулы... ОСНОВНОЙ с 1964, и они уже могли вычислить вид формулы, которую я представил как пример
f) Несколько идей, несколько вдохновения были бы действительно достаточно - у меня просто нет подсказки, как сделать приоритет оператора и круглые скобки - я ДЕЙСТВИТЕЛЬНО, однако, знаю, что он включает AST и что многие люди используют стек
Так, что Вы думаете?
3 ответа
Для синтаксического анализатора на основе стека, реализованного на PHP, который использует алгоритм маневрового двора Джикстры для преобразования инфикса в постфиксную нотацию и с поддержкой функций с различным количеством аргументов, вы можете посмотреть в источнике вычислительная машина PHPExcel
Вы должны узнать о парсерах Рекурсивного спуска .
Ознакомьтесь с упражнением Code Golf, выполняя именно это, 10 различными способами:
Code Golf: вычислитель математических выражений (который уважает PEMDAS).
Некоторые из этих «гольфовых» решений представляют собой синтаксические анализаторы с рекурсивным спуском, просто закодированные в разных способами.
Вы обнаружите, что выполнение простого синтаксического анализа выражений, безусловно, самая простая вещь в компиляторе. Разобрать остальную часть языка сложнее, но понять, как взаимодействуют элементы кода и как сгенерировать хороший код, гораздо сложнее.
Вам также может быть интересно, как выразить синтаксический анализатор с помощью BNF и как что-то сделать с этим BNF. Вот пример того, как анализировать алгебру и манипулировать ею символически с явным BNF и неявным AST в качестве основы. Это не то, что обычно делают компиляторы, но механизм, который это делает, глубоко основан на технологии компиляции.
Традиционно процессоры формул на компьютерах используют нотацию POSTFIX. Они используют стек, выдвигают 2 элемента в качестве операндов, выдвигают третий элемент в качестве оператора и передают результат.
Что вам нужно, так это преобразователь нотации INFIX в POSTFIX, что на самом деле довольно просто. Как только вы перейдете к постфиксной обработке, это будет самое простое, что вы когда-либо сделаете.