Построение системы компьютерной алгебры
-
29-10-2019 - |
Вопрос
Я создаю CAS (систему компьютерной алгебры) на PHP, но сейчас я застрял.Я использую этот веб-сайт .
Теперь я написал токенизатор.Он преобразует следующее уравнение:
общийк этому:
общий(где группа - это еще один набор токенов).Как я могу упростить это уравнение?Да, я знаю, что вы можете сделать: добавить X-вары, но они находятся в подгруппе.Какой лучший метод я могу использовать для обработки этих токенов?
Решение
Следующим действительно полезным шагом было бы создание дерева синтаксического анализа:
Вы можете сделать одно из них, написав инфиксный синтаксический анализатор. Вы можете сделать это, написав простой рекурсивный анализатор спуска, или добавив большие пушки и с помощью генератора парсеров . В любом случае это помогает построить формальную грамматику:
общий Обратите внимание, что эта грамматика не обрабатывает синтаксис кода 2x
, но ее должно быть легко добавить.
Обратите внимание на умное использование рекурсии в правилах грамматики. primary
захватывает только переменные, числа и выражения в скобках и останавливается, когда встречается с оператором. multiplicative
анализирует одно или несколько выражений primary
, разделенных знаками *
, но останавливается, когда встречается со знаком +
или -
. additive
анализирует одно или несколько выражений multiplicative
, разделенных +
и -
, но останавливается, когда встречается с )
. Следовательно, схема рекурсии определяет приоритет операторов.
Реализовать прогнозирующий синтаксический анализатор с помощью рукой, как я сделал ниже ( см. полный пример на ideone.com ):
общийИтак, теперь у вас есть прекрасное дерево синтаксического анализа и даже красивая картинка к нему. Что теперь? Ваша цель (на данный момент) может состоять в том, чтобы просто объединить термины для получения результата в форме:
общийЯ оставлю это вам. Наличие дерева синтаксического анализа должно упростить задачу.
Другие советы
PHP хорош для строк, чисел и массивов. Но это плохой язык для реализации манипуляций с символьными формулами, потому что в нем нет собственного механизма для обработки «символьных выражений», для которых вам действительно нужны деревья. Да, вы можете реализовать всю эту технику. Сложнее выполнять алгебраические манипуляции . Это довольно большая работа, если вы хотите создать что-то полусложное. В идеале вы хотите, чтобы оборудование помогало вам писать преобразования напрямую и легко.
Например, как вы будете реализовывать произвольные правила алгебры? Ассоциативность и коммутативность? Термин «сопоставление на расстоянии»?, Например,
родовое словоВы можете посмотреть, как можно реализовать простой CAS с помощью нашего < a href="http://www.semanticdesigns.com/Products/DMS/ProgramTransformation.html" rel="nofollow"> система преобразования программ DMS . DMS имеет встроенные сложные математические конструкции, такие как коммутативность и ассоциативность, и вы можете явно писать правила алгебры для работы с символьными формулами.
Книга Компьютерная алгебра и символьные вычисления: математические методы Джоэла С. Коэна описывает алгоритм автоматического упрощения алгебраических выражений.
Этот алгоритм используется в библиотеке компьютерной алгебры Symbolism для C #.Следуя вашему примеру, следующая программа C #:
общийотображает на консоли следующее:
общий