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.

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


 

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

35464. Безопасность ИС 978 KB
  Цифровые системы закрытия речи. харки системы Закрытие в аналоговых каналах Аналоговый скремблер ЗС закрытый сигнал ОС открытый сигнал АО аналоговая обработка АПд АПр Аналоговый передатчик приемник Аналоговые скремблеры Аналоговым скремблированием называется преобразование исходного речевого сигнала с целью минимизации признаков речевого сообщения в результате которого этот сигнал становится неразборчивым и неузнаваемым. Цифровые системы связи. В качестве возможных нежелательных воздействий на системы должны рассматриваться: 1.
35465. Реформы Н.С. Хрущёва 30.08 KB
  Многие реформы являлись реакцией на сиюминутную ситуацию и преследовали цель быстро изменить ситуацию к лучшему. Непродуманные, подчас не подкрёпленные необходимыми финансовыми и материальными средствами, новшества просто навязывались сверху. Поэтому проводить подобный курс можно было лишь с использованием старой командно-административной системы управления
35466. Проектирование информационных систем 701 KB
  Суть: описание обработки потоков данных с определением их переходов от функции к функции хранения внешних обменов. Любая реализация накопления и хранения данных. Построение модели: 1 определение общих данных 2 построение контекстной диаграммы м. 4 Описание: составляются спецификации действий и данных.
35467. Основные параметры микропроцессоров. Типы микропроцессоров 130.5 KB
  Дополнительные инструкции в небольших количествах вводились во многих МП 286 486 Pentium Pro и т. Но существенное изменение состава инструкций произошло в МП 386 этот состав далее принят за базовый Pentium MMX Pentium III Pentium 4. отличающиеся от базовой модели разрядностью шин тактовой частотой надежностью работы габаритами потреблением энергии амплитудой напряжения и другими параметрами; микропроцессоры Pentium Pentium II Pentium III имеют много различных модификаций некоторые из них будут названы ниже; число...
35468. Разновидности системных плат 247 KB
  Системные платы Системная или материнская motherboard MB плата это важнейшая часть компьютера содержащая основные электронные компоненты машины. С помощью материнской платы осуществляется взаимодействие между большинством устройств машины. Существует две основные разновидности конструкции системной платы СП: на плате жестко закреплены все необходимые для работы микросхемы сейчас такие платы используются лишь в простейших домашних компьютерах называемых одноплатными; непосредственно на системной плате размещается лишь...
35469. Системы телеобработки данных 51 KB
  Под техническими средствами телеобработки понимается совокупность технических средств системы обеспечивающих ввод данных в систему передачу данных по каналам связи сопряжение каналов связи с компьютером обработку данных и выдачу результатных данных абоненту. Наряду с техническими средствами для осуществления режима телеобработки у компьютера должно иметься и достаточно сложное программное обеспечение выполняющее такие функции как: обеспечение работы компьютера в различных режимах телеобработки; управление сетью телеобработки данных;...
35470. Классификация и архитектура информационно-вычислительных сетей 30 KB
  Основное назначение информационновычислительных сетей ИВС обеспечение эффективного предоставления различных информационновычислительных услуг пользователям сети путем организации удобного и надежного доступа к ресурсам распределенным в этой сети. Эффективность решения указанных задач обеспечивается: распределенными в сети аппаратными программными и информационными ресурсами; дистанционным доступом пользователя к любым видам этих ресурсов; возможным наличием централизованной базы данных наряду с распределенными базами данных; ...
35471. ПРИНЦИПЫ ПОСТРОЕНИЯ ТЕЛЕКОММУНИКАЦИОННЫХ ВЫЧИСЛИТЕЛЬНЫХ СЕТЕЙ (ТВС) 199.5 KB
  Абонентская система AC это совокупность ЭВМ программного обеспечения периферийного оборудования средств связи с коммуникационной подсетью вычислительной сети выполняющих прикладные процессы. Для ТВС принципиальное значение имеют следующие обстоятельства: ЭВМ находящиеся в составе разных абонентских систем одной и той же сети или различных взаимодействующих сетей связываются между собой автоматически в этом заключается основная сущность протекающих в сети процессов; каждая ЭВМ сети должна быть приспособлена как для работы в...
35472. Модель взаимодействия открытых систем 113 KB
  Указанные задачи решаются с помощью системы протоколов и стандартов регламентирующих нормализованные процедуры взаимодействия элементов сети при установлении связи и передаче данных. Протокол это набор правил и методов взаимодействия объектов вычислительной сети охватывающий основные процедуры алгоритмы и форматы взаимодействия обеспечивающие корректность согласования преобразования и передачи данных в сети. Говоря на разных языках люди могут не понимать друг друга также и сети использующие разные протоколы.