20618

Восходящий синтаксический метод

Лекция

Коммуникация, связь, радиоэлектроника и цифровые приборы

Значения атрибутов вычисляются согласно семантическим правилам которые связаны с продукциями грамматики. В этом обобщении с каждым грамматическим символом связываются множество атрибутов. Синтезируемые атрибуты Наследуемые атрибуты каждому символу грамматики можно поставить ряд атрибутов Синтезируемые атрибуты значение вычисляется по значению атрибутов в дочерних по отношению к данному узлу узлах. Наследуемые атрибуты значение определяется значением атрибутов соседних узлов и родительского узла.

Русский

2013-07-31

180.5 KB

0 чел.

Лекция № 4.

Восходящий синтаксический метод.

Произвести разбор 9*(8+5)

1 SE  С4

2 ET  С2

3 TT*F  С1

4 F(E)  С3

5 EE+T  С2

6 TF  С1

7 F0…9

Метод свертки - переноса.

В алгоритме работы используется магазинный автомат со стеком.

На каждом шаге работы сравнивается пара символов:

  •  Текущий символ входящей цепочки (I)
  •  Текущий символ в вершине стека (M)

По результату сравнения возможны следующие действия:

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

Алгоритм работы магазинного автомата записывается в виде таблицы, где по строкам стоит текущий входной символ, а по столбцам символ в стеке и на пересечении их записываются необходимые действия.

В клетках таблицы задаются следующие действия:

  1.  Сообщение об ошибке (-)
  2.  Сообщение об успешном завершении работы (+)
  3.  Перенос символа из входной цепочки в стек (П)
  4.  Свертка (Сn), где n – номер соответствующего правила грамматики.

Ограничимся продукцией F*(F+F) для простоты

     (I)

(M)

+

*

(

)

T

F

E

#

+

-

-

П

-

С2

С1

-

-

*

-

-

П

-

С2

С1

-

-

(

-

-

П

-

С2

С1

П

-

)

П

П

-

С3

-

-

-

П

T

П

П

-

П

-

-

-

С2

F

П

П

-

П

-

-

-

С1

E

П

П

-

С3

-

-

-

С4

#

-

-

П

С3

С2

С1

С4

-

Синтаксически управляемая трансляция

грамматическое правило     семантическое правило

Пример: задана строка (9+2)*3. Построить дерево синтаксического разбора для данной грамматики.

Последовательность синтаксически управляемой трансляции:

Входная строка

Дерево синтаксического разбора

Аннотированное дерево разбора

Граф зависимостей

Порядок выполнения семантических правил

Информация, соответствующая конструкциям языка программирования (грамматическим правилам), связывается с атрибутами грамматических символов представляющих данную конструкцию.

Значения атрибутов вычисляются согласно семантическим правилам, которые связаны с продукциями грамматики.

Существует два вида записей семантических правил:

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

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

Синтаксически управляемые определения - представляют собой обощение контекстно-свободной грамматики.

В этом обобщении с каждым грамматическим символом связываются множество атрибутов.

  1.  Синтезируемые атрибуты

  1.  Наследуемые атрибуты

(каждому символу грамматики можно поставить ряд атрибутов)

Синтезируемые атрибуты – значение вычисляется по значению атрибутов в дочерних по отношению к данному узлу узлах.

Наследуемые атрибуты – значение определяется значением атрибутов соседних узлов и родительского узла.

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

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

Синтаксические определения, которые используют только синтезируемые атрибуты, называются S-атрибутными синтаксическими определениями и используются наиболее часто.

Грамматические правила

Семантические правила

Дерево разбора, показывающее значение атрибутов в каждом узле называется  аннотированным.

Пример: дерево разбора для real id1, id2, id3.

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


 

А также другие работы, которые могут Вас заинтересовать

32653. Анализ эффективности реализации и управления проектом 40 KB
  Анализ эффективности реализации проекта Реализация любого проекта направлена на достижение заранее заданных и четко сформулированных целей и связанных с ними конкретных результатов. В свою очередь планируемый результат является объектом целеполагания проекта. Цели и соответственно результаты проекта могут быть экономическими например получение прибыли снижение себестоимости продукции достижение определенного уровня эффективности работ повышение конкурентоспособности продукции социальноэкономическими создание новых рабочих мест рост...
32654. Место и роль управления проектами в современной теории управления. Сущность проектного и процессного подходов 35 KB
  Роль управления проектами в современном мире. Эти средства активно применяются не только для управления федеральными проектами и программами но и для осуществления управленческих функций внутри правительственного аппарата. В России же где организационная система и методы управления гораздо слабее чем на Западе эффект от внедрения УП окажется еще более значительным.
32655. Основные признаки, понятия и характеристики проекта 30 KB
  Основные признаки понятия и характеристики проекта. Но цели проекта ограничены во времени. При успешном завершении проекта целевая установка данная руководителю проекта заказчиком отпадает. Признак изменения Этот признак является наиболее важной характеристикой проекта так как осуществление проекта всегда несет изменения вещественной системы или предметной области в которой реализуется проект.
32656. Особенности управления программами и портфелями проектов 40.5 KB
  Особенности управления программами и портфелями проектов. При определенных условиях множество взаимосвязанных проектов объединяются в программу. Программа может быть сформулирована в терминах проектов и представлена как совокупность проектов объединенных общей целью выделенными ресурсами временем на ее выполнение технологией организацией и др. В дальнейшем мы будем рассматривать программы как совокупность проектов.
32657. Классификация проектов и программ 28 KB
  в которых осуществляется проект: социальные проекты экономические проекты организационные проекты технические проекты смешанные проекты. Сложные проекты включающие подпроекты и элементы различных типов проектов. Вид проекта: По характеру предметной области проекта: учебнообразовательные проекты; проекты исследования и развития; инновационные проекты.; инвестиционные проекты.
32658. Понятие о декомпозиции работ по проекту. Критерии выбора эффективной декомпозиции работ 46 KB
  Понятие о декомпозиции работ по проекту. Критерии выбора эффективной декомпозиции работ. Структура разбиения декомпозиции работ WBS Work Brekdown Structure иерархическая структура последовательной декомпозиции проекта на подпроекты пакеты работ различного уровня пакеты детальных работ. СРР является базовым средством для создания системы управления проектом так как позволяет решать проблемы организации работ распределения ответственности оценки стоимости создания системы отчетности эффективно поддерживать процедуры сбора...
32659. Типы структурных моделей проекта 202 KB
  Типы структурных моделей проекта. Типы структурных моделей проектов Типы структурных моделей проекта. Структурная модель проекта и принцип структуризации широко используются для построена и других структурных моделей применяемых в управлении проектом. Отметим наиболее существенные из них: Дерево целей и результатов первая по времени разработки структурная модель декомпозиции цели проекта на составные части.
32660. Жизненные циклы проекта и продукта 26.5 KB
  Жизненные циклы проекта и продукта. Жизненный цикл проекта совокупность последовательных фаз развития проекта и изобразить его концептуальную схему. Наиболее традиционным является разбиение проекта на четыре крупных этапа: определение проекта концепция разработка реализация и завершение. Определение проекта по существу подразумевает функцию выбора проекта.
32661. Участники проекта и их роль в обеспечении успеха проекта 31 KB
  Участники проекта и их роль в обеспечении успеха проекта. В настоящем разделе работы рассматривается состав участников проекта их роли и взаимосвязи распределение функций и ответственности. Главный участник Заказчик будущий владелец и пользователь результатов проекта. При этом заказчиком может быть как одна единственная организация так и несколько организаций объединивших свои усилия интересы и капиталы для реализации проекта и использования его результатов.