Анализ выражений и вычисление их значения
Кащенко Илья
ученик 10 класса средней школы N36
Проблема синтаксического анализа и вычисления значений
арифметических выражений во время исполнения программы,
т.е. "на лету", далеко не новая, но достаточно важная. Не
решив ее, невозможно создать программы для
математических расчетов, построения всевозможных
графиков. Написать какую-либо конкретную программу,
обходя эту проблему, довольно легко, но если, например,
придется решить другую систему уравнений, то придется
исправлять программу и перекомпилировать ее заново.
Понятно, что этот процесс не только является неудобным,
долгим и достаточно трудоемким, но и доступен только для
человека, знакомого с программированием. Гораздо удобнее
создать инструмент, способный принимать математические
формулы, проверять их на правильность и вычислять
значения этих функций с заданными параметрами.
Программные модули, реализующие обработку формул "на лету",
являются по своей природе интерпретаторами или
компиляторами и состоят из нескольких этапов. Рассмотрим
характерный процесс обработки выражения:
- Проверка правильности выражения
- Перевод выражения в некоторую форму, удобную для
дальнейших манипуляций
- Вычисление значения выражения с данными
параметрами либо компиляция
Проверка правильности выражения включает в себя лексический
и синтаксический анализ. Первый создает лексическую
свертку и сразу же выявляет неверные лексемы, то есть
лексические ошибки. Например, если вместо правильного
"COS(X)", на вход анализатора подается выражение "CPS(X)"
в ходе лексической проверки эта ошибка должна быть
выявлена, а дальнейшая обработка выражения
приостановлена. В задачу синтаксического анализа также
входит проверка выражения на наличие таких ошибок как
несоответствие количества открывающих и закрывающих
скобок и.т.п.
Если выражение было введено правильно, то оно
преобразуется в более удобную форму для подсчета
конечного значения. Одной из таких форм является
обратная польская запись. Это бесскобочная запись
выражения, где все знаки стоят в порядке выполнения
действий, которые они обозначают. Например, если в
обычном формате выражение будет выглядеть a*b+c*(d-e), то
в польской записи оно свернется в ab*cde-*+. Для человека
такой способ записи выражений непривычен, но его намного
легче и удобнее обрабатывать.
Работа выполнена под руководством научного руководителя:
асп. Кащенко Дмитрия Сергеевича
© ярославский областной Центр Дистанционного Обучения школьников, 1998