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.

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


 

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

78849. Научное, ненаучное, псевдонаучное знание 30.5 KB
  Научное ненаучное псевдонаучное знание. Научное знание система знаний о законах природы общества мышления. Научное знание составляет основу научной картины мира и отражает законы его развития. Научное знание: является результатом постижения действительности и когнитивной основой человеческой деятельности; социально обусловлено; и обладает различной степенью достоверности.
78850. Метатеоретический уровень научного знания 26.5 KB
  мета за после это теория о теории: объектом научного анализа для метатеории выступает сама теория. Метатеоретический подход не просто реорганизует научное знание является не только способом научного анализа теории но производит в ней сдвиги содержательного порядка порождает новое знание. Рефлексия является своеобразным способом развития самого содержания знания одним из важных путей разработки теории Дело в том что плодотворен сам по себе выход за пределы теории отстраненный взгляд на нее. На основе метатеории в процессе...
78852. Философские основания науки 27 KB
  Философские основания науки Предисловие: Философское основание науки представляет особой один из элементов философии науки направление в философии изучающее научную деятельность ее особенности и характеристики; ее цель – устанавливать правильность научных суждений и теорий и объяснять место и роль науки в современной культуре наряду с теоретическим и эмпирическим знанием. Философские основания науки. Философские основания науки. Функции функция философского обоснования: Любая новая идея для того чтобы стать либо частью картины мира...
78853. Структура эмпирического знания. Проблема факта 28.5 KB
  Проблема факта Эмпирические факты образуют базис на который опираются научные теории. Факты фиксируются в языке науки в высказываниях типа: более половины опрошенных в городе недовольны экологией городской среды и т. Вернадский: эмпирические факты хлеб науки. Проблема факта: Эмпирические факты содержат не только информацию об изучаемых явлениях но и как правило включают ошибки наблюдателя и т.
78854. Структура теоретического знания 29 KB
  Теоретический уровень научного познания как и эмпирический имеет ряд подуровней среди которых можно выделить следующие по степени общности: а аксиомы теоретические законы; б частные теоретические законы описывающие структуру свойства и поведение идеализированных объектов; в частные единичные высказывания утверждающие нечто о конкретных во времени и пространстве состояниях свойствах и отношениях некоторых идеализированных объектов 2 вида научных законов: 1Универсальные и частные законы. Универсальными принято называть законы...
78855. Функции научной теории 14.81 KB
  Функции научной теории. Объяснение и предсказание окружающих нас вещей и явлений представляет собой важнейшую функцию науки в целом и научной теории в частности. Основные функций теории можно отнести следующие. Методологическая функция на базе теории формулируются многообразные методы способы и приемы исследовательской деятельности.
78856. Методы научного познания и их классификация 41.5 KB
  Методы научного познания и их классификация Метод систематизированная совокупность шагов действий кые необходимо предпринять чтобы решить определенную задачу или достичь определенной цели. Методы эмпирического познания Методы теоретического познания. Моделирование от лат – образец мира – метод при ком исследуемый объект оригинал замещается другим модель специально созданным для его изучения. Рефлексия – основной метод метатеоретического познания в науке познание обращенное ученым на самого себя.
78857. Ценности и их роль в познании 35.5 KB
  Ценности и их роль в познании Философское учение о ценстях и их природе называется аксиологией. Эпоха Возрождения выдвигает на первый план ценсти гуманизма. В Новое время развитие науки и новых общественных отношений во многом определяют и основной подход к рассмотрению предметов и явлений как ценстей. Кант впервые употребляет понятие ценсти в специальном узком смысле.