Генерация дерева синтаксического анализа

Одно и то же арифметическое выражение может быть записано тремя способами:

1. Инфиксный способ записи (знак операции находится между операндами):

((a / (b + c)) + (x * (y - z)))

Все арифметические операции, привычные нам со школьных лет, записываются именно таким образом.

2. Префиксный способ записи (знак операции находится перед операндами):

+(/(a, +(b,c)), *(x, -(y,z)))

Из знакомых всем нам функций префиксный способ записи используется, например, для sin(x), tg(x), f(x,y,z) и т.п.

3. Постфиксный способ записи (знак операции находится после операндов):

((a,(b,c)+)/,(x,(y,z)-)*)+

Этот способ записи менее распространен, однако и с ним многим из нас приходилось сталкиваться уже в школе: примером будет n! (факториал).

Разумеется, вид дерева синтаксического анализа (ДСА)¹⁾ арифметического выражения не зависит от способа записи этого выражения (см. рис. 12.1), поскольку определяет его не форма записи, а порядок выполнения операций. Но процесс построения дерева, конечно же, зависит от способа записи выражения. Далее мы разберем все три варианта алгоритма построения ДСА.

Рис. 12.1. Дерево синтаксического анализа и способ описания его элементов

type ukaz = ^tree; tree = record symbol: char; left: ukaz; right: ukaz; end;

Дата добавления: 2014-01-03