16.2 Представление арифметических выражений

Важным вопросом при разработке алгоритмов эквивалентных преобразований является способ представления арифметических выражений. Здесь предлагается использовать синтаксические деревья, которые строятся при проведении синтаксического разбора арифметических выражений. В качестве грамматики предлагается использовать следующую контекстно-свободную грамматику:
       1.<E> - начальный нетерминал;
       2.<E>, <T>, <D> - множество нетерминальных символов;
       3.function, name, const, +, -, *, /, (, ) - множество терминальных символов;
       4.Правила:
              (1) <E>= > <T> + <E>,
              (2) <E>= > <T> ? <E>,
              (3) <E> = > <T>,
              (4) <T>= > <D> * <T>,
              (5) <T>= ><D> / <T>,
              (6) <D> = > function(<E>),
              (7) <D> = > name
              (8) <D> = > (<E>),
              (9) <D> = > const.
       Используя алгоритм рекурсивного спуска для данной грамматики, получим синтаксические деревья для арифметических выражений. Например, для выражения a * (b + c) - x получим следующее синтаксическое дерево (см. рис.15.1):

рис.15.1 Пример синтаксического дерева
       Необходимо отметить, что наличие нескольких узлов <Т> для узла <E> показывает аддитивные составляющие в арифметическом выражении, а наличие нескольких узлов <D> для узла <T> - мультипликативные составляющие. Также легко убедиться, что левосторонний обход синтаксического дерева с записью листьев дает само арифметическое выражение.