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.

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


 

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

29160. Удержание в гражданском праве 22 KB
  Кредитор у которого находится вещь подлежащая передаче должнику либо лицу указанному должником вправе в случае неисполнения должником в срок обязательства по оплате этой вещи или возмещению кредитору связанных с нею издержек и других убытков удерживать ее до тех пор пока соответствующее обязательство не будет исполнено. Требования кредитора удерживающего вещь удовлетворяются из ее стоимости в объеме и порядке предусмотренном законом для удовлетворения требований обеспеченных залогом. Кредитор может удерживать находящуюся у него вещь...
29161. Перемена лиц в обязательстве 32.5 KB
  Особенности: Перемена лиц в обязательстве не оказывает никакого влияния на надлежащее исполнение обязательств кредитору все равно кто ответит по обязательствам Изменение стороны может быть в силу закона наследования; страховщику прав кредитора к должнику ответственному за наступление страхового случая и договора. Существуют 2 формы перемены лиц в обязательстве: Уступка право требования цессия Для перехода к другому лицу прав кредитора согласия должника как правило не требуется. Перевод долга соглашение между кредитором...
29162. Уступка права требования 26 KB
  Уступка права требования Уступка требования кредитором другому лицу допускается если она не противоречит закону иным правовым актам или договору. Уступка требования основанного: на сделке совершенной в простой письменной или нотариальной форме должна быть совершена в соответствующей письменной форме. Первоначальный кредитор уступивший требование отвечает перед новым кредитором за недействительность переданного ему требования но не отвечает за неисполнение этого требования должником кроме случая когда первоначальный кредитор принял на...
29165. Ответственность за неисполнение денежного обязательства 26 KB
  Размер процентов определяется существующей в месте жительства кредитора а если кредитором является юридическое лицо в месте его нахождения учетной ставкой банковского процента на день исполнения денежного обязательства или его соответствующей части. При взыскании долга в судебном порядке суд может удовлетворить требование кредитора исходя из учетной ставки банковского процента на день предъявления иска или на день вынесения решения. Проценты за пользование чужими средствами взимаются по день уплаты суммы этих средств кредитору если...
29166. Общая характеристика оснований прекращения обязательств 24 KB
  Обязательство прекращается полностью или частично по основаниям: Надлежащее исполнение кредитор принимая исполнение обязан по требованию должника выдать ему расписку в получении исполнения полностью или в соответствующей части акт выполненных работ. Отступное по соглашению сторон обязательство может быть прекращено предоставлением взамен исполнения отступного уплатой денег передачей имущества. Зачет Обязательство прекращается полностью или частично зачетом встречного однородного требования срок которого наступил либо срок...
29168. Судебная баллистика 52.5 KB
  Судебная баллистика – это отрасль криминалистической техники, изучающая огнестрельное оружие и боеприпасы, следы их применения, а также разрабатывающая приёмы и методы обнаружения, собирания и исследования этих объектов с целью решения вопросов установления истины по делу, решения вопросов и задач расследования