part411

Пред. страница . След. страница Раздел Содержание

4.3. Бесскобочные выражения

Обычные арифметические выражения, используемые в повседневной практике и содержащие скобки называют инфиксными выражениями, поскольку знак операции располагается между операндами. Порядок выполнения действий в таких выражениях определяется старшинством опреаций и скобками. Вычисление и компиляция таких выражений подразумевает их предварительный анализ с целью выявления порядка выполнения операций. Существуют формы записи арифметических выражений без скобок, в которых порядок действий задается порядком знаков операций в выражении. Такие формы записи называются польской или бесскобочной записью. Польская запись может быть префиксной, в которой знак операции предшествует операндам, и постфиксной, в которой знак операции следует за операндом. Вычисление и компиляция бесскобочных выражений оказывается проще, чем выражений со скобками, поскольку операции должны выполняться в порядке описания и предварительный анализ не требуется.

4.3.1. Префиксная польская запись.

Определение. Префиксную польскую запись (ПрПЗ) определим так:
1) Если инфиксное выражение Е представляет собой один операнд а, то
ПрПЗ выражение Е - это просто а.
2) Если инфиксное выражение Е₁*Е₂, где * - знак операции,а Е₁ и Е₂
инфиксные выражения для операндов, то ПрПЗ этого выражения - это
*Е₁'E₂',где E₁', E₂' - ПрПЗ выражений Е₁ и Е₂.
3) Если (Е) есть инфиксное выражение, то ПрПЗ этого выражения есть
ПрПЗ Е.

Это определение определяет порядок построения ПрПЗ заданного инфиксного выражения.
Например для выражений (a + b) * (c - d) построение ПрПЗ можно выполнить так. Обозначим операнды первой выполняемой операции:

E₁ = (a + b) и E₂ = (c - d).

Согласно определению префиксная запись выражения Е₁*Е₂ - это *E₁'E₂', где Е₁',Е₂' -префиксные записи выражений Е₁ и Е₂. Выполняя построение постфиксных записей для этих выражений,

E₁' = +ab, E₂' = -cd,

окончательно получаем результат в виде :

*+ab-cd

4.3.2. Вычисление префиксных польских записей.

Вычисление ПрПЗ можно представить следующим образом:
1. Просматриваем выражение слева направо, пока не найдем знак операции, за которым
следуют два операнда.
2. Выполняем операцию и результат записываем на место выбранной тройки.
3. Повторяем пункт (1), пока не получим вместо выражения один результат.
Вычисление построчного префиксного выражения можно представить в следующем виде:

1. *+ab-cd
2. *R₁-cd
3. *R₁R₂
4. R₃

Приведенные правила вычисления префиксных записей достаточно просты, однако, вычисление таких выражений на практике реализуется обычно с использованием магазина. Вычисление ПрПЗ с использованием магазина выполняется следующим образом.

1. Прочитать очередной символ входной цепочки.

2. Если входной символ - оператор, то занести его в магазин
безусловно.

3. Если входной символ - операнд, то выполняемые действия
зависят от того какой символ находится в вершине магазина:

a) Если в вершине находится оператор, то выполнить
запись в магазин.

б) Если в вершине находится операнд, то выполнить
    чтение операнда и следующего за ним оператора,
    а затем выполнить операцию и повторить п.3 - проверку
    символа в вершине магазина.

4. Повторить п.1 пока не будут прочитаны все символы
входной цепочки.

Порядок вычислений префиксных выражений покажем на
примере входной цепочки *+ab-cd в виде следующей схемы:

Вход Магазин Операция

1. *+ab-cd h_о

2. +ab-cd h_о*

3. ab-cd h_о*+

4. b-cd h_о*+a

5. -cd h_о*R₁ a+b=R₁

6. cd h_о*R₁-

7. d h_о*R₁-c

8. $ h_о*R₁ c-d=R₂, R₁*R₂=R₃

h_оR₃

4.3.3. Постфиксная польская запись.

