Как обнаружить циклическую логику или рекурсию в оценщике пользовательских выражений? - PullRequest
Новая
       12

Как обнаружить циклическую логику или рекурсию в оценщике пользовательских выражений?

3 голосов
/ 26 ноября 2008

Я написал экспериментальный оценщик функций, который позволяет мне связывать простые функции так, чтобы при изменении переменных все функции, которые зависят от этих переменных (и функции, которые полагаются на эти функции и т. Д.), Обновлялись одновременно. Я делаю это вместо того, чтобы оценивать функцию сразу после ее ввода, я сохраняю функцию. Только когда запрашивается выходное значение, я оцениваю функцию и оцениваю ее каждый раз, когда запрашивается выходное значение.

Например: 

pi = 3.14159
rad = 5
area = pi * rad * rad
perim = 2 * pi * rad

Я определяю 'pi' и 'rad' как переменные (ну, функции, которые возвращают константу), а 'area' и 'perim' как функции. Каждый раз, когда меняются «pi» или «rad», я ожидаю, что результаты «area» и «perim» изменятся в натуральной форме. Аналогично, если бы были какие-либо функции, зависящие от «области» или «перима», результаты этих изменений также изменились бы.

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

Например: 

a = b
b = c
c = a

Прямо сейчас оценка последней строки приводит к исключению StackOverflowException (в то время как первые две строки оцениваются как «0» - необъявленная переменная / функция равна 0). То, что я хотел бы сделать, это обнаружить круговую логическую ситуацию и запретить пользователю вводить такое утверждение. Я хочу сделать это независимо от того, насколько глубоко скрыта круговая логика, но я понятия не имею, как это сделать.

Кстати, за кулисами входные строки преобразуются в токены с помощью простого сканера, затем в абстрактное синтаксическое дерево с помощью рукописного синтаксического анализатора рекурсивного спуска, а затем оценивается AST. Язык C #, но я не ищу решение кода - одна логика будет в порядке.

Примечание: это личный проект, который я использую, чтобы узнать о том, как работают парсеры и компиляторы, поэтому он не является критически важным - однако знания, которые я извлекаю из этого, я планирую применить в реальной жизни в какой-то момент , Любая помощь, которую вы, ребята, можете предоставить, будет принята с благодарностью. =)

Редактировать: Если кому-то интересно, этот пост в моем блоге описывает, почему я пытаюсь изучить это, и что я получаю из этого.

Ответы [ 3 ]

6 голосов
/ 26 ноября 2008

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

Прежде чем я поместил каждое имя переменной в стек, я бы проверил, было ли оно там. Если это так, то это была круговая ссылка. Я даже смог отобразить имена переменных в циклической цепочке ссылок (так как они будут в стеке и могут выталкиваться последовательно, пока я не достигну оскорбительного имени).

РЕДАКТИРОВАТЬ: Конечно, это было для отдельных формул ... Для вашей проблемы лучшим вариантом будет циклический график присваивания переменных.

2 голосов
/ 26 ноября 2008

Решение (возможно, не лучшее) состоит в создании графа зависимостей.

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

Это можно оборвать. Каждый раз, когда функция добавляется или изменяется, помечайте ее. Если результатом оценки является вызов функции, которая помечена, у вас есть цикл.

Пример:

a = b

  • флаг
  • eval b (не найден)
  • разблокировать

b = c

  • флаг b
  • eval c (не найден)
  • разблокировать b

c = a

  • флаг с
  • eval a
  • eval b
  • eval c (помечено) -> Cycle, отменить изменение на c!
  • разблокировать c
0 голосов
/ 27 ноября 2008

В ответ на комментарий к ответу два:

(Извините, только что испортил мое openid создание, так что мне придется связать старый материал позже ...)

Если вы поменяете «flag» для «push» и «unflag» для «pop», это почти одно и то же :) Единственным преимуществом использования стека является простота, с которой вы можете предоставить подробную информацию о цикле, независимо от его глубины. (Полезно для сообщений об ошибках :))

Andrew

...