Нужен способ разобрать алгебраические выражения в C

Question

Мне нужно разобрать алгебраические выражения для приложения, над которым я работаю, и я надеюсь украсить немного коллективной мудрости, прежде чем взломать его и, возможно, Дорога.

Что мне нужно сделать, это довольно прямолинейно: с учетом текстового алгебраического выражения (3 * x - 4 (y - sin (pi))) создает объектное представление уравнения. Пользовательские объекты уже существуют, поэтому мне нужен синтаксический анализатор, который создает дерево, в которое я могу ходить, чтобы создать объекты, которые мне нужны.

Основные требования будут:

1. Способность выражать алгебру как грамматики, так что я есть контроль и может настроить/продлить его по мере необходимости.

2. Исходный синтаксис будет содержать целые числа, вещественные числа, константы, переменные, арифметические операторы (+, -, *, /), степени (^), уравнения (=), скобки, приоритет и простые функции (sin (Пи)). Я надеюсь расширить приложение довольно быстро, чтобы поддерживать соответствующие функции (f (x) = 3x +2).

3. Должен компилироваться в C, поскольку его необходимо интегрировать в мой код.

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

Я сделал свою домашнюю работу в Google, и это выглядит как самый лучший подход заключается в использовании грамматики BNF и программного обеспечения для создания компилятора в С. Так мои вопросы:

1. делает грамматику BNF с соответствующими генератор парсера для алгебраических выражений (или, еще лучше, LaTex) уже существует? Кто-то должен был это сделать уже. Я ДЕЙСТВИТЕЛЬНО хочу, чтобы меня не сворачивали, главным образом потому, что я не хочу его проверять. Я был бы готов заплатить разумную сумму за библиотеку (до 50 долларов США)

2. Если нет, то какой генератор парсера для C вы считаете наиболее простым для изучения/использования здесь? Лекс? YACC? Flex, Bison, Python/SymPy, другие? Я не знаком ни с одним из них.

Answer 1

Мне очень повезло с ANTLR. Он имеет время автономной работы для разных языков, включая C, и имеет очень хороший синтаксис для указания грамматик и построения деревьев. Недавно я написал аналогичную грамматику (алгебраические выражения) в 131 строке, что определенно управляемо.

Answer 2

Стандартные инструменты Linux flex и bison, вероятно, будут наиболее подходящими здесь. IIRC аналитики образцов и лексеры, используемые в этих инструментах, делают что-то близкое к тому, что вы хотите, поэтому вы можете просто изменить этот код, чтобы получить то, что вам нужно.

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

Answer 3

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

Answer 4

Я использовал код (найденный в сети) из следующих:

Программы перевод Основа»Питер Calingaert

Я расширенный его для обработки функций , который позволяет вам реализовывать такие вещи, как «if (a, b, c)» (вроде того, как Excel что-то делает).