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.

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


 

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

19926. Персонал предприятия (ПП) 22.01 KB
  Лекция №9 Тема: персонал предприятия ПП. Вопросы: Состав и структура ПП Планирование и подбор кадров Производительность труда Заработная плата тарифная система формы и системы оплаты труда. Формирования фонда зарплаты фонды оплаты труда ФОТ. ...
19927. Персонал предприятия. Движения рабочей силы 27.82 KB
  Лекция №10 Тема: Персонал предприятия. Для учета и отчетности пользуются абсолютными и средними показателями численности. К абсолютным относятся: Списочная численность работников. Это количество всех работающих принятых на постоянную сезонную или временную раб
19928. Персонал предприятия. Уровни производительности труда 24.86 KB
  Лекция №11 Тема: персонал. При изучении уровней производительности труда используют: Среднечасовая выработка рабочего . 1 Среднедневная выработка рабочего 2 . 3 Факторы нарушения производительности труда – самостоятельно. Заработная плата тари...
19929. Формирование фонда оплаты труда 20.9 KB
  Лекция №11 Тема: Формирование фонда оплаты труда. Фонд ОЗП основной заработной платы включает вознаграждения за выполненную работу в соответствии с установленными нормами труда должностной оклад. Фонд дополнительной ЗП – включает доплаты надбавки гарантийные и к...
19930. СОЦІОЛОГІЯ – НАУКА ПРО СУСПІЛЬСТВО 104.5 KB
  ЛЕКЦІЯ 1 СОЦІОЛОГІЯ – НАУКА ПРО СУСПІЛЬСТВО П Л А Н Виникнення та становлення соціології як самостійної науки. Предмет об’єкт функції та структура соціології. Соціологічні закони та категорії. Метод соціології. Взаємозв'язок соціології з іншими науками...
19931. ТЕОРІЯ СОЦІАЛЬНОЇ СТРУКТУРИ СУСПІЛЬСТВА 472 KB
  ЛЕКЦІЯ 3 ТЕОРІЯ СОЦІАЛЬНОЇ СТРУКТУРИ СУСПІЛЬСТВА П Л А Н Поняття соціальної структури її роль та місце в житті суспільства. Соціальні інтереси соціальні переміщення та соціальна мобільність. 1. Поняття соціальної структури її роль та місце в житті су
19932. СОЦІАЛЬНІ СТАТУСИ І СОЦІАЛЬНІ РОЛІ. СОЦІАЛЬНА СТРАТИФІКАЦІЯ 99 KB
  ЛЕКЦІЯ 4 СОЦІАЛЬНІ СТАТУСИ І СОЦІАЛЬНІ РОЛІ. СОЦІАЛЬНА СТРАТИФІКАЦІЯ П Л А Н Поняття статусу. Особистий та соціальний статуси. Соціальні ролі та їх різновиди. Теорія соціальної стратифікації. Соціальна стратифікація українського суспільства. 1. Поня...
19933. СОЦІОЛОГІЯ ОСОБИСТОСТІ 84.5 KB
  ЛЕКЦІЯ 5 СОЦІОЛОГІЯ ОСОБИСТОСТІ П Л А Н 1. Поняття особистості у соціології. 2. Особистість як об’єкт і суб’єкт суспільних відносин. 3. Основні соціологічні теорії особистості. 4. Соціологічна структура особистості. 1. Поняття особистості у соціології Термін о...
19934. СОЦІАЛІЗАЦІЯ ОСОБИСТОСТІ В СУСПІЛЬСТВІ 110 KB
  Під соціалізацією в сучасній соціології зазвичай розуміють процес засвоєння індивідом зразків поведінки, психологічних механізмів, соціальних норм і цінностей, необхідних для успішного функціонування індивіда в даному суспільстві.