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.

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


 

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

48723. ИССЛЕДОВАНИЕ АКТИВНОГО RC-ФИЛЬТРА 695 KB
  ФАКУЛЬТЕТ РАДОИСВЯЗИ РАДИОВЕЩАНИЯ И ТЕЛЕВИДЕНИЯ Курсовая работа на тему: ИССЛЕДОВАНИЕ АКТИВНОГО RCФИЛЬТРА Выполнил студент группы Проверила: Чечулина Людмила Александровна СанктПетербург 2003 Содержание Нахождение операторной передаточной АЧХ ФЧХ характеристик первого звена .5 Таблица значений АЧХ ФЧХ обоих звеньев и всего фильтра а также их графики . Нахождение переходной характеристики для первого звена фильтра 8 5. Проверка устойчивости фильтра по расположению...
48724. Нахождение операторной передаточной характеристики ARC звена 1.07 MB
  Нахождение операторной передаточной характеристики RC звена ; кОм; Ф; Ом; Ом; т. n=3 Схема ФПНЧ ; ; ; Передаточная функция полиномиального низкочастотного фильтрапрототипа: ; Преобразуем схему ФПНЧ в схему проектируемого фильтра: Ом; Ф Гн; Ф Гн; Ф Гн Расчет передаточной функции проектируемого...
48725. Cложная система с использованием объектно-ориентированного подхода 172.5 KB
  Моделирование поведения стада животных. На территории леса в хаотичном порядке расположены деревья и животные. На одном из краёв леса находится корм для животных. Во время движения на животных действуют два стимула: достижение корма и стремление быть близко друг к другу.
48726. Основы хирургии нарушений венозного и лимфатического кровотока. ЯЗВЫ. СВИЩИ 664 KB
  Заболеваниями венозной и лимфатической систем страдают 35 млн. человек. У 15% из них имеются декомпенсированные формы заболеваний, требующие оперативного лечения. Материальные затраты на лечение этих заболеваний огромны и достигают в промышленно развитых странах
48727. Анализ и диагностика финансово-хозяйственной деятельности предприятии ОАО «КБ «Вымпел» и оценки эффективности его работы в условиях рыночной экономики 123.96 KB
  Содержанием АФХД является глубокое и всестороннее изучение экономической информации о функционировании анализируемого субъекта хозяйствования с целью принятия оптимальных управленческих решений по обеспечению выполнения производственных программ предприятия, оценки уровня их выполнения, выявления слабых мест и внутрихозяйственных резервов.
48728. Принципы организации производственного процесса 68.92 KB
  Главной задачей, стоящей перед работниками остается своевременное, качественное и полное удовлетворение народного хозяйства и населения в перевозках и повышение экономической эффективности работы отрасли.
48729. Історія України. НАВЧАЛЬНО-МЕТОДИЧНИЙ ПОСІБНИК 482.09 KB
  Вивчення історії України має не тільки пізнавальне, а й виховне значення, в якому закладено глибокий гуманістичний зміст. Зокрема, одним із головних завдань викладання вітчизняної історії є виховання у студентської молоді почуття патріотизму, громадянської свідомості, виховання майбутніх спеціалістів, яким належить утверджувати державність України.