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.

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


 

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

14127. UNIT 5. MOTHERBOARD 35 KB
  UNIT 5. MOTHERBOARD I. Practice reading the following words: motherboard personal circuit electronic controller component either via determine features wireless expansion industry micro architecture proprietary endure accommodate video monitor prior processor universally current Ethernet graphics existing extension firmware rear failure volatile. II. Before reading the text try to answer these questions: 1. What is a motherboard 2. What is a...
14128. UNIT 6. PERIPHERALS 39 KB
  UNIT 6. PERIPHERALS I. Practise reading the following words: attached scanner internal video accessories refers component processing access similarly represents audio converted accommodate typical processor transform electronic capture included Ethernet chat advantage convert item graphics monitor produces permanent transparencies primarily via. II. Before reading the text try to answer these questions: 1. What components does an ordinary PC...
14129. UNIT 7. KEYBOARDS 46 KB
  UNIT 7. KEYBOARDS I. Practise reading the following words: component primary commands virtually obsolete corporate term universal specification equipment status automating layout arrangement area numeric mode isolated modified vendor menu cursor simulate mandatory via economic requirement environment support minimize sacrifice. II. Before reading the text try to answer these questions: 1. What input devices do you know 2. What input devices d...
14130. Основні етапи розвязування задачі з використанням компютера 67.5 KB
  Тема уроку: Основні етапи розвязування задачі з використанням компютера Мета уроку: Дати поняття про основні етапи розвязування задачі з використанням компютера.Тип уроку: Лекційний. Теоретичний матеріал: Зараз важко уявити собі життя людини без компютера. Люди в
14131. Поняття інформаційної моделі 39 KB
  Тема уроку: Поняття інформаційної моделі Мета уроку: Дати поняття про моделювання та створення інформаційних моделей обєктів.Тип уроку: Лекційний. На початку уроку рекомендується провести усне опитування за темою попереднього уроку з метою визначення засвоєного ма...
14132. Величини. Типи даних. Стандартні типи даних. Набір функцій і операцій, введених для кожного зі стандартних типів 83.5 KB
  Тема уроку: Величини. Типи даних. Стандартні типи даних. Набір функцій і операцій введених для кожного зі стандартних типів. Мета уроку: дати поняття величини та типів даних визначити стандартні типи даних їх опис та набір функцій і операцій для кожного зі стандартних ...
14133. Вказівка надання значення. Вказівки введення та виведення. Структура програми на мові програмування Паскаль 60 KB
  Тема уроку: Вказівка надання значення. Вказівки введення та виведення. Структура програми на мові програмування Паскаль. Мета уроку: дати поняття вказівки присвоювання познайомитись з вказівками введення та виведення зі структурою програми на мові Паскаль.Тип уроку:...
14134. Формування зображення на екрані ПЕОМ. Створення найпростіших лінійних програм 66.5 KB
  Тема уроку: Формування зображення на екрані ПЕОМ. Створення найпростіших лінійних програм Мета уроку: Дати дитині поняття про режими роботи монітору та принципи виведення зображення на екран в цих режимах.Тип уроку: Лекційний з практичними прикладами. Лекційний мате...
14135. Створення найпростіших лінійних програм 27 KB
  Тема уроку: Створення найпростіших лінійних програм Мета уроку: Дати дитині поняття про режими роботи монітору та принципи виведення зображення на екран в цих режимах.Тип уроку: Практична робота. На початку уроку необхідно нагадати дітям правила поведінки в комп'юте