Генерация дерева синтаксического анализа
Одно и то же арифметическое выражение может быть записано тремя способами:
-
Инфиксный способ записи (знак операции находится между операндами):
((a / (b + c)) + (x * (y - z)))
Все арифметические операции, привычные нам со школьных лет, записываются именно таким образом.
-
Префиксный способ записи (знак операции находится перед операндами):
+( /(a, +(b,c)), *(x, -(y,z)))
Из знакомых всем нам функций префиксный способ записи используется, например, для sin(x), tg(x), f(x,y,z) и т.п.
-
Постфиксный способ записи (знак операции находится после операндов):
((a,(b,c)+ )/ ,(x,(y,z)- )* )+
Этот способ записи менее распространен, однако и с ним многим из нас приходилось сталкиваться уже в школе: примером будет n! (факториал).
Разумеется, вид дерева синтаксического анализа (ДСА)1) арифметического выражения не зависит от способа записи этого выражения (см. рис. 12.1), поскольку определяет его не форма записи, а порядок выполнения операций. Но процесс построения дерева, конечно же, зависит от способа записи выражения. Далее мы разберем все три варианта алгоритма построения ДСА.
Рис. 12.1. Дерево синтаксического анализа и способ описания его элементов
type ukaz = ^tree; tree = record symbol: char; left: ukaz; right: ukaz; end;
