20619

Синтаксическое дерево

Лекция

Коммуникация, связь, радиоэлектроника и цифровые приборы

Синтаксическое дерево. Синтаксическое дерево представляет собой дерево синтаксического разбора сжатом виде и может быть построено на основе синтаксически управляемых определений. Грамматическое правило Семантическое правило Синтаксическое дерево узлы которого могут иметь одного родителя называется направленным ациклическим графом выражений DAG. Для ускорения поиска используется ХЭШ – функция по сигнатуре op l r Пример: Построить дерево синтаксического разбора синтаксическое дерево и DAG для выражения.

Русский

2013-07-31

93.5 KB

15 чел.

Лекция № 6.

Синтаксическое дерево.

Синтаксическое дерево представляет собой дерево синтаксического разбора сжатом виде и может быть построено на основе синтаксически управляемых определений.

Используется в качестве промежуточного представления после этапа синтаксического анализа.

Пример:

Пусть имеется выражение вида  2+3*4.

                                                                    

Каждый узел в синтаксическом дереве реализуется как запись с несколькими полями:

  •  Одно поле идентифицирует операцию
  •  Остальные поля содержат указатели на узлы операндов

Кроме того, могут быть использованы дополнительные поля для хранения дополнительной информации.

Для описания конструирования деревьев могут быть использованы функции следующего вида:

  •  mknode(op, left, right) – содержит узел операции c меткой op  и указателями  left, right.
  •  mkleaf(id, entry) – создает узел идентификатора с меткой id и полем entry содержащим указатель на запись в таблице символов для этого идентификатора.
  •  mkleaf(num, val) – создает узел числа num c полем val содержащим значение числа.

Каждая из функций возвращает указатель на вновь созданный узел.

Пример:

Пусть имеется выражение a-4+b. Последовательность вызовов функций для построения дерева.

p1:=mkleaf(а,pa)

p2:=mkleaf(num,4)

p3:=mkleaf(-,p1 ,p2)

p4:=mknode(c, pc)

p5:=mknode(+, p3, p4)

Синтаксически управляемое определение для построения синтаксических деревьев.

Грамматическое правило

Семантическое правило

Синтаксическое дерево, узлы которого могут иметь одного родителя, называется направленным ациклическим графом выражений (DAG).

Пример:

а+(b-c)+a+d*(b-c)

Пример:

i:= i+3

DAG для этого выражения будет выглядеть следующим образом.

                          

Алгоритм метода номера значения построения узла DAGа.

Индекс массива, содержащий информацию о некотором узле, называется номером значения этого узла.

Если узел описывается полями с метками op, l, r ( opоперация, l и  r левые и правые потомки этого узла), тогда список <op, l ,r> называется сигнатурой узла.

Метод состоит в поиске в массиве уже существующего узла сигнатуры <op, l ,r> и возвращении его номера, или если он отсутствует, создании нового узла.

Для ускорения поиска используется ХЭШ – функция по сигнатуре op, l ,r

Пример:

Построить дерево синтаксического разбора, синтаксическое дерево и DAG для выражения.

(a+b)*[(b-a*c)+b*b]


 

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

73526. Сущность менеджмента в производстве 278 KB
  Определение управления. Место управления в производственной системе. Предприятие это производственная система которая осуществляет производительное соединение элементов производства средств и предметов труда живого труда при помощи технологии и организации производства и управления предприятием с целью получения продуктов труда. Управление предприятием это целенаправленное воздействие управляющей системы органа управления на управляемую систему объект управления.
73527. Эволюция управленческой мысли. Успешный менеджмент 44.09 KB
  Принципы управления. Методы управления. Цель лекции: Уяснение становления и развития науки управления сущности принципов и методов управления. Вклад основных подходов в науку управления.
73528. Функции и функциональные подсистемы менеджмента 88.5 KB
  Функции управления это серия непрерывных взаимосвязанных действий в процессе управления каждое из которых само по себе представляет законченный процесс. Планирование это процесс установления цели целей путей достижения цели целей и распределения ресурсов для достижения цели целей в системе управления. Организация взаимодействия это процесс создания структуры управления предприятием разработки взаимодействия подразделений и взаимоотношений полномочий которые на основе координации деятельности людей позволяет им эффективно...
73529. Подсистема планирования в производственном менеджменте 228.5 KB
  Стратегическое планирование деятельности предприятия. Планирование реализации стратегии деятельности предприятия. Цель лекции: Изучение сущности назначения и процесса планирования деятельности в производственном менеджменте Изучив данную тему студенты должны знать...