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.

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


 

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

16589. Митоз в клетках корешков лука 382 KB
  Лабораторная работа № 4 Тема: Митоз в клетках корешков лука Цель работы: выявить отличительные особенности стадий митотического деления клеток. Оборудование: микроскоп спиртовка микропрепарат Митоз в клетках корешков лукафильтровальная бумагапрепарова
16590. Изучение приспособленности организмов к среде обитания 394.5 KB
  Лабораторная работа № 7 Тема: Изучение приспособленности организмов к среде обитания Цель: выяснить механизм образования приспособлений к среде обитания и их относительный характер сделать вывод о том что приспособленность результат действия естественного о
16591. Каталитическая активность ферментов в живых клетках 38 KB
  Лабораторная работа № 9 Тема: Каталитическая активность ферментов в живых клетках Цель: выявить каталитическую функцию белков в живых клетках сформировать знания о роли ферментов в клетках закрепить умение работать с микроскопом проводить опыты и объяснять резу...
16592. Изучение фенотипов местных сортов растений 55.5 KB
  Лабораторная работа № 12 Тема: Изучение фенотипов местных сортов растений Цель: расширить знания о задачах современной селекции. Оборудование: пакетики семян различных сортов томатов два экземпляра натуральных или гербарных образцов злаковых растений одного ...
16593. Сравнение строения тканей многоклеточных организмов (на примере: растений, грибов, животных и человека).Типы тканей и их функции 1.21 MB
  Лабораторная работа № 3 Тема: Сравнение строения тканей многоклеточных организмов на примере: растений грибов животных и человека.Типы тканей и их функции. Ткань это группа клеток и межклеточное вещество объединенные общим строением функцией и происхождение...
16594. Строение половых клеток. Изучение мейоза в пыльниках цветковых растений 697.5 KB
  Лабораторная работа № 5 Тема: Строение половых клеток. Изучение мейоза в пыльниках цветковых растений. Цель работы: выявить отличительные особенности строения половых клеток. Увидеть на препаратах процесс деления наследственного материала хромосом во время фор
16595. СОВРЕМЕННЫЕ МОЛОДЕЖНЫЕ ПРОГРАММЫ НА ТЕЛЕВИДЕНИИ КРАСНОДАРСКОГО КРАЯ: ПОИСК ОПТИМАЛЬНОЙ МОДЕЛИ 1.79 MB
  Термином «молодежные программы» часто определяются передачи, предназначенные для молодежной аудитории. Но для того, чтобы понять реальные телеинтересы и телепотребности нынешних молодых телезрителей, попробуем разобраться в особенностях молодежной аудитории
16596. Определение ароморфозов и идиоадаптаций в эволюции растений и животных 101.5 KB
  Лабораторная работа № 8 Тема: Определение ароморфозов и идиоадаптаций в эволюции растений и животных Цель: выявить ароморфозы и идиоадаптации у растений Оборудование: гербарные растения чучела хордовых рыб земноводных птиц пресмыкающихся млекопитающих...
16597. Многооконный интерфейс. Управление объектами с помощью клавиш 136 KB
  Лабораторная работа 1 Многооконный интерфейс. Управление объектами с помощью клавиш. Цель работы: Создать программу которая позволяет пользователю управлять объектом с помощью стрелок на клавиатуре а также позволяет менять цвет этого объекта посредством выбора цве