Определение. Постфиксную польскую запись (ПоПЗ) определим так:
     1. Если инфиксное выражение Е представляет собой один операнд а, то ПоПЗ выражения Е - это а.
     2. Если инфиксное выражение Е₁*Е₂, где * - знак операции, E₁, E₂ - инфиксные выражения для операндов, то ПоПЗ этого выражения это - Е₁'E₂'*, где Е₁',E₂' - постфиксные выражения Е₁,Е₂.
    3. Если (Е) есть инфиксное выражение, то постфиксная   запись этого выражения есть постфиксная запись Е.

Аналогично предыдущему примеру построим ПоПЗ выражения

(a + b) * (c - d).

Обозначая операнды внешней операции

E₁ = (a + b) и E₂ = (c - d),

найдем постфиксные записи операндов, которые имеют вид:

E₁' = ab+ и E₂' = cd-.

Подставляя полученные постфиксные записи в выражение

E₁'E₂'*,

окончательно получаем :

ab+cd-* .

4.3.4. Вычисление постфиксных польских записей

Вычисление постфиксной записи выражения можно представить следующим образом.
1. Просматриваем выражение слева направо пока не найдем два стоящих рядом операнда, за
которыми следует знак операции.
2. Выполняем операцию и записываем результат вместо выбранных операндов и операций.
3. Повторяем пункт (1) пока не получим вместо выражения единственный результат.
Вычисление построенного постфиксного выражения можно представить в следующем виде:

1. ab+cd-*

2. R₁cd-*

3. R₁R₂*

4. R₃

На практике вычисление постфиксных выражений реализуется с применением магазина. В этом случае вычисления выполняются по следующим правилам.
1. Прочитать очередной символ входной цепочки.
2. Если входной символ - операнд, то выполнить его запись   в магазин.
3. Если входной символ - оператор,то прочитать два операнда из магазина, выполнить
    операцию и результат занести в магазин   как операнд.
4. Повторять п.1, пока во входной цепочке не будут прочитаны все символы.
Последовательность вычислений продемонстрируем на примере входной цепочки
                                                            ab+cd-*
и изобразим ее в виде следующей схемы:

Вход Магазин Операция

        ab+cd-*
1.     b+cd-*                    a
2.     +cd-*                      ab
3.     cd-*                        R₁                             a+b=R₁
4.     d-*                          R₁c
5.     -*                            R₁cd
6.      *                            R₁R₂                        c-d = R₂
7.      $                            R₃                          R₁*R₂= R₃

4.3.5. Примеры постфиксных польских записей.

Польские постфиксные записи часто используют в качестве промежуточного представления операторов языков программаирования на этапе синтаксического анализа при компиляции. В качестве примеров такого применения приведем постфиксные выражения для некоторых
операторов Паскаля.
Знак присваивания можно рассматривать как символ операции, поэтому оператор присваивания:

<I> := <E>,

где I-идентификатор, а Е- арифметическое выражение, можно записать в виде
постфиксного выражения

<I><E>':= ,

где E'- постфиксная запись выражения Е .
Для описания построения записи конструкции с условием требуется введение новых элементов: метки и операторов условного и безусловного переходов.
Условимся для обозначения меток в постфиксных выражениях использовать идентификаторы М,М₁,М₂,...,а для обозначения переходов воспользуемся операторами Условный Переход
по значению Ложь (УПЛ) и Безусловный Переход (БП). Операндами этих операторов являются метки.
Первый оператор выполняет переход к метке, если значение выражения, предшествующего этому оператору, ложно. Если же значение выражения, предшествующего оператору УПЛ, истинно, то оператор пропускается и выполняется оператор, расположенный непосредственно за УПЛ.
Результатом оператора безусловного перехода с меткой М является то, что следующим выполняется оператор из рассматриваемой последовательности, помеченный М.
Для постфиксного представления простого условного оператора

IF <R> THEN <S> ,

где <R> - отношение, а <S> - оператор , воспользуемся условным оператором перехода.
В результате получаем выражение:

<R'>M УПЛ <S'>M ,

в котором <R'> и <S'> являются постфиксными выражениями соответствующего выражения и оператора, а М - метка. Опреатор <S'> в этом выражении также как и в заданном
условном операторе выполняется только в том случае, когда отношение <R'> - истино.
Для полного условного оператора

IF <R> THEN <S₁>ELSE <S₂>,

где<R> - отношение, а <S₁>,<S₂ >- операторы, постфиксное представление должно обеспечивать выполнение одного из операторов <S₁>или <S₂>в зависимости от условия <R>.
Исходя из этого положения, постфиксную форму полного условного оператора можно записать так:

<R'> M₁ УПЛ <S₁'> M₂ БП М₁ <S₂'> M₂ ,

где <R'> - постфиксная запись отношения <R>, <S₁'> и <S₂'>- постфиксные записи операторов <S₁>,<S₂>, а М₁ и М₂ - метки.

4.3.6. Примеры СУ - схем.

Описанные способы задания перевода в основном используются при построении компиляторов.
Они являются основой для проектирования лексических и синтаксических анализаторов. Чтобы показать, как описание перевода может быть использовано применительно к языкам программирования, приведем несколько СУ - схем, задающих перевод последовательности операторов или отдельных опреаторов в польскую запись.
Правила СУ - схемы Т₅, изображенные ниже, определяют перевод последовательности операторов присваивания, разделенных точкой с запятой, в последовательность постфиксных записей. В правой части каждого оператора присваивания может находиться инфиксное арифметическое выражение без скобок, в котором могут быть использованы знаки сложения и умножения. Начальным символом СУ - схемы является U, а терминальный символ i используется для обозначения идентификатора.

Т₄_.5: Q = { <U> ╝ <A₂>. , < A₂>{.};
                    < A₂ >╝ <S>< R₂ > , <S>< R₂ >;
                     <R₂ >╝ ;<S>< R₂ >, {; }<S>< R₂ >;
                     <R₂ >╝ $ , $ ;
                     <S >╝ i <B₂ >, {i}<B₂ >;
                     <B₂ >╝ :=<H> , < H>{:=}
                     <H >╝ i <R> , {i}<R>;
                     <R> ╝ +i <R> , {i}{+}<R>;
                     <R> ╝ *i <R> , {i}{*}<R>;
                     <R> ╝ $ , $
                  }.

Правила СУ - схемы, описывающей перевод условных операторов в постфиксную форму записи имеет вид:

Т₄_.6: Q = {    <R₄ >╝ i <R₃ > , {i}<R₃ >;
                        <R₃ >╝ <i , {<}{i} ;
                         <R₃ >╝ =i , {=}{i} ;
                          <V> ╝ .IF.<R₄ ><C₂ > , <R₄ ><C₂ >;
                          <C₂ >╝ .THEN.<S>< C₃ > , {M₁}{УПЛ}<S>< C₃ >;
                          <C₃ >╝ .ELSE.<S>,   {M₂}{M₁}{БП}<S>{M₂};
                          <C₃ >╝ $ , {M₁}}.

Схема построена, исходя из допущения о том, что в качестве отношения <R₄> и условном операторе могут быть использованы выражения, состоящие из двух идентификаторов, разделяемых знаками меньше или равенства. В схеме символы М₁ и М₂ обозначают метки,
а УПЛ и БП - команды перехода.
Правила СУ - схем, задающих перевод двух операторов цикла языка Паскаль в постфиксную форму записи, можно записать так:

Т₄_.7: Q = { <W> ╝ WHILE <R₄ ><C₄ >, {M₁}<R₄>{M₂}{УПЛ}<C₄ >
<C₄ >╝ DO <S> , < S>{M₁}{БП}{M₂} }.

T_4.8: Q = {<W₁>╝ REPEAT <S> <C₅ >, {M₁}<S>< C₅ >
<C₅ >╝ UNTIL <R₄ >, <R₄>{M₁}{УПЛ} }.

В последних двух СУ - схемах <R₄ >обозначает отношение, определенное в СУ - схеме Т₄_.6, а <S> -оператор присваивания, определение которого дано в Т_4.5.

Пред. страница . След. страница Раздел Содержание