Математическая логика и теория алгоритмов. Стенюшкина В.А. - 106 стр.

ным, динамическая – ее логика изменения транслятору не известна. Кроме об-
ластей для хранения значений локальных и промежуточных переменных,
транслятор должен выделить ячейки для сохранения состояния вычислительно-
го процесса процедур, для приема значений фактических параметров, решать
многие другие вопросы.

      6.11 Операторные грамматики

     Контекстно свободные грамматики включают в себя так называемые опе-
раторные грамматики /10/. Правила этих грамматик таковы, что никакие два
нетерминала не являются смежными в правой части. В этом случае лежащий
между ними терминал можно представить как оператор. Рассмотрим частный
случай операторных грамматик – грамматику операторного предшествования
(ГОП).
       Определим правила:
       a≈b, если A→αaβbγ∈P; здесь α,γ∈V* и β∈N∪{λ};
       a≺ b, если A→ αaBβ∈P; здесь B ⇒+γbδ, γ∈N∪{Λ} и α,β,δ∈V*;
      a>b, если A→ αBbβ∈P; здесь B ⇒+γaδ, δ∈N∪{Λ} и α,β,γ ∈V*;
      ├ a, если S ⇒+αaβ, α∈N∪{Λ}, β∈V*;
      a≻ ┤, если S ⇒+αaβ, β∈N∪{Λ}, α∈V*.
      Здесь символы ≺ , ≈ и ≻ обозначают отношения предшествования:
«имеет меньшее старшинство», «имеет равное старшинство» и «имеет большее
старшинство» соответственно. Сами отношения определяются на множестве
T∪{├, ┤}, где и - новые символы, ограничивающие предложения.
      Пример - E→E+T T, T→T*P P, P→(E) x. Для этой грамматики отно-
шения предшествования соответствуют таблице

      Таблица

              +       *        (        )       x        ┤
     ├        ≺       ≺        ≺                ≺
     +        ≻       ≺        ≺        ≻       ≺        ≻
     *        ≻       ≻        ≺        ≻       ≺        ≻
     (        ≺       ≺        ≺        ≈       ≺
     )        ≻       ≻                 ≻                ≻
     x        ≻       ≻                 ≻                ≻

       Построим вывод предложения ├ x*(x+x) ┤ в этой ГОП. Заменяя x целы-
ми числами, 2, 3, 4, получаем ├2*(3+4) ┤. Записывая отношения предшество-
вания под этим выражением, замечаем , как определяется порядок вычислений.
       ├ 2 *;
        ≺    ≻ ;