Программирование на языке Pascal

       

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


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

  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! (факториал).

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


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

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



Содержание раздела