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.

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


 

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

12214. Измерение электропроводности электролитов различной концентрации и определение температурного коэффициента электропроводности 230.5 KB
  Измерение электропроводности электролитов различной концентрации и определение температурного коэффициента электропроводности Цель работы: установить зависимость удельной и эквивалентной электропроводности электролита от концентрации и температуры. Определить т
12215. Определение константы скорости инверсии тростникового сахара (сахарозы) 185.5 KB
  Лабораторная работа: Определение константы скорости инверсии тростникового сахара сахарозы Цель работы: Ознакомиться с оптическим методом изучения кинетики реакции; определить порядок реакции по сахару и катализатору; определить средние константы скор
12216. Йодирование ацетона в кислой среде 33.62 KB
  Лабораторная работа №4 Йодирование ацетона в кислой среде. Цель работы: исследование кинетики реакции йодирования ацетона в кислой среде – определение порядка реакции константы скорости реакции. Кинетические эксперименты позволя
12217. Определение чисел переноса в растворе серной кислоты 103 KB
  Определение чисел переноса в растворе серной кислоты. Какие процессы протекают на инертных электродах при электролизе раствора H2SO4 Что называют числом переноса и от каких факторов оно зависит Число переноса ионного компонента ti число граммэкв
12218. Определение электропроводности растворов различных концентраций и температурной зависимости константы диссоциации слабого электролита 35.5 KB
  Лабораторная работа Определение электропроводности растворов различных концентраций и температурной зависимости константы диссоциации слабого электролита. Цель: Определить Кд уксусной кислоты и изучить зависимость от температуры. Суть метода: Определение элект...
12219. Определение порядка реакции окисления йодид-ионов ионами трёхвалентного железа 92 KB
  Лабораторная работа №1 Определение порядка реакции окисления йодидионов ионами трёхвалентного железа. выполнил студент 3 курса 7 группы Криштафович А.В. Цель работы: определить частные порядки и общий кинетический порядок реакции 2Fe3 2I → 2Fe2 I2 в водном растворе...
12220. Кинетика каталитического разложения перекиси водорода 293 KB
  Лабораторная работа №2 Кинетика каталитического разложения перекиси водорода. выполнил студент 3 курса 7 группы Криштафович А.В. Цель работы: Определить порядок реакции константы скорости при двух температурах и вычислить энергию активации каталитического разл
12221. Оптический метод изучения кинетики реакции тростникового сахара (сахарозы) 95 KB
  В молекулах всех трёх сахаров содержатся ассиметрические атомы углерода, что делает эти вещества оптически активными. Водный раствор сахарозы вращает плоскость полимеризации проходящего света вправо, ратвор продуктов реакции влево
12222. Иодирование ацетона в кислой среде 164 KB
  Лабораторная работа №4 Иодирование ацетона в кислой среде. Цель работы: исследование кинетики реакции иодирования ацетона в кислой среде – определение порядка реакции константы скорости и энергии активации. Ход работы: Основная реакция: протекает в 2 с