Алгоритм рекурсивного спуска. 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Алгоритм рекурсивного спуска.



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

Тело программы – обработчика строится по правой части и вызывается по средствам вызова обработчика.

 

Пример:

 

Обработчик Р

Обработчик S

Если текущий символ =., то выход

Иначе

Если текущий символ =;, то Обработчик Р

Иначе ошибка

Условимся, что у нас есть некоторая процедура, которая строит дерево.

 

Программа «Дерево»

 

r1

 

 

r2 r3 r4 r1=Дерево(r2,r3,r4)

 

 

Усовершенствованный вариант обработчика Р, с построением дерева. На выходе будет выходной параметр.

 

Обр.Р(var r) var-т.к.выходной параметр;

Обр.S(r1) r1-выходной показатель;

Если текущий символ=. то r=Дерево(r1,”.”);

Выход

Иначе, если текущий символ=; то Обр.Р(r2);

r=Дерево(r1,”;”,r2);

Выход

Иначе ОШИБКА

 

 

2. Семантика языков программирования.

Понятия:

1. Перевод с одного формата языка на другой.

2. Схема синтаксически управляемого (СУ) перевода.

3. Атрибутная грамматика, как результат обобщения схем синтаксически управляемого (СУ) перевода.

 

 

2 класса:

Интерпретирующая семантика.

Компилирующая семантика.

Интерпретирующая семантика – это некоторая функция, которая любую программу/набор данных отображает в виде результата:

 

Компилирующая семантика:

Интерпретирующую семантику задает интерпретатор.

 

 

 
 

 

 


ПОЛИЗ(польс.инверсная запись)

Триады

Системы внутреннего Ассемблер

представления

 

Семантика лексических единиц.

Таблица символов.

Лексическая единица Тип лекс.един. Числовой тип Кол-во Измерений Размер Кол-во байт Всего байт Адрес
a Ид. Int           .
b Ид. Real           .
0,5 Const real           .

 

 
 
 
 

 

Память

Формальные системы для внутреннего (промежуточного)

Представления программ.

Триады – набор из 5 операций:

 

Последовательность триад

 

Адрес метки для перехода kon A b c
  + A b C
  br - N -
  cbr P N -
  cbm A N b

 

 

Kon – код операции;

C:=a+b

-*/v&

1-й,3-й не используются, а в «b» стоит метка N.

 

 

Системы перевода формальных языков.

Входной язык Выходной язык

(вводим на входе) (получаем на выход.яз.)

 

Это перевод с одного формального языка на другой формальный язык.

 

Типы перевода:

1. Гомоморфизм – некоторое отображение, сохраняющее алгебраическую операцию.

 

В нашем случае конкатенацию.

 

 

Вх.строка вых.строка

 

 

2. Схемы синтаксически управляемого переводов.

(СУ схемы).

 

 

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

 

 

Входное правило Выходное правило

E→T T

E→E+T ET+

T→M M

T→T*M TM*

M→a a

M→(E) E

 

Это СУ схема с 2-мя правилами: входное и выходное.

 

Пример, как работает эта схема:

 

 

E E

T T

T * M T M *

M C

() M C

E E

E T E +

+ T

T M T M

 

M b M b

 

a a

 

 

Как хранится у нас это входное дерево:

 

E→T E→T

T→T*M T→TM*

T→M T→M

M→(E) M→E

E→E+T E→ET+

E→T E→T

T→M T→M

M→a M→a

T→M T→M

M→b M→b

M→c M→c

 

Эта схема называется простой схемой СУ перевода. Простые СУ переводы – это подкласс СУ перевода.

Особенностью простых СУ схем является то, что в выходном правиле нетерминалы следуют в том же порядке, что и во входном.

 

 



Поделиться:


Последнее изменение этой страницы: 2017-02-07; просмотров: 138; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.94.150.98 (0.022 с.